2019/11/21 by Sudakov, Benny, Tomon, Istvan, Wagner, Adam Zsolt
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1911.09533
The Boolean lattice 2[n] is the family of all subsets of [n]=\1,…,n\ ordered by inclusion, and a chain is a family of pairwise comparable elements of 2[n]. Let s=2n/\binomn\lfloor n/2\rfloor, which is the average size of a chain in a minimal chain decomposition of 2[n]. We prove that 2[n] can be partitioned into \binomn\lfloor n/2\rfloor chains such that all but at most o(1) proportion of the chains have size s(1+o(1)). This asymptotically proves a conjecture of Füredi from 1985. Our proof is based on probabilistic arguments. To analyze our random partition we develop a weighted variant of the graph container method. Using this result, we also answer a Kalai-type question raised recently by Das, Lamaison and Tran. What is the minimum number of forbidden comparable pairs forcing that the largest subfamily of 2[n] not containing any of them has size at most \binomn\lfloor n/2\rfloor? We show that the answer is (√\fracπ8+o(1))2n√(n). Finally, we discuss how these uniform chain decompositions can be used to optimize and simplify various results in extremal set theory.