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

详细信息	查看全文 | 推荐本文 |

• 作者：Hsu ; Tim ; Logan ; Mark J. ; Shahriari ; Shahriar ; Towse ; Christopher
• 关键词：Boolean lattice ; Chain decompositions ; Fü ; redi’ ; s problem ; Normalized matching property ; LYM property
• 刊名：European Journal of Combinatorics
• 出版年：2003
• 期刊代码：65_01956698
• 类别：mt
• 出版时间：February, 2003
• 卷：24
• 期：2
• 页码：219-228
• 文件大小：120 K

摘要

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

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)√π/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.