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.