Title of article :
On the order dimension of 1-sets versus k-sets
Author/Authors :
Kierstead، نويسنده , , H.A.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 1996
Pages :
10
From page :
219
To page :
228
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(l,k;n) denote the dimension of Bn(l,k), the suborder of the Boolean lattice on [n] consisting of l-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(l,k;n). In particular we answer a question of Trotter by showing that dim(l,logn;n) = Θ(log3 n/log log n). The estimation of dim(l,logn;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(l,logn;n) < log3 n.
Journal title :
Journal of Combinatorial Theory Series A
Serial Year :
1996
Journal title :
Journal of Combinatorial Theory Series A
Record number :
1530077
Link To Document :
بازگشت