Independent sets in the hypercube revisited

DOI10.1112/jlms.12331zbMath1454.05088arXiv1907.00862OpenAlexW3100492754MaRDI QIDQ5141874

Will Perkins, Matthew Jenssen

Publication date: 22 December 2020

Published in: Journal of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1907.00862

zbMATH Keywords

cluster expansionweighted independent setsabstract polymer modelsSapozhenko's graph container methods

Mathematics Subject Classification ID

Graph polynomials (05C31) Enumeration in graph theory (05C30) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (10)

Independent sets of a given size and structure in the hypercube ⋮ Note on the number of balanced independent sets in the Hamming cube ⋮ The number of maximal independent sets in the Hamming cube ⋮ 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 ⋮ Independent sets in the middle two layers of Boolean lattice ⋮ A proof of the upper matching conjecture for large graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hypergraph containers
• \(H\)-coloring tori
• Cluster expansion for abstract polymer models
• On homomorphisms from the Hamming cube to \(\mathbb{Z}\)
• Algorithmic Pirogov-Sinai theory
• The number of 4-colorings of the Hamming cube
• Counting independent sets in graphs
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• A Threshold Phenomenon for Random Independent Sets in the Discrete Hypercube
• On a Method of Calculation of Semi-Invariants
• On Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$
• Counting independent sets in unbalanced bipartite graphs
• Algorithms for #BIS-hard problems on expander graphs
• Independent sets in hypergraphs
• Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• Homomorphisms from the torus

This page was built for publication: Independent sets in the hypercube revisited