Partitioning the Boolean Lattice into Chains of Large Minimum Size
✍ Scribed by Tim Hsu; Mark J. Logan; Shahriar Shahriari; Christopher Towse
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 187 KB
- Volume
- 97
- Category
- Article
- ISSN
- 0097-3165
No coin nor oath required. For personal study only.
✦ Synopsis
Let 2 [n] denote the Boolean lattice of order n, that is, the poset of subsets of {1, ..., n} ordered by inclusion. Recall that 2 [n] may be partitioned into what we call the canonical symmetric chain decomposition (due to de Bruijn, Tengbergen, and Kruyswijk), or CSCD. Motivated by a question of Füredi, we show that there exists a function d(n) ' 1 2 n such that for any n \ 0, 2 [n] may be partitioned into ( n Nn/2M ) chains of size at least d(n). (For comparison, a positive answer to Füredi's question would imply that the same result holds for some d(n) ' p/2 `n .) More precisely, we first show that for 0 [ j [ n, the union of the lowest j+1 elements from each of the chains in the CSCD of 2 [n] forms a poset T j (n) with the normalized matching property and log-concave rank numbers. We then use our results on T j (n) to show that the nodes in the CSCD chains of size less than 2d(n) may be repartitioned into chains of large minimum size, as desired.