A random version of Sperner's theorem

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)
199 Downloads (Pure)

Abstract

Let P(n) denote the power set of [n], ordered by inclusion, and let P(n,p) be obtained from P(n) by selecting elements from P(n) independently at random with probability p. A classical result of Sperner asserts that every antichain in P(n) has size at most that of the middle layer, (n choose ⌊n/2⌋). In this note we prove an analogous result for P(n,p): If pn→∞ then, with high probability, the size of the largest antichain in P(n,p) is at most (1+o(1))p(n choose ⌊n/2⌋). This solves a conjecture of Osthus who proved the result in the case when pn/logn→∞. 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.
Original languageEnglish
Pages (from-to)104-110
Number of pages7
JournalJournal of Combinatorial Theory, Series A
Volume128
Early online date14 Aug 2014
DOIs
Publication statusPublished - Nov 2014

Fingerprint

Dive into the research topics of 'A random version of Sperner's theorem'. Together they form a unique fingerprint.

Cite this