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

DOI10.1002/RSA.20094zbMATH Open1105.05064arXiv1206.3165OpenAlexW2952032359MaRDI QIDQ5486322FDOQ5486322

David Galvin, Prasad Tetali

Publication date: 6 September 2006

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)

Cited In (21)

• Homomorphisms from the torus
• Hitting time asymptotics for hard-core interactions on grids
• Independent sets in the middle two layers of Boolean lattice
• Probability and algorithmics: a focus on some recent developments
• \(H\)-coloring tori
• Metastability of hard-core dynamics on bipartite graphs
• Fast algorithms at low temperatures via Markov chains†
• Note on the number of balanced independent sets in the Hamming cube
• Independent sets in the hypercube revisited
• Glauber dynamics on nonamenable graphs: boundary conditions and mixing time
• Approximately counting independent sets in bipartite graphs via graph containers
• A Spectral Independence View on Hard Spheres via Block Dynamics
• A general lower bound for mixing of single-site dynamics on graphs
• Title not available (Why is that?)
• Sampling independent sets in the discrete torus
• Rigidity of proper colorings of \(\mathbb{Z}^d \)
• Tunneling of the hard‐core model on finite triangular lattices
• GIBBS MEASURES ON CAYLEY TREES: RESULTS AND OPEN PROBLEMS
• The Growth Constant of Odd Cutsets in High Dimensions
• Slow Mixing of Markov Chains Using Fault Lines and Fat Contours
• A Threshold Phenomenon for Random Independent Sets in the Discrete Hypercube

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)