Independent sets in the hypercube revisited

Abstract

We revisit Sapozhenko's classic proof on the asymptotics of the number of independent sets in the discrete hypercube $\{0,1{\}}^d$ and Galvin's follow-up work on weighted independent sets. We combine Sapozhenko's graph container methods with the cluster expansion and abstract polymer models, two tools from statistical physics, to obtain considerably sharper asymptotics and detailed probabilistic information about the typical structure of (weighted) independent sets in the hypercube. These results refine those of Korshunov and Sapozhenko and Galvin, and answer several questions of Galvin.

Typo corrected in equation (6)

References in corpus (1)

• Independent sets in the discrete hypercube

Cited by in corpus (5)

• On the number of high-dimensional partitions
• Algorithms for the ferromagnetic Potts model on expanders
• Efficient Algorithms for Weakly-Interacting Quantum Spin Systems
• Counting independent sets in percolated graphs via the Ising model
• A refined graph container lemma and applications to the hard-core model on bipartite expanders