Independent sets in the discrete hypercube

2019/01/06 by David Galvin, Galvin, David · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1901.01991

arXiv admin note: text overlap with arXiv:0807.0836, arXiv:1206.3152

arxiv created 2019/01/06 · arxiv updated 2019/01/09

Abstract

In this expository note we describe a proof due to A. Sapozhenko that the number of independent sets in the discrete d-dimensional hypercube Q_d is asymptotically 2 √(e) 2^2^d-1 as d tends to infinity.

Citations

• A threshold phenomenon for random independent sets in the discrete hypercube
• On homomorphisms from the Hamming cube to \bf Z

Cited by

• Asymptotic enumeration via graph containers and entropy

Related

• Independent sets of a given size and structure in the hypercube
• Independent sets in random subgraphs of the hypercube
• Independent sets in discrete tori of odd sidelength
• The number of maximal independent sets in the Hamming cube
• A threshold phenomenon for random independent sets in the discrete hypercube