A Threshold Phenomenon for Random Independent Sets in the Discrete Hypercube
From MaRDI portal
Publication:3068811
DOI10.1017/S0963548310000155zbMath1231.05134arXiv0807.0836OpenAlexW2130083422MaRDI QIDQ3068811
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
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
