Sampling independent sets in the discrete torus

DOI10.1002/rsa.20223zbMath1219.60083arXiv1007.4822MaRDI QIDQ3608300

David Galvin

Publication date: 4 March 2009

Published in: Random Structures and Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Glauber dynamics; mixing time; independent sets; discrete torus; hard-core model; conductance; Peierl's argument

Mathematics Subject Classification ID

60D05: Geometric probability and stochastic geometry

60K35: Interacting random processes; statistical mechanics type models; percolation theory

Related Items

The Growth Constant of Odd Cutsets in High Dimensions, Phase Coexistence for the Hard-Core Model on ℤ², Tunneling of the hard‐core model on finite triangular lattices, Phase coexistence and torpid mixing in the 3-coloring model on ${\mathbb Z}^d$, Homomorphisms from the torus, Hitting time asymptotics for hard-core interactions on grids, Odd cutsets and the hard-core model on \(\mathbb{Z}^{d}\), \(H\)-coloring tori, Spatio-spectral limiting on discrete tori: adjacency invariant spaces, Rigidity of proper colorings of \(\mathbb{Z}^d \)

Cites Work

• Unnamed Item
• Loss networks
• Percolation and the hard-core lattice gas model
• Counting independent sets up to the tree threshold
• On Counting Independent Sets in Sparse Graphs
• Investigation of Gibbsian States for Three-Dimensional Lattice Systems
• Fast convergence of the Glauber dynamics for sampling independent sets
• On Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$
• On Markov Chains for Independent Sets
• Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations