Monday, April 16, 2018 4pm-5pm Burnside 1205
Warwick University
Supersaturation in Posets

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.

Winter 2018 Schedule