Sampling independent sets in the discrete torus

The even discrete torus is the graph TL,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 TL,d is the probability distribution piλ on the independent sets (sets of vertices spanning no edges) of TL,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 in-dependent sets of TL,d whose stationary distribution is piλ. We show that for λ = ω(d−1/4 log3/4 d) and d sufficiently large the convergence to stationarity is (essen-tially) exponentially slow in Ld−1. This improves a result of Borgs et al., 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 conduc-tance argument of Borgs et al., adding to it some combinatorial enumeration meth-ods that are modifications of those used by Galvin and Kahn to show that the hard-core model with parameter λ on the integer lattice Zd exhibits phase coexistence for λ = ω(d−1/4 log3/4 d). The discrete even torus is a bipartite graph, with partition classes E (consisting of those vertices the sum of whose coordinates is even) and 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 piλ, then the probability that ||I ∩ E | − |I ∩ O| | is at most ρ(λ)Ld is exponentially small in Ld−1