Mathematical Sciences Seminar - A random version of Sperner's theorem
When:
—
Venue:
Birkbeck Main Building, Malet Street
No booking required
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, ⌊ n/2 ⌋). I will demonstrate an analogous result for P(n,p), that if pn tends to infinity 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 who proved the result in the case when pn/log n tends to infinity. The proof uses a simplified application of the novel and powerful `hypergraph container' method, which has driven significant progress on many combinatorial problems over the past couple of years. This is joint work with Jozsef Balogh and Andrew Treglown.
Contact name:
Department of Economics, Mathematics and Statistics