Independent sets in the hypercube revisited

Matthew Jenssen, Will Perkins

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
184 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)645-669
JournalJournal of the London Mathematical Society
Volume102
Issue number2
Early online date22 Apr 2020
DOIs
Publication statusE-pub ahead of print - 22 Apr 2020

Keywords

  • 05C30
  • 05C31
  • 05C69 (primary)
  • 82B20 (secondary)

Fingerprint

Dive into the research topics of 'Independent sets in the hypercube revisited'. Together they form a unique fingerprint.

Cite this