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.