Sampling independent sets in the discrete torus

The even discrete torus is the graph T-L,T-d on vertex set {0,...,L - 1}(d) (with L even) in which two vertices are adjacent if they differ oil exactly one coordinate and differ by I (modL.) on that coordinate. The hard-core measure with activity lambda on T-L,T-d is the probability distribution pi(lambda) on the independent sets (Sets of vertices spanning no edges) of T-L,T-d in which all independent set I is chosen with probability proportional to lambda(vertical bar I vertical bar). 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 oil the set of independent sets of T-L,T-d whose stationary distribution is pi(lambda). We show that for lambda = omega(d-(1/4) log(3/4) d) and d sufficiently large the convergence to stationarity is (essentially) exponentially slow in Ld-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 lambda growing exponentially with d. Our proof. which extends to rho-local chains (chains which alter the state of at most a proportion rho of the vertices in each step) for suitable rho, 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 lambda on the integer lattice Z(d) exhibits phase coexistence for lambda = omega(d(-1/4) log(3/4) d). The discrete even torus is a bipartite graph. with partition classes epsilon (consisting of those vertices the sum of whose coordinates is even) and O. Our result call be expressed combinatorially as the statement that for each sufficiently large lambda, there is a rho(lambda) > 0 such that if I is an independent set chosen according to pi(lambda). then the probability that parallel to I boolean AND epsilon vertical bar - vertical bar I boolean AND O parallel to is at most rho(lambda)L-d is exponentially small in Ld-1. In particular, we obtain the combinatorial result that for all epsilon > 0 the probability that a uniformly chosen independent set from T-L,T-d satisfies parallel to I boolean AND epsilon vertical bar - vertical bar I boolean AND O parallel to <= (.25 - epsilon)L-d is exponentially small in Ld-1. (C) 2008 Wiley Periodicals, Inc.