next up previous
Next: Hamiltonian cycles Up: Dimension Previous: The case i=1

The case i>1

 

The results for i>1 we are going to sample are all very recent. In fact, they are all contained in (or accessible through) papers coauthored by Brightwell, Füredi, Hurlbert, Kierstead, Kostochka, Talysheva and Trotter; these papers all appeared in Volume 11 of ORDER in 1994. See [5], [21] and [32].

We start with a formal analogue to Dushnik's and Miller's original result on P(1,n-1;n). In [32], it is shown that dim(2,n-2;n)=n-2 and that, moreover, the order p(2,n-2;n) is (n-1)-irreducible for all tex2html_wrap_inline2030 . The analogy even extends to Dushnik's analysis of dim(1,j;n) for j large compared to n: For tex2html_wrap_inline2030 , [32] provides conditions on dim(2,j;n) which (almost) give the exact value of dim(2,j;n) for j exceeding some critical value tex2html_wrap_inline1960 (with tex2html_wrap_inline2048 ). `Almost' here means that for certain exceptional values of j, tex2html_wrap_inline1956 , the estimate obtained is only accurate to within 1.

The same paper ([32]) credits to Kostochka and Talysheva a proof of dim(3,n-3;n)=n-2, valid for tex2html_wrap_inline2058 .

Extending these results, Füredi showed in [21] that generally one has tex2html_wrap_inline2060 for all n>2i. The proof relies on the Lovász-Kneser graph theorem. In fact, the main theorem of [21] gives the exact value of dim(i,n-i;n) for all large n: For tex2html_wrap_inline2068 and tex2html_wrap_inline2070 , we have dim(i,n-i;n)=n-2. The proof is based on a new variant of the Erdös-Ko-Rado theorem.

The final group of results we are going to report deal with dim(i,i+k;n) for k relatively small. All are from [5]:

The following result provides an upper bound on dim(i,i+k;n) in terms of values of dim(1,j;n): If tex2html_wrap_inline2082 and tex2html_wrap_inline2084 , then tex2html_wrap_inline2086 . Since tex2html_wrap_inline2088 (see [23]), this establishes tex2html_wrap_inline2090 provided tex2html_wrap_inline2084 .

For k=1 and tex2html_wrap_inline2096 , a better estimate is possible: tex2html_wrap_inline2098 . The authors credit Kostochka with establishing tex2html_wrap_inline2100 . For the most interesting case, that of the middle two layers of a Boolean lattice with an odd number of atoms, the following upper and lower bounds are given: Let n=2i+1, then tex2html_wrap_inline2104 .


next up previous
Next: Hamiltonian cycles Up: Dimension Previous: The case i=1

Jürg Schmid