The paper concerns lattice triangulations, that is, triangulations of the integer points in a polygon in @math whose vertices are also integer points. Lattice triangulations have been studied extensively both as geometric objects in their own right and by virtue of applications in algebraic geometry. Our focus is on random triangulations in which a triangulation @math has weight @math , where @math is a positive real parameter, and @math is the total length of the edges in @math . Empirically, this model exhibits a "phase transition" at @math (corresponding to the uniform distribution): for @math very large regions of aligned edges appear. We substantiate this picture as follows. For @math we show that the mixing time is exponential. These are apparently the first rigorous quantitative results on the structure and dynamics of random lattice triangulations.
The literature on structural properties and Glauber dynamics of lattice spin systems is too vast to summarize here. We refer the reader to the standard references @cite_19 for structural properties such as spatial mixing, and @cite_1 for mixing times of Glauber dynamics. As explained earlier, while triangulations may be viewed as a spin system, their geometry is very different from that of a traditional spin system on the lattice; our paper can be seen as a first step towards obtaining structural and mixing time results for triangulations analogous to those for classical spin systems.
@cite_19 @cite_1
1999150260 2092260192 2126692288 2031651515
Spin systems are a general way to describe local interactions between nodes in a graph. In statistical mechanics, spin systems are often used as a model for physical systems. In computer science, they comprise an important class of families of combinatorial objects, for which approximate counting and sampling algorithms remain an elusive goal. The Dobrushin condition states that every row sum of the "influence matrix" for a spin system is less than 1 - epsiv, where epsiv > 0. This criterion implies rapid convergence (O(n log n) mixing time) of the single-site (Glauber) dynamics for a spin system, as well as uniqueness of the Gibbs measure. The dual criterion that every column sum of the influence matrix is less than 1 - epsiv has also been shown to imply the same conclusions. We examine a common generalization of these conditions, namely that the maximum eigenvalue of the influence matrix is less than 1 epsiv. Our main result is that this criterion implies O(n log n) mixing time for the Glauber dynamics. As applications, we consider the Ising model, hard-core lattice gas model, and graph colorings, relating the mixing time of the Glauber dynamics to the maximum eigenvalue for the adjacency matrix of the graph. For the special case of planar graphs, this leads to improved bounds on mixing time with quite simple proofs We prove that for finite range discrete spin systems on the two dimensional latticeZ2, the (weak) mixing condition which follows, for instance, from the Dobrushin-Shlosman uniqueness condition for the Gibbs state implies a stronger mixing property of the Gibbs state, similar to the Dobrushin-Shlosman complete analyticity condition, but restricted to all squares in the lattice, or, more generally, to all sets multiple of a large enough square. The key observation leading to the proof is that a change in the boundary conditions cannot propagate either in the bulk, because of the weak mixing condition, or along the boundary because it is one dimensional. As a consequence we obtain for ferromagnetic Ising-type systems proofs that several nice properties hold arbitrarily close to the critical temperature; these properties include the existence of a convergent cluster expansion and uniform boundedness of the logarithmic Sobolev constant and rapid convergence to equilibrium of the associated Glauber dynamics on nice subsets ofZ2, including the full lattice. Studies two widely used algorithms, Glauber dynamics and the Swendsen-Wang (1987) algorithm, on rectangular subsets of the hypercubic lattice Z sup d . We prove that, under certain circumstances, the mixing time in a box of side length L with periodic boundary conditions can be exponential in L sup d-1 . In other words, under these circumstances, the mixing in these widely used algorithms is not rapid; instead it is torpid. The models we study are the independent set model and the q-state Potts model. For both models, we prove that Glauber dynamics is torpid in the region with phase coexistence. For the Potts model, we prove that the Swendsen-Wang mixing is torpid at the phase transition point. We consider Glauber dynamics (starting from an extremal configuration) in a monotone spin system, and show that interjecting extra updates cannot increase the expected Hamming distance or the total variation distance to the stationary distribution. We deduce that for monotone Markov random fields, when block dynamics contracts a Hamming metric, single-site dynamics mixes in O(n log n) steps on an n-vertex graph. In particular, our result completes work of Kenyon, Mossel and Peres concerning Glauber dynamics for the Ising model on trees. Our approach also shows that on bipartite graphs, alternating updates systematically between odd and even vertices cannot improve the mixing time by more than a factor of log n compared to updates at uniform random locations on an n-vertex graph. Our result is especially effective in comparing block and single-site dynamics; it has already been used in works of Martinelli, Toninelli, Sinclair, Mossel, Sly, Ding, Lubetzky, and Peres in various combinations.