Joint Colloquium - Shayla Redlin

Title: Counting Antichains in the Boolean Lattice

Abstract:

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.