Sampling independent sets in the discrete torus

DOI10.1002/RSA.20223zbMATH Open1219.60083arXiv1007.4822OpenAlexW4229677283MaRDI QIDQ3608300FDOQ3608300

Authors: David Galvin 

Publication date: 4 March 2009

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

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}.

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

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
• Improved mixing condition on the grid for counting and sampling independent sets

zbMATH Keywords

hard-core modelmixing timeconductanceGlauber dynamicsindependent setsdiscrete torusPeierl's argument

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Cites Work

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

Cited In (14)

• Homomorphisms from the torus
• Hitting time asymptotics for hard-core interactions on grids
• Odd cutsets and the hard-core model on \(\mathbb{Z}^{d}\)
• Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
• Tunneling of the hard-core model on finite triangular lattices
• \(H\)-coloring tori
• 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
• Spatio-spectral limiting on discrete tori: adjacency invariant spaces
• Torpid mixing of local Markov chains on 3-colorings of the discrete torus
• Slow mixing of Glauber dynamics for the hard-core model on the hypercube
• Rigidity of proper colorings of \(\mathbb{Z}^d \)
• 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)