Partitioning the Boolean lattice into chains of large minimum size

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:97

Article

Hsu, T ; Logan, MJ ; Shahriari, S ; Towse, C

关键词: Boolean lattice;    chain decompositions;    Furedi's problem;    Griggs' conjecture;    normalized matching property;   

DOI  :  10.1006/jcta.2001.3197

来源: Elsevier

【 摘 要 】

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 Furedi, we show that there exists a function d(n) similar to 1/2 rootn such that for any n greater than or equal to 0, 2([n]) may be partitioned into (([n/2]) (n)) chains of size at least d(n). (For comparison, a positive answer to Furedi's question would imply that the same result holds for some d(n) similar to rootpi/2rootn) more precisely, we first show that for 0 less than or equal to j less than or equal to 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. (C) 2001 Elsevier Science.

【 授权许可】

Free