A random version of Sperner's theorem

Abstract

Let $\mathcal{P}(n)$ denote the power set of $[n]$, ordered by inclusion, and let $\mathcal{P}(n,p)$ be obtained from $\mathcal{P}(n)$ by selecting elements from $\mathcal{P}(n)$ independently at random with probability $p$. A classical result of Sperner asserts that every antichain in $\mathcal{P}(n)$ has size at most that of the middle layer, $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$. In this note we prove an analogous result for $\mathcal{P}(n,p)$: If $pn\to \infty$ then, with high probability, the size of the largest antichain in $\mathcal{P}(n,p)$ is at most $(1+o(1))p\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$. This solves a conjecture of Osthus who proved the result in the case when $pn/\log n\to \infty$. Our condition on $p$ is best-possible. In fact, we prove a more general result giving an upper bound on the size of the largest antichain for a wider range of values of $p$.

7 pages. Updated to include minor revisions and publication data

References in corpus (1)

• Sperner's Theorem and a Problem of Erdos-Katona-Kleitman

Cited by in corpus (1)

• Online containers for hypergraphs, with applications to linear equations