Uniform chain decompositions and applications. Issue 2 (12th July 2021) - Sudakov, Benny; Tomon, István; Wagner, Adam Zsolt
Abstract: 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 = 2 n / n ⌊ n / 2 ⌋, 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 n ⌊ n / 2 ⌋ 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 n ⌊ n / 2 ⌋ ? We show that the answer is ( π 8 + o ( 1 ) ) 2 n n . Finally, we discuss how these uniform chain decompositions can be used to optimize and simplify various results in extremal set theory.