A random version of Spernerʹs theorem

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 [12] asserts that every antichain in P ( n ) has size at most that of the middle layer, ( n ⌊ n / 2 ⌋ ) . In this note we prove an analogous result for P ( n , p ) : If p n → ∞ then, with high probability, the size of the largest antichain in P ( n , p ) is at most ( 1 + o ( 1 ) ) p ( n ⌊ n / 2 ⌋ ) . This solves a conjecture of Osthus [9] who proved the result in the case when p n / log ⁡ n → ∞ . 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.