5
$\begingroup$

I'd like to ask questions about a "random domino tiling of the plane". However, it's not quite obvious how to go about precisely specifying what this means.

My first instinct was to do something like "the center of a random tiling of a large square". More formally, consider the following property for a random distribution on grid-aligned domino tilings in the plane:

For each $r>0$, the distribution of domino positions within distance $r$ of the origin is the limit of the distributions on that region among randomly-selected tilings of $2N\times 2N$ origin-centered squares as $N$ goes to infinity.

Clearly, if a distribution satisfying this property exists, it is unique, and seems like a reasonable definition to use. However, while intuitive, it is not clear to me how to show that the centers of random tilings of large squares converge in the necessary sense.

The most pressing question about this distribution is whether it actually exists, which I strongly suspect is the case. Conditional on that being true, I have several followup questions:

  • Is the same distribution obtained if we replace "square" with "torus" or "aztec diamond"? Random tilings of the latter are substantially easier to describe and generate (see the Arctic Circle theorem).

  • Is the distribution translation-invariant? Again, I strongly suspect this is the case, but I don't know how I'd go about proving it. If so, how far into a large square do we need to go to see this distribution? E.g., is it the case that a patch of a random $2N\times 2N$ tiling at distance $\log(N)$ from the border asymptotically looks like a patch at the center?

  • What exact probabilities of different configurations does it have? For instance, what are the odds that the origin is not a vertex of any domino? Concretely, at the center of a $2k\times 2k$ grid we have probabilities of $1,\frac19,\frac{361}{841},\frac{139129}{811801},\ldots$, which is approximately $1,0.1111,0.4293,0.1714,\ldots$.

  • Is there a reasonably efficient algorithm to sample from finite portions of this distribution? Ideally in a constructive manner, i.e. an algorithm which when initialized with a random seed spits out progressively more and more dominoes around the origin that extend to a tiling of the plane.

Possibly relevant is the fact that a random tiling of a $2N\times 2N$ square is given in the limit by starting with any tiling and randomly flipping any two dominoes joined in a $2\times 2$ square (see e.g. Laslier and Toninelli 2012).

This was previously posted on Math StackExchange here, without much progress. In the comments, a paper of P. W. Kasteleyn was linked which may be relevant.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

This distribution is the maximal entropy Gibbs measure for domino tilings of the plane. Burton and Pemantle (https://projecteuclid.org/euclid.aop/1176989121) proved many important facts about this distribution, including some remarkable formulas for specific probabilities. (But beware of typos: if I remember right, a few formulas have typos in them.)

Rick Kenyon (http://www.numdam.org/article/AIHPB_1997__33_5_591_0.pdf) showed how to compute all probabilities of local configurations explicitly, via determinantal formulas.

This is enough to answer your questions about tilings of squares or tori: everything converges to maximal entropy statistics and can be computed explicitly.

For more general regions, it depends on the tilt of the height function, but you should get maximal entropy statistics whenever the height function is flat. To resolve the local statistics problem in full generality, you need two things: a classification of Gibbs measures, and the knowledge that the local statistics are translation-invariant in the continuum limit.

Scott Sheffield (http://www.numdam.org/issue/AST_2005__304__R1_0.pdf) completed the classification of all ergodic, translation-invariant Gibbs measures, including the ones with smaller entropy.

Amol Aggarwal (https://arxiv.org/abs/1907.09991) has a recent paper that proves translation invariance in the limit for lozenge tilings. That’s very close to the domino case, but extending it to that case would take a little more (see page 7 of Aggarwal’s article).

For the special case of the Aztec diamond, Chhita, Johansson, and Young (https://projecteuclid.org/euclid.aoap/1427124128) obtained this local convergence result.

I’m not sure about sampling algorithms. My initial thought is to relate the problem to spanning forests (see Burton and Pemantle’s article) and use Wilson’s cycle popping algorithm (https://dl.acm.org/doi/10.1145/237814.237880), but I haven’t thought this through carefully and I’m not sure what’s known about sampling from Gibbs measures.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for writing this! I was starting to draft an answer, but you know a lot of references I don't. I'll take the liberty of adding a few things as comments. First of all, Henry mentions the height function and its tilt. If you aren't familiar with this, it is an integer valued function on the vertices of the domino tiling which encodes the tiling; see Figure 4 in arxiv.org/abs/math/0310326 . When you tile a simply connected planar region, the values of the height function at the boundary are independent of the particular choice of tiling. $\endgroup$
    – David E Speyer
    Commented Feb 2, 2021 at 3:11
  • $\begingroup$ Second, Henry left out his own very nice paper, together with Rick Kenyon and Jim Propp arxiv.org/abs/math/0008220 . In summary, if a sequence of simply connected planar regions grow in size while approaching a limiting shape, and the boundary height functions likewise approach a limit, then the height function in the interior approaches a certain limiting function with probability $1$. $\endgroup$
    – David E Speyer
    Commented Feb 2, 2021 at 3:12
  • $\begingroup$ To see the effect of the boundary, contrast the following two regions. One is a $2n \times 2n$ square, colored in chessboard fashion. The other is the union of the $2n \times 2n$ square with the $n$ additional white squares bordering it to the left and the $n$ additional black squares bordering it to the right. The latter region has only one tiling, and it looks very different from a random tiling of the square. The two regions have almost the same shape, but very different boundary functions. $\endgroup$
    – David E Speyer
    Commented Feb 2, 2021 at 3:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .