# From dominoes to hexagons

Dylan P. Thurston  Department of Mathematics
Harvard University
Cambridge, MA 02138
USA<EMAIL_ADDRESS>
###### Abstract.

There is a natural generalization of domino tilings to tilings of a polygon by
hexagons, or, dually, configurations of oriented curves that meet in triples.
We show exactly when two such tilings can be connected by a series of moves
analogous to the domino flip move. The triple diagrams that result have
connections to Legendrian knots, cluster algebras, and planar algebras.

##  1\. Introduction

The study of tilings of a planar region by lozenges, as in Figure 1(a), or
more generally by rhombi, as in Figure 1(c), has a long history in
combinatorics. Interesting questions include deciding when a region can be
tiled, connectivity of the space of tilings under the basic move
$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/lozenge.20}}}\leftrightarrow\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/lozenge.21}}}$, counting the number of
tilings, and behavior of a random tiling.

One useful tool for studying these tilings is the dual picture, as in Figures
1(b) and 1(d). It consists of replacing each rhombus in the tiling by a cross
of two strands connecting opposite, parallel sides. If we trace a strand
through the tiling it comes out on a parallel face on the opposite side of the
region, independently of the tiling of the region.

Conversely, if we take any set of strands connecting the same pairs boundary
points as in, for instance, Figures 1(b) or 1(d) which are both _generic_
(only two strands intersect at a time) and _minimal_ (no strand intersects
itself and no two strands intersect more than once), then there is a
corresponding dual tiling by rhombuses.

(a) Lozenge tiling

(b) Lozenge dual

(c) Rhombus tiling

(d) Rhombus dual

Figure 1. Tilings by lozenges or more general rhombi and their duals.

It is less well-known that tilings by dominoes (Figure 2(a)) also have a dual
picture (Figure 2(b)), in which we replace each domino by an “asterisk” of
three strands which are not generic, but rather meet in a triple point. When
we perform the basic _domino flip_

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/domino.20}}}\leftrightarrow\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/domino.21}}}$

on domino tilings, the dual strands perform what we will call a
_$2\leftrightarrow 2$ move_

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/domino.25}}}\leftrightarrow\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/domino.26}}}.$

In particular, the connectivity of the strands as we trace them across the
diagram is unchanged. Since the space of domino tilings is connected under the
domino flip, the connectivity of the strands depends only on the shape of the
region and not on the particular tiling (Figure 2(c)).

Conversely, it follows from results in this paper that this is a faithful
representation: every set of immersed arcs with the same connectivity as a
domino tiling, meeting only in triple points, and with a minimal number of
triple points corresponds uniquely to a domino tiling.

As in the case of rhombus tilings, strands always connect parallel sides.
Unlike in the rhombus case, strands may intersect each other arbitrarily many
times. For the special case of the tiling of the Aztec diamond (Figures
2(a)–2(c)), strands connecting parallel sides do not cross in the net
connectivity across the diagram. But this is not true in general, as you can
see in Figures 2(d)–2(f).

(a) An Aztec diamond

(b) Aztec dual

(c) Aztec connectivity

(d) A $5\times 4$ rectangle

(e) Rectangle dual

(f) Rect. connectivity

Figure 2. Domino tilings and their duals, along with the connectivity of the
strands

But there is something we can say about the crossings of strands. Consider the
complementary regions to the strands. Because they meet with six around a
vertex, they may be checkerboard colored with two colors, black and white.
Orient the strand segments clockwise around the black regions and
counterclockwise around the white regions. Because 6 is congruent to 2 modulo
4, the orientations are consistent when we follow a strand through a triple
crossing:

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/arcs.0}}}.$

See Figure 2(e) for the orientations of the strands in the dual to the domino
tiling in Figure 2(d). Another way to characterize these orientations is to
consider a generic curve inside the diagram; the strands that it crosses will
alternate crossing left-to-right and right-to-left.

The appropriate analogue of the minimal condition for the diagrams dual to
rhombus tilings is that strands connecting parallel sides oriented in the same
direction never cross each other.

These pictures suggest a natural generalization.

######  Definition 1.

A _triple diagram_ is a collection of oriented one-manifolds, possibly with
boundary, mapped smoothly into the disk. The image of a connected component is
a _strand_ ; it is either an _arc_ (the image of an interval) or a _loop_ (the
image of a circle). The maps are required to satisfy:

  * •

Three strands cross at each point of intersection;

  * •

the endpoints of arcs are distinct points on the boundary of the disk, and no
other points map to the boundary; and

  * •

the orientations on the strands induce consistent orientations on the
complementary regions.

Triple diagrams are considered up to homotopy among such diagrams. This makes
them essentially combinatorial objects, 6-valent graphs with some extra
structure.

######  Definition 2.

A _connected_ triple diagram $D$ is a diagram in which the image of the
immersed curves together the boundary of the disk is connected. Equivalently,
it is a diagram in which each complementary region to the image is a disk. A
_disjoint component_ of a triple diagram is a connected component of the image
of the immersed curves which does not meet the boundary of the disk. A _simple
loop_ is a loop which goes through no simple crossings and bounds an empty
disk.

A diagram in which all strands are arcs is automatically connected.

If the diagram is connected, the condition on orientations amounts to
requiring that the orientations alternate in and out around each triple point,
and is automatically satisfied if we start anywhere and start assigning
alternating orientations around vertices. Since all the complementary regions
of a connected diagram are disks, we can construct the dual, which is a
topological tiling by hexagons. Note that a domino tiling can be turned into a
tiling by hexagons by adding a vertex in the middle of the long edges of each
domino. The triple crossing diagram described above is dual to this tiling by
hexagons.

As before, the connectivity of the arcs gives a matching of the vertices on
the boundary of the disk. A natural question to ask is which matchings of the
boundary vertices are achievable by a triple diagram. There is one immediate
restriction. The orientations on the strands alternate in and out as we go
around the boundary of the disk, and every inward-pointing end gets matched
with an outward-pointing end. The matching is a bijection between the in and
out endpoints.

######  Theorem 1.

In a disk with $2n$ endpoints on the boundary, all $n!$ pairings of in
endpoints with out endpoints are achievable by some triple point diagram
without closed strands.

The proof is in Section 2.

If we think about these diagrams by analogy with group theory, this theorem
assures us that triple crossings _generate_ admissible pairings. The next
question is _relations_ : What moves on diagrams of triple points allow us to
pass between two diagrams which induce the same matching? One natural move is
the $2\leftrightarrow 2$ move above. This move suffices if the total number of
triple points is as small as possible.

######  Definition 3.

A _minimal_ triple diagram is a connected diagram with no more triple points
than any other triple diagram inducing the same pairing on the boundary.

(The condition of connectivity merely rules out small loops with no crossings
disconnected from the rest of the diagram.)

######  Theorem 2.

Any two minimal triple point diagrams with the same matching on the endpoints
can be related by a sequence of $2\leftrightarrow 2$ moves.

The restriction to minimal diagrams is necessary, since the $2\leftrightarrow
2$ move, as per its name, keeps the total number of triple points unchanged.
To drop this restriction, we need to introduce some moves that change the
number of triple points while preserving the matching. These moves have no
analogues in domino tilings, since the number of triple crossings in a domino
tiling is the number of dominoes, i.e., half the area of the region, which is
invariant.

######  Theorem 3.

Any triple point diagram can be reduced to any minimal triple point diagram
(with the same matching) by a sequence of the following moves:

  * •

$2\leftrightarrow 2$ moves $\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt
-1.00374pt]{draws/moves.0}}}\leftrightarrow\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/moves.1}}}$;

  * •

$1\to 0$ moves $\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt
-1.00374pt
-1.00374pt]{draws/moves.11}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/moves.12}}}$; and

  * •

Dropping a simple loop  with no crossings and an empty interior.

Note that this version of the theorem is a little stronger than you might
expect: we never increase the number of triple crossings.

Theorems 2 and 3 are proved in section 3.

######  Remark.

There is an alternate version of Theorem 3 which stays within the space of
connected diagrams: any connected diagram can be reduced to a minimal diagram
by a sequence of connected diagrams related by

  * •

$2\leftrightarrow 2$ moves;

  * •

$1\to 0$ moves;

  * •

Dropping move 1 $\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt
-1.00374pt
-1.00374pt]{draws/moves.20}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/moves.21}}}$; and

  * •

Dropping move 2 $\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt
-1.00374pt
-1.00374pt]{draws/moves.30}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/moves.31}}}$.

Since this version stays entirely within connected diagrams, it can also be
stated in the dual language of hexagons. We will not prove this version here.
It can be deduced as a corollary of Theorem 3 by analyzing the diagram just
before applying a $1\to 0$ move which disconnects the diagram.

There is also an internal characterization of which triple point diagrams are
minimal.

######  Theorem 4.

A connected triple point diagram is minimal if and only if it has no strands
which intersect themselves (_monogons_) or pairs of strands which intersect at
two points, $x$ and $y$, with both strands oriented from $x$ to $y$ (_parallel
bigons_).

The proof is in section 4. Note that a disconnected component is either a
simple loop or has a monogon so the restriction to connected diagrams is not a
large restriction.

This is an analogue of the theorem that a generic immersion of arcs in the
plane has a minimal number of crossing points for the given pairing of the
boundary (and corresponds to a tiling by rhombi) iff there are no monogons or
bigons. Note that in the triple point diagrams in Figure 2 you can see many
bigons, but all of these bigons are anti-parallel: if the intersections are at
A and B, one strand runs from A to B and the other strand runs from B to A.

### Acknowledgements

I would like to thank Vaughan Jones for suggesting this problem originally,
and for his patience in waiting for me to write it up. I would also like to
thank Vladimir Arnol’d, Andre Henriques, Michael Polyak, Jim Propp, and Chung-
chieh Shan for many helpful discussions and comments.

##  2\. Generating matchings

In order to prove Theorem 1, we will explicitly construct a triple diagram
that achieves a given pairing of in and out endpoints. The triple diagrams we
construct turn out to be minimal diagrams. We will use this construction in
the sections that follow: we will show that any two diagrams are related by
reducing both of them to a diagram of the form we construct here.

We are given a circle with $2n$ endpoints around the boundary, alternately
marked “in” and “out”, and a pairing of the in endpoints with the out
endpoints. Each pair of an in endpoint and an out endpoint divides the circle
into two _intervals_. These intervals are ordered by inclusion. Pick a minimal
interval $I$ with respect to this order. Now start to construct the triple
diagram by running a _boundary-parallel_ strand $S$ along $I$, introducing a
triple crossing for each pair of strands that we cross over:

Note that there will always be an even number of strands to cross over because
of the alternation of in and out endpoints.

Remove $S$ from our original pairing and swap the pairs we crossed over. The
in and out endpoints in the new pairing still alternate and there are fewer
strands. Continue by induction until all the endpoints are paired up.

A diagram constructed in this way is called _standard_.

######  Remark.

We could be a little more liberal in which intervals we allow, while still
preserving minimality of the resulting triple crossing diagram. We can
distinguish between the two intervals arising from a given matching according
to whether the interval runs clockwise or counterclockwise from the in
endpoint to the out endpoint. If we always pick an interval that is minimal
only among all clockwise (resp. counterclockwise) intervals in the
construction above, the resulting triple diagram is still minimal.

We can also count the number of crossings in a standard diagram using only the
connectivity information of the strands.

######  Theorem 5.

The number of triple crossings in a standard triple diagram $D$ is equal to
the number of endpoints $a,b,c,d$, with strands running from $a$ to $c$ and
$b$ to $d$, and either

  * •

$a<b<c<d$; or

  * •

$d<c<b<a$.

Here $<$ is any linear ordering which gives the cyclic ordering on the
boundary of $D$.

The theorem tells us to count the number of parallel crossings between
strands, where “parallel” is defined by reference to a basepoint on the
boundary. The resulting count is also the number of crossings in any minimal
diagram.

###### Proof.

We proceed by induction on the number of strands. Pick a minimal interval from
$a$ to $b$ that does not include the basepoint. Without loss of generality,
suppose $a<b$. Now consider what happens when we run a boundary-parallel
strand $S$ from $a$ to $b$ crossing a pair of adjacent endpoints $c$ (pointing
out) and $d$ (pointing in). Let the strand ending at $c$ be $T$, and the
strand ending at $d$ be $U$, with other endpoint $e$ and $f$, respectively.
Let the diagram (with one fewer strand) above $S$ be $D^{\prime}$. Consider
the location of $e$ and $f$ relative to $a$ and $b$:

Case 1. $e<a$, $f<a$:

The crossing between $S$ and $T$ is parallel, the crossing between $S$ and $U$
is anti-parallel, and any crossing created or destroyed between $T$ and $U$ is
anti-parallel.

Case 2. $b<e$, $b<f$:

The crossing between $S$ and $T$ is anti-parallel, the crossing between $S$
and $U$ is parallel, and any crossing created or destroyed between $T$ and $U$
is anti-parallel.

Case 3. $f<a<b<e$:

The crossings between $S$ and $T$ and $S$ and $U$ are both anti-parallel,
while $D^{\prime}$ has one fewer parallel crossing between $T$ and $U$ than
$D$ does.

Case 4. $e<a<b<f$:

The crossings between $S$ and $T$ and $S$ and $U$ are both parallel, while
$D^{\prime}$ has one more parallel crossing between $T$ and $U$ than $D$ does.

Note that we cannot have $a<e<b$ or $a<f<b$ by the assumption that $S$ is
minimal. In each case, the sum

$\begin{split}(\text{parallel crossings between $S$ and $T$ or
$U$})&+(\text{parallel crossings between $T$ and $U$ in~{}$D$})\\\
&-(\text{parallel crossings between $T$ and $U$
in~{}$D^{\prime}$})\end{split}$

is equal to 1. Thus each triple crossing over a pair of strands along this
boundary-parallel strand gives a net gain of 1 in the count of parallel
crossings. $\square$

##  3\. Reducing diagrams

In order to prove Theorems 2 and 3, we will start with an arbitrary diagram
and reduce it to one of the form described in Section 2 by straightening the
strands one-by-one along the boundary.

The basic blocks in the proof are some relations which let us slide one strand
past another.

######  Lemma 4.

Each of the following triple-point diagrams can be related by sequences of
$2\leftrightarrow 2$ moves:

  1. (a)

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/domino.30}}}\leftrightarrow\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/domino.35}}}$

  2. (b)

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/domino.40}}}\leftrightarrow\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/domino.45}}}$

  3. (c)

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/domino.50}}}\leftrightarrow\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/domino.55}}}$

In each diagram the central section can be repeated an arbitrary number of
times.

###### Proof.

In each case, the two triple-point diagrams come from two different domino
tilings of the same region:

  1. (a)

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/domino.31}}}\leftrightarrow\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/domino.36}}}$

  2. (b)

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/domino.41}}}\leftrightarrow\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/domino.46}}}$

  3. (c)

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/domino.51}}}\leftrightarrow\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/domino.56}}}$

Any two domino tilings of the same region can be related by a sequence of
domino flips. $\square$

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/simplify.10}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt
-1.00374pt]{draws/simplify.11}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/simplify.12}}}$

(a) Remove loops

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/simplify.0}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt
-1.00374pt]{draws/simplify.1}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/simplify.2}}}$

(b) Remove anti-parallel bigons

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/simplify.20}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt
-1.00374pt]{draws/simplify.21}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt
-1.00374pt]{draws/simplify.22}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/simplify.23}}}$

(c) Remove parallel bigons

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/simplify.30}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt
-1.00374pt]{draws/simplify.31}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/simplify.32}}}$

(d) Comb anti-parallel strand

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/simplify.40}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt
-1.00374pt]{draws/simplify.41}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/simplify.42}}}$

(e) Comb parallel strand

Figure 3. Steps in the proof of Lemma 5

######  Lemma 5.

Let $D$ be a triple diagram and let $I$ be a minimal interval of the
associated pairing. Then $D$ is related, by a sequence of $2\leftrightarrow
2$, $1\to 0$ and loop dropping moves, to a diagram $D^{\prime}$ in which there
is a strand boundary-parallel along $I$.

###### Proof.

We proceed by induction on the number of crossings and number of loop
components in $D$, repeatedly applying the lemma to regions contained inside
of $D$. We successively straighten the strand $S$ which connects the endpoints
of $I$.

Step 1. Remove self-intersections of $S$:

If $S$ has self-intersections, consider an innermost loop $L$ of $S$: a loop
of $S$ which does not intersect itself, although it may intersect other
portions of $S$. In Figure 3(a), $L$ is shown solid and the rest of $S$ is
dashed. Consider the region contained inside $L$, including all triple
crossings on the boundary of $L$ except for the self-intersection crossing
itself. This region has fewer triple crossings than the original diagram $D$
(since we omitted the self-intersection), and the short interval between the
two points where $L$ intersects the boundary of the region is minimal, so by
induction we can apply a sequence of $2\leftrightarrow 2$ and $1\to 0$ moves
to reduce $L$ so that it is boundary-parallel inside the region. A single
further $1\to 0$ move removes the original self-intersection of $S$.

Repeat this step until no self-intersections of $S$ remain.

Step 2. Remove double intersections with $S$:

Consider the region $R$ enclosed by the strand $S$ and the interval $I$, not
including the triple crossings along $S$ itself. If there is some strand that
intersects $S$ at least twice, then consider a strand segment $T$ that gives a
minimal interval along the boundary of $R$. Because there are fewer triple
crossings inside $R$ than there were in $D$, we can by induction apply moves
until $T$ is boundary-parallel to $R$. If $T$ and $S$ form an anti-parallel
bigon, we can apply Lemma 4(a) as in Figure 3(b) to remove the bigon. If $T$
and $S$ form a parallel bigon, we can similarly apply Lemma 4(c) and two $0\to
2$ moves as in Figure 3(c) to remove the bigon.

Repeat this step until there are no strands that intersect $S$ twice. The
number of triple intersections along $S$ strictly decreases at each step, so
this terminates.

Step 3. Comb out triple crossings:

At this point, the only strands left between $S$ and $I$ come from the
boundary within the interval $I$ and cross $S$. (Here we use the minimality of
$I$: no strands connect $I$ to itself.) We wish to make $S$ boundary parallel:
that is, we want all the strands starting from $I$ run directly to $S$,
without any triple crossings first. Consider the strand $T$ with the leftmost
endpoint along $I$ which violates this condition. By the hypothesis on $T$ and
the minimality of $S$, the interval corresponding to $T$ is minimal inside the
region $R$ between $S$ and the boundary, omitting the strands to the left of
$T$ and the triple crossings along $S$. Apply induction inside $R$ to reduce
$T$ until it is boundary parallel. If $T$ is oriented anti-parallel to $S$,
apply Lemma 4(b) to make $T$ run straight to $S$, as in Figure 3(d); if $T$ is
oriented parallel to $S$, instead apply Lemma 4(c), as in Figure 3(e).

Repeat this step until every strand runs directly from $I$ to $S$.

Step 4. Remove disconnected components:

Now $S$ is boundary parallel, with the exception of possible disconnected
components of the diagram between $S$ and the boundary. For each disconnected
component, consider a region $R$ that encloses all of the component except for
one arc $T$ on the boundary of the component. The diagram contained inside $R$
has no more triple crossings than $D$ and at least one fewer loop, so by
induction we can reduce it until the unique arc runs boundary parallel on the
side facing $T$. This strand forms a simple loop with $T$, which we can drop.

Repeat this step until there are no disconnected components between $S$ and
the boundary, and so $S$ is boundary parallel. The total number of loops in
the diagram decreases at each step, so this terminates. $\square$

###### Proof of Theorem 2.

Start with two minimal diagram $D$ and $D^{\prime}$. By repeatedly applying
Lemma 5 to $D$, we can obtain a standard diagram $D^{\prime\prime}$ of the
form described in Section 2. Since $D$ is minimal, we did not use any $1\to 0$
moves in this process. Furthermore, any loop dropping move is necessarily
preceded by a $1\to 0$ move since $D$ is connected and $2\leftrightarrow 2$
moves preserve connectivity. Therefore we only used $2\leftrightarrow 2$
moves. In the same way $D^{\prime}$ can be connected to $D^{\prime\prime}$ by
a sequence of $2\leftrightarrow 2$ moves, and so $D$ and $D^{\prime}$ can be
connected by a sequence of $2\leftrightarrow 2$ moves, as desired. $\square$

###### Proof of Theorem 3.

An arbitrary diagram can be reduced to a standard diagram by a sequence of
$2\leftrightarrow 2$, $1\to 0$, or loop dropping moves. A standard diagram is
minimal by the above discussion. $\square$

######  Remark.

One proof of the connectivity of tilings of a region by dominoes [8] exploits
a _height function_ defined on the vertices of the tiling which changes by
$\pm 1$ along each edge of the tiling and by $\pm 3$ along edges of the square
grid which are not edges of the tiling. To show the space of domino tilings is
connected, transform a diagram to an extremal one with minimal height function
by repeatedly looking for a vertex which is a local maximum of the height
function and performing a domino flip at that vertex. The extremal diagrams
with respect to the height function are also standard diagrams in our
terminology. Furthermore, general triple diagrams admit a multi-dimensional
height function on the regions of the diagram which changes by 1 in one
coordinate when you cross an edge. Standard diagrams are extremal with respect
to an appropriate projection from the multi-dimensional height function to
$\mathbb{R}$. Both proofs involve connecting an arbitrary tiling to an
extremal one.

##  4\. Minimal diagrams

Minimal triple diagrams play a somewhat special role in the proof above. In
order to get a better understanding of minimal diagrams, we will prove Theorem
4

######  Definition 6.

A _badgon_ in a general diagram of oriented curves, not necessarily a triple
diagram, is a monogon, parallel bigon, or simple loop

Theorem 4 says that a diagram is minimal if and only if it has no badgons.

###### Proof of Theorem 4.

First suppose a diagram $D$ has a monogon or parallel bigon. In either case,
we can straighten the strand as in the proof of Lemma 5, Steps 1 and 2
(Figures 3(a) and 3(c)) respectively. At the end of the straightening (and
possibly earlier), there are one or two $1\to 0$ moves, which strictly reduces
the number of triple crossings; thus $D$ was not minimal.

For the other direction, we need a lemma.

######  Lemma 7.

Let $D$ and $D^{\prime}$ be general diagrams, not necessarily connected or
with only triple crossings, related by one of the following moves:

  1. (a)

An anti-parallel self-tangency involving distinct strands
$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/moves.50}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/moves.51}}}$;

  2. (b)

Perturbing a triple crossing into 3 double crossings
$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/moves.60}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/moves.61}}}$; or

  3. (c)

A $2\leftrightarrow 2$ move $\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt
-1.00374pt]{draws/moves.0}}}\to\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/moves.1}}}$.

Then $D$ and $D^{\prime}$ either both have no badgons or both have at least
one badgon.

###### Proof.

We consider each case in turn.

  1. (a)

There are two crossings created by the self tangency; call them $x$ and $y$.
All other crossings are the same in the two diagrams. Any badgon that does not
involve $x$ or $y$ will be the same on the two sides of the diagram, so let us
suppose there is none. Because the two strands are different, there is no
monogon created in $D^{\prime}$. Because the self-tangency is anti-parallel,
we can only have a parallel bigon in $D^{\prime}$ involving both $x$ and $y$
if one of the two strands is a loop, which necessarily has badgon in $D$ as
well. The only remaining possibility for a badgon in $D^{\prime}$ that is not
in $D$ is a parallel bigon involving (wlog) $x$ and another crossing elsewhere
in the diagram, say $z$, like this:

In $D^{\prime}$, one strand $S$ runs from $x$ through $y$ to $z$; the other
strand $T$ runs in one direction from $x$ to $z$. In the other direction $T$
runs from $x$ to $y$. After the intersection with $y$, $T$ is inside the bigon
formed by $S$ and $T$ and must exit somewhere. If it exits by crossing $T$,
there is a monogon; if it exits by crossing $S$, there is another parallel
bigon. In either case, this new badgon exists in both $D$ and $D^{\prime}$.

  2. (b)

If any two of the strands involved in the triple crossing are the same, there
is a monogon in both $D$ and $D^{\prime}$. Otherwise, a badgon in $D^{\prime}$
will only involve at most one of the three crossings and there gives a badgon
in $D$ as well, and vice versa.

  3. (c)

If any two of the strands involved are the same, there is a badgon on both
sides of the diagram, so let us suppose all strands are distinct. The
$2\leftrightarrow 2$ move can be decomposed into a sequence of the moves
above: perturb the two triple crossings, perform two anti-parallel self-
crossings, and collect the crossings into two new triple crossings. None of
these steps change the presence of badgons. $\square$

By Theorem 3, any connected non-minimal diagram $D$ can be turned into a
minimal diagram by a sequence of moves, necessarily involving a $1\to 0$ move.
Let $D^{\prime}$ be the diagram just before the first $1\to 0$ move.
$D^{\prime}$ has a monogon at the site of the $1\to 0$ move. $D$ and
$D^{\prime}$ are related by a sequence of $2\leftrightarrow 2$ moves, so by
Lemma 7, $D$ has a badgon as well. $\square$

##  5\. Connections and future directions

###  5.1. Invariants of plane curves and Legendrian knots

One natural connection is with Arnol’d’s theory of invariants of plane curves
[1]. Deforming a generic smooth oriented plane curve in a generic way, you
pass through three types of non-generic points (what Arnol’d calls
_perestroikas_): triple crossing, direct self-tangency, and inverse self-
tangency. If an invariant of generic plane curves does not change under a
triple crossing, it can be extended naturally to an invariant of curves with
triple points. If, in addition, it does not change under an inverse self-
tangency, it will not change under the domino flip move.

For instance, Arnol’d’s $J_{+}$ invariant of plane curves, the simplest
invariant unchanged under these two operations, when evaluated on a curve with
only alternating triple points and no double points gives the number of triple
points plus the index of the curve,plus or minus 1 (depending on the
orientation on the boundary of the exterior region of the plane).

One way to construct invariants of plane curves that do not change under a
triple crossing or an inverse self-tangency is by taking an invariant of the
_Legendrian knot_ in $\mathbb{R}^{2}\times S^{1}$ obtained by lifting the
curve to the unit tangent bundle of the plane. This connection with Legendrian
knots leads to some natural questions:

######  Question 8.

Which Legendrian knots have planar representations with only alternating
triple points?

######  Question 9.

Can two different triple diagrams for a single Legendrian knot always be
related by domino moves?

###  5.2. Cluster algebras and the octahedron recurrence

(This section is joint work with Andre Henriques.)

There are two natural cluster algebras as introduced by Fomin and Zelevinsky
[4] associated to triple diagrams with a given connectivity. Loosely speaking,
a _cluster algebra_ $A$ of rank $n$ is a commutative algebra with unit and no
zero divisors with a distinguished set of _clusters_ : sets of elements
$x_{1},\ldots,x_{n}\in A$ so that every element in $A$ can be written as a
Laurent polynomial in the $x_{i}$ in any given cluster. (A Laurent polynomial
in the $x_{i}$ is a polynomial in the $x_{i}$ and $x_{i}^{-1}$.) Furthermore,
any two clusters can be connected by a sequence of _exchange relations_ :
replacing one element $x_{i}$ of a cluster by a conjugate variable
$\tilde{x}_{i}$, related by

$x_{i}\tilde{x}_{i}=M_{1}+M_{2}$

where $M_{1}$ and $M_{2}$ are monomials in the $n-1$ other elements of the
cluster. (This is a description of cluster algebras, not a definition.)

Each connectivity class of triple diagrams gives a cluster algebra, with each
triple diagram giving a cluster. The variables in the cluster correspond to
the white regions in the checkerboard coloring of the triple crossing diagram.

When you perform a $2\leftrightarrow 2$ move, the cluster variables are
unchanged if the region in the center of the move is black. If the region is
white, the conjugate variable to the variable in the bigon is given by

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/moves.40}}}\longrightarrow\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/moves.41}}}$

where

$f=\frac{ac+bd}{e}.$

One initially surprising fact is the _Laurent phenomenon_ : start from an
arbitrary triple diagram and apply a number of these $2\leftrightarrow 2$
moves. Express the variables on each region in terms of the variables on the
original regions using the exchange relation. Each variable will be a Laurent
polynomial! The number of terms in these Laurent polynomials becomes quite
large, and you have to divide by earlier polynomials in the exchange relation,
but in each case the division comes out exactly. Furthermore, the coefficients
of the Laurent polynomials are positive integers.

This cluster algebra turns out to be a disguised version of the
$n$-dimensional octahedron recurrence [5].

######  Problem 10.

Find a direct combinatorial interpretation for the coefficients of the Laurent
polynomals that appear, analogous to those found by David Speyer [7] for the
3-dimensional octahedron recurrence.

###  5.3. Relations between relations

If Theorem 1 guarantees that triple diagrams generate all possible
permutations and Theorem 3 guarantees that the $2\leftrightarrow 2$, $1\to 0$,
and loop dropping moves give all relations between triple diagrams, the next
natural question is what the relations between relations are. For simplicity,
we will restrict ourselves to minimal triple diagrams.

Figure 4. Conjectured relations between relations

######  Conjecture 11.

For a given connectivity of diagrams, consider the 2-complex $C$ with vertices
given by minimal triple diagrams, edges given by $2\leftrightarrow 2$ moves,
and 2-cells of the following types:

  1. (1)

Squares for two different $2\leftrightarrow 2$ moves in non-interfering parts
of the diagram;

  2. (2)

Pentagons as on the left of Figure 4 or their orientation reverse; and

  3. (3)

Decagons as on the right of Figure 4.

Note that the connectivity of the left (resp. right) of Figure 4 has each
strand connected 3 (resp. 5) positions around the boundary of the diagram.
More generally, one can conjecture that there is a contractible complex with
fundamental $n$-cells given by diagrams with $2n+6$ endpoints, each one
connected the same odd number of positions around the boundary. Note that for
$n=0$ you get a single triple crossing and for $n=1$ you get the
$2\leftrightarrow 2$ move. As in Conjecture 11, you also have to allow
products of lower-dimensional cells.

###  5.4. Planar algebras

The original motivation for considering triple crossings came from _planar
algebras_ as introduced by Jones [6]. Briefly, planar algebras in the form we
consider have a complex vector space $B_{n}$ for each $n$, the space of _$n$
-boxes_. Each $n$-box conceptually has $2n$ strands attached to the boundary,
alternating in and out. They may be joined together by oriented _arc diagrams_
like this one:

This diagram, for instance, has 4 inputs (the little circles), with 4, 2, 4,
and 4 strands, respectively; the output (the large circle) has 8 strands. This
diagram therefore gives a multilinear map

$B_{2}\otimes B_{1}\otimes B_{2}\otimes B_{2}\to B_{4}.$

Each arc diagram gives a similar multilinear map, and if you plug the output
of one multilinear map into the input of another, you get the multilinear map
corresponding to gluing together the two arc diagrams. Formally, this is the
structure of a (typed) operad. (To be precise, you must also provide some
markings to know the orientations when you plug in elements.)

Typically one assumes that $B_{0}$ is 1-dimensional and is identified with
$\mathbb{C}$. In particular, this implies that a simple loop, which can be
thought of as an element of $B_{0}$, has some definite value
$\delta\in\mathbb{C}$.111One of the subtleties we’re ignoring is that a
clockwise and counterclockwise loop could potentially have different values.

One natural way to start to classify planar algebras is by their generating
sets. Every planar algebra contains the _Temperley-Lieb algebra_ , consisting
of diagrams with only non-crossing arcs and no inputs. Non-crossing diagrams
with no loops give us $1,1,2,5,14,\ldots$ elements inside $B_{n}$ for
$n=0,1,2,3,4,\ldots$. Most planar algebras are not spanned by the Temperley-
Lieb algebra, but are generated by the addition of some extra elements. For
example, Bisch and Jones [2, 3] have studied planar algebras that are
generated by a single 2-box. Consider instead planar algebras where the 0-,
1-, and 2-boxes are spanned by Temperly-Lieb elements and which are generated
by a single 3-box. If we draw the 3-box as a triple crossing,222Another
subtlety we’re ignoring here is that the 3-box need not be symmetric under
rotation by 120 degrees, as the triple crossing is. This turns out not to
affect the subsequent discussion. then every triple diagram gives an $n$-box.
If we assume further that the dimension of $B_{4}$ is less than or equal to 25
and that the relations are “generic” and “symmetric” in senses to be made
precise below, the results in this paper imply that the dimension of $B_{n}$
is less than or equal to $n!$ for all $n$.

To prove this, consider diagrams modulo “simpler” diagrams that either have
fewer loops or fewer triple crossings, and look at the three moves used in
Theorem 3.

  * •

A loop is equal to a constant $\delta$.

  * •

Because $B_{2}$ is spanned by Temperly-Lieb elements, the LHS of the $1\to 0$
move  is equal to a linear combination of diagrams with no crossings.

  * •

There are 26 elements of $B_{4}$ obtained from the 14 elements of the
Temperly-Lieb algebra, the 8 ways of adding a single arc to a single triple
crossing, and the 4 ways of connecting two triple crossings along two adjacent
arcs, so by assumption there is at least a 2-dimensional space of relations
between these 26 elements. The highest terms are of the last kind. Assume that
the relations are generic: when we take the quotient by the space spanned by
the first 22 diagrams, the space of relations is a 2-dimensional subspace $W$
of the 4-dimensional space $V$ with basis given by the remaining 4 diagrams.
Rotating by 90 degrees gives a symmetry of order two of $V$ that must preserve
$W$. $V$ decomposes into two subspaces $V=V^{+}\oplus V^{-}$, both of
dimension two. If we furthermore assume that $W$ is symmetric when we reverse
all the arrows, $W$ must be equal to either $V^{+}$ or $V^{-}$. Then we have
either

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/moves.0}}}=\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/moves.1}}}+(\text{lower order terms})$

or

$\vbox{\hbox{\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{draws/moves.0}}}=-\vbox{\hbox{\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{draws/moves.1}}}+(\text{lower order
terms}),$

respectively.

In either case, the three moves involved in Theorem 3 are all true up to sign
and modulo lower order terms. Therefore,

  * •

Non-minimal diagrams are equal to 0 modulo lower order terms, and

  * •

Minimal diagrams with the same connectivity are equal to plus or minus each
other modulo lower order terms.

Therefore $B_{n}$ is spanned $n!$ minimal diagrams, one for each connectivity.

One source of planar algebras satisfying these hypotheses is the skein module
of the HOMFLY polynomial, a well-known invariant of oriented links. You might
expect a knot invariant to give a planar algebra based on a simple crossing,
which would be a 2-box; however, the orientations in the HOMFLY polynomial and
the requirement that the strands alternate in-out force you to consider triple
crossings.

## References

  * [1] Vladimir I. Arnold, _Topological invariants of plane curves and caustics_ , University lecture series, vol. 5, American Mathematical Society, Providence, R.I., 1994.
  * [2] Dietmar Bisch and Vaughan Jones, _Singly generated planar algebras of small dimension_ , Duke Math. J. 101 (2000), no. 1, 41–75.
  * [3] by same author, _Singly generated planar algebras of small dimension. II_ , Adv. Math. 175 (2003), no. 2, 297–318.
  * [4] Sergey Fomin and Andrei Zelevinsky, _Cluster algebras I: Foundations_ , J. Amer. Math. Soc 15 (2002), no. 2, 497–526, arXiv:math.RT/0104151.
  * [5] Andre Henriques and Joel Kamnitzer, _A monoidal category built using the octahedron recurrence_ , in preparation, available from http://www-math.mit.edu/~andrhenr, March 2004.
  * [6] Vaughan F. R. Jones, _Planar algebras, I_ , Tech. report, U. C. Berkeley, September 1999, arXiv:math.QA/9909027.
  * [7] David E. Speyer, _Perfect matchings and the octahedron recurrence_ , arXiv:math.CO/0402452.
  * [8] William P. Thurston, _Conway’s tiling groups_ , Amer. Math. Monthly 97 (1990), no. 8, 757–773.