Answers are grounded in this paper and cite their sources.
The Boolean lattice consists of all subsets of partially ordered under the containment relation. Sperner's Theorem states that the largest antichain of the Boolean lattice is given by a middle layer: the collection of all sets of size , or also, if is odd, the collection of all sets of size . Given , choose each subset of with probability independently. We show that for every constant , the largest antichain among these subsets is also given by a middle layer, with probability tending to 1 as tends to infinity. This is best possible, and we also characterize the largest antichains for every constant . Our proof is based on some new variations of Sapozhenko's graph container method.
No takes yet. Share an insight, caveat, or question.
Balogh et al. (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: