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

Abstract

TThe prototypical problem we study here is the following. Given a $2L\times 2L$ square, there are approximately $\exp (4K{L}^2/\pi )$ ways to tile it with dominos, i.e. with horizontal or vertical $2\times 1$ rectangles, where $K\approx 0.916$ is Catalan's constant [Kasteleyn '61, Temperley-Fisher '61]. 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 $1$, two adjacent horizontal dominos are flipped to vertical dominos, or vice-versa. The unique invariant measure is the uniform one and a classical question [Wilson 2004,Luby-Randall-Sinclair 2001] is to estimate the time $T_{mix}$ it takes to approach equilibrium (i.e. the running time of the algorithm). In [Luby-Randall-Sinclair 2001, Randall-Tetali 2000], fast mixin was proven: $T_{mix}=O(L^C)$ for some finite $C$. Here, we go much beyond and show that $c{L}^2\le T_{mix}\le L^{2+o(1)}$. Our result applies to rather general domain shapes (not just the $2L\times 2L$ square), provided that the typical height function associated to the tiling is macroscopically planar in the large $L$ limit, under the uniform measure (this is the case for instance for the Temperley-type boundary conditions considered in [Kenyon 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.

to appear on PTRF; 42 pages, 9 figures; v2: typos corrected, references added

References in corpus (2)

• Asymptotics of uniformly random lozenge tilings of polygons. Gaussian free field
• Mixing times of monotone surfaces and SOS interfaces: a mean curvature approach

Cited by in corpus (1)

• Lozenge tilings, Glauber dynamics and macroscopic shape