Reading Group on Entropy and Counting - Richard Lang

Tuesday, March 12, 2019 2:00 pm - 2:00 pm EDT (GMT -04:00)

Title: Counting maximal independent sets in the hypercube

Speaker: Richard Lang
Affiliation: University of Waterloo
Room: MC 6486

Abstract:

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.