English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

TThe prototypical problem we study here is the following. Given a $2L\times2L$ square, there are approximately $\exp(4KL^2/\pi )$ ways to tile it withdominos, i.e. with horizontal or vertical $2\times 1$ rectangles, where$K\approx 0.916$ is Catalan's constant [Kasteleyn '61, Temperley-Fisher '61]. Aconceptually simple (even if computationally not the most efficient) way ofsampling uniformly one among so many tilings is to introduce a Markov Chainalgorithm (Glauber dynamics) where, with rate $1$, two adjacent horizontaldominos are flipped to vertical dominos, or vice-versa. The unique invariantmeasure is the uniform one and a classical question [Wilson2004,Luby-Randall-Sinclair 2001] is to estimate the time $T_{mix}$ it takes toapproach 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 $cL^2\le T_{mix}\le L^{2+o(1)}$. Our result applies to rather general domainshapes (not just the $2L\times 2L$ square), provided that the typical heightfunction associated to the tiling is macroscopically planar in the large $L$limit, under the uniform measure (this is the case for instance for theTemperley-type boundary conditions considered in [Kenyon 2000]). Also, ourmethod extends to some other types of tilings of the plane, for instance thetilings associated to dimer coverings of the hexagon or square-hexagonlattices.

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