Simons Collaboration on Algorithms and Geometry Monthly Meeting, October 2020

Counting maximal independent sets in the cube

[The $d$-dimensional Hamming cube is $\{0, 1\}^d$ with the natural graph structure, and an independent set in a graph is a set of vertices spanning no edges.]

The center of this discussion is a recent result of Jinyoung Park and myself stating that the number of maximal independent sets in the cube is asymptotically $2d2^{N/4}$, where $N = 2^d$. We’ll spend some time putting this in context (combinatorial and statistical mechanical), and try to give some idea of what goes into its proof. One ingredient there is a new isoperimetric inequality for the cube that raises some interesting questions.