Transcript Aztec diamond

Circles in Aztec Diamonds. Aztec
Diamonds in Groves. Circles in
Groves?
Limiting Behavior of Combinatorial
Models
Circles in Aztec Diamonds
•
An Aztec diamond of order n is defined as the union of those lattice squares whose interiors lie inside
the region {(x,y) : |x+y|<= n+1}.
Circles in Aztec Diamonds
•
•
An Aztec diamond of order n is defined as the union of those lattice squares whose interiors lie inside
the region {(x,y) : |x+y|<= n+1}.
A domino tiling of an Aztec diamond is a way to cover the region with 2 by 1 rectangles (dominoes)
so that none of the dominoes overlap, and none of the dominoes extend outside the boundary of the
region.
Circles in Aztec Diamonds
•
•
An Aztec diamond of order n is defined as the union of those lattice squares whose interiors lie inside
the region {(x,y) :|x+y|<= n+1}.
A domino tiling of an Aztec diamond is a way to cover the region with 2 by 1 rectangles (dominoes)
so that none of the dominoes overlap, and none of the dominoes extend outside the boundary of the
region.
Circles in Aztec Diamonds
•
The number of domino tilings of an Aztec diamond is 2^(n(n+1)/2). Any of these tilings can be
generated uniformly at random by a procedure called domino shuffling described in a paper of Elkies,
Kuperberg, Larsen, and Propp.
Circles in Aztec Diamonds
Shuffling:
Circles in Aztec Diamonds
Shuffling:
1. Slide dominoes
Circles in Aztec Diamonds
Shuffling:
1. Slide dominoes
2. Fill in randomly
Circles in Aztec Diamonds
Shuffling:
1. Slide dominoes
Circles in Aztec Diamonds
Shuffling:
1. Slide dominoes
2. Fill in randomly
Circles in Aztec Diamonds
Shuffling:
0. Delete bad blocks
Circles in Aztec Diamonds
Shuffling:
0. Delete bad blocks
1. Slide dominoes
Circles in Aztec Diamonds
Shuffling:
0. Delete bad blocks
1. Slide dominoes
2. Fill in randomly
Circles in Aztec Diamonds
Shuffling:
0. Delete bad blocks
Circles in Aztec Diamonds
Shuffling:
0. Delete bad blocks
1. Slide dominoes
Circles in Aztec Diamonds
Shuffling:
0. Delete bad blocks
1. Slide dominoes
2. Fill in randomly
Circles in Aztec Diamonds
•
A domino is called North-going if it migrates north under shuffling, similarly for south,
east, and west.
Circles in Aztec Diamonds
•
Equivalently, they may be defined by the checkerboard coloring of the plane. A north
going domino has a black square on the left and a white square on the right. A south
going domino has a white square on the left and a black square on the right. Similarly for
east and west.
Circles in Aztec Diamonds
•
Equivalently, they may be defined by the checkerboard coloring of the plane. A north
going domino has a black square on the left and a white square on the right. A south
going domino has a white square on the left and a black square on the right. Similarly for
east and west.
Circles in Aztec Diamonds
•
We typically color the tiles red, yellow, blue, and green.
Circles in Aztec Diamonds
•
A domino is called frozen if it can never be annihilated by further shuffling.
Circles in Aztec Diamonds
The Arctic Circle Theorem (Jockusch, Propp, Shor): As n (the order of the Aztec diamond) goes to
infinity, the expected shape of the boundary between the frozen region and temperate zone is a circle.
Circles in Aztec Diamonds
The Arctic Circle Theorem (Jockusch, Propp, Shor): Examine the growth model on Young diagrams
where each growth position has independent probability ½ of adding a box. This has limiting
shape of a quarter-circle (suitably scaled).
Circles in Aztec Diamonds
Further Statistics of Aztec diamonds:
(Cohn, Elkies, and Propp) – Expectations within the temperate zone
Circles in Aztec Diamonds
Further Statistics of Aztec diamonds:
(Johansson) – Fluctuations about the circle. The method of non-intersecting paths, or Brownian motion
model yields a link to random matrices and Tracy-Widom distribution. Johansson ultimately equated
this model to the random growth model for the Young diagram.
Aztec Diamonds in Groves
f(1) = 2
f(2) = 8
f(3) = (2f(2)^2)/f(1) = 64
f(4) = (2f(3)^2)/f(2) = 1024
Aztec diamonds can be enumerated by the octahedron recurrence. Let f(n) = the number of Aztec diamonds of
order n. Then f(n)f(n-2) = 2f(n-1)^2.
Aztec Diamonds in Groves
Polynomial version of octahedron recurrence: f(i,j,k)f(i,j,k-2) = f(i-1,j,k-1)f(i+1,j,k-1)+f(i,j-1,k-1)f(i,j+1,k1) where f(i,j,k) = x(i,j,k) if k=0,-1. Otherwise f(i,j,n) encodes all the tilings of an Aztec diamond of
order n. The rational functions that are generated are not just rational in the x(i,j,k), they are Laurent
polynomials.
Aztec Diamonds in Groves
> f(0,0,2);
x(0, 0, 0) x(2, 0, 0) x(-2, 0, 0)
--------------------------------x(1, 0, -1) x(-1, 0, -1)
+
x(1, 1, 0) x(1, -1, 0) x(-2, 0, 0)
+ ---------------------------------x(1, 0, -1) x(-1, 0, -1)
+
x(2, 0, 0) x(-1, 1, 0) x(-1, -1, 0)
----------------------------------x(1, 0, -1) x(-1, 0, -1)
x(1, 1, 0) x(1, -1, 0) x(-1, 1, 0) x(-1, -1, 0)
----------------------------------------------x(0, 0, 0) x(1, 0, -1) x(-1, 0, -1)
x(1, 1, 0) x(-1, 1, 0) x(1, -1, 0) x(-1, -1, 0)
+ ----------------------------------------------x(0, 0, 0) x(0, 1, -1) x(0, -1, -1)
x(0, 2, 0) x(1, -1, 0) x(-1, -1, 0)
+ ----------------------------------x(0, 1, -1) x(0, -1, -1)
=
x(1, 1, 0) x(-1, 1, 0) x(0, -2, 0)
---------------------------------x(0, 1, -1) x(0, -1, -1)
x(0, 0, 0) x(0, 2, 0) x(0, -2, 0)
--------------------------------x(0, 1, -1) x(0, -1, -1)
+
+
+
+
+
+
+
+
+
Octahedron Recurrence: f(i,j,k)f(i,j,k-2) = f(i-1,j,k-1)f(i+1,j,k-1)+f(i,j-1,k-1)f(i,j+1,k-1)
Aztec Diamonds in Groves
•
•
Cube Recurrence: f(i,j,k)f(i-1,j-1,k-1) = f(i-1,j,k)f(i,j-1,k-1)+f(i,j-1,k)f(i-1,j,k-1)+f(i-1,j-1,k)f(i,j,k-1)
The cube recurrence is a generalization of the octahedron recurrence. As shown by Fomin and
Zelevinsky using cluster algebra methods, it also produces Laurent polynomials. But what do the
polynomials encode?
Aztec Diamonds in Groves
= ??
Cube Recurrence: f(i,j,k)f(i-1,j-1,k-1) = f(i-1,j,k)f(i,j-1,k-1)+f(i,j-1,k)f(i-1,j,k-1)+f(i-1,j-1,k)f(i,j,k-1)
Aztec Diamonds in Groves
= Groves
Cube Recurrence: f(i,j,k)f(i-1,j-1,k-1) = f(i-1,j,k)f(i,j-1,k-1)+f(i,j-1,k)f(i-1,j,k-1)+f(i-1,j-1,k)f(i,j,k-1)
Aztec Diamonds in Groves
Trivial initial conditions
A grove is a new combinatorial object, due to Carroll and Speyer, given by the cube recurrence. Groves
can be viewed as forests that live on a very special planar region or more intuitively, on a three
dimensional surface with lattice point corners (- a big pile of cubes). What the surface looks like is
specified by some initial conditions.
Aztec Diamonds in Groves
Trivial initial conditions 
Unique grove on trivial initials
A grove is a new combinatorial object given by the cube recurrence. Groves can be viewed as forests that
live on a very special planar region, given by some specified initial conditions. However, note that
the forests have severely restricted behavior.
Aztec Diamonds in Groves
Trivial initial conditions 
Unique grove on trvial initials 
The grove
A grove is a new combinatorial object given by the cube recurrence. Groves can be viewed as forests that
live on a very special planar region, given by some specified initial conditions. However, note that
the forests have severely restricted behavior.
Aztec Diamonds in Groves
Kleber initial conditions (4,2,3)
Random grove on KI(4,2,3)
The grove
A grove is a new combinatorial object given by the cube recurrence. Groves can be viewed as forests that
live on a very special planar region, given by some specified initial conditions. However, note that
the forests have severely restricted behavior.
Aztec Diamonds in Groves
Aztec diamond initial conditions
of order 4
Random grove on AD(4)
The grove
A grove is a new combinatorial object given by the cube recurrence. Groves can be viewed as forests that
live on a very special planar region, given by some specified initial conditions. However, note that
the forests have severely restricted behavior.
Aztec Diamonds in Groves
Octahedron Recurrence: f(i,j,k)f(i,j,k-2) = f(i-1,j,k-1)f(i+1,j,k-1)+f(i,j-1,k-1)f(i,j+1,k-1)
Cube Recurrence: f(i,j,k)f(i-1,j-1,k-1) = f(i-1,j,k)f(i,j-1,k-1)+f(i,j-1,k)f(i-1,j,k-1)+f(i-1,j-1,k)f(i,j,k-1)
Remember that the octahedron recurrence is a special case of the cube recurrence.
Aztec Diamonds in Groves
There is a correspondence between tilings of Aztec diamonds of order n and certain groves on Aztec
initial conditions of order n.
Aztec Diamonds in Groves
> f(0,0,2);
x(0,0,0) x(2,0,0) x(-2,0,0)
---------------------------
x(2,0,0) x(-1,1,0) x(-1,-1,0)
+
-----------------------------
x(1,0,-1) x(-1,0,-1)
x(1,1,0) x(1,-1,0) x(-2,0,0)
x(1,0,-1) x(-1,0,-1)
x(1,1,0) x(1,-1,0) x(-1,1,0) x(-1,-1,0)
+ ---------------------------- + --------------------------------------x(1,0,-1) x(-1,0,-1)
x(0,0,0) x(1,0,-1) x(-1,0,-1)
x(1,1,0) x(-1,1,0) x(1,-1,0) x(-1,-1,0)
x(1,1,0) x(-1,1,0) x(0,-2,0)
+ --------------------------------------- +
----------------------------
x(0,0,0) x(0,1,-1) x(0,-1,-1)
x(0,2,0) x(1,-1,0) x(-1,-1,0)
+ -----------------------------x(0,1,-1) x(0,-1,-1)
x(0,1,-1) x(0,-1,-1)
x(0,0,0) x(0,2,0) x(0,-2,0)
+
---------------------------x(0,1,-1) x(0,-1,-1)
Because the octahedron recurrence is a special case of the cube recurrence, there is actually an injection
from the set of tilings of Aztec diamonds into the set of groves on Aztec initial conditions.
Aztec Diamonds in Groves
Standard initial conditions of order 8
The standard initial conditions for a grove look like the compliment of an upside down Q*Bert board.
Aztec Diamonds in Groves
A grove on standard initial conditions
Aztec Diamonds in Groves
Groves on standard initial conditions are better represented in a triangular lattice. Notice that we may
ignore the short edges. This representation is called a simplified grove.
Aztec Diamonds in Groves
Like domino shuffling, there is a way to generate groves on standard initial conditions uniformly at
random, called grove shuffling (or cube-popping in general).
Aztec Diamonds in Groves
Like domino shuffling, there is a way to generate groves on standard initial conditions uniformly at
random, called grove shuffling (or cube-popping in general).
Aztec Diamonds in Groves
Like domino shuffling, there is a way to generate groves on standard initial conditions uniformly at
random, called grove shuffling (or cube-popping in general).
Aztec Diamonds in Groves
Like domino shuffling, there is a way to generate groves on standard initial conditions uniformly at
random, called grove shuffling (or cube-popping in general).
Aztec Diamonds in Groves
Like domino shuffling, there is a way to generate groves on standard initial conditions uniformly at
random, called grove shuffling (or cube-popping in general).
Aztec Diamonds in Groves
Like domino shuffling, there is a way to generate groves on standard initial conditions uniformly at
random, called grove shuffling (or cube-popping in general).
Aztec Diamonds in Groves
Like domino shuffling, there is a way to generate groves on standard initial conditions uniformly at
random, called grove shuffling (or cube-popping in general).
Aztec Diamonds in Groves
Like domino shuffling, there is a way to generate groves on standard initial conditions uniformly at
random, called grove shuffling (or cube-popping in general).
Aztec Diamonds in Groves
Like domino shuffling, there is a way to generate groves on standard initial conditions uniformly at
random, called grove shuffling (or cube-popping in general).
Aztec Diamonds in Groves
Like domino shuffling, there is a way to generate groves on standard initial conditions uniformly at
random, called grove shuffling (or cube-popping in general).
Circles in Groves?
Four representations of a
randomly generated
grove of order 20.
With grove shuffling we can generate large random groves fairly quickly.
Circles in Groves?
Representation of an order 200 grove.
With grove shuffling we can generate large random groves fairly quickly.
Circles in Groves?
The most promising method of attacking the grove problem seems to be by projecting down one of the
colors in a corner,
Circles in Groves?
The most promising method of attacking the grove problem seems to be by projecting down one of the
colors in a corner, isolating the frozen region, and making the situation look like a Young diagram
model with growth probability equal ½ .
Circles in Groves?
Projection of frozen region of a random grove of order 20 above, Young diagram growth model after 20 growth stages below (p= ½ ).
The most promising method of attacking the grove problem seems to be by projecting the frozen region
down to a Young diagram model with growth probability equal ½ .
Circles in Groves?
Projection of frozen region of a random grove of order 100 above, Young diagram growth model after 100 growth stages below (p= ½ ).
The most promising method of attacking the grove problem seems to be by projecting the frozen region
down to a Young diagram model with growth probability equal ½ .
Circles in Groves?
Looking at a given grove whose projection is above, the observed probabilities of growth are sometimes
zero and sometimes 2/3, but never ½! However, I think that if we can take the weighted probabilities
over all groves with this projection, then we will find the total probability is equal to the infinite sum
of (1/3)^k, k=1 to infinity. What is this sum? ½.
Circles in Groves?
Other peculiarities…
Non-intersecting paths for groves…
Circles in Groves?
Any Questions?
Comments?
Suggestions?