TY - JOUR

T1 - Partitioning the Boolean lattice into a minimal number of chains of relatively uniform size

AU - Hsu, Tim

AU - Logan, Mark J.

AU - Shahriari, Shahriar

AU - Towse, Christopher

PY - 2003/2

Y1 - 2003/2

N2 - 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)∼c nlogn 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/2⌋ n 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)∼ π/2 n and f(n)=e(n)+1.) The main tool used is an apparently new observation about rank-collection in normalized matching (LYM) posets.

AB - 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)∼c nlogn 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/2⌋ n 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)∼ π/2 n and f(n)=e(n)+1.) The main tool used is an apparently new observation about rank-collection in normalized matching (LYM) posets.

KW - Boolean lattice

KW - Chain decompositions

KW - Füredi's problem

KW - LYM property

KW - Normalized matching property

UR - http://www.scopus.com/inward/record.url?scp=0037222173&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0037222173&partnerID=8YFLogxK

U2 - 10.1016/S0195-6698(02)00133-6

DO - 10.1016/S0195-6698(02)00133-6

M3 - Article

AN - SCOPUS:0037222173

VL - 24

SP - 219

EP - 228

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

IS - 2

ER -