How quickly can we sample a uniform domino tiling of the square via Glauber dynamics?

• 成果类型: Article
• 署名作者: Laslier, Benoit; Toninelli, Fabio Lucio
• 署名单位: Universite Claude Bernard Lyon 1; Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS); Ecole Centrale de Lyon; Institut National des Sciences Appliquees de Lyon - INSA Lyon; Universite Claude Bernard Lyon 1; Universite Jean Monnet
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-014-0553-0
• 发表日期: 2015
• 页码: 509-559
• 关键词: dimers; lattice

摘要

The prototypical problem we study here is the following. Given a square, there are approximately ways to tile it with dominos, i.e. with horizontal or vertical rectangles, where is Catalan's constant (Kasteleyn in Physica 27:1209-1225, 1961; Temperley and Fisher in Phil Mag 6:1061-1063, 1997). A conceptually simple (even if computationally not the most efficient) way of sampling uniformly one among so many tilings is to introduce a Markov Chain algorithm (Glauber dynamics) where, with rate , two adjacent horizontal dominos are flipped to vertical dominos, or vice-versa. The unique invariant measure is the uniform one and a classical question (Levin et al. in Am Math Soc, 2009; Luby et al. SIAM J Comput 31:167-192, 2001; Wilson in Ann Appl Probab 14:274-325, 2004) is to estimate the time it takes to approach equilibrium (i.e. the running time of the algorithm). Luby et al. in (SIAM J Comput 31:167-192, 2001) and Randall and Tetali in (J Math Phys 41(3): 1598-1614, 2000) fast mixing was proven: for some finite . Here, we go much beyond and show that . Our result applies to rather general domain shapes (not just the square), provided that the typical height function associated to the tiling is macroscopically planar in the large limit, under the uniform measure [this is the case for instance for the Temperley-type boundary conditions considered in Kenyon (Ann Probab 28:759-795, 2000)]. Also, our method extends to some other types of tilings of the plane, for instance the tilings associated to dimer coverings of the hexagon or square-hexagon lattices.