Premium
Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
Author(s) -
Galvin David,
Tetali Prasad
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20094
Subject(s) - glauber , mathematics , bipartite graph , combinatorics , markov chain , hypercube , discrete mathematics , measure (data warehouse) , mixing (physics) , graph , physics , statistics , computer science , database , scattering , optics , quantum mechanics
Let ∑ = ( V,E ) be a finite, d ‐regular bipartite graph. For any λ > 0 let π λ be the probability measure on the independent sets of ∑ in which the set I is chosen with probability proportional to λ | I | (π λ is the hard‐core measure with activity λ on ∑). We study the Glauber dynamics, or single‐site update Markov chain, whose stationary distribution is π λ . We show that when λ 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 (∑)|. In particular, if ∑ is the d ‐dimensional hypercube {0,1} d we show that for values of λ 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. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006