Article ID Journal Published Year Pages File Type
6424117 European Journal of Combinatorics 2015 12 Pages PDF
Abstract

Füredi conjectured that the Boolean lattice 2[n] can be partitioned into (n⌊n/2⌋) chains such that the size of any two differs in at most one. In this paper, we prove that there is an absolute constant α≈0.8482 with the following property: for every ϵ>0, if n is sufficiently large, the Boolean lattice 2[n] has a chain partition into (n⌊n/2⌋) chains, each of them of size between (α−ϵ)n and O(n/ϵ).We deduce this result by looking at the more general setup of unimodal normalized matching posets. We prove that a unimodal normalized matching poset P of width w has a chain partition into w chains, each of size at most 2|P|w+5, and it has a chain partition into w chains, where each chain has size at least |P|2w−12.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,