A random version of Spemer%26apos;s theorem

作者：Balogh Jozsef^*; Mycroft Richard; Treglown Andrew

来源：Journal of Combinatorial Theory - Series A, 2014, 128: 104-110.

DOI：10.1016/j.jcta.2014.08.003

• Boolean lattice
• Antichain
• Container method

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 left perpendicular n/2 right perpendicular). In this note we prove an analogous result for P(n,p): If infinity then pn -%26gt; infinity, with high probability, the size of the largest antichain in P(n,p) is at most (1 + o(1))p(n left perpendicular n/2 right perpendicular). This solves a conjecture of Osthus [9] who proved the result in the case when pn/ logn -%26gt; infinity. 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.

• 出版日期2014-11