Uniform chain decompositions and applications. Issue 2 (12th July 2021)

• Record Type: Journal Article
• Authors: Sudakov, Benny; Tomon, István; Wagner, Adam Zsolt
• Is Part Of: Random structures & algorithms. Volume 60:Issue 2(2022)
• Page Start: 261
• Page End: 286
• Publication Date: 2021-07-12
• Subjects: antichain -- Boolean lattice -- chain decomposition -- container method -- Furedi's conjecture; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21034
• Languages: English
• ISSNs: 1042-9832

Abstract

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.