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.