×

On the sampling problem for \(H\)-colorings on the hypercube lattice. (English) Zbl 1074.05032

Nešetřil, J. (ed.) et al., Graphs, morphisms and statistical physics. Proceedings of the workshop held at Rutgers University, Piscataway, NJ, USA, March 19–21, 2001. Providence, RI: American Mathematical Society (AMS) (ISBN 0-8218-3551-3/hbk). DIMACS. Series in Discrete Mathematics and Theoretical Computer Science 63, 13-28 (2004).
Given a fixed finite graph \(H\) without multiple edges (possibly with loops) and a simple, locally finite graph \(G\) with countably many vertices, an \(H\)-coloring of \(G\) is a homomorphism from \(G\) to \(H\). The authors study the random \(H\)-colorings of rectangular subsets of the hypercubic lattice \(\mathbb{Z}^d\), where the color \(i\) is assigned by the weight \(\lambda_i \in (0,\infty)\). They consider quasi–local Markov chains on a periodic box of even side length \(L\) (that is, Markov chains that do not change more than a fraction \(\rho < 1\) of the sites in the box in any single move). It is proved that for any \(\rho < 1\) and any finite connected non–trivial \(H\), there exist weights \(\{\lambda_i\}\) such that all quasi–local ergodic Markov chains have slow mixing (with the mixing time being exponential in \(L^{d-1}\)). Under the same conditions, the phase coexistence is proved (in the sense that there are at least two extremal Gibbs states); also, it is proved that, for a large class of graphs \(H\), it is possible to choose weights \(\{\lambda_i\}\) such that the corresponding Gibbs measure has exponentially fast spatial mixing.
For the entire collection see [Zbl 1051.05003].

MSC:

05C15 Coloring of graphs and hypergraphs
60K35 Interacting random processes; statistical mechanics type models; percolation theory
68W20 Randomized algorithms
82B26 Phase transitions (general) in equilibrium statistical mechanics
PDFBibTeX XMLCite