MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have been reading David Speyer's Perfect Matchings and the Octahedron Recurrence, trying to carry out his "cross-wrenches" generalization of the Aztec diamond. In what follows, I'm asking for a construction of $G_{n_0,i_0,j_0}$ in the case where the infinite graph $\mathcal{G}$ gives square-octagon tiling.

I found Speyer's notation very difficult. Maybe section 4 of Perfect Matchings and Perfect Powers by Mihai Ciucu will be easier to use for this special case.

In section 1.2 the "Aztec Diamond" theorem is stated $f(n_0, i_0, j_0) = \sum m(M)$

  • $f(n_0,i_0,j_0)$ is the solution to the octahedron recurrence. $$ f(n,i,j)f(n-2,i,j)= f(n-1,i-1,j)f(n-1,i+1,j)-f(n-1,i,j-1)f(n-1,i,j+1)$$
  • The sum over matchings of generalized Aztec diamond graphs $G(n_0, i_0, j_0)$ is called $\sum m(M)$. These graphs are embeeded in an infinite grid $\mathcal{G}$.
  • For now, every matching is counted with unit weight: $m(M)=1$.
  • $n_0+i_0+j_0 \equiv 0 \mod 2$

What is the sequence of shapes corresponding to Speyer's "crosses+wrenches" construction for the square-octagon lattice? Section 3.7 some relevant info.

The faces of his lattices are indexed by pairs of integers $(i,j) \in \mathbb{Z}^2$. He defines a "level" ( I really want to avoid using his word "height", which has another meaning in terms of dominos.) $$ h(i,j) = \left\{ \begin{array}{rc} 0 & \text{if }(i,j) \equiv (0,0) \mod 2\mathbb{Z}\times 2 \mathbb{Z} \\\\ 0 & \text{if }(i,j) \equiv (1,1) \mod 2\mathbb{Z}\times 2 \mathbb{Z} \\\\ 1 & \text{if }(i,j) \equiv (0,1) \mod 2\mathbb{Z}\times 2 \mathbb{Z} \\\\ -1 & \text{if }(i,j) \equiv (1,0) \mod 2\mathbb{Z}\times 2 \mathbb{Z} \end{array} \right.$$ The Octahedron recurrence has initial conditions $f(h(i,j),i,j)=1$ and specializes here to powers of 5: \begin{array}{rlc} f(2n,i,j) & = 5^{n^2} & \\\\ f(2n+1,i,j) & = 5^{n^2+n} & \text{if } i \equiv n \mod 2\\\\ f(2n+1,i,j) & = 2 \cdot 5^{n^2+n} & \text{if } j \equiv n \mod 2 \end{array} I'm not even sure this list of possibilities is exhaustive. For $(2n+1,i,j)$ only one of $i,j$ can be odd.

The shapes $G(n_0, i_0, j_0)\subset \mathcal{G}$ are planar graphs with "open" and "closed" faces. He defines the "lattice", "edges", and "faces": \begin{eqnarray} \mathcal{L} &=& \{ (n,i,j) \in \mathbb{Z}^2 : n = i + j \mod 2\} \\\\ \mathcal{E} &=& \{ (i,j) \in \mathbb{Z}^2: i + j \equiv 1 \mod 2\} \times \{ a,b,c,d\} \\\\ \mathcal{F} &=& \mathbb{Z}^2 \end{eqnarray} The faces are indexed by pairs of integers. The edges are labelled a,b,c,d.

In section 2.1 Speyer defined some cones in $\mathbb{Z}^3$: \begin{eqnarray} p_{(n_0,i_0,j_0)} &=& n_0 - |i - i_0| - |j - j_0| \\\\ C_{(n_0,i_0,j_0)} &=& \{ (n,i,j) \in \mathcal{L}: n \leq n_0 - |i - i_0| - |j - j_0| \} \\\\ \mathring{C}_{(n_0,i_0,j_0)} &=& \{ (n,i,j) \in \mathcal{L}: n < n_0 - |i - i_0| - |j - j_0| \} \\\\ \partial C_{(n_0,i_0,j_0)} &=& \{ (n,i,j) \in \mathcal{L}: n = n_0 - |i - i_0| - |j - j_0| \} \\\\ \mathcal{I} &=& \{ (i,j, n) \in \mathcal{L}: n = h(i,j) \} \\\\ \mathcal{U} &=& \{ (i,j, n) \in \mathcal{L}: n > h(i,j) \} \end{eqnarray}

I have been unable to sort out definition of $G_{n_0,i_0,j_0}$ in section 3.3

It would be really amazing if one could show how the dominos actually "shuffle".

share|cite|improve this question
I strongly suggest substituting "his notation is impossible" with something like "I don't understand his notation". – Angelo Oct 20 '12 at 17:02
Or even personalize, like "It is impossible for me to follow". And today is not my "Pick on John Mangual Day" . Gerhard "That Happens Sometime Next Year" Paseman, 2012.10.20 – Gerhard Paseman Oct 20 '12 at 18:07
Could you give a little bit more detail about what exactly you're asking? Since you're referring to one specific paper, there's no reason not to give precise references to particular numbered results or even page numbers. – j.c. Oct 21 '12 at 11:37
The only issue here is to find the graphs that Ciucu and Speyer construct. I would appreciate anyone's help here. – john mangual Oct 21 '12 at 15:45
I assume that they turn out to be something quite similar to the "fortress graphs" described for instance in (see the picture on page 13 and take the dual graph). These graphs are (under my way of thinking) the analogue of the Aztec diamond for the square-octagon graph. But I haven't read Speyer's paper in a while, so it could be that his construction goes down a different road and ends up somewhere else. – James Propp May 30 '14 at 16:17

The faces are indexed by $\mathbb{Z}^2$, but $ \mathring{C}_{(n_0,i_0,j_0)} \cap \mathcal{I} \in \mathbb{Z}^3$. The closed faces of $G = G_{(n_0,i_0,j_0)}$ centered at $(n_0,i_0,j_0)$ satisfy an inequality:

$$ \mathring{C}_{(n_0,i_0,j_0)} \cap \mathcal{I} = \{ (i,j,n): n = h(i,j) < n_0 - |i - i_0| - |j - j_0| \}$$

How do we get a planar graph? Speyer defines a projection map that drops the last coordinate:

$$\alpha(\mathring{C}_{(n_0,i_0,j_0)} \cap \mathcal{I}) = \{ (i,j): h(i,j) + |i - i_0| + |j - j_0|< n_0 \}$$

This number $h(i,j) + |i - i_0| + |j - j_0|$ seems to be important for building the graph.

One simple ``height function" is an alternating pattern of 0's and 1's. We then overlay taxicab distances from various points to get the height function. The Aztec Diamond patterns emerge

010101      3        444
101010     333      44244
010101    33133    4422244
101010   3311133  442202244
010101    33133    4422244
101010     333      44244
            3        444

Let's try this procedure for square octagon lattice.

We get a clear general sense of the shape. The Mathematica code is:

h[x_, y_] := Switch[{Mod[x, 2], Mod[y, 2]}, 
             {0, 0}, 0, {1, 1}, 0, {1, 0}, 1, {0, 1}, -1]
cut[x_, y_] = If[ x < y, x, "."]
b = Table[
             cut[Abs[k] + Abs[l] + h[k + 1, l], 6],
             {k, -6, 6}, {l, -6, 6}

It seems to be possible to take off the corners and still be an acceptable "diamond".

The analogue of "domino" shuffling in these case would be an "inductive" way of moving from one Aztec Diamond to the next. Not sure how to do this at the moment. There seems to be more than one way

alt text

share|cite|improve this answer
The image is now no longer available. – Joel Reyes Noche Jul 30 '14 at 4:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.