RANDOM LATTICE TRIANGULATIONS: STRUCTURE AND ALGORITHMS

• 成果类型: Article
• 署名作者: Caputo, Pietro; Martinelli, Fabio; Sinclair, Alistair; Stauffer, Alexandre
• 署名单位: Roma Tre University; University of California System; University of California Berkeley
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/14-AAP1033
• 发表日期: 2015
• 页码: 1650-1685
• 关键词: NUMBER

摘要

The paper concerns lattice triangulations, that is, triangulations of the integer points in a polygon in R-2 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 a has weight Ala I, where is a positive real parameter, and vertical bar sigma vertical bar is the total length of the edges in a. Empirically, this model exhibits a phase transition at lambda = 1 (corresponding to the uniform distribution): for lambda < 1 distant edges behave essentially independently, while for lambda > 1 very large regions of aligned edges appear. We substantiate this picture as follows. For lambda < 1 sufficiently small, we show that correlations between edges decay exponentially with distance (suitably defined), and also that the Glauber dynamics (a local Markov chain based on flipping edges) is rapidly mixing (in time polynomial in the number of edges in the triangulation). This dynamics has been proposed by several authors as an algorithm for generating random triangulations. By contrast, for lambda > 1 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.