Sampling independent sets in the discrete torus
From MaRDI portal
Publication:3608300
Abstract: The even discrete torus is the graph T_{L,d} on vertex set {0,...,L-1}^d (L even) with two vertices adjacent if they differ by 1 (mod L) on one coordinate. The hard-core measure with activity x on T_{L,d} is the distribution pi_x on the independent sets (sets of vertices spanning no edges) of T_{L,d} in which a set I is chosen with probability proportional to x^|I|. This distribution occurs in problems from statistical physics and communication networks. We study Glauber dynamics, a single-site update Markov chain on the set of independent sets of T_{L,d} whose stationary distribution is pi_x. We show that for x > cd^{-1/4}log^{3/4}d (and d large) the convergence to stationarity is exponentially slow in L^{d-1}. This improves a result of Borgs et al., who had shown slow mixing for x > c^d. Our proof, which extends to r-local chains (chains which alter the state of at most a proportion r of the vertices in each step) for suitable r, follows the conductance argument of Borgs et al., adding to it some combinatorial enumeration methods that are modifications of those used by Galvin and Kahn to show that the hard-core model with parameter x on the integer lattice Z^d exhibits phase coexistence for x > cd^{-1/4}log^{3/4}d. The graph T_{L,d} is bipartite, with partition classes E (the vertices the sum of whose coordinates is even) and O. Our result can be expressed combinatorially as the statement that for each sufficiently large x, there is an r(x)>0 such that if I is an independent set chosen according to pi_x, then the probability that ||I cap E|-|I cap O|| is at most r(x)L^d is exponentially small in L^{d-1}. In particular, for all eps>0 the probability that a uniformly chosen independent set from T_{L,d} satisfies ||I cap E|-|I cap O|| leq (.25 - eps)L^d is exponentially small in L^{d-1}.
Recommendations
- Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
- Slow mixing of Glauber dynamics for the hard-core model on the hypercube
- Torpid mixing of local Markov chains on 3-colorings of the discrete torus
- Fast convergence of the Glauber dynamics for sampling independent sets
Cites work
- scientific article; zbMATH DE number 4160792 (Why is no real title available?)
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Counting independent sets up to the tree threshold
- Fast convergence of the Glauber dynamics for sampling independent sets
- Investigation of Gibbsian States for Three-Dimensional Lattice Systems
- Loss networks
- On Counting Independent Sets in Sparse Graphs
- On Markov Chains for Independent Sets
- On Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$
- Percolation and the hard-core lattice gas model
- Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
Cited in
(14)- Spatio-spectral limiting on discrete tori: adjacency invariant spaces
- Spectral independence in high-dimensional expanders and applications to the hardcore model
- Phase coexistence and torpid mixing in the 3-coloring model on \({\mathbb Z}^d\)
- The growth constant of odd cutsets in high dimensions
- Rigidity of proper colorings of \(\mathbb{Z}^d \)
- Odd cutsets and the hard-core model on \(\mathbb{Z}^{d}\)
- Tunneling of the hard-core model on finite triangular lattices
- Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
- Torpid mixing of local Markov chains on 3-colorings of the discrete torus
- \(H\)-coloring tori
- Slow mixing of Glauber dynamics for the hard-core model on the hypercube
- Hitting time asymptotics for hard-core interactions on grids
- Homomorphisms from the torus
- Phase coexistence for the hard-core model on \(\mathbb{Z}^2\)
This page was built for publication: Sampling independent sets in the discrete torus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608300)
