Joint Pure Math/C&O Grad Colloquium

Shayla Redlin, Department of Combinatorics & Optimization, University of Waterloo

"Counting Antichains in the Boolean Lattice"

How many antichains are there in the Boolean lattice P(n)? Sperner's theorem (1928) tells us that the largest antichain in P(n) has size A = (n choose n/2). A subset of an antichain is an antichain, so there are at least 2^A antichains in P(n). Interestingly, it turns out that this is close to the total, as Kleitman (1969) showed that the number of antichains is 2^(A(1+x)) where x goes to zero as n goes to infinity. In this talk, we investigate an alternate proof that uses the 'container method'. Although the container method is a graph theoretic technique, a background in graph theory is not assumed.

Zoom link: https://us02web.zoom.us/j/81243444090?pwd=S2NLODVCZHoyRUFqTXpZQ1V6UjNmdz09