Title: Counting Antichains in the Boolean Lattice
|Affiliation:||University of Waterloo|
|Zoom:||Contact Maxwell Levit|
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.