Monday, April 16, 2018 | 4pm-5pm | Burnside 1205 |
A classical result in extremal combinatorics is Sperner's Theorem from 1928, which says that the size of the largest antichain in the poset P(n) of subsets of an n-element set under the inclusion relation is (n choose [n/2]). Three natural questions extending Sperner's Theorem are
(Q1) How many "comparable pairs" must exist in a subset of P(n) of size (n choose [n/2])+t for t≥1?
(Q2) How many antichains are there in P(n)?
(Q3) What is the size of the largest antichain in a random subposet of P(n) of density p for 0 ≤ p ≤ 1?
As it turns out, combining the answer to Q1 (called a "supersaturation" theorem) with the "container method" yields good results for Q2 and Q3. In this talk, I will explain how this works and how the ideas extend (with several added difficulties) to other posets, in particular {0,1,2}^n under the "coordinate wise" partial order. This is based on joint work with Alex Scott and Benny Sudakov.