These two pictures illustrate the relationship between domino tilings and alternating sign matrices, and a conjecture of Jim Propp that was proved in Spring 2001 by SSL-participant Hal Canary. This result states that domino tilings for which the associated alternating sign matrices contain no -1's are essentially the same thing as Baxter permutations.
What to look at:
The TILES: On the right, a region composed of 60 unit squares (tilted at a 45 degree angle) has been divided into 30 dominos (1-by-2 rectangles). This large region is called an Aztec diamond of order 5. (The four "spurs" in the corners play a role discussed below.)
The MATRICES: On the left, we see two matrices superimposed: a blue matrix of 0's and 1's and a red matrix of 0's and blocks. These entries occur at the vertices where tiles meet, and the colors alternate: a red entry is surrounded by four blue entries and vice versa.
The COLORS of the tiles (right): A tile of slope +1 is yellow or blue, according to the color (red versus blue) of the matrix entry associated with the midpoint of the lower of the two long edges of the domino. A tile of slope -1 is red or green, according to the color (red versus blue) of the matrix entry associated with the midpoint of the higher of the two long edges of the domino.
The BLUE NUMBERS (left): A blue number records the number of tile-edges that meet there, minus 3. (Note that a spur counts as a tile-edge.) Since each vertex is incident with 2, 3, or 4 tile-edges/spurs, all the blue entries equal -1, 0, or 1. The blue entries form an alternating sign matrix (ASM): the non-zero entries in each row or column alternate in sign. In this particular example, there are no blue -1s.
The RED NUMBERS (left): A red entry is equal to 3 minus the number of incident tile-edges/spurs. The red entries form another ASM. In this particular example, all the non-zero red entries have been replaced by red blocks. A red -1 corresponds to a place where tiles of all four colors meet.
The WINDMILL (left): If a red entry is non-zero, then there are entries in the adjoining blue rows and the adjoining blue columns forming a certain kind of pattern. In particular, if the red entry is a -1 (as is the case here), the blue 1's ordinarily form a windmill pattern. This lemma is a key step in the proof of the theorem.
The back of the T-shirt shows a state of the hexagonal FPL (Fully Packed Loop) model, rendered with curved segments for greater visual appeal. In uncurved form, such a state is a spanning subgraph G' of a regular hexagonal grid G, where G has pendant edges at the boundary that also belong to G', and where every non-pendent vertex of G' has degree 2.
o o
\ /
o o---o o
\ / \ /
o o---o o---o o
\ / \ / \ /
o---o o---o o---o
/ \ / \ / \
o---o o---o o---o o---o
\ / \ / \ /
o---o o---o o---o
/ \ / \ / \
The graph G: o---o o---o o---o o---o
\ / \ / \ /
o---o o---o o---o
/ \ / \ / \
o---o o---o o---o o---o
\ / \ / \ /
o---o o---o o---o
/ \ / \ / \
o o---o o---o o
/ \ / \
o o---o o
/ \
o o
o o
\ /
o o---o o
\ /
o o---o o---o o
\ \ / /
o---o o o o---o
\ / \ /
o---o o---o o---o o---o
\ /
o---o o---o o---o
\ / \ /
An FPL state: o---o o o o o o---o
\ / \ / \ /
o---o o---o o o
/ \
o---o o---o o---o o---o
\ / \ /
o o o o o---o
/ \ / \ / \
o o o o o o
/ \ / \
o o o o
/ \
o o
FPL-states on an hexagonal grid
have been investigated in analogy with FPL-states on a square grid,
which correspond to ASMs.
In contrast, FPL-states on a hexagonal grid with pendent edges correspond
to perfect matchings of the graph
from which the pendent edges have been removed
(to see this, look at the edges of G that are _not_ in G'),
and these in turn correspond to tilings of the hexagon by rhombuses.
The picture on the T-shirt was obtained from a rhombus-tiling of a hexagon by drawing two 60-degree arcs on each tile, centered on the acute corners. These arcs combine to form loops, each of which is either a closed curve in the interior of the hexagon or an open path joining two points on the boundary. The regions between the loops are alternately shaded blue and green for visual appeal, but this coloring has no mathematical significance; what is important are the loops themselves.
Note that the loops that originate in the corners of the hexagon tend to travel a significant distance toward the middle before being deflected. The region within such deflections occur is called the "temperate zone", and it has been shown that as the size of the regular hexagon goes to infinity, the temperate zone tends toward the interior of the circle inscribed in the hexagon.
For some details on the FPL model on a square grid, see the 1998 Tilings Research Group tee-shirt or the article The Many Faces of Alternating Sign Matrices.
The members of the Spatial Systems Laboratory during Spring 2001 were: Jim Propp, Michael Lang, Boytcho Peytchev, Hal Canary, Rachel Dahl, Geir Helleloid, Kristin Jehring, Dominic Johann-Berkel, Pavle Juranic, Dan Luu, Nick Pongratz, Joel Scherpelz, and Abraham Smith.