Title of article :
Partitioning the Boolean lattice into a minimal number of chains of relatively uniform size
Author/Authors :
Hsu، نويسنده , , Tim and Logan، نويسنده , , Mark J. and Shahriari، نويسنده , , Shahriar and Towse، نويسنده , , Christopher، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2003
Abstract :
Let 2[n] denote the Boolean lattice of order n, that is, the poset of subsets of {1,…,n} ordered by inclusion. Extending our previous work on a question of Füredi, we show that for any c>1, there exist functions e(n)∼n/2 and f(n)∼cnlogn and an integer N (depending only on c) such that for all n>N, there is a chain decomposition of the Boolean lattice 2[n] into n⌊n/2⌋ chains, all of which have size between e(n) and f(n). (A positive answer to Füredi’s question would imply that the same result holds for some e(n)∼π/2n and f(n)=e(n)+1.) The main tool used is an apparently new observation about rank-collection in normalized matching (LYM) posets.
Keywords :
Boolean lattice , chain decompositions , Füredi’s problem , LYM property , normalized matching property
Journal title :
European Journal of Combinatorics
Journal title :
European Journal of Combinatorics