Maximal Chains and Antichains in Boolean Lattices
Dwight Duffus, Bill Sands, Peter M. Winkler · SIAM Journal on Discrete Mathematics · 1990
The following equivalent results in the Boolean lattice $2^n $ are proven. (a) Every fibre of $2^n $ contains a maximal chain. (b) Every cutset of $2^n $ contains a maximal antichain. (c) Every red-blue colouring of the vertices of $2^n $ produces either a red maximal chain or a blue maximal antichain. (d) Given any n antichains in $2^n $ there is a disjoint maximal antichain. Statement (a) is then improved to: (a') Every fibre of $2^n $ contains at least $n!/2^{n - 1} $ maximal chains. One conjecture of Lonc and Rival is supported, and another conjecture disproved, by showing: (i) Every fibre of $2^n $ has order $\Omega ( 1.25^n )$elements. (ii) There is a minimal fibre of $2^n ( n\geqq 4 )$ of size $2^{n - 1} + 2$.