Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424117 | European Journal of Combinatorics | 2015 | 12 Pages |
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
István Tomon,