Independent sets in the hypercube revisited
From MaRDI portal
Abstract: We revisit Sapozhenko's classic proof on the asymptotics of the number of independent sets in the discrete hypercube 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.
Recommendations
- Independent sets of a given size and structure in the hypercube
- Note on the number of balanced independent sets in the Hamming cube
- A threshold phenomenon for random independent sets in the discrete hypercube
- Independent sets in the middle two layers of Boolean lattice
- Counting independent sets in regular hypergraphs
Cites work
- H-coloring tori
- A threshold phenomenon for random independent sets in the discrete hypercube
- Algorithmic Pirogov-Sinai theory
- Algorithms for #BIS-hard problems on expander graphs
- An entropy approach to the hard-core model on bipartite graphs
- Cluster expansion for abstract polymer models
- Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
- Counting independent sets in graphs
- Counting independent sets in unbalanced bipartite graphs
- Homomorphisms from the torus
- scientific article; zbMATH DE number 3833857 (Why is no real title available?)
- scientific article; zbMATH DE number 4160792 (Why is no real title available?)
- scientific article; zbMATH DE number 1023434 (Why is no real title available?)
- Hypergraph containers
- Independent sets in hypergraphs
- On a Method of Calculation of Semi-Invariants
- On homomorphisms from the Hamming cube to \(\mathbb{Z}\)
- On Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$
- Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
- The number of 4-colorings of the Hamming cube
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
Cited in
(26)- On independent and \((d, n)\)-domination numbers of hypercubes
- A proof of the upper matching conjecture for large graphs
- Note on the number of balanced independent sets in the Hamming cube
- Independent sets in the middle two layers of Boolean lattice
- The number of maximal independent sets in the Hamming cube
- scientific article; zbMATH DE number 5901714 (Why is no real title available?)
- A threshold phenomenon for random independent sets in the discrete hypercube
- Independent sets of a given size and structure in the hypercube
- Approximately counting independent sets in bipartite graphs via graph containers
- Homomorphisms from the torus
- Intersecting families of sets are typically trivial
- On the number of high‐dimensional partitions
- Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
- Mutually independent bipanconnected property of hypercube
- On the zeroes of hypergraph independence polynomials
- Algorithms for the ferromagnetic Potts model on expanders
- Lipschitz functions on weak expanders
- 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
- A spectral approach to approximately counting independent sets in dense bipartite graphs
- On the evolution of structure in triangle-free graphs
- Independent sets in discrete tori of odd sidelength
- The number of colorings of the middle layers of the Hamming cube
- A sharp threshold for a random version of Sperner's theorem
- Sumsets in the hypercube
- On Dedekind's problem, a sparse version of Sperner's theorem, and antichains of a given size in the Boolean lattice
This page was built for publication: Independent sets in the hypercube revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5141874)
