Abstract
A family F of s-subsets of [t] is a (θ, s, t)-family iff the intersection of any two distinct elements of F has cardinality less than θ. Let f(θ, s, t) be the greatest integer n such that there exists an (θ, s, t)-family of cardinality n. Let dim(1, k; n) denote the dimension of Bn(1, k), the suborder of the Boolean lattice on [n] consisting of 1-subsets and k-subsets of [n]. We use upper and lower bounds on f(θ, s, t) to derive new lower and upper bounds on dim(1, k; n). In particular we answer a question of Trotter by showing that dim(1, log n; n) = Ω(log3 n/log log n). The estimation of dim(1, log n; n) plays a critical role in the determination of the maximum dimension of an ordered set with fixed maximum degree. Previously it was only known that (log2 n/4 < dim(1, log n; n) <log3 n.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 219-228 |
| Number of pages | 10 |
| Journal | Journal of Combinatorial Theory. Series A |
| Volume | 73 |
| Issue number | 2 |
| DOIs | |
| State | Published - 1996 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Fingerprint
Dive into the research topics of 'On the order dimension of 1-sets versus k-sets'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS