Simons Collaboration on Algorithms and Geometry Monthly Meeting, October 2020

Date & Time

10:15 AM – 12:30 PM

• Agenda
 10:15-11:15 AM Jeff Kahn, Counting maximal independent sets in the cube, Part I 11:15 - 11:30 AM Break 11:30 AM -12:30 PM Jeff Kahn, Counting maximal independent sets in the cube, Part II
• Abstract

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.

Subscribe to MPS announcements and other foundation updates