Uniform chain decompositions and applications

Abstract

The Boolean lattice $2^{[n]}$ is the family of all subsets of $[n]=\{1,\dots ,n\}$ ordered by inclusion, and a chain is a family of pairwise comparable elements of $2^{[n]}$. Let $s=2^n/\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$, 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 $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ 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 $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$? We show that the answer is $(\sqrt{\frac{\pi }{8}}+o(1))2^n\sqrt{n}$. Finally, we discuss how these uniform chain decompositions can be used to optimize and simplify various results in extremal set theory.

22 pages