A Threshold Phenomenon for Random Independent Sets in the Discrete Hypercube

DOI10.1017/S0963548310000155zbMath1231.05134arXiv0807.0836OpenAlexW2130083422MaRDI QIDQ3068811

David Galvin

Publication date: 17 January 2011

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Independent sets of a given size and structure in the hypercube ⋮ The number of 4-colorings of 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 ⋮ The independent set sequence of regular bipartite graphs ⋮ Independent sets in the middle two layers of Boolean lattice ⋮ Independent sets in the hypercube revisited ⋮ \(H\)-coloring tori

Cites Work

• On the ratio of optimal integral and fractional covers
• On homomorphisms from the Hamming cube to \(\mathbb{Z}\)
• Two combinatorial covering theorems
• On Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$
• Probability Inequalities for Sums of Bounded Random Variables
• Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs