A sharp threshold for a random version of Sperner's Theorem

MaRDI QIDQ6399975zbMATH OpenFDO

Authors József Balogh, Robert A. Krueger

Publication date 23 May 2022

Mathematics Subject Classification ID

Extremal set theory (05D05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorial probability (60C05)

Abstract: The Boolean lattice $mathcalP(n)$ consists of all subsets of $[n]=1,dots,n$ 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 $lfloorn/2floor$, or also, if $n$ is odd, the collection of all sets of size $lceiln/2ceil$. Given $p$, choose each subset of $[n]$ with probability $p$ independently. We show that for every constant $p>3/4$, the largest antichain among these subsets is also given by a middle layer, with probability tending to $1$ as $n$ tends to infinity. This $3/4$ is best possible, and we also characterize the largest antichains for every constant $p>1/2$. Our proof is based on some new variations of Sapozhenko's graph container method.

This page was built for publication: A sharp threshold for a random version of Sperner's Theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6399975)