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

preprint2014arXivOpen access

Abstract

TThe prototypical problem we study here is the following. Given a 2L×2L2L\times 2L square, there are approximately exp⁡(4KL2/π)\exp(4KL^2/π) ways to tile it with dominos, i.e. with horizontal or vertical 2×12\times 1 rectangles, where K≈0.916K\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 11, 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 TmixT_{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: Tmix=O(LC)T_{mix}=O(L^C) for some finite CC. Here, we go much beyond and show that cL2≤Tmix≤L2+o(1)c L^2\le T_{mix}\le L^{2+o(1)}. Our result applies to rather general domain shapes (not just the 2L×2L2L\times 2L square), provided that the typical height function associated to the tiling is macroscopically planar in the large LL 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.