December 8, 1997

Matthew Blum

A random tiling of a large regular region in the plane often has non-homogeneous behavior throughout the region. Near the center, the tiling appears random, but near the boundaries, the tiling appears uniform and has zero entropy. This paper discusses several different types of tilings and what characterizes their arctic boundaries.

*E* in graph
*G* is the number of perfect matchings of the graph obtained by
deleting *E* and both of its endpoints removed, divided by the
number of matchings of *G* itself.

**Aztec diamond** of order n is the union of unit
squares in the plane whose centers are contained in the equation |x| +
|y| <= n. The graph in figure 1 is an Aztec diamond of order 5.
Given a bipartite graph, one can convert the graph into its dual
tiling by dimers. A **dimer** is a shape consisting of two adjacent
faces, corresponding to two adjacent vertices in the matching. Each
dimer contains two faces where each face corresponds to a vertex in
the dual. Figure 1 shows a graph with a perfect matching overlaid on
its corresponding tiling on the right.

Figure 1

Order five Aztec diamond with a matching corresponding to a tiling

Figure 2

Random domino tiling of an order 50 Aztec diamond

_{1}, v_{2}, ...,
v_{2n}} is **alternating** if there are exactly n edges
between consecutive vertices in the cycle. There are two ways of
having an alternating cycle. One way of having an alternating cycle
is to have v_{1}, v_{2} matched; v_{3},
v_{4} matched, etc. The other way is to have v_{2},
v_{3} matched; v_{4}, v_{5} matched, etc.

Figure 3

A cycle can be matched two ways.

**pure phase** of a periodic infinite graph has the property that
there are no alternating cycles. We can see in the Aztec diamond
picture in figure 2, in the hexagon in figure 7, and in the fortress
in figure 10, that near the corners of the tilings, the tiles exist in
a pure phase, meaning that there are no local moves that can be made
there to produce another tiling.

**simple pure phases** to be the set of pure phases that are
independent of each other, so that one phase cannot be created from
other pure phases.

Figure 4

Herringbone pattern as a combination of two simple pure phases

Figure 5

Two different lattices that do not permit a pure phase

**Propp-Wilson algorithm**, as discussed in [4] is an
algorithm for creating a random tiling in a much more efficient way.
Since tilings of R exactly correspond to perfect matchings of their dual
graphs of *R*, it is easier to talk about creating a random
matching of a bipartite graph *G*. The Propp-Wilson algorithm
involves creating two special matchings and then coupling them
together to make a random matching.

**minimum and maximum states**. An alternating cycle is in its
minimum state if while one looks at the vertices in a clockwise order,
then for each edge in the cycle, the black vertex occur before the red
one. The cycle is in the maximum state if the red vertex comes before
the black vertex. Figure 3 shows a cycle in the graph, along with its
minimum and maximum states in a matching. A cycle can be
**raised** or **lowered** by moving it between its minimum and
maximum state. This definition for raising and lowering cycles is
arbitrary and the opposite definition is also perfectly equally
valid, but it just needs to be consistent.

**minimum** matching of a whole
graph simply by flipping all existing alternating cycles to their
minimum state so that no maximum alternating cycles still exist. For
a finite region, there is always a finite number of lowering moves
that need to be made until it is impossible to make any more. It is
also true that the minimum matching of any region is unique. The
**maximum** matching is made the same way as the minimum matching,
but is made by raising all the cycles until there is no cycle that can
be raised. For the Aztec diamond, the minimum matching contains only
horizontal tiles and the maximum matching contains only vertical tiles.

**coupled** if they have become the same as a result of removing
discrepancies. If a particular cycle is alternating in only one of
the matchings, matchings, then set only that cycle according to the
coin flip.

*t* and
evolve the matchings for *t* time steps. If they have coupled at
time zero, then the coupled matching is random. If they have not
coupled, then start at time -2*t*, and run until time zero, but
using the __same__ coin flips between -*t* and 0, as before.
If they still have not coupled after 2*t* time steps, start at
time -4*t* and run for 4*t* time steps until hitting time
zero, but making sure the same coin flips are used between time
2*t* and 0. We repeat this process, starting from -8*t*,
-16*t*, and so on as necessary.

*G* will occur more frequently than other matchings, thus
making the random matching not uniformly random.

**Arctic
region** of a matching is the largest set of edges of the matching
that exactly match the corresponding edges in either the minimum or
the maximum matching, that contains no islands in the middle.

Figure 6

Maximum and minimum matchings defining Arctic

region on random matching (same one as in fig 1)

Figure 7

Random tiling of an order 20 hexagon

*n* x 2*n* square has
homogeneous behavior everywhere through the tiling showing it is an
example of a region with no "frozen" areas. In the limit as *n*
grows to infinity, the probability of seeing any of the four types of
dominoes in any location approaches exactly 1/4.

**Aztec-like** boundary. Along
each side of the square, the outermost vertices alternate between red
and black and do not stay the same color, so the boundary is not
Aztec-like.

Figure 8

How edges get forced along an Aztec-like boundary

**fortress** that has an
Aztec-like boundary. Figure 9 shows an order 5 fortress graph, with
its matching and dual tiling overlaid. The fortress has an Aztec-like
boundary will all black vertices at the outermost edge on the upper
left and lower right sides, and red vertices on the outermost edge on
the other two sides.

Figure 9

Random tiling of an order 5 fortress

Figure 10

An order 25 fortress

Figure 11

An order 30 dragon

[1] Jockusch, W., Propp, J.,, Shor, P., "Random Domino Tilings and the Arctic Circle Theorem", October 10, 1995.

[2] Wilson, D., and Propp, J. "How to Get a Perfectly Random Sample From a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph", May 21, 1997.

[3] Cohn, H., Larsen, M., Propp, J., "The Shape of a Typical Boxed Plane Partition", September 2, 1996.

[4] Propp, J., Wilson, D., "Exact Sampling with Coupled Markov
Chains and Applications to Statistical Mechanics", *
Random Structures and Algorithms*. Vol. 9, pp. 223-252, 1996.