# Double-dimers, the Ising model and the hexahedron recurrence.

1 Introduction

We study the hexahedron recurrence and its specialization to the Kashaev recurrence. In this introductory section we review known facts about the related cube and octahedron recurrences and state the main definitions and results for the hexahedron recurrence.

A function f: [Z.sup.3] [right arrow] C is said to satisfy the octahedron recurrence (or Hirota bilinear difference equation) if

[f.sub.(1)][f.sub.(23)] = [f.sub.(2)][f.sub.(13)] + [f.sub.(3)][f.sub.(12)]. (1)

Here, [f.sub.(S)] represents f evaluated at the translate of [upsilon] by the basis vectors in S, e.g., [f.sub.(12)]([upsilon]) = f ([upsilon] + [e.sub.1] + [e.sub.2]). This is a specialization to [Z.sup.3] of a transformation on that replaces a vertex [upsilon] of a locally finite graph by a vertex w with slightly different local connections and replaces the value f ([upsilon]) by f (w) := [f ([[upsilon].sub.1])f ([[upsilon].sub.2]) + f([[upsilon].sub.3]) f([[upsilon].sub.4])]/f ([upsilon]). Such a move is an example of a cluster algebra mutation (Fomin and Zelevinsky 2002b). The Laurent phenomenon for cluster algebras implies that the new values of f produced by iterating such moves, which are a fortiori rational functions of the original values, are in fact Laurent polynomials in those values (Fomin and Zelevinsky 2002a). The octahedron recurrence goes back to Dodgson (1866) who observed that it was satisfied by subdeterminants and used it as a means of recursively computing determinants.

The function g: [Z.sup.3] [right arrow] C is said to satisfy the cube recurrence (or Miwa equation) if

[g.sub.(123)]g = [g.sub.(1)][g.sub.(23)] + [g.sub.(2)][g.sub.(13)] + [g.sub.(3)][g.sub.(12)]. (2)

This recurrence also has its roots in the 19th century. Consider a resistor network containing somewhere in it a node, v, of degree 3. It was observed by Kennelly (1899) that replacing the three resistors incident to v by three resistors making pairwise connections between the neighbors of v leaves the effective resistance of the network unchanged, provided that the new resistances are related to the old resistance via (using a different parametrization) the cube recurrence.

The main object of study in this paper is the hexahedron recurrence. The quantities related by the hexahedron recurrence are variables indexed by the vertices and faces of the cubic lattice [Z.sup.3]. Let [Z.sup.3.sub.1/2] denote the even vertices of 1/2 [Z.sup.3], that is, those whose coordinates sum to an integer. Each non-integer point of [Z.sup.3.sub.1/2] is the center of a square face of the cubic lattice, perpendicular to one of the three coordinate axes.

Let

h, [h.sup.(x)], [h.sup.(y)], [h.sup.(z)]: [Z.sup.3] [right arrow] C

be four functions on the three-dimensional lattice. We think of h([upsilon]) as sitting on the vertex v. Similarly, [h.sup.(x)] ([upsilon]) sits on the face center perpendicular to the x-axis having vertices [upsilon], [upsilon] + [e.sub.2], [upsilon] + [e.sub.3] and [upsilon] + [e.sub.2] + [e.sub.3]; the values of [h.sup.(y)]([upsilon]) and [h.sup.(z)]([upsilon]) are similarly situated at face centers of the other two types. We may identify these four functions with a single function f on [Z.sup.3.sub.1/2], where for integers [upsilon],

f ([upsilon]) = h([upsilon]), f ([upsilon] + (0,1/2,1/2)) = [h.sup.(x)]([upsilon]), f ([upsilon] + (1/2,0,1/2)) = [h.sup.(y)]([upsilon]) and f ([upsilon] + (1/2,1/2,0)) = [h.sup.(z)]([upsilon]).

Definition 1 (hexahedron recurrence) We say that four functions h, [h.sup.(x)], [h.sup.(y)] and [h.sup.(z)] satisfy the hexahedron recurrence if the following equations are satisfied for all [upsilon] [member of] [Z.sup.3].

[h.sup.(x).sub.(1)][h.sup.(x)]h = [h.sup.(y)][h.sup.(y)][h.sup.(z)] + [h.sub.(1)][h.sub.(2)][h.sub.(3)] + h[h.sub.(1)][h.sub.(23)] (3)

[h.sup.(y).sub.(2)][h.sup.(y)]h = [h.sup.(x)][h.sup.(y)][h.sup.(z)] + [h.sub.(1)][h.sub.(2)][h.sub.(3)] + h[h.sub.(2)][h.sub.(13))] (4)

[h.sup.(z).sub.(3)][h.sup.(z)]h = [h.sup.(x)][h.sup.(y)][h.sup.(z)] + [h.sub.(1)][h.sub.(2)][h.sub.(3)] + h[h.sub.(3)][h.sub.(12)] (5)

Double-dimers and the hexahedron recurrence

[h.sub.(123)][h.sup.2][h.sup.(x)][h.sup.(y)][h.sup.(z)] = [([h.sup.(x)][h.sup.(y)][h.sup.(z)]).sup.2] (6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

Here again [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and so on.

Statistical mechanical interpretations

The octahedron recurrence on [Z.sup.3] expresses [f.sub.[upsilon]] as a Laurent polynomial in the values [f.sub.w] as w ranges over variables in a region lying underneath [upsilon] in an initial plane. This Laurent polynomial is a generating function for a statistical mechanical ensemble: its monomials are in bijection with perfect matchings of the Aztec diamond graph, associated with the region in the initial graph lying underneath [upsilon] (see, e.g., Speyer 2007). Setting the initial indeterminates all equal to one allows us to count perfect matchings; in general the indeterminates represent multiplicative weights, which we may change in certain natural ways to study further properties of the ensemble of perfect matchings.

The cube recurrence (2) also has a combinatorial interpretation. Its monomials are in bijection with cube groves. These were first defined and studied by Carroll and Speyer (2004). In a cube grove, each edge of a large triangular box in the planar triangular lattice is either present or absent. The allowed configurations are those in which there are no cycles and no islands (thus they are essential spanning forests), and the connectivity of boundary points has a prescribed form. Both Aztec diamond matchings and cube groves have limiting shapes. Specifically, as the size of the box goes to infinity, there is a boundary, which is an algebraic curve, outside of which there is no entropy and inside of which there is positive entropy per site. The hexahedron recurrence has a statistical mechanical interpretation as well. In Section 2 we define the double-dimer model on a finite bipartite graph; in Section 4 we prove the following theorem.

Theorem The monomials of the Laurent polynomial [h.sub.nnn] are in bijection with taut double-dimer coverings of the graph [GAMMA]([U.sub.-3n]).

The remainder of the paper is spent investigating the properties of the double- dimer ensemble. In Section 5 we analyze the limiting shape under several natural, periodic specifications of the initial varibles. In Section 6 we find a specialization of the initial variables under which urban renewal becomes the Ising Y-[DELTA] transformation, which is a transformation of the Ising model changing the interaction strengths in a different way from how they change under the resistor network Y-[DELTA] transformation, but changing the graph in exactly the same way.

2 Dimer model

Definitions

Let [GAMMA] be a finite bipartite graph with positive edge weights v: E [right arrow] [R.sub.+]. A dimer cover or perfect matching is a collection of edges with the property that every vertex is an endpoint of exactly one edge. The "dimers" of a dimer cover are the chosen edges (terminology suggesting a collection of bi-atomic molecules packed into the graph). We let [[OMEGA].sub.d]([GAMMA]) be the set of dimer covers and we define the probability measure [[mu].sub.d] on [[OMEGA].sub.d] giving a dimer cover m [member of] [[OMEGA].sub.d] a probability proportional to the product of its edge weights. A double-dimer configuration is a union of two dimer covers: it is a covering of the graph with loops and doubled edges. The double dimer measure [[mu].sub.dd] is the probability measure defined by taking the union of two [[mu].sub.d]-independent dimer covers.

It is convenient to parametrize the measure [[mu].sub.d] by parameters other than the edge weight function v. Given a function A on the faces of a planar bipartite graph, define

[v.sub.A](e) = 1/A(f) A(g), (8)

where f and g are the two faces containing e.

Urban renewal

Certain local rearrangements of [GAMMA] preserve the dimer measure [[mu].sub.d], see Ciucu (1998). Some are obvious. For example, given a vertex [upsilon] of degree 2 (with equal edge weights) one can contract its two edges, erasing [upsilon] and merging its two neighbors into one vertex. Another local rearrangement is called urban renewal. It involves taking a quadrilateral face, call it 0, and adding "legs". This is shown in Figure 1, ignoring for the moment the specific values [a.sub.0], ..., [a.sub.4] shown for the pre-weights A(0), ..., A(4). Let us designate the faces around face 0 by the numbers 1, 3, 2 and 4. Each of these faces gains two new edges. In the new graph [GAMMA]', there are faces 1', 2', 3' and 4' each with two more edges than the corresponding face 1, 2, 3,4. There is a face 0' which is also square. Each other face f of [GAMMA] corresponds to a face f' of [GAMMA]' with the same number of edges as f. There are four new neighboring relations among faces: 1', 2', 3' and 4' are neighbors in cyclic order, in addition to any neighboring relations that may have held before. The point of urban renewal is to give a corresponding adjustment of the weights that preserves [[mu].sub.d]. This is most easily done in terms of the A variables.

[FIGURE 1 OMITTED]

Proposition 2 (urban renewal) Suppose 0 is a quadrilateral face of [GAMMA]. Let [GAMMA]' be constructed from r as above. Define the new pre-weight function A: F' [right arrow] C by A(f') = A(f) if f [not equal to] 0 and

A(0') = A(1)A(2) + A(3)A(4)/A(0).

Let [mu]' denote the dimer measure on [GAMMA]' with face weights [X.sup.A'] and [mu] the dimer measure on [GAMMA] with face weights [X.sup.A]. Then [mu] and [mu]' may be coupled so that the sample pair (m, m') agrees on every edge other than the four edges bounding face 0 in [GAMMA] and the eight edges touching face 0' in [GAMMA]'. []

The transformation of ([GAMMA], A) to ([GAMMA]', A') under urban renewal is, in the language of cluster algebras, a mutation operation. It follows (Fomin and Zelevinsky 2002a) that that the final variables after any number of urban renewals are Laurent polynomials in the original variables {A(f): f [member of] [GAMMA]}.

Superurban renewal transformation for the dimer model

Figure 2 defines superurban renewal as a sequence of six urban renewals on a planar face-weighted bipartite graph at a hexagonal face for which with at least one alternating set of neighbors is quadrilateral.

[FIGURE 2 OMITTED]

The end result of superurban renewal is the transformation of face-weighted graphs shown in Figure 3.

[FIGURE 3 OMITTED]

Computing the result of the six operations yields the following equations for the four new quantities [a.sup.*.sub.0], [a.sup.*.sub.1], [a.sup.*.sub.1] and [a.sup.*.sub.3] in Figure 3 in terms of the old quantities [a.sub.0] - [a.sub.9].

[a.sup.*.sub.1] = [a.sub.1][a.sub.2][a.sub.3] + [a.sub.4][a.sub.5][a.sub.6] + [a.sub.0][a.sub.4][a.sub.7]/[a.sub.0][a.sub.1] (9)

[a.sup.*.sub.2] = [a.sub.1][a.sub.2][a.sub.3] + [a.sub.4][a.sub.5][a.sub.6] + [a.sub.0][a.sub.5][a.sub.8]/[a.sub.0][a.sub.2] (10)

[a.sup.*.sub.3] = [a.sub.1][a.sub.2][a.sub.3] + [a.sub.4][a.sub.5][a.sub.6] + [a.sub.0][a.sub.6][a.sub.9]/[a.sub.0][a.sub.3] (11)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

Because superurban renewal is built from urban renewal, the Laurent property for urban renewal stemming from its cluster algebra representation immediately yields

Proposition 3 (Laurent property for superurban renewal) Under iterated superurban renewal, all new variables are Laurent polynomials in the original variables. []

Just as urban renewal is the basis for the octahedron recurrence, we will see that superurban renewal is the basis for the hexahedron recurrence (see Section 3). In section 6 we show how superurban renewal specializes to the Y-Delta transformation for the Ising model.

3 Stepped surfaces and the operation of adding a cube

A stepped solid in [R.sup.3] is a union U of lattice cubes that is downwardly closed (closed under moves in the -x, -y and -z directions). A stepped surface is the topological boundary of a stepped solid. Every stepped surface is the union of lattice squares and every lattice square has vertex set of the form {[upsilon], [upsilon] + [e.sub.i], [upsilon] + [e.sub.j], [upsilon] + [e.sub.i] + [e.sub.j]} for some [upsilon] [member of] [Z.sup.3] and some integers 1 [less than or equal to] i < j [less than or equal to] 3. For each stepped surface [partial derivative]U, the associated graph [GAMMA](U) is obtained by starting with the planar dual graph and replacing each vertex by a small quadrilateral. Figure 4 shows the 4-6-12 graph, which is the graph [GAMMA](U) when U = [Z.sub.2] is the union of all cubes lying entirely within the region {(x, y, z): x + y + z [less than or equal to] 2}.

[FIGURE 4 OMITTED]

Proposition 4 (superurban renewal is adding a cube) Let U be a downwardly closed stepped solid with stepped surface [partial derivative]U and associated graph [GAMMA](U). Suppose that (i, j, k) is a point of [partial derivative]U which is a local minimum with respect to the height function i + j + k. Let [U.sup.+ijk] be the union of U with the cube [i, i + 1] x [j, j + 1] x [k, k +1].

1. The face in [GAMMA](U) corresponding to (i, j, k) is a hexagon with alternating neighbors quadrilateral.

2. The graph [GAMMA]([U.sup.+ijk]) is obtained from the graph [GAMMA](U) by superurban renewal at this hexagon.

3. The variables associated with each face of [GAMMA](U) transform under superurban renewal (9)-(12) according to the hexahedron recurrence (3)-(7), provided we interpret h(i, j, k) = A(i, j, k), [h.sup.(x)](i, j, k) = A(i, j + 1/2, k +1/2) and so forth.

We now know that adding a cube to a downwardly closed stepped solid corresponds to superurban renewal on the associated graph, which corresponds to the use of the hexahedron recurrence to write the top variable in terms of lower variables.

Let [U.sub.0] be the union of cubes in the negative orthant. The associated graph [GAMMA]([U.sub.0]) is called the cubic corner graph and is shown on the left of Figure 5. Let L be the lattice of all downwardly closed subsets of [U.sub.0] containing all but finitely many cubes of [U.sub.0]. For each U [member of] L, one may add a finite sequence of cubes resulting in [U.sub.0]. Therefore, a finite sequence of superurban renewals represents A(0,0,0) in terms of the variables labeling faces and vertices of the stepped surface [partial derivative]U that are in the union of the removed lattice cubes. Denote this set of variables by I = I(U).

Proposition 5 (i) The rational function F representing A(0, 0, 0) in terms of the variables in I is a Laurent polynomial. (ii) If U' [subset or equal to] U in L and the representation of each variable w [member of] I(U) in terms of variables in I(U') is substituted into F, the resulting Laurent polynomial is the representation of A(0, 0, 0) in terms of variables in I(U').

[FIGURE 5 OMITTED]

Proof: By Proposition 4, the expression F is obtained by a sequence of superurban renewals. By definition, each of these is a sequence of six urban renewals, hence part (i) follows from the Laurent property for urban renewal. Part (ii) is a consequence of the lack of relations among the variables in any stepped surface.

Two classes of examples of stepped surfaces play a role in our combinatorial interpretations of these formulae. The first are the parallel surfaces [Z.sub.-n] defined to be the set of all lattice cubes lying in the halfspace x + y + z [less than or equal to] -n. The associated graph [GAMMA]([partial derivative][Z.sub.-n]) is isomorphic to the 4-6-12 graph of Figure 4. Its labels are precisely I([Z.sub.-n]) of [Z.sup.3] at levels -n -2, -n - 1 and -n together with the half integer points at level -n - 1. The second are the surfaces [U.sub.-n] defined to be those cubes of [U.sub.0] lying entirely within the halfspace {(x, y, z): x + y + z [less than or equal to] -n}. This solid and its associated graph are illustrated for n = -1 (only the top cube removed) on the right of Figure 5.

The graphs [U.sub.-n] differ from [U.sub.0] by finitely many cubes so they are better for recurrences, while the graphs [Z.sub.-n] are translation invariant so they are better for exhibiting translation invariant formulae. The hexahedron recurrence imposes no relations on I(-n), hence from the point of view of determining A(0,0,0) as a function of the variables in I(-n), we may use [U.sub.-n] instead, thus guaranteeing a finite recursion.

We define a double-dimer configuration [m.sub.0] on the cubic corner graph r([U.sub.0]) as in Figure 6. This configuration [m.sub.0] plays the role of our initial configuration. This configuration has the following property. If we erase a finite piece of [m.sub.0], there is a unique way to complete it to a double-dimer configuration which has the same boundary connections, that is, connections between far-away points. For U [member of] L, we say that a double-dimer configuration on [GAMMA](U) is taut if it has the same boundary connections as [m.sub.0], that is, it is identical to [m.sub.0] far from the origin and there is a bijection between its bi-infinite paths and those of [m.sub.0] which is the identity near [infinity]. There are a finite number of taut configurations. See Figure 6 for one such on [GAMMA]([U.sub.-1]).

4 Main formula

Given a taut dimer configuration m, let c(m) denote the number of loops in m and define c(m; i, j, k) := L(i, j, k) - 2 - d(m; i, j, k) where L(i, j, k) is the number of edges in the face (i, j, k) and d(m; i, j, k) is the number of dimers lying along the face (i, j, k) in the matching m. In the configuration [m.sub.0], all quadrilateral faces have 2 dimers and all octagonal faces have 6 dimers, so the only face (i, j, k) with c([m.sub.0]; i, j, k) [not equal to] 0 is the hexagonal face which has 3 dimers and c([m.sub.0]; 0,0,0) = 6 - 2 - 3 = 1. Any taut configuration differs from [m.sub.0] in finitely many places, hence has finitely many variables appearing in it.

[FIGURE 6 OMITTED]

Theorem 6 Fix any U [member of] L and let I(U) be the labels of [GAMMA](U). Use the notation m [??] U to signify that m is a taut double-dimer configuration on [GAMMA] (U). Then the representation of A(0,0,0) as a Laurent polynomial in the variables in I(U) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (13)

Specializing to [U.sub.-n] and A(i, j, k) = 1 for all i, j, k with -n - 2 [less than or equal to] i + j + k [less than or equal to] -n gives the formula

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For example, the middle configuration of Figure 6 has monomial [a.sup.2.sub.4][a.sub.5][a.sub.6][a.sub.7]/[a.sub.0][a.sub.1][a.sub.2][a.sub.3].

Proof: We induct on U. It is true for U = [U.sub.2]: there is one configuration, [m.sub.0], with c([m.sub.0]; i, j, k) = 1 if i = j = k = 0 and zero otherwise. For the induction, we need to see that the conclusion remains true if we remove a maximal cube, that is, when we execute a superurban renewal. Checking this for each type of boundary connection is straightforward. In one instance, the ratio of monomials on the right side and left side of the equation is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The other cases are similar.

5 Limit shapes

Isotropic solutions

In this section we specialize values of the initial variables in several natural ways and study the behavior of the resulting ensembles. Let I = I(2) denote the integer vertices (i, j, k) with i + j + k = 0, 1, 2 together with the half integer vertices with i + j + k = 1. Say that the function f is isotropic if it depends only on i + j + k and whether (i, j, k) is integral. If f is isotropic on I then the hexahedron recurrence extends f to an isotropic function on all of [Z.sup.3.sub.1/2]. Letting An denote the common value on integral points with i + j + k = n and [B.sub.n] be the value at nonintegral points with i + j + k = n + 1, it is easy to find isotropic solutions to the recurrence. The simplest is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (14)

Another interesting solution is obtained by setting the initial variables [A.sub.0], [A.sub.1], [A.sub.2], [B.sub.0] all equal to 1. This yields [A.sub.3] = 14, [B.sub.1] = 3 and [B.sub.2] = 14 and leads to the following proposition.

Proposition 7 The number of taut double-dimer configurations of r([U.sub.-n]), weighted by [2.sup.c(m)], is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Recurrence for the derivative

Isotropic initial conditions allow simplification of the formal derivative of the four hexahdron recurrence equations with respect to a parameter t. Let [g.sub.([upsilon])] denote the formal derivative of log [f.sub.([upsilon])] with respect to a formal parameter t. Taking the logarithmic derivative of the four recurrence relations and plugging in the initial conditions (14) gives the linear system

[g.sub.(123)] = -g + [1/3]([g.sub.(1)] + [g.sub.(2)] + [g.sub.(3)] + [g.sub.(23)] + [g.sub.(13)] + [g.sub.(12)])

and similar equations for [g.sup.(x).sub.(1)], [g.sup.(y).sub.(2)] and [g.sup.(z).sub.(3)]. The first of these equations gives a self-contained recurrence for the logarithmic derivatives at the integer points. In other words, letting F(x, y, z) = [summation]2 [g.sub.i,j,k] [x.sup.i][y.sup.j][z.sup.k], we see that the solution to the recurrence above with boundary conditions g(0,0,0) = 1, g(i, j, k) = 0 for other points (i, j, k) with i + j + k [less than or equal to] 0 and satisfying the recurrence everywhere except at (-1 -1 -1), we see that

F (x, y, z) = G(x, y, z)/H (x, y, z) = 1/[1 + xyz - [1/3] (x + y + z + xy + xz + yz)].

This is the same as the recurrence as is satisfied by the cube grove placement probabilities (Petersen and Speyer 2005). The boundary of the dual cone is known as the "arctic circle", which is the inscribed circle in the triangular region {x + y + z = n, x, y, z [greater than or equal to] 0}. Outside of this, the placement probabilities decay exponentially while inside the arctic circle they do not. Inside, the limit function is homogeneous of degree -1 and is asymptotically equal to the inverse of the distance to the arctic circle in the plane normal to the diagonal direction (Baryshnikov and Pemantle 2011). We can conclude from this that with high probability, a random configuration from [[GAMMA].sub.n] is equal to [m.sub.0] outside a neighborhood of size o(n) of the arctic circle and that there is positive local entropy everywhere inside the arctic circle.

Different periodic initial conditions lead to different limiting shapes. As a somewhat generic example, let [A.sub.0] = 1, [B.sub.0] = 1, [A.sub.1] = 2, [A.sub.2] = 3. The resulting linear system is more complicated but may be solved and yields a recursion with characteristic polynomial

H = 63 [x.sup.2][y.sup.2][z.sup.2] - 62([x.sup.2]yz + x[y.sup.2]z + xy[z.sup.2]) - ([x.sup.2][y.sup.2] + [x.sup.2][z.sup.2] + [y.sup.2][z.sup.2]) + 62([x.sup.y] + xz + yz) + ([x.sup.2] + [y.sup.2] + [z.sup.2]) - 63.

The generating function F(x, y, z) = [[summation].sub.i,j,k] g(i, j, k) [x.sup.i][y.sup.j][z.sup.k] is a rational function with denominator H. Asymptotics for g(i, j, k) may be computed from the generating functions by the methods of Baryshnikov and Pemantle (2011). We briefly sketch the computation.

Step one is to compute the leading homogeneous part [bar.H] of H at (1,1,1), namely the terms of lowest degree in the Taylor expansion there. In this case [bar.H] is the symmetric function

[bar.H] = 62([x.sup.2]y + x[y.sup.2] + [x.sup.2]z + [y.sup.2]z + x[z.sup.2] + y[z.sup.2]) + 132xyz.

The arctic boundary is the algebraic dual of this cubic curve, which may be computed by setting z = ax + by and setting [partial derivative][bar.H]/[partial derivative]x = [partial derivative][bar.H]/[partial derivative]y = 0, yielding

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The arctic boundary is shown in Figure 7 after the change to barycentric coordinates [alpha] = a/(1 - a - b), [beta] = b/(1 - a - b).

The meaning of this curve is that it represents the regions of subexponential decay of coefficients of the generating function: the triangle represents the set of directions in the positive orthant in [Z.sup.3]; a direction ([alpha], [beta], [gamma]) outside or on the arctic curve means that the coefficient [G.sub.[n[alpha]],[n[beta]],[n[gamma]]] decays exponentially fast with n. The coefficients within the "temperate region" decay polynomially. The coefficients in the facet region near the center decay exponentially towards a constant nonzero value.

[FIGURE 7 OMITTED]

The case for general initial conditions [A.sub.0], [A.sub.1], [A.sub.2], [B.sub.0] is not much different. Dividing out by a constant, the leading homogeneous term of the characteristic polynomial is in general given by

[bar.H] = [x.sup.2]y + x[y.sup.2] + [x.sup.2]z + [y.sup.2]z + x[z.sup.2] + y[z.sup.2] + [lambda]xyz

with [lambda] [member of] (2, 3]. This is irreducible for [lambda] in the open interval (2,3). The picture varies continuously with [lambda]. When [lambda] = 3, which corresponds to the initial conditions (14), the outer curve is the inscribed circle and the facet has shrunk to a point; in fact [bar.H] factors in this case and is the same as the

characteristic polynomial for cube groves. As [lambda] approaches 2, the outer curve approaches an inscribed triangle and the facet expands to fill up the entire temperate region. The limiting characteristic polynomial at [lambda] = 2 is the product (x + y)(x + z)(y + z) of linear factors but is not attained by any initial conditions.

6 Ising model, the Ising-Y-Delta move, and Kashev's equation

In this section we will show how the Ising-Y-Delta move for the Ising model is a special case of the hexahedron recurrence. We begin by recalling the definition of the Ising model. Let G = (V, E) be a finite graph with c: E [right arrow] [R.sub.+] a positive weight function on edges. The Ising model is a probability measure [mu] on the configuration space Q = [{[+ or -]1}.sup.V]. A configuration of spins [sigma] [member of] [OMEGA] has probability

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (15)

where the product is over all edges in E and the partition function Z is the sum of the unweighted probabilities [PI]c[(e).sup.(1+[sigma]([upsilon])[sigma]([upsilon]'))/2] over all configurations [sigma]. In other words, the probability of a configuration is proportional to the product of the edge weights of those edges where the spins are equal. The Ising model originated as a thermodynamical ensemble with energy function H([sigma]) = -[[summation].sub.e][sigma]([upsilon])[sigma]([upsilon]') J(e): take J(e) = (T/2) log c(e) where T is Boltzmann's constant times the temperature.

The Ising-Y-Delta move on the weighted graph G = (V, E, c) transforms the graph the same way as does the Y-Delta move for electrical networks but transforms the edge weights differently. The transformation is depicted in Figure 8. Its key property is preservation of the associated measure.

A = [square root of ((abc + 1)(a + bc)/(b + ac)(c + ab))] (16)

B = [square root of ((abc + 1)(b + ac)/(a + bc)(c + ab))] (17)

C = [square root of ((abc + 1)(c + ab)/(a + bc)(b + ac))]. (18)

[FIGURE 8 OMITTED]

When placed on a lattice, these relations have an interpretation as a recurrence for stepped surfaces. Previously we associated a graph [GAMMA](U) with each stepped surface [partial derivative]U; now we associate a planar graph T(U). The vertices of T(U) are taken to be the even vertices of [partial derivative]U and the edges of Y(U) are the digaonals of the faces of [partial derivative]U whose endpoints are even. If f: [Z.sup.d] [right arrow] [R.sup.+] is a positive function, define edge weight w(e) on an edge e of T(U) to be the positive solution to [(w - 1/w).sup.2]/4 = b where b = f ([upsilon]) f ([upsilon]')/(f([upsilon]) f(u')), where e = {[upsilon], [upsilon]'} and where u and u' are the other two vertices of the face of [partial derivative]U on which e lies. The following lemma is known as Kashaev's difference equation.

Lemma 8 (Kashaev (1996)) Let U [subset or equal to] U' be stepped solids differing by a single cube.

1. The graph Y(U') differs from Y(U) by a Y-Delta move: Y to Delta if the bottom vertex of the added cube was even and Delta to Y otherwise.

2. If e is a weight function on the edges of Y(U), extended by the Ising-Y-Delta relations to the edges of Y(U'), and if f is a function on the vertices of [Z.sup.d] inducing e on the edges of Y(U) and Y(U') then at the eight vertices of the added cube, f satisfies the relations

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (19)

Kashaev's equation for f: [Z.sup.3] [right arrow] C may be embedded in the hexahedron recurrence by extending f to [Z.sup.3.sub.1/2] as follows.

Proposition 9 Suppose f: [Z.sup.3.sub.1/2] [right arrow] C satisfies the following relation for integer (i, j, k):

f [(i + 1/2, j + 1/2, k).sup.2] = f (i, j, k)f (i + 1, j + 1, k) + f (i, j + 1, k)f (i + 1, j, k)

f [(i + 1/2, j, k + 1/2).sup.2] = f (i, j, k)f (i + 1, j, k + 1) + f (i, j, k + 1)f (i + 1, j, k)

f [(i, j + 1/2, k + 1/2).sup.2] = f (i, j, k)f (i, j + 1, k + 1) + f (i, j, k + 1)f (i, j + 1, k).

Then f satisfies Kashaev's relation (19) at integer points if and only if f satisfies the hexahedron relations (3)-(7), where as usual we interpret h = f, [h.sup.(x)] = [f.sub.(0,1/2,1/2)], and so forth.

Specializing the hexahedron recurrence creates redundancy, which may be exploited to produce simpler forms of the hexahedron/Kashaev recurrence. The following result may be proved.

Theorem 10 Let X([upsilon]) := [f.sup.(x).sub.([upsilon])], Y([upsilon]) := [f.sup.(y).sub.([upsilon])], and Z([upsilon]) := [f.sup.(z).sub.([upsilon])]. Then [f.sub.i,j,k] may be written as a Laurent polynomial in the initial variables [{[f.sub.i,j,k]}.sub.0[less than or equal to]i+j+k[less than or equal to]2] and [{[X.sub.i,j,k], [Y.sub.i,j,k,], [Z.sub.i,j,k]}.sub.i+j+k=0] with the X, Y, Z variables appearing only with power 0 or 1.

Open question What are the natural combinatorial structures counted by [f.sub.i,j,k]?

References

Y. Baryshnikov and R. Pemantle. Asymptotics of multivariate sequences, part III: quadratic points. Adv. Math., 228:3127-3206, 2011.

G. Carroll and D. Speyer. The cube recurrence. Electronic Journal of Combinatorics, 11: paper 73, 31 pages, 2004.

M. Ciucu. A complementation theorem for perfect matchings of graphs having a cellular completion. J. Comb. Theory, ser. A, 81:34-68, 1998.

C. Dodgson. Condensation of determinants, being a new and brief method for computing their arithmetical values. Proc. Royal Soc. London, 15:150-155, 1866.

S. Fomin and A. Zelevinsky. The Laurent phenomenon. Adv. Appl. Math., 28:119- 144, 2002a.

S. Fomin and A. Zelevinsky. Cluster algebras, I. J. Amer. Math. Soc., 15:497- 529, 2002b.

R. Kashaev. On discrete three-dimensional equations associatied with the local Yang-Baxter equation. Lett. Math. Phys., 33:389-397, 1996.

A. Kennelly. Equivalence of triangles and stars in conducting networks. Elec. World and Engineer, 34: 3413-U4, 1899.

T. Petersen and D. Speyer. An arctic circle theorem for groves. J. Comb. Theory, ser. A, 111:137-164, 2005.

D. Speyer. Perfect matchings and the octahedron recurrence. J. Alg. Comb., 25:309-348, 2007.

Richard Kenyon (1) ([dagger]) and Robin Pemantle (2) ([double dagger])

(1) Department of Mathemtics, Brown University, 151 Thayer Street, Providence, RI02912, USA

(2) Department of Mathematics, University of Pennsylvania, 209 South 33rd Street, Phildelphia, PA 19096, USA

([dagger]) Partially supported by the Natioinal Science Foundation

([double dagger]) Supported by NSF Grant #DMS-1209117

We study the hexahedron recurrence and its specialization to the Kashaev recurrence. In this introductory section we review known facts about the related cube and octahedron recurrences and state the main definitions and results for the hexahedron recurrence.

A function f: [Z.sup.3] [right arrow] C is said to satisfy the octahedron recurrence (or Hirota bilinear difference equation) if

[f.sub.(1)][f.sub.(23)] = [f.sub.(2)][f.sub.(13)] + [f.sub.(3)][f.sub.(12)]. (1)

Here, [f.sub.(S)] represents f evaluated at the translate of [upsilon] by the basis vectors in S, e.g., [f.sub.(12)]([upsilon]) = f ([upsilon] + [e.sub.1] + [e.sub.2]). This is a specialization to [Z.sup.3] of a transformation on that replaces a vertex [upsilon] of a locally finite graph by a vertex w with slightly different local connections and replaces the value f ([upsilon]) by f (w) := [f ([[upsilon].sub.1])f ([[upsilon].sub.2]) + f([[upsilon].sub.3]) f([[upsilon].sub.4])]/f ([upsilon]). Such a move is an example of a cluster algebra mutation (Fomin and Zelevinsky 2002b). The Laurent phenomenon for cluster algebras implies that the new values of f produced by iterating such moves, which are a fortiori rational functions of the original values, are in fact Laurent polynomials in those values (Fomin and Zelevinsky 2002a). The octahedron recurrence goes back to Dodgson (1866) who observed that it was satisfied by subdeterminants and used it as a means of recursively computing determinants.

The function g: [Z.sup.3] [right arrow] C is said to satisfy the cube recurrence (or Miwa equation) if

[g.sub.(123)]g = [g.sub.(1)][g.sub.(23)] + [g.sub.(2)][g.sub.(13)] + [g.sub.(3)][g.sub.(12)]. (2)

This recurrence also has its roots in the 19th century. Consider a resistor network containing somewhere in it a node, v, of degree 3. It was observed by Kennelly (1899) that replacing the three resistors incident to v by three resistors making pairwise connections between the neighbors of v leaves the effective resistance of the network unchanged, provided that the new resistances are related to the old resistance via (using a different parametrization) the cube recurrence.

The main object of study in this paper is the hexahedron recurrence. The quantities related by the hexahedron recurrence are variables indexed by the vertices and faces of the cubic lattice [Z.sup.3]. Let [Z.sup.3.sub.1/2] denote the even vertices of 1/2 [Z.sup.3], that is, those whose coordinates sum to an integer. Each non-integer point of [Z.sup.3.sub.1/2] is the center of a square face of the cubic lattice, perpendicular to one of the three coordinate axes.

Let

h, [h.sup.(x)], [h.sup.(y)], [h.sup.(z)]: [Z.sup.3] [right arrow] C

be four functions on the three-dimensional lattice. We think of h([upsilon]) as sitting on the vertex v. Similarly, [h.sup.(x)] ([upsilon]) sits on the face center perpendicular to the x-axis having vertices [upsilon], [upsilon] + [e.sub.2], [upsilon] + [e.sub.3] and [upsilon] + [e.sub.2] + [e.sub.3]; the values of [h.sup.(y)]([upsilon]) and [h.sup.(z)]([upsilon]) are similarly situated at face centers of the other two types. We may identify these four functions with a single function f on [Z.sup.3.sub.1/2], where for integers [upsilon],

f ([upsilon]) = h([upsilon]), f ([upsilon] + (0,1/2,1/2)) = [h.sup.(x)]([upsilon]), f ([upsilon] + (1/2,0,1/2)) = [h.sup.(y)]([upsilon]) and f ([upsilon] + (1/2,1/2,0)) = [h.sup.(z)]([upsilon]).

Definition 1 (hexahedron recurrence) We say that four functions h, [h.sup.(x)], [h.sup.(y)] and [h.sup.(z)] satisfy the hexahedron recurrence if the following equations are satisfied for all [upsilon] [member of] [Z.sup.3].

[h.sup.(x).sub.(1)][h.sup.(x)]h = [h.sup.(y)][h.sup.(y)][h.sup.(z)] + [h.sub.(1)][h.sub.(2)][h.sub.(3)] + h[h.sub.(1)][h.sub.(23)] (3)

[h.sup.(y).sub.(2)][h.sup.(y)]h = [h.sup.(x)][h.sup.(y)][h.sup.(z)] + [h.sub.(1)][h.sub.(2)][h.sub.(3)] + h[h.sub.(2)][h.sub.(13))] (4)

[h.sup.(z).sub.(3)][h.sup.(z)]h = [h.sup.(x)][h.sup.(y)][h.sup.(z)] + [h.sub.(1)][h.sub.(2)][h.sub.(3)] + h[h.sub.(3)][h.sub.(12)] (5)

Double-dimers and the hexahedron recurrence

[h.sub.(123)][h.sup.2][h.sup.(x)][h.sup.(y)][h.sup.(z)] = [([h.sup.(x)][h.sup.(y)][h.sup.(z)]).sup.2] (6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

Here again [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and so on.

Statistical mechanical interpretations

The octahedron recurrence on [Z.sup.3] expresses [f.sub.[upsilon]] as a Laurent polynomial in the values [f.sub.w] as w ranges over variables in a region lying underneath [upsilon] in an initial plane. This Laurent polynomial is a generating function for a statistical mechanical ensemble: its monomials are in bijection with perfect matchings of the Aztec diamond graph, associated with the region in the initial graph lying underneath [upsilon] (see, e.g., Speyer 2007). Setting the initial indeterminates all equal to one allows us to count perfect matchings; in general the indeterminates represent multiplicative weights, which we may change in certain natural ways to study further properties of the ensemble of perfect matchings.

The cube recurrence (2) also has a combinatorial interpretation. Its monomials are in bijection with cube groves. These were first defined and studied by Carroll and Speyer (2004). In a cube grove, each edge of a large triangular box in the planar triangular lattice is either present or absent. The allowed configurations are those in which there are no cycles and no islands (thus they are essential spanning forests), and the connectivity of boundary points has a prescribed form. Both Aztec diamond matchings and cube groves have limiting shapes. Specifically, as the size of the box goes to infinity, there is a boundary, which is an algebraic curve, outside of which there is no entropy and inside of which there is positive entropy per site. The hexahedron recurrence has a statistical mechanical interpretation as well. In Section 2 we define the double-dimer model on a finite bipartite graph; in Section 4 we prove the following theorem.

Theorem The monomials of the Laurent polynomial [h.sub.nnn] are in bijection with taut double-dimer coverings of the graph [GAMMA]([U.sub.-3n]).

The remainder of the paper is spent investigating the properties of the double- dimer ensemble. In Section 5 we analyze the limiting shape under several natural, periodic specifications of the initial varibles. In Section 6 we find a specialization of the initial variables under which urban renewal becomes the Ising Y-[DELTA] transformation, which is a transformation of the Ising model changing the interaction strengths in a different way from how they change under the resistor network Y-[DELTA] transformation, but changing the graph in exactly the same way.

2 Dimer model

Definitions

Let [GAMMA] be a finite bipartite graph with positive edge weights v: E [right arrow] [R.sub.+]. A dimer cover or perfect matching is a collection of edges with the property that every vertex is an endpoint of exactly one edge. The "dimers" of a dimer cover are the chosen edges (terminology suggesting a collection of bi-atomic molecules packed into the graph). We let [[OMEGA].sub.d]([GAMMA]) be the set of dimer covers and we define the probability measure [[mu].sub.d] on [[OMEGA].sub.d] giving a dimer cover m [member of] [[OMEGA].sub.d] a probability proportional to the product of its edge weights. A double-dimer configuration is a union of two dimer covers: it is a covering of the graph with loops and doubled edges. The double dimer measure [[mu].sub.dd] is the probability measure defined by taking the union of two [[mu].sub.d]-independent dimer covers.

It is convenient to parametrize the measure [[mu].sub.d] by parameters other than the edge weight function v. Given a function A on the faces of a planar bipartite graph, define

[v.sub.A](e) = 1/A(f) A(g), (8)

where f and g are the two faces containing e.

Urban renewal

Certain local rearrangements of [GAMMA] preserve the dimer measure [[mu].sub.d], see Ciucu (1998). Some are obvious. For example, given a vertex [upsilon] of degree 2 (with equal edge weights) one can contract its two edges, erasing [upsilon] and merging its two neighbors into one vertex. Another local rearrangement is called urban renewal. It involves taking a quadrilateral face, call it 0, and adding "legs". This is shown in Figure 1, ignoring for the moment the specific values [a.sub.0], ..., [a.sub.4] shown for the pre-weights A(0), ..., A(4). Let us designate the faces around face 0 by the numbers 1, 3, 2 and 4. Each of these faces gains two new edges. In the new graph [GAMMA]', there are faces 1', 2', 3' and 4' each with two more edges than the corresponding face 1, 2, 3,4. There is a face 0' which is also square. Each other face f of [GAMMA] corresponds to a face f' of [GAMMA]' with the same number of edges as f. There are four new neighboring relations among faces: 1', 2', 3' and 4' are neighbors in cyclic order, in addition to any neighboring relations that may have held before. The point of urban renewal is to give a corresponding adjustment of the weights that preserves [[mu].sub.d]. This is most easily done in terms of the A variables.

[FIGURE 1 OMITTED]

Proposition 2 (urban renewal) Suppose 0 is a quadrilateral face of [GAMMA]. Let [GAMMA]' be constructed from r as above. Define the new pre-weight function A: F' [right arrow] C by A(f') = A(f) if f [not equal to] 0 and

A(0') = A(1)A(2) + A(3)A(4)/A(0).

Let [mu]' denote the dimer measure on [GAMMA]' with face weights [X.sup.A'] and [mu] the dimer measure on [GAMMA] with face weights [X.sup.A]. Then [mu] and [mu]' may be coupled so that the sample pair (m, m') agrees on every edge other than the four edges bounding face 0 in [GAMMA] and the eight edges touching face 0' in [GAMMA]'. []

The transformation of ([GAMMA], A) to ([GAMMA]', A') under urban renewal is, in the language of cluster algebras, a mutation operation. It follows (Fomin and Zelevinsky 2002a) that that the final variables after any number of urban renewals are Laurent polynomials in the original variables {A(f): f [member of] [GAMMA]}.

Superurban renewal transformation for the dimer model

Figure 2 defines superurban renewal as a sequence of six urban renewals on a planar face-weighted bipartite graph at a hexagonal face for which with at least one alternating set of neighbors is quadrilateral.

[FIGURE 2 OMITTED]

The end result of superurban renewal is the transformation of face-weighted graphs shown in Figure 3.

[FIGURE 3 OMITTED]

Computing the result of the six operations yields the following equations for the four new quantities [a.sup.*.sub.0], [a.sup.*.sub.1], [a.sup.*.sub.1] and [a.sup.*.sub.3] in Figure 3 in terms of the old quantities [a.sub.0] - [a.sub.9].

[a.sup.*.sub.1] = [a.sub.1][a.sub.2][a.sub.3] + [a.sub.4][a.sub.5][a.sub.6] + [a.sub.0][a.sub.4][a.sub.7]/[a.sub.0][a.sub.1] (9)

[a.sup.*.sub.2] = [a.sub.1][a.sub.2][a.sub.3] + [a.sub.4][a.sub.5][a.sub.6] + [a.sub.0][a.sub.5][a.sub.8]/[a.sub.0][a.sub.2] (10)

[a.sup.*.sub.3] = [a.sub.1][a.sub.2][a.sub.3] + [a.sub.4][a.sub.5][a.sub.6] + [a.sub.0][a.sub.6][a.sub.9]/[a.sub.0][a.sub.3] (11)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

Because superurban renewal is built from urban renewal, the Laurent property for urban renewal stemming from its cluster algebra representation immediately yields

Proposition 3 (Laurent property for superurban renewal) Under iterated superurban renewal, all new variables are Laurent polynomials in the original variables. []

Just as urban renewal is the basis for the octahedron recurrence, we will see that superurban renewal is the basis for the hexahedron recurrence (see Section 3). In section 6 we show how superurban renewal specializes to the Y-Delta transformation for the Ising model.

3 Stepped surfaces and the operation of adding a cube

A stepped solid in [R.sup.3] is a union U of lattice cubes that is downwardly closed (closed under moves in the -x, -y and -z directions). A stepped surface is the topological boundary of a stepped solid. Every stepped surface is the union of lattice squares and every lattice square has vertex set of the form {[upsilon], [upsilon] + [e.sub.i], [upsilon] + [e.sub.j], [upsilon] + [e.sub.i] + [e.sub.j]} for some [upsilon] [member of] [Z.sup.3] and some integers 1 [less than or equal to] i < j [less than or equal to] 3. For each stepped surface [partial derivative]U, the associated graph [GAMMA](U) is obtained by starting with the planar dual graph and replacing each vertex by a small quadrilateral. Figure 4 shows the 4-6-12 graph, which is the graph [GAMMA](U) when U = [Z.sub.2] is the union of all cubes lying entirely within the region {(x, y, z): x + y + z [less than or equal to] 2}.

[FIGURE 4 OMITTED]

Proposition 4 (superurban renewal is adding a cube) Let U be a downwardly closed stepped solid with stepped surface [partial derivative]U and associated graph [GAMMA](U). Suppose that (i, j, k) is a point of [partial derivative]U which is a local minimum with respect to the height function i + j + k. Let [U.sup.+ijk] be the union of U with the cube [i, i + 1] x [j, j + 1] x [k, k +1].

1. The face in [GAMMA](U) corresponding to (i, j, k) is a hexagon with alternating neighbors quadrilateral.

2. The graph [GAMMA]([U.sup.+ijk]) is obtained from the graph [GAMMA](U) by superurban renewal at this hexagon.

3. The variables associated with each face of [GAMMA](U) transform under superurban renewal (9)-(12) according to the hexahedron recurrence (3)-(7), provided we interpret h(i, j, k) = A(i, j, k), [h.sup.(x)](i, j, k) = A(i, j + 1/2, k +1/2) and so forth.

We now know that adding a cube to a downwardly closed stepped solid corresponds to superurban renewal on the associated graph, which corresponds to the use of the hexahedron recurrence to write the top variable in terms of lower variables.

Let [U.sub.0] be the union of cubes in the negative orthant. The associated graph [GAMMA]([U.sub.0]) is called the cubic corner graph and is shown on the left of Figure 5. Let L be the lattice of all downwardly closed subsets of [U.sub.0] containing all but finitely many cubes of [U.sub.0]. For each U [member of] L, one may add a finite sequence of cubes resulting in [U.sub.0]. Therefore, a finite sequence of superurban renewals represents A(0,0,0) in terms of the variables labeling faces and vertices of the stepped surface [partial derivative]U that are in the union of the removed lattice cubes. Denote this set of variables by I = I(U).

Proposition 5 (i) The rational function F representing A(0, 0, 0) in terms of the variables in I is a Laurent polynomial. (ii) If U' [subset or equal to] U in L and the representation of each variable w [member of] I(U) in terms of variables in I(U') is substituted into F, the resulting Laurent polynomial is the representation of A(0, 0, 0) in terms of variables in I(U').

[FIGURE 5 OMITTED]

Proof: By Proposition 4, the expression F is obtained by a sequence of superurban renewals. By definition, each of these is a sequence of six urban renewals, hence part (i) follows from the Laurent property for urban renewal. Part (ii) is a consequence of the lack of relations among the variables in any stepped surface.

Two classes of examples of stepped surfaces play a role in our combinatorial interpretations of these formulae. The first are the parallel surfaces [Z.sub.-n] defined to be the set of all lattice cubes lying in the halfspace x + y + z [less than or equal to] -n. The associated graph [GAMMA]([partial derivative][Z.sub.-n]) is isomorphic to the 4-6-12 graph of Figure 4. Its labels are precisely I([Z.sub.-n]) of [Z.sup.3] at levels -n -2, -n - 1 and -n together with the half integer points at level -n - 1. The second are the surfaces [U.sub.-n] defined to be those cubes of [U.sub.0] lying entirely within the halfspace {(x, y, z): x + y + z [less than or equal to] -n}. This solid and its associated graph are illustrated for n = -1 (only the top cube removed) on the right of Figure 5.

The graphs [U.sub.-n] differ from [U.sub.0] by finitely many cubes so they are better for recurrences, while the graphs [Z.sub.-n] are translation invariant so they are better for exhibiting translation invariant formulae. The hexahedron recurrence imposes no relations on I(-n), hence from the point of view of determining A(0,0,0) as a function of the variables in I(-n), we may use [U.sub.-n] instead, thus guaranteeing a finite recursion.

We define a double-dimer configuration [m.sub.0] on the cubic corner graph r([U.sub.0]) as in Figure 6. This configuration [m.sub.0] plays the role of our initial configuration. This configuration has the following property. If we erase a finite piece of [m.sub.0], there is a unique way to complete it to a double-dimer configuration which has the same boundary connections, that is, connections between far-away points. For U [member of] L, we say that a double-dimer configuration on [GAMMA](U) is taut if it has the same boundary connections as [m.sub.0], that is, it is identical to [m.sub.0] far from the origin and there is a bijection between its bi-infinite paths and those of [m.sub.0] which is the identity near [infinity]. There are a finite number of taut configurations. See Figure 6 for one such on [GAMMA]([U.sub.-1]).

4 Main formula

Given a taut dimer configuration m, let c(m) denote the number of loops in m and define c(m; i, j, k) := L(i, j, k) - 2 - d(m; i, j, k) where L(i, j, k) is the number of edges in the face (i, j, k) and d(m; i, j, k) is the number of dimers lying along the face (i, j, k) in the matching m. In the configuration [m.sub.0], all quadrilateral faces have 2 dimers and all octagonal faces have 6 dimers, so the only face (i, j, k) with c([m.sub.0]; i, j, k) [not equal to] 0 is the hexagonal face which has 3 dimers and c([m.sub.0]; 0,0,0) = 6 - 2 - 3 = 1. Any taut configuration differs from [m.sub.0] in finitely many places, hence has finitely many variables appearing in it.

[FIGURE 6 OMITTED]

Theorem 6 Fix any U [member of] L and let I(U) be the labels of [GAMMA](U). Use the notation m [??] U to signify that m is a taut double-dimer configuration on [GAMMA] (U). Then the representation of A(0,0,0) as a Laurent polynomial in the variables in I(U) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (13)

Specializing to [U.sub.-n] and A(i, j, k) = 1 for all i, j, k with -n - 2 [less than or equal to] i + j + k [less than or equal to] -n gives the formula

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For example, the middle configuration of Figure 6 has monomial [a.sup.2.sub.4][a.sub.5][a.sub.6][a.sub.7]/[a.sub.0][a.sub.1][a.sub.2][a.sub.3].

Proof: We induct on U. It is true for U = [U.sub.2]: there is one configuration, [m.sub.0], with c([m.sub.0]; i, j, k) = 1 if i = j = k = 0 and zero otherwise. For the induction, we need to see that the conclusion remains true if we remove a maximal cube, that is, when we execute a superurban renewal. Checking this for each type of boundary connection is straightforward. In one instance, the ratio of monomials on the right side and left side of the equation is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The other cases are similar.

5 Limit shapes

Isotropic solutions

In this section we specialize values of the initial variables in several natural ways and study the behavior of the resulting ensembles. Let I = I(2) denote the integer vertices (i, j, k) with i + j + k = 0, 1, 2 together with the half integer vertices with i + j + k = 1. Say that the function f is isotropic if it depends only on i + j + k and whether (i, j, k) is integral. If f is isotropic on I then the hexahedron recurrence extends f to an isotropic function on all of [Z.sup.3.sub.1/2]. Letting An denote the common value on integral points with i + j + k = n and [B.sub.n] be the value at nonintegral points with i + j + k = n + 1, it is easy to find isotropic solutions to the recurrence. The simplest is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (14)

Another interesting solution is obtained by setting the initial variables [A.sub.0], [A.sub.1], [A.sub.2], [B.sub.0] all equal to 1. This yields [A.sub.3] = 14, [B.sub.1] = 3 and [B.sub.2] = 14 and leads to the following proposition.

Proposition 7 The number of taut double-dimer configurations of r([U.sub.-n]), weighted by [2.sup.c(m)], is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Recurrence for the derivative

Isotropic initial conditions allow simplification of the formal derivative of the four hexahdron recurrence equations with respect to a parameter t. Let [g.sub.([upsilon])] denote the formal derivative of log [f.sub.([upsilon])] with respect to a formal parameter t. Taking the logarithmic derivative of the four recurrence relations and plugging in the initial conditions (14) gives the linear system

[g.sub.(123)] = -g + [1/3]([g.sub.(1)] + [g.sub.(2)] + [g.sub.(3)] + [g.sub.(23)] + [g.sub.(13)] + [g.sub.(12)])

and similar equations for [g.sup.(x).sub.(1)], [g.sup.(y).sub.(2)] and [g.sup.(z).sub.(3)]. The first of these equations gives a self-contained recurrence for the logarithmic derivatives at the integer points. In other words, letting F(x, y, z) = [summation]2 [g.sub.i,j,k] [x.sup.i][y.sup.j][z.sup.k], we see that the solution to the recurrence above with boundary conditions g(0,0,0) = 1, g(i, j, k) = 0 for other points (i, j, k) with i + j + k [less than or equal to] 0 and satisfying the recurrence everywhere except at (-1 -1 -1), we see that

F (x, y, z) = G(x, y, z)/H (x, y, z) = 1/[1 + xyz - [1/3] (x + y + z + xy + xz + yz)].

This is the same as the recurrence as is satisfied by the cube grove placement probabilities (Petersen and Speyer 2005). The boundary of the dual cone is known as the "arctic circle", which is the inscribed circle in the triangular region {x + y + z = n, x, y, z [greater than or equal to] 0}. Outside of this, the placement probabilities decay exponentially while inside the arctic circle they do not. Inside, the limit function is homogeneous of degree -1 and is asymptotically equal to the inverse of the distance to the arctic circle in the plane normal to the diagonal direction (Baryshnikov and Pemantle 2011). We can conclude from this that with high probability, a random configuration from [[GAMMA].sub.n] is equal to [m.sub.0] outside a neighborhood of size o(n) of the arctic circle and that there is positive local entropy everywhere inside the arctic circle.

Different periodic initial conditions lead to different limiting shapes. As a somewhat generic example, let [A.sub.0] = 1, [B.sub.0] = 1, [A.sub.1] = 2, [A.sub.2] = 3. The resulting linear system is more complicated but may be solved and yields a recursion with characteristic polynomial

H = 63 [x.sup.2][y.sup.2][z.sup.2] - 62([x.sup.2]yz + x[y.sup.2]z + xy[z.sup.2]) - ([x.sup.2][y.sup.2] + [x.sup.2][z.sup.2] + [y.sup.2][z.sup.2]) + 62([x.sup.y] + xz + yz) + ([x.sup.2] + [y.sup.2] + [z.sup.2]) - 63.

The generating function F(x, y, z) = [[summation].sub.i,j,k] g(i, j, k) [x.sup.i][y.sup.j][z.sup.k] is a rational function with denominator H. Asymptotics for g(i, j, k) may be computed from the generating functions by the methods of Baryshnikov and Pemantle (2011). We briefly sketch the computation.

Step one is to compute the leading homogeneous part [bar.H] of H at (1,1,1), namely the terms of lowest degree in the Taylor expansion there. In this case [bar.H] is the symmetric function

[bar.H] = 62([x.sup.2]y + x[y.sup.2] + [x.sup.2]z + [y.sup.2]z + x[z.sup.2] + y[z.sup.2]) + 132xyz.

The arctic boundary is the algebraic dual of this cubic curve, which may be computed by setting z = ax + by and setting [partial derivative][bar.H]/[partial derivative]x = [partial derivative][bar.H]/[partial derivative]y = 0, yielding

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The arctic boundary is shown in Figure 7 after the change to barycentric coordinates [alpha] = a/(1 - a - b), [beta] = b/(1 - a - b).

The meaning of this curve is that it represents the regions of subexponential decay of coefficients of the generating function: the triangle represents the set of directions in the positive orthant in [Z.sup.3]; a direction ([alpha], [beta], [gamma]) outside or on the arctic curve means that the coefficient [G.sub.[n[alpha]],[n[beta]],[n[gamma]]] decays exponentially fast with n. The coefficients within the "temperate region" decay polynomially. The coefficients in the facet region near the center decay exponentially towards a constant nonzero value.

[FIGURE 7 OMITTED]

The case for general initial conditions [A.sub.0], [A.sub.1], [A.sub.2], [B.sub.0] is not much different. Dividing out by a constant, the leading homogeneous term of the characteristic polynomial is in general given by

[bar.H] = [x.sup.2]y + x[y.sup.2] + [x.sup.2]z + [y.sup.2]z + x[z.sup.2] + y[z.sup.2] + [lambda]xyz

with [lambda] [member of] (2, 3]. This is irreducible for [lambda] in the open interval (2,3). The picture varies continuously with [lambda]. When [lambda] = 3, which corresponds to the initial conditions (14), the outer curve is the inscribed circle and the facet has shrunk to a point; in fact [bar.H] factors in this case and is the same as the

characteristic polynomial for cube groves. As [lambda] approaches 2, the outer curve approaches an inscribed triangle and the facet expands to fill up the entire temperate region. The limiting characteristic polynomial at [lambda] = 2 is the product (x + y)(x + z)(y + z) of linear factors but is not attained by any initial conditions.

6 Ising model, the Ising-Y-Delta move, and Kashev's equation

In this section we will show how the Ising-Y-Delta move for the Ising model is a special case of the hexahedron recurrence. We begin by recalling the definition of the Ising model. Let G = (V, E) be a finite graph with c: E [right arrow] [R.sub.+] a positive weight function on edges. The Ising model is a probability measure [mu] on the configuration space Q = [{[+ or -]1}.sup.V]. A configuration of spins [sigma] [member of] [OMEGA] has probability

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (15)

where the product is over all edges in E and the partition function Z is the sum of the unweighted probabilities [PI]c[(e).sup.(1+[sigma]([upsilon])[sigma]([upsilon]'))/2] over all configurations [sigma]. In other words, the probability of a configuration is proportional to the product of the edge weights of those edges where the spins are equal. The Ising model originated as a thermodynamical ensemble with energy function H([sigma]) = -[[summation].sub.e][sigma]([upsilon])[sigma]([upsilon]') J(e): take J(e) = (T/2) log c(e) where T is Boltzmann's constant times the temperature.

The Ising-Y-Delta move on the weighted graph G = (V, E, c) transforms the graph the same way as does the Y-Delta move for electrical networks but transforms the edge weights differently. The transformation is depicted in Figure 8. Its key property is preservation of the associated measure.

A = [square root of ((abc + 1)(a + bc)/(b + ac)(c + ab))] (16)

B = [square root of ((abc + 1)(b + ac)/(a + bc)(c + ab))] (17)

C = [square root of ((abc + 1)(c + ab)/(a + bc)(b + ac))]. (18)

[FIGURE 8 OMITTED]

When placed on a lattice, these relations have an interpretation as a recurrence for stepped surfaces. Previously we associated a graph [GAMMA](U) with each stepped surface [partial derivative]U; now we associate a planar graph T(U). The vertices of T(U) are taken to be the even vertices of [partial derivative]U and the edges of Y(U) are the digaonals of the faces of [partial derivative]U whose endpoints are even. If f: [Z.sup.d] [right arrow] [R.sup.+] is a positive function, define edge weight w(e) on an edge e of T(U) to be the positive solution to [(w - 1/w).sup.2]/4 = b where b = f ([upsilon]) f ([upsilon]')/(f([upsilon]) f(u')), where e = {[upsilon], [upsilon]'} and where u and u' are the other two vertices of the face of [partial derivative]U on which e lies. The following lemma is known as Kashaev's difference equation.

Lemma 8 (Kashaev (1996)) Let U [subset or equal to] U' be stepped solids differing by a single cube.

1. The graph Y(U') differs from Y(U) by a Y-Delta move: Y to Delta if the bottom vertex of the added cube was even and Delta to Y otherwise.

2. If e is a weight function on the edges of Y(U), extended by the Ising-Y-Delta relations to the edges of Y(U'), and if f is a function on the vertices of [Z.sup.d] inducing e on the edges of Y(U) and Y(U') then at the eight vertices of the added cube, f satisfies the relations

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (19)

Kashaev's equation for f: [Z.sup.3] [right arrow] C may be embedded in the hexahedron recurrence by extending f to [Z.sup.3.sub.1/2] as follows.

Proposition 9 Suppose f: [Z.sup.3.sub.1/2] [right arrow] C satisfies the following relation for integer (i, j, k):

f [(i + 1/2, j + 1/2, k).sup.2] = f (i, j, k)f (i + 1, j + 1, k) + f (i, j + 1, k)f (i + 1, j, k)

f [(i + 1/2, j, k + 1/2).sup.2] = f (i, j, k)f (i + 1, j, k + 1) + f (i, j, k + 1)f (i + 1, j, k)

f [(i, j + 1/2, k + 1/2).sup.2] = f (i, j, k)f (i, j + 1, k + 1) + f (i, j, k + 1)f (i, j + 1, k).

Then f satisfies Kashaev's relation (19) at integer points if and only if f satisfies the hexahedron relations (3)-(7), where as usual we interpret h = f, [h.sup.(x)] = [f.sub.(0,1/2,1/2)], and so forth.

Specializing the hexahedron recurrence creates redundancy, which may be exploited to produce simpler forms of the hexahedron/Kashaev recurrence. The following result may be proved.

Theorem 10 Let X([upsilon]) := [f.sup.(x).sub.([upsilon])], Y([upsilon]) := [f.sup.(y).sub.([upsilon])], and Z([upsilon]) := [f.sup.(z).sub.([upsilon])]. Then [f.sub.i,j,k] may be written as a Laurent polynomial in the initial variables [{[f.sub.i,j,k]}.sub.0[less than or equal to]i+j+k[less than or equal to]2] and [{[X.sub.i,j,k], [Y.sub.i,j,k,], [Z.sub.i,j,k]}.sub.i+j+k=0] with the X, Y, Z variables appearing only with power 0 or 1.

Open question What are the natural combinatorial structures counted by [f.sub.i,j,k]?

References

Y. Baryshnikov and R. Pemantle. Asymptotics of multivariate sequences, part III: quadratic points. Adv. Math., 228:3127-3206, 2011.

G. Carroll and D. Speyer. The cube recurrence. Electronic Journal of Combinatorics, 11: paper 73, 31 pages, 2004.

M. Ciucu. A complementation theorem for perfect matchings of graphs having a cellular completion. J. Comb. Theory, ser. A, 81:34-68, 1998.

C. Dodgson. Condensation of determinants, being a new and brief method for computing their arithmetical values. Proc. Royal Soc. London, 15:150-155, 1866.

S. Fomin and A. Zelevinsky. The Laurent phenomenon. Adv. Appl. Math., 28:119- 144, 2002a.

S. Fomin and A. Zelevinsky. Cluster algebras, I. J. Amer. Math. Soc., 15:497- 529, 2002b.

R. Kashaev. On discrete three-dimensional equations associatied with the local Yang-Baxter equation. Lett. Math. Phys., 33:389-397, 1996.

A. Kennelly. Equivalence of triangles and stars in conducting networks. Elec. World and Engineer, 34: 3413-U4, 1899.

T. Petersen and D. Speyer. An arctic circle theorem for groves. J. Comb. Theory, ser. A, 111:137-164, 2005.

D. Speyer. Perfect matchings and the octahedron recurrence. J. Alg. Comb., 25:309-348, 2007.

Richard Kenyon (1) ([dagger]) and Robin Pemantle (2) ([double dagger])

(1) Department of Mathemtics, Brown University, 151 Thayer Street, Providence, RI02912, USA

(2) Department of Mathematics, University of Pennsylvania, 209 South 33rd Street, Phildelphia, PA 19096, USA

([dagger]) Partially supported by the Natioinal Science Foundation

([double dagger]) Supported by NSF Grant #DMS-1209117

Printer friendly Cite/link Email Feedback | |

Author: | Kenyon, Richard; Pemantle, Robin |
---|---|

Publication: | DMTCS Proceedings |

Article Type: | Report |

Geographic Code: | 1USA |

Date: | Jan 1, 2013 |

Words: | 5835 |

Previous Article: | Descent sets for oscillating tableaux. |

Next Article: | Ehrhart [h.sup.*]-vectors of hypersimplices. |

Topics: |