Premium
Uniform chain decompositions and applications
Author(s) -
Sudakov Benny,
Tomon István,
Wagner Adam Zsolt
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21034
Subject(s) - conjecture , mathematics , chain (unit) , pairwise comparison , combinatorics , partition (number theory) , family of sets , discrete mathematics , probabilistic logic , lattice (music) , set (abstract data type) , computer science , statistics , physics , astronomy , acoustics , programming language
The Boolean lattice2 [ n ]is the family of all subsets of [ n ] = { 1 , … , n } ordered by inclusion, and a chain is a family of pairwise comparable elements of2 [ n ]. Let s = 2 n /n ⌊ n / 2 ⌋, which is the average size of a chain in a minimal chain decomposition of2 [ n ]. We prove that2 [ n ]can be partitioned inton ⌊ 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 of2 [ n ]not containing any of them has size at mostn ⌊ n / 2 ⌋? We show that the answer is (π 8+ o ( 1 ) ) 2 nn. Finally, we discuss how these uniform chain decompositions can be used to optimize and simplify various results in extremal set theory.