Title: Counting maximal independent sets in the hypercube
|Affiliation:||University of Waterloo|
In this talk we count the number of maximal independent set in the hypercube. It is not hard to see that the n-dimensional hypercube contains at least 2(n-2) maximal independent sets. Duffus, Frankl, and Rödl conjectured that this is also an upper bound. We will discuss a short entropic proof of Ilinca and Kahn (2013) which confirms the conjecture asymptotically.
200 University Avenue West
Waterloo, ON N2L 3G1