Printer Friendly

Gale-Robinson sequences and Brane Tilings.

1 Introduction

This article is concerned with a variant of the Gale-Robinson integer sequence [Gal91], i.e. {[x.sub.n]} satisfying [x.sub.n] [x.sub.n-N] = [x.sub.n-r] [x.sub.n-N+r] + [x.sub.n-s] [x.sub.n-N+s], where we include a second alphabet of variables, {[y.sub.1], [y.sub.2], ..., [y.sub.n]}, that breaks the symmetry of this recurrence. This deformation is motivated by the theory of cluster algebras with principal coefficients.

The undeformed version of this sequence has been studied by several authors [BPW09, FZ02b, S07]. For example, Bousquet-Melou, Propp, and West [BPW09] describe sequences of graphs, termed pinecones, such that the nth term in the associated Gale-Robinson sequence enumerates perfect matchings in the nth pinecone graph. Such pinecones can also be constructed by using Speyer's "crosses-and-wrenches" method [S07], which provides graph theoretical formulas for Laurent expansions of expressions satisfying the Octahedron recurrence. In particular, if one chooses the appropriate plane of initial conditions, then one can build graphs that are known by experts to be isomorphic (modulo elementary transformations) to the pinecones. We now further investigate pinecone graphs with the following goals in mind:

1) Develop a more natural way to obtain pinecone graphs from cluster algebra theory directly. This will take us on a detour through the physics literature of brane tilings which motivates further families of examples for future study. Though most of these details are omitted in this extended abstract, the interested reader may turn to [J], [JMZ], or [Z] for further details. We also turn the reader's attention to Eager's work [E11] which discusses these examples in terms of terminology from physics and geometry.

2) Explain how to generalize results of [BPW09] and [S07] to include principal coefficients. Our main result to this effect is the following Theorem.

Theorem 1 Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the cluster algebra with principal coefficients associated to the Gale-Robinson quiver of type (r, s, N). For n [member of] {N +1, N + 2, ...}, define the cluster variables [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by mutating the initial seed [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] periodically by the sequence 1, 2, 3, ..., N, 1, 2, .... Let [G.sup.(r,s,N).sub.n] be the graph as in Definition 16. Then for n [greater than or equal to] N + 1, the Laurent expansion of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is given by the combinatorial formula: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The Gale-Robinson quivers are defined in Section 3, the graphs [G.sup.(r,s,N).sub.n] are defined in Section 5, and the weights appearing in the combinatorial formula appear in Section 6. We conjecture that formulas for a large class of examples from [S07] and the physics literature [E11, EF, DHP10, FHKVW, HS12] can be generalized similarly, but we leave their study for the future.

2 Preliminaries: Periodic Quivers and Cluster Mutation

In this section, we review the necessary background material on cluster mutation and periodic quivers from [FZ02a, FZ02b] and [FM11]. A quiver Q = ([Q.sub.0], [Q.sub.1]) is a directed finite graph with vertex set [Q.sub.0] and edge set [Q.sub.1] (also known as the set of arrows). We will usually assume that quivers have no 1-cycles nor 2-cycles, and state when this restriction is relaxed. Let [absolute value of ([Q.sub.0])] = N.

Definition 2 (Quiver Mutation) The mutation of Q at vertex k, denoted by [[mu].sub.k] Q, is constructed (from Q) by the following three steps: (1) For every 2-path i [right arrow] k [right arrow] j in Q, add an arrow i [right arrow] j. (2) Reverse the direction of all arrows incident to vertex k. (3) Remove any 2-cycles created by steps (1) and (2).

To any quiver, we can associate a cluster algebra defined as follows. First, we associate a variable, which we denote as [x.sub.i], to each vertex of Q. This yields an initial cluster, {[x.sub.1], [x.sub.2], ..., [x.sub.N]}, associated to Q. We then define a cluster mutation that proceeds alongside the aforementioned quiver mutation.

Remark 3 Later on, we will discuss how to associate brane tilings, i.e. bipartite graphs on a torus, to the quivers we study. In this context, quiver mutation corresponds to Urban Renewal or Seiberg Duality.

Definition 4 (Cluster Mutation) Given a quiver Q and a cluster X = {[X.sub.1], [X.sub.2], ..., [X.sub.N]}, the mutation of the cluster seed (Q,X) in the direction k is defined as [[mu].sub.k] (Q,X) = ([[mu].sub.k] Q,X'), where X' equals X\{[X.sub.k]} [union] {[X'.sub.k]} and [X'.sub.k] is defined below. If there is an arrow from vertex i to vertex k in Q, we let [b.sub.ik] denote the number of such arrows, and [] = -[b.sub.ik], yielding a skew- symmetric matrix B. We define [X'.sub.k] as


A cluster seed (Q, {[X.sub.1], [X.sub.2], ..., [X.sub.N]}) can be mutated in N directions. Then, these newly constructed seeds can then be again mutated in N directions, noting that [[mu].sup.2.sub.k] = id. There will possibly be cycles in this mutation graph, but we generally get an infinite tree where each vertex has degree N.

Definition 5 (Cluster variables and algebras) The set of cluster variables is the union of all clusters obtained via all finite sequences of mutations. The cluster algebra [A.sub.Q] associated with the initial seed (Q, {[x.sub.1], ..., [x.sub.N]}) is the subalgebra of Q([x.sub.1], ..., [x.sub.N]), the field of rational functions in N variables, generated by the set of cluster variables.

Please see [FZ02a, GSV10] for more details about cluster algebras in general. We now introduce Fordy and Marsh's notion of periodic quivers [FM11]. For convenience, we draw such quivers by arranging the vertices on a regular N-gon in clockwise order. Let [rho] denote (1, N, N - 1, N - 2, ..., 3,2), the permutation which rotates the vertices of the quiver Q clockwise while keeping the arrows fixed.

Definition 6 (Periodic Quiver) We say that a quiver Q is periodic, of period m, if the mutated quiver [Q.sup.(m)] = [[mu].sub.m] x ... x [[mu].sub.2] x [[mu].sub.1] (Q) equals [[rho].sup.m] (Q). In other words, the quiver obtained by mutating by 1, 2, ..., m in sequence is equal to the quiver obtained by cyclically permuting the vertex labels of Q.

In particular, a quiver Q is of period 1 if and only if mutating at vertex 1 and then applying [[rho].sup.-1] (sending 2 [right arrow] 1, 3 [right arrow] 2, ..., N [right arrow] N - 1, 1 [right arrow] N) yields back the original quiver Q. The importance of period 1 quivers is that as long as we mutate at 1, 2, 3, ... in sequence and periodically, the quivers obtained by mutation are equivalent to one another, up to cyclic permutation.

Definition 7 (Primitive Period 1 Quiver) Following [FM11], for 1 [less than or equal to] k [less than or equal to] N/2, we define the primitive period 1 quiver +[P.sup.(k).sub.N] (resp. -[P.sup.(k).sub.N]) as the N vertex quiver with N arrows (See Figure 1for examples):

* For all 1 [less than or equal to] i [less than or equal to] k, draw an arrow i + N - k [right arrow] i (resp. i [right arrow] i + N - k),

* For all 1 [less than or equal to] j [less than or equal to] N - k, draw an arrow j + k [right arrow] j (resp. j [right arrow] j + k).

We also let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the quiver [+ or -] [P.sup.(k).sub.N] where the vertices are relabeled using [i.sub.1], ..., [i.sub.N'].

For a periodic quiver Q and an initial cluster {[x.sub.1], [x.sub.2], ..., [x.sub.N]}, we may define [x.sub.n], for all n [greater than or equal to] 1, by mutating periodically at 1, 2, 3, ... For example, we denote the new clusters [[mu].sub.1] ({[x.sub.1], [x.sub.2], ..., [x.sub.N]}, Q) and [[mu].sub.2] x [[mu].sub.1] ({[x.sub.1], [x.sub.2], ..., [x.sub.n]}, Q) as {[x.sub.N+1], [x.sub.2], ..., [x.sub.N]} and {[x.sub.N+1], [x.sub.N+2], ..., [x.sub.N]}, respectively. More generally, for n = mq + r, we define [x.sub.n] to be the rth element of the cluster obtained by the mutation [[mu].sub.r] x [[mu].sub.r-1] x ... x [[mu].sub.1] x [([[mu].sub.m] x [[mu].sub.m-1] x ... x [[mu].sub.1]).sup.q] ({[x.sub.1], [x.sub.2], ..., [x.sub.N]}, Q). We obtain a one-parameter infinite subsequence of cluster variables indexed by the positive integers. If Q is of period 1, then there is a single recurrence relation


satisfied by all n [greater than or equal to] N + 1. For higher periods, there are m interlaced recurrence relations instead.

3 Gale-Robinson Sequences

Using the constructions of the previous section, we now focus on a certain two- parameter family of period 1 quivers. These quivers correspond to the Gale-Robinson sequence [Gal91] and were studied, implicitly, in work by Bousquet-Melou, Propp, and West [BPW09]. The Somos 4 and Somos 5 sequences (due to M. Somos as described in [Gal91]) appear as special cases. Any Gale-Robinson sequence can also be shown to be a specialization of the Octahedron Recurrence [S07]. See Remark 10 for details.

Definition 8 (Gale Robinson Sequences) For 1 [less than or equal to] r [less than or equal to] s < N/2, the Gale Robinson sequence of type (r, s, N) is defined to be the sequence {[x.sub.n] : n [greater than or equal to] 1} satisfying the recurrence relation (for n [greater than or equal to] N + 1):

[x.sub.n] [x.sub.n-N] [x.sub.n-r] [x.sub.n-N+r] + [x.sub.n-s] [x.sub.n-N+s]. (1)

As explained in Example 8.7 of [FM11], for each triple of positive integers (r, s, N) with r < s [less than or equal to] N/2, there is a unique period 1 quiver whose mutations yield the sequence of [x.sub.n]'s satisfying recurrence (1).

Definition 9 (The Gale-Robinson Quiver) For 1 [less than or equal to] r [greater than or equal to] s < N/2, we let [Q.sub.N]'s) denote the quiver constructed by the following four step process, starting with the edge-less quiver on N vertices:

1. For all 1 [less than or equal to] i [less than or equal to] N - r, draw an arrow i [right arrow] i + r, and for all 1 [less than or equal to] j [less than or equal to] r, draw an arrow j [right arrow] N - r + j, i.e. adjoin the primitive period 1 quiver - [P.sup.(r).sub.N].

2. For all 1 [less than or equal to] i [less than or equal to] N - s, draw an arrow s + i [right arrow] i, and for all 1 [less than or equal to] j [less than or equal to] s, draw an arrow N - s + j [right arrow] j, i.e. adjoin the primitive period 1 quiver + [P.sup.(s).sub.N] (resp. +2[P.sup.(N/2).sub.N] if s = N/2).

3. For all 1 [less than or equal to] i [less than or equal to] N - r - s, draw an arrow from r + i [right arrow] s + i and for all 1 [less than or equal to] j [less than or equal to] s - r, draw an arrow r + j [right arrow] N - s + j, i.e. adjoin - [P.sup.(s-r).sub.r+1+2,...,N- r] (resp. -2[P.sup.(N/2-r).sub.r+1,r+2m,...,N-r] if s = N/2).

4. Erase any 2-cycles created in [Q.sup.(r,s).sub.N].

Note that there might be multiple arrows between vertices i and j. See Figure 1for the example of [Q.sup.(2,3).sub.7].

In [BPW09], the authors provide a combinatorial interpretation for the Gale- Robinson sequence, given by {[x.sub.n] : n [greater than or equal to] 1}, with the initial conditions [x.sub.1] = [x.sub.2] = ... = [x.sub.N] = 1. In particular, each [x.sub.n] is an integer, which is a non-trivial fact since the recurrence relation (1) involves division. This was proven directly in [Gal91], and also follows from Fomin and Zelevinsky's Laurent Phenomenon [FZ02b], which states that every cluster variable is a Laurent polynomial in terms of the initial cluster.

More specifically, in [BPW09], they introduce a family of graphs, known as pinecones. For each quadruple of positive integers (n, r, s, N) such that r < s [less than or equal to] N/2 and n > N, they define the pinecone P(n; r, N - r, s, N - s) so that the specialized cluster variable [x.sub.n] ([x.sub.1] = [x.sub.2] = ... = [x.sub.N] = 1) counts the number of perfect matchings in P(n; r, N - r, s, N - s). In the next section, we provide an alternate construction of pinecones that is motivated by recent literature on supersymmetric quiver gauge theories.

Remark 10 While it has not been written down explicitly in print, the pinecone graphs constructed in [BPW09] are equivalent to the subgraphs obtained in [S07] by David Speyer using his method of "crosses and wrenches". More generally, for any sequence of cluster variables {f (i, j, k)} coming from a specialization of the Octahedron Recurrence:

f (i, j, k)f (i - 2, j, k) = f (i - 1, j - 1, k)f (i - 1, j + 1, k) - f (i - 1, j, k - 1)f (i - 1, j, k + 1),

Speyer's method constructs families of graphs {[G.sub.i,j,k]} and a weighting w(M) for the perfect matchings of [G.sub.i,j,k] such that the Laurent polynomial (equiv. cluster variable) f (i, j, k) equals the generating function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. A variant of this weighting was also presented in [GK], and we will elaborate on and utilize this in Section 6. As explained in [S07, Section 1.3]), by choosing an appropriate plane of initial conditions, namely, (i, j, k) such that -N < [Ni + (2r - N) j + (2s - N)k/2] [less than or equal to] 0, a subset of the f (i, j, k)'s satisfy the Gale-Robinson recurrence relation of type (r, s, N).

4 From Gale-Robinson Quivers to Brane Tilings

We now describe how to use techniques from Supersymmetric Quiver Gauge Theories [FHH01, FHKVW, FHMSVW] to obtain the pinecones more directly. By letting r = a and s = c, the Gale-Robinson sequence {[x.sub.n]} defined above agrees with the {[Z.sub.n]}'s appearing in [EF, Section 9.1]. In the quiver gauge theory and brane tiling literature, Zn denotes a Pyramid Partition Function (cluster variable) associated to a certain cascade of Seiberg dualities (mutation sequence). The example highlighted in Section 9.1 of [EF] is inspired by a [L.sup.a,b,c]-geometry which comes from a toric Calabi-Yau 3- manifold. See [FHMSVW] for more on the construction of the [L.sup.a,b,c]-geometry and how to obtain a corresponding brane tiling. Further details also appear in [E11], which describes connections to [S07], as in Remark 10, in this language.

A brane tiling is a tiling of the torus, which we visualize as a doubly-periodic tiling of its universal cover, the infinite plane. We now summarize how to go from a Gale-Robinson quiver, [Q.sup.(r,s).sub.N], to an associated brane tiling, denoted as [T.sup.(r,s).sub.N]. Towards this end, we must now allow quivers with 2-cycles. Let [bar.[Q.sup.(r,s).sub.N]] denote the quiver obtained by following steps (1)- (3) of Definition 9. By abuse of notation, we will also refer to [bar.[Q.sup.(r,s).sub.N]] as a Gale-Robinson quiver, since 2- cycles do not affect the associated recurrence.

1. Firstly, since [bar.[Q.sup.(r,s).sub.N]] is highly symmetric, we can unfold it onto the plane, obtaining an infinite quiver [[??].sup.(r,s).sub.N] that is straightforward to describe:

a) Start with the Z2 lattice as an undirected graph, connecting (a, b) with (a [+ or -] 1, b) and (a, b [+ or -] 1).

b) Label the vertex at the origin (0,0) as 1. For all integer points (A, B), we label the corresponding vertex as (1 + Ar + Bs)(mod N) [member of] {1,2, ..., N}.

c) We now turn this lattice into a directed graph. For all horizontal edges, we orient i [right arrow] j if and only if i < j. For all vertical edges, we do the opposite (orient i [right arrow] j if and only if i > j).

d) Lastly, we add diagonal arrows as needed so that all triangles or squares in this planar directed graph are cyclically oriented. Proposition 11 ensures that this process is well- defined.

2. Secondly, we take the planar dual of [[??].sup.(r,s).sub.N], and label its faces using the labels of vertices of [[??].sup.(r,s).sub.N]. The resulting doubly-periodic tiling of the plane is the brane tiling [bar.[T.sup.(r,s).sub.N]]. See Figure 3 for an example.

Proposition 11 Consider a square S with vertices corresponding to i, i + s, i + r + s, i + r [member of] {1, 2, 3, ..., N}, taken modulo N and in clockwise order starting from the lower-left. Orient the four edges of the square using the convention of (1c). Then, as in Figure 2, either the edges of S form an oriented 4-cycle, or can be split into to two cyclically oriented triangles by adding a single oriented diagonal.

Remark 12 These four local configurations also appear in the square-ice or six- vertex models.

Proposition 13 Construct [[??].sup.(r,s).sub.N] as above and then identify vertices with the same labels. The resulting folded-up quiver exactly agrees with the Gale-Robinson quiver [bar.[Q.sup.(r,s).sub.N]] (possibly with 2-cycles).

Remark 14 If we attempted to unfold the 2-cycle-less [Q.sup.(r,s).sub.N] instead of unfolding [bar.[Q.sup.(r,s).sub.N]], we would be missing some of the diagonal edges which are relevant for obtaining a regular pattern of hexagons.

Corollary 15 For 1 [less than or equal to] i [less than or equal to] r, and N - r [less than or equal to] i [less than or equal to] N, the faces labeled with an i are squares. On the other hand, the faces labeled with an i for r + 1 [less than or equal to] i [less than or equal to] N - r - 1 are hexagons.

Note: When drawing brane tilings or their subgraphs, we will depict hexagonal faces as horizontal rectangles of height one and width two.

5 From Brane Tilings to Pinecones

We now describe how to obtain the pinecone graphs, P(n; r, N - r, s, N - s), constructed in [BPW09], directly from brane tilings. Given a Gale-Robinson sequence and quiver [bar.[Q.sup.(r,s).sub.N]], we described in the last section how to construct the associated brane tiling [T.sup.(r,s).sub.N]. We now describe how to construct a family of finite subgraphs of [T.sup.(r,s).sub.N], each of which we denote as [Q.sup.(r,s,N).sub.n] for n [greater than or equal to] N + 1.

Definition 16 (Gale-Robinson Brane Subgraphs) For N + 1 [less than or equal to] n [less than or equal to] N + r, we define [Q.sup.(r,s,N).sub.n] as the subgraph of [T.sup.(r,s).sub.N] consisting of the square face labeled n - N. If n > N + r, we instead build [G.sup.(r,s,N).sub.n] layer-by-layer. For this construction, we need some notation. For n > N + r, let [bar.n] [member of] {1,2, ..., r} denote the integer such that n [equivalent to] N + [bar.n] (mod r). Define the horizontal strip [H.sup.(r,N).sub.n] to be the induced subgraph of [T.sup.(r,s).sub.N] obtained by taking the grid graph of unit height and width equal to 2 [n - N - 1/2] + 1 starting with the square face labeled as [bar.n] as the left-most face. In particular, [H.sup.(r,N).sub.n] is defined to be empty if n [less than or equal to] N.

For n > N + r, we then construct a graph by using [H.sup.(r,N).sub.n] as a central horizontal strip, and then gluing to its top (resp. bottom) the strips [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] until the strips added above and below are empty. We glue these together in the unique way so that successive strips, emanating out from the center, are contained in the interior of the more central strip. This defines an induced subgraph of [T.sup.(r,s).sub.N], that we denote as [G.sup.(r,s,N).sub.n].

Example 17 Consider the case r = 2, s = 3, and N = 7. The corresponding quiver [Q.sup.(2,3).sub.7] appears in Figure 1 and its brane tiling [T.sup.(2,3).sub.7] appears in Figure 3. Then for 8 [less than or equal to] n [less than or equal to] 16, the strips [H.sup.(2,7).sub.n] are:

Gluing these strips together, we obtain the Gale-Robinson brane subgraphs {[G.sup.(2,3,7).sub.n]} for 8 [less than or equal to] n [less than or equal to] 16:

For example, the graph [G.sup.(2,3,7).sub.16] is obtained by gluing together the horizontal strips (from top to bottom) [H.sup.(2,7).sub.8], [H.sup.(2,7).sub.12], [H.sup.(2,7).sub.16], [H.sup.(3,7).sub.13], and [H.sup.(2,7).sub.10]. (The highlighted edges are minimal matchings which are discussed further in Definition 23.)

Remark 18 As will be described in [JMZ], the graphs [G.sup.(r,s,N).sub.n] can also be constructed by superimposing Aztec Diamonds of increasing sizes centered on top of a face (of the center row) of the brane tiling [T.sup.(r,s).sub.N]. In particular, the first r graphs are squares labeled with 1 [less than or equal to] i [less than or equal to] r. Subsequently, we have r subsequences of Aztec Diamonds. In particular, for N' [greater than or equal to] 0, the graph [G.sup.(r,s,N).sub.rN'+i] can be constructed by the following:

(i) locate a face of [T.sup.(r,s).sub.N] labeled as i. If it is a square, let (a, b) denote this face, as viewed in the [Z.sup.2] lattice. If instead it is a hexagon, let (a, b) denote the left-hand-side of this face.

(ii) Take the Aztec Diamond of size (N' + 1) (which has a central row of size 2N' + 1) and center it on top of the cell (a + N', b).

(iii) This superposition will usually result in a graph containing vertices of degree one. By removing these, one-by-one, we obtain the desired subgraph [G.sup.(r,s,N).sub.n].

See Figure 4 for an example. Note that this procedure is equivalent to taking the core ofa pinecone, as described in [BPW09, Section 2.4].

Proposition 19 For each choice of integers 1 [less than or equal to] r < s [less than or equal to] N/2 and n [greater than or equal to] N + 1, the graphs [G.sup.(r,s,N).sub.n] and pinecones P(n; r, N - r, s, N - s) from [BPW09] are equal (up to a vertical reflection).

Remark 20 A method for constructing subgraphs of brane tilings also appears in the string theory literature. For instance, in [EF, Sections 6, 7.3], they discuss a construction for the "shadow of a pyramid".

6 Principal Coefficients and Combinatorial Formulas

We now generalize Theorem 9 of [BPW09] by enriching the cluster algebra [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with principal coefficients. More generally, a coefficient system for a cluster algebra can be constructed by enlarging the set of initial cluster variables by including so called frozen variables. These variables correspond to new vertices at which mutation is disallowed. A system of principal coefficients is a special case where the arrows incident to the new vertices are particularly simple. By Theorem 3.7 of [FZ07], it follows that any coefficient system of geometric type can be algebraically deduced from a system of principal coefficients.

Definition 21 (Quiver with Principal Coefficients) Given a quiver Q with N vertices, we let [??] denote the quiver on 2N vertices that (i) contains Q as an induced subgraph on the vertices {1,2, ..., N}, and (ii) contains a single arrow [upsilon] [right arrow] [upsilon] - N for each vertex [upsilon] [member of] {N + 1, N + 2,..., 2N}.

We then let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the cluster algebra [A.sub.[??]], which we refer to as the cluster algebra for Q with principal coefficients. Just as in Section 2, we obtain an infinite sequence of cluster variables by mutating the enlarged quiver [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] periodically by 1, 2, ... . We let {[x.sub.1], [x.sub.2], ..., [x.sub.N], [y.sub.1], [y.sub.2], ..., [y.sub.N]} denote the corresponding initial cluster, and denote the next two clusters as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Continuing in this way, we let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the infinite sequence of non-initial cluster variables obtained by this periodic mutation sequence. Since we never mutate at vertex [upsilon] for [upsilon] [member of] {N + 1, N + 2, ..., 2N}, it follows that all of the [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]'s are Laurent polynomials whose denominators are free of [y.sub.i]'s. We now discuss how to generalize the numerical result of [BPW09] to obtain a combinatorial interpretation of the [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]'s.

Given a graph G, a set of edges M which covers all vertices in G exactly once is called a (perfect) matching of G. We say that G is a weighted graph if there is a real number or a formal variable w(e) associated to each edge e. When G is a subgraph of a brane tiling, we now define a weighting scheme inspired by the Conductance Coordinates(i) appearing in [GK, Section 5.3] and Speyer's weighting [S07].

Definition 22 (Weight of a perfect matching) Given a subgraph G of a brane tiling (with face labels Fi), we define the weight x(e) of an edge e (straddling faces [F.sub.i] and [F.sub.j]) to be x(e) = 1/[x.sub.i][x.sub.j]. Given a perfect matching M of G, we define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We additionally utilize height functions, as appearing in the literature [CKP01, CY, MSW11, P, Th90].

Definition 23 (Height of a perfect matching) For a pinecone graph G = [G.sup.(r,s,N).sub.n] of the brane tiling [T.sub.(r,s).sub.N], let [M.sub.-] denote the unique perfect matching of G using only horizontal edges. See for instance the highlighted edges in Example 17. Given another perfect matching M, we let M [direct sum] [M.sub.-] denote the superposition of these two perfect matchings. We then define the height, y(M), as the monomial


We also have to define a certain monomial that is given by the labels of the faces appearing in G and its boundary in the ambient tiling T.

Definition 24 (Covering monomial of a subgraph) Given a subgraph G of a brane tiling T (with face labels [F.sub.i]), let [bar.G] denote the subgraph of T consisting of all faces that are incident to an edge appearing in G. In particular, [bar.G] contains G as a proper subgraph, as well as a "ring" of exterior faces. (These are referred to as "open faces" in [S07].) Recall that by definition, each face of T is a 2k-gon where k [greater than or equal to] 2. Then for any face F of G, with label i, we define m(F) = [x.sup.[#edgeinF/2]- 1.sub.i]. For any of the open faces F [member of] [bar.G]\G, with label i, we define m(F) = [x.sup.[#edgeinFincidenttpG/2]]. Then the covering monomial of G is defined to be cm(G) = [[PI].sub.F[member of][bar.G]] m(F).

Remark 25 A more general definition of covering monomials appears in [J].

Given the above definition, the weight of a graph G is defined as w(G) = cm(G) x [[summation].sub.M] x(M)y(M), where the sum is taken over all perfect matchings M of G.

We now give a sketch of our main result, Theorem 1, stated in Section 1. See [JMZ] for the full proof.


Step 1: We show that as we mutate QN s) periodically at 1, 2, 3, ..., N, 1,2, ..., we get a Gale-Robinson recurrence relation (with coefficients) of the following form:


where d(n - N - i, r, N - r) denotes #{(A, B) [member of] [Z.sup.2.sub.[greater than or equal to]0] such that (n - N - i) = A x r + B x (N - r)}.

Step 2: For i [member of] {1, 2, ..., N} and integer n such that n > N, we show that d(n - N - i, r, N - r) equals the number of faces labeled i in the central strip [H.sup.(r,N).sub.n] of [G.sup.(r,s,N).sub.n].

Step 3: Finally, we apply Kuo's technique of graphical condensation [K04]. A superposition of a perfect matching of [G.sup.(r,s,N).sub.n-N] centered on top of a perfect matching [G.sup.(r,s,N).sub.n] can be decomposed uniquely (up to cycles) as exactly one of the following: (i) Into an east-west superposition of perfect matchings of [G.sup.(r,s,N).sub.n-r] and [G.sup.(r,s,N).sub.n-N+r]; or (ii) a north-south superposition of perfect matchings of [G.sup.(r,s,N).sub.n-s] and [G.sup.(r,s,N).sub.n-N+s]. This method is also detailed for this case in [BPW09] and follows from Speyer's more general proof in [S07]. In particular, this decomposition is weight-preserving with respect to edge-weights and covering monomials.

For this part of the proof, what is new relative to [BPW09] and [S07] is that an east-west superposition of minimal matchings again decomposes into a decomposition of minimal matchings of [G.sup.(r,s,N).sub.n-N] and [G.sup.(r,s,N).sub.n]. However a north-south superposition of minimal matchings does not. Instead, such a superposition decomposes into a minimal matching of [G.sup.(r,s,N).sub.n-N] and a perfect matching of [G.sup.(r,s,N).sub.n] where every face in the central strip [H.sup.(r,N).sub.n] has been twisted down [P] exactly once. In the twisting down operation, one perfect matching of the square or rectangle is exchanged for the other. This is also referred to as a plaquette flip in [CY] and elsewhere. The proof of the Theorem then follows from Steps 1 and 2. ?

Remark 26 Related formulas also appeared in [EF, Appendix B] where all the [x.sub.i]'s are set to be one so that F-polynomials [FZ07] are recovered. In the physics literature, these are referred to as pyramid partition functions. F-polynomials for the related case of Aztec Diamonds also appear in [G11].

7 Further Topics

The authors have already started investigating other families of brane tilings and their connections to cluster algebras. See [J] and [Z] for the related REU reports. Further details will appear in [JMZ].

In particular, In-Jee Jeong investigated the cluster algebras associated to the four-vertex quiver where the vertices are arranged clockwise around a square, and there are two clockwise arrows between any pair of adjacent vertices. If one mutates this quiver periodically, one obtains cluster variables whose Laurent polynomials can be expressed in terms of w([AD.sub.n]) where [AD.sub.n] is the nth Aztec Diamond, with a certain face label. However, for certain non-periodic mutation sequences, Jeong also obtained graph theoretical interpretations for the cluster variables here too. Jeong also initiated an investigation for a more general framework that was part of the motivation for further study of the brane tiling literature.

Sicong Zhang studied a certain six vertex quiver, known as the dP3 (del-Pezzo 3 quiver) in the physics literature. Certain subgraphs of the associated brane tiling were previously studied by C. Cottrell-B.Young [CY] and M. Ciucu [C03] after being introduced by J. Propp [P99] under the name Aztec Dragons. Zhang proved that like above, a certain infinite sequence of cluster variables associated to this quiver, obtained by periodic mutation, has the property that their Laurent polynomial expansions can be expressed, under a suitable weighting scheme, in terms of perfect matchings of these subgraphs.


We thank Philippe Di Francesco, Sergey Fomin, Max Glick, Rinat Kedem, Rick Kenyon, Robert Marsh, Diane Maclagan, Jim Propp, Idun Reiten, Hugh Thomas, Dylan Thurston, and Lauren Williams for many helpful discussions. We are especially thankful to David Speyer for discussing his work on the Octahedron Recurrence with us and for highlighting several motivational questions, and to Gordana Todorov for her careful reading of a draft. We also thank the FPSAC referees for their editorial suggestions. Some of this work utilized computer software such as [Sage], including the author's cluster algebra package with Christian Stump [MS11], and Bernhard Keller's Quiver applet in Java [K]. Part of this research was done during the 2011 and 2012 Research Experiences for Undergraduate at Minnesota, Twin Cities. We would like to thank Pasha Pylyavskyy, Vic Reiner, and Dennis Stanton for their work as co-mentors of these REU's. This work was also completed while G. M. was at MSRI, which was an invigorating environment in which to work. We thank MSRI for their hospitality.


[BPW09] M. Bousquet-Melou, J. Propp, and J. West. Perfect matchings for the three-term Gale-Robinson sequences, Electron. J. Combin. 16 no. 1, Research Paper 125 (2009), 1-37.

[C03] M. Ciucu. Perfect matchings and perfect powers, J. Algebraic Combin. 17 (2003), 335-375.

[CKP01] H. Cohn, R. Kenyon, J. Propp. A variational principle for domino tilings, J. Amer. Math. Soc. 14 (2001), 297-346.

[CY] C. Cottrell and B. Young. Domino shuffling for the Del Pezzo 3 lattice. eprint, arXiv:1011.0045, 2010.

[DHP10] J. Davey, A. Hanany, and J. Pasukonis, On the classification of brane tilings, J. High Energy Physics 2010 1 (2010), 1-30.

[E11] R. Eager, Brane tilings and non-commutative geometry, J. High Energy Physics 2011 no. 3, 026 (2011), 1-20.

[EF] R. Eager and S. Franco, Colored BPS Pyramid Partition Functions, Quivers and Cluster Transformations, eprint, arXiv:1112.1132, 2011.

[EKLP92] N. Elkies, G. Kuperberg, M. Larsen, J. Propp, Alternating-Sign Matrices and Domino Tilings (Part I), J. Algebraic Combin. 1 (1992), no. 2, 11-132

[FHH01] B. Feng, A. Hanany, and Y-H. He., D-brane gauge theories from toric singularities and toric duality. Nucl. Phys. B, 595:165-200, 2001.

[FM11] A. Fordy and R. Marsh, Cluster mutation-periodic quivers and associated Laurent sequences, J. Algebraic Combin. 34 no. 1 (2011), 19-66.

[FZ02a] S. Fomin and A. Zelevinsky. Cluster algebras I: Foundations, J. Amer. Math Soc. 15 (2002), 497-529.

[FZ02b] S. Fomin and A. Zelevinsky, The Laurent phenomenon, Adv. in Applied Math. 28 (2002), 119-144.

[FZ07] S. Fomin and A. Zelevinsky, Cluster Algebras IV: Coefficients, Comp. Math. 143 (2007), 112-164.

[F] S. Franco, Bipartite Field Theories: From D-Brane Probes to Scattering Amplitudes, eprint, arXiv:1207.0807, 2012.

[FHKVW] S. Franco, A. Hanany, K. D. Kennaway, D. Vegh, and B. Wecht, Brane Dimers and Quiver Gauge Theories, J. High Energy Physics 0601,096 (2006) [hep-th/0504110]

[FHMSVW] S. Franco, A. Hanany, D. Martelli, J. Sparks, D. Vegh, and B. Wecht, Gauge Theories from Toric Geometry and Brane Tilings, J. High Energy Physics 0601, 128 (2006) [hep- th/0505211]

[Gal91] D. Gale, The strange and surprising saga of the Somos sequences, Math. Intelligencer 13 (1991), no. 1, 40-43.

[GSV10] M. Gekhtman, M. Shapiro and A. Vainshtein, Cluster algebras and Poisson geometry, Mathematical Surveys and Monographs, 167. American Mathematical Society, Providence, RI2010.

[G11] M. Glick, The pentagram map and Y-patterns, Adv. Math., 227 (2011), 1019- 1045.

[GK] A.B. Goncharov and R. Kenyon, Dimers and cluster integrable systems, arXiv:1107.5588.

[HS12] A. Hanany and R.-K. Seong. Brane tilings and reflexive polygons. Fortschritte der Physik, 60:695-803, June 2012. hep-th/1201.2614

[J] I. Jeong. Bipartite graphs, quivers, and cluster variables, REU Report http://www.math.umn. edu/~reiner/REU/Jeong2011, 2011.

[JMZ] I. Jeong, G. Musiker, and S. Zhang. Brane tilings and cluster algebras. (in preparation)

[K] B. Keller,^keller/quivermutation.

[K04] E. H. Kuo. Applications of graphical condensation for enumerating matchings and tilings. Theoretical Computer Science, 319:0304090, 2004.

[MSW11] G. Musiker, R. Schiffler, L. Williams, Positivity for cluster algebras from surfaces, Adv. Math., 227, (2011), 2241-2308.

[MS11] G. Musiker and C. Stump, A compendium on the cluster algebra and quiver package in SAGE. Seminaire Lotharingien de Combinatoire 65 (2011), Article B65d.

[P] J. Propp, Lattice structure for orientations of graphs, preprint (1993), arXiv:math/02 0 950 05.

[P99] J. Propp. Enumeration of Matchings: Problems and Progress, volume 38 of New perspectives in algebraic combinatorics. Cambridge Univ. Press, Cambridge, 255-291, 1999.

[S07] D. E Speyer. Perfect Matchings and the Octahedron Recurrence, J. Algebraic Combin. 25, no 3 (2007), 309-348.

[Sage] W. A. Stein and others, Sage Mathematics Software, [Th90] W. Thurston, Conway's tiling groups, Amer. Math. Monthly 97 (1990), 757- 773.

[Z] S. Zhang. Cluster variables and perfect matchings of subgraphs of the dP3 Lattice, REU Report 012.pdf, 2012.

(i) Unlike Goncharov and Kenyon, we have weights only on faces, i.e. trivial weights on vertices.

In-Jee Jeong (1) ([dagger])

Gregg Musiker (2) ([double dagger])

Sicong Zhang (3) ([section])

(1) Brown University, Department of Mathematics, Providence, RI, USA

(2) University of Minnesota, School of Mathematics, Minneapolis, MN, USA

(3) Columbia University, Department of Mathematics, New York, NY, USA

([dagger]) Supported by NSF grant DMS-1001933.

([double dagger]) Supported by NSF grants DMS-1067183 and DMS-1148634.

([section]) Supported by the Columbia University Rabi Scholars Program.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Jeong, In-Jee; Musiker, Gregg; Zhang, Sicong
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2013
Previous Article:The unreasonable ubiquitousness of quasi-polynomials.
Next Article:A generalization of Mehta-Wang determinant and Askey-Wilson polynomials.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |