Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs

DOI10.1002/RSA.20094MaRDI QIDQ5486322zbMATH OpenOpenAlexFDO

Authors David Galvin, Prasad Tetali

Publication date 6 September 2006

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

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

zbMATH Keywords

Markov chaindistributionconvergenceConductanceDiscrete HypercubeHard-Core ModelMixing Time

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05)

Abstract: Let $gS=(V,E)$ be a finite, $d$-regular bipartite graph. For any $lambda>0$ let $p{i}_{l}ambda$ be the probability measure on the independent sets of $gS$ in which the set $I$ is chosen with probability proportional to $lambd{a}^{|I|}$ ($p{i}_{l}ambda$ is the {em hard-core measure with activity $lambda$ on $gS$}). We study the Glauber dynamics, or single-site update Markov chain, whose stationary distribution is $p{i}_{l}ambda$. We show that when $lambda$ is large enough (as a function of $d$ and the expansion of subsets of single-parity of $V$) then the convergence to stationarity is exponentially slow in $|V(gS)|$. In particular, if $gS$ is the $d$-dimensional hypercube ${0,1}^d$ we show that for values of $lambda$ tending to 0 as $d$ grows, the convergence to stationarity is exponentially slow in the volume of the cube. The proof combines a conductance argument with combinatorial enumeration methods.

Recommendations

• Slow mixing of Glauber dynamics for the hard-core model on the hypercube
• Sampling independent sets in the discrete torus
• Sampling 3-colourings of regular bipartite graphs
• Fast convergence of the Glauber dynamics for sampling independent sets
• Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model

Cited in

(29)

• A general lower bound for mixing of single-site dynamics on graphs
• Metastability of hard-core dynamics on bipartite graphs
• Probability and algorithmics: a focus on some recent developments
• Gibbs measures on Cayley trees: results and open problems
• Approximately counting independent sets in bipartite graphs via graph containers
• Note on the number of balanced independent sets in the Hamming cube
• Sampling independent sets in the discrete torus
• Sampling 3-colourings of regular bipartite graphs
• Spectral independence in high-dimensional expanders and applications to the hardcore model
• Fast algorithms at low temperatures via Markov chains†
• The growth constant of odd cutsets in high dimensions
• A spectral independence view on hard spheres via block dynamics
• Rigidity of proper colorings of \(\mathbb{Z}^d \)
• Glauber dynamics on nonamenable graphs: boundary conditions and mixing time
• scientific article; zbMATH DE number 7650108 (Why is no real title available?)
• Phase transitions in sampling algorithms and the underlying random structures
• Independent sets in the hypercube revisited
• Convergence details about \(k\)-DPP Monte-Carlo sampling for large graphs
• Independent sets in the middle two layers of Boolean lattice
• A threshold phenomenon for random independent sets in the discrete hypercube
• Tunneling of the hard-core model on finite triangular lattices
• \(H\)-coloring tori
• Algorithms and Computation
• Slow mixing of Glauber dynamics for the hard-core model on the hypercube
• Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs
• Hitting time asymptotics for hard-core interactions on grids
• Homomorphisms from the torus
• Slow Mixing of Markov Chains Using Fault Lines and Fat Contours
• Can extra updates delay mixing?

This page was built for publication: Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5486322)