Sampling independent sets in the discrete torus

The even discrete torus is the graph T L , d on vertex set {0,…, L – 1} d (with L even) in which two vertices are adjacent if they differ on exactly one coordinate and differ by 1(mod L ) on that coordinate. The hard‐core measure with activity λ on T L , d is the probability distribution π λ on the independent sets (sets of vertices spanning no edges) of T L , d in which an independent set I is chosen with probability proportional to λ | I | . This distribution occurs naturally in problems from statistical physics and the study of 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 π λ . We show that for λ = ω( d −1/4 log 3/4 d ) and d sufficiently large the convergence to stationarity is (essentially) exponentially slow in L d −1 . This improves a result of Borgs, Chayes, Frieze, Kim, Tetali, Vigoda, and Vu (Proceedings of the IEEE FOCS (1999), 218–229) 5 who had shown slow mixing of Glauber dynamics for λ growing exponentially with d . Our proof, which extends to ρ‐local chains (chains which alter the state of at most a proportion ρ of the vertices in each step) for suitable ρ, closely follows the conductance argument of Borgs et al., 5 adding to it some combinatorial enumeration methods that are modifications of those used by Galvin and Kahn (Combinatorics, Probability and Computing 13 (2004), 137–164) 12 to show that the hard‐core model with parameter λ on the integer lattice ℤ d exhibits phase coexistence for λ = ω ( d −1/4 log 3/4 d ). The discrete even torus is a bipartite graph, with partition classes ε (consisting of those vertices the sum of whose coordinates is even) and $$ \cal{O} $$ . Our result can be expressed combinatorially as the statement that for each sufficiently large λ, there is a ρ(λ) > 0 such that if I is an independent set chosen according to π λ , then the probability that ‖ I ∩ε|—| I ∩ $ \cal{O} $ ‖ is at most ρ(λ) L d is exponentially small in L d −1 . In particular, we obtain the combinatorial result that for all ε > 0 the probability that a uniformly chosen independent set from T L , d satisfies ‖ I ∩ε|—| I ∩ $ \cal{O} $ ‖≤ (.25 ‐ ε ) L d is exponentially small in L d −1 . © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008