Glauber dynamics on trees and hyperbolic graphs

We study continuous time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap |₁–₂|) for the dynamics on trees and on planar hyperbolic graphs, is polynomial in n. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that for general graphs, if the relaxation time ₂ satisfies ₂=O(1), then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp.Research supported by Microsoft graduate fellowship.Supported by a visiting position at INRIA and a PostDoc at Microsoft research.Research supported by NSF Grants DMS-0104073, CCR-0121555 and a Miller Professorship at UC Berkeley.Acknowledgement We are grateful to David Aldous, David Levin, Laurent Saloff-Coste and Peter Winkler for useful discussions. We thank Dror Weitz for helpful comments on [19].     

On Reverse Hypercontractivity

We study the notion of reverse hypercontractivity. We show that reverse hypercontractive inequalities are implied by standard hypercontractive inequalities as well as by the modified log-Sobolev inequality. Our proof is based on a new comparison lemma for Dirichlet forms and an extension of the Stroock–Varopoulos inequality. A consequence of our analysis is that all simple operators ${L = Id - \mathbb{E}}$ as well as their tensors satisfy uniform reverse hypercontractive inequalities. That is, for all q < p < 1 and every positive valued function f for ${t \geq \log \frac{1-q}{1-p}}$ we have ${\| e^{-tL}f\|_{q} \geq \| f\|_{p}}$ . This should be contrasted with the case of hypercontractive inequalities for simple operators where t is known to depend not only on p and q but also on the underlying space. The new reverse hypercontractive inequalities established here imply new mixing and isoperimetric results for short random walks in product spaces, for certain card-shufflings, for Glauber dynamics in high-temperatures spin systems as well as for queueing processes. The inequalities further imply a quantitative Arrow impossibility theorem for general product distributions and inverse polynomial bounds in the number of players for the non-interactive correlation distillation problem with m-sided dice.