Combinatorial Interpretations for Rank-Two Cluster Algebras of Affine Type
Gregg Musiker
Department of Mathematics University of California, San Diego
La Jolla, CA 92093-0112 gmusiker@math.ucsd.edu
James Propp
Department of Mathematical Sciences University of Massachusetts Lowell
Lowell, MA 01854
propp@jamespropp.org.ignorethis
Submitted: Feb 20, 2006; Accepted: Jan 11, 2007; Published: Jan 19, 2007 Mathematics Subject Classification: 05A99, 05C70
Abstract
Fomin and Zelevinsky [6] show that a certain two-parameter family of rational recurrence relations, here called the (b, c) family, possesses the Laurentness property:
for all b, c, each term of the (b, c) sequence can be expressed as a Laurent polyno- mial in the two initial terms. In the case where the positive integers b, c satisfy bc <4, the recurrence is related to the root systems of finite-dimensional rank 2 Lie algebras; whenbc >4, the recurrence is related to Kac-Moody rank 2 Lie algebras of general type [9]. Here we investigate the borderline cases bc= 4, corresponding to Kac-Moody Lie algebras of affine type. In these cases, we show that the Lau- rent polynomials arising from the recurence can be viewed as generating functions that enumerate the perfect matchings of certain graphs. By providing combinato- rial interpretations of the individual coefficients of these Laurent polynomials, we establish their positivity.
1 Introduction
In [5, 6], Fomin and Zelevinsky prove that for all positive integers b and c, the sequence of rational functions xn (n ≥0) satisfying the “(b, c)-recurrence”
xn=
(xbn−1+ 1)/xn−2 for n odd (xcn−1+ 1)/xn−2 for n even
is a sequence of Laurent polynomial in the variables x1 and x2; that is, for all n ≥2, xn
can be written as a sum of Laurent monomials of the form axi1xj2, where the coefficient a is an integer and i and j are (not necessarily positive) integers. In fact, Fomin and Zelevinsky conjecture that the coefficients are always positive integers.
It is worth mentioning that variants of this recurrence typically lead to rational func- tions that are not Laurent polynomials. For instance, if one initializes with x1, x2 and defines rational functions
xn =
(xbn−1+ 1)/xn−2 for n= 2 (xcn−1+ 1)/xn−2 for n= 3 (xdn−1+ 1)/xn−2 for n= 4 (xen−1+ 1)/xn−2 for n= 5
withb, c, d, eall integers larger than 1, then it appears thatx5 is not a Laurent polynomial (in x1 and x2) unless b = d and that x6 is not a Laurent polynomial unless b = d and c=e. (This has been checked by computer in the cases where b, c, d, e are all between 2 and 5.)
One reason for studying (b, c)-recurrences is their relationship with root systems as- sociated to rank two Kac-Moody Lie algebras. Furthermore, algebras generated by a sequence of elements satisfying a (b, c)-recurrence provide examples of rank two cluster algebras, as defined in [6, 7] by Fomin and Zelevinsky. The property of being a sequence of Laurent polynomials, Laurentness, is in fact proven for all cluster algebras [6] as well as a class of examples going beyond cluster algebras [5]. In this context, the positivity of the coefficients is no mere curiosity, but is related to important (albeit still conjectural) total-positivity properties of dual canonical bases [13].
The cases bc < 4 correspond to finite-dimensional Lie algebras (that is, semisimple Lie algebras), and these cases have been treated in great detail by Fomin and Zelevinsky [6, 12]. For example, the cases (1,1), (1,2), and (1,3) correspond respectively to the Lie algebras A2, B2, and G2. In these cases, the sequence of Laurent polynomials xn is periodic. More specifically, the sequence repeats with period 5 when (b, c) = (1,1), with period 6 when (b, c) = (1,2) or (2,1), and with period 8 when (b, c) = (1,3) or (3,1). For each of these cases, one can check that each xn has positive integer coefficients.
Very little is known about the cases bc >4, which should correspond to Kac-Moody Lie algebras of general type. It can be shown that for these cases, the sequence of Laurent polynomialsxn is non-periodic.
This article gives a combinatorial approach to the intermediate cases (2,2), (1,4) and (4,1), corresponding to Kac-Moody Lie algebras of affine type; specifically algebras of types A(1)1 and A(2)2 . Work of Sherman and Zelevinsky [12] has also focused on the rank two affine case. In fact, they are able to prove positivity of the (2,2)-, (1,4)- and (4,1)-cases, as well as a complete description of the positive cone. They prove both cases simultaneously by utilizing a more general recurrence which specializes to either case. By using Newton polygons, root systems and algebraic methods analogous to those used in the finite type case [7], they are able to construct the dual canonical bases for these cluster algebras explicitly.
Our method is intended as a complement to the purely algebraic method of Sherman and Zelevinsky [12]. In each of the cases (2,2), (1,4) and (4,1) we show that the positivity conjecture of Fomin and Zelevinsky is true by providing (and proving) a combinatorial interpretation of all the coefficients of xn. That is, we show that the coefficient of xi1xj2 in xn is actually the cardinality of a certain set of combinatorial objects, namely, the set of those perfect matchings of a particular graph that contain a specified number of
“x1-edges” and a specified number of “x2-edges”. This combinatorial description provides a different way of understanding the cluster variables, one where the binomial exchange relations are visible geometrically.
The reader may already have guessed that the cases (1,4) and (4,1) are closely related.
One way to think about this relationship is to observe that the formulas xn = (xbn−1+ 1)/xn−2 for n odd
and
xn = (xcn−1+ 1)/xn−2 forn even can be re-written as
xn−2 = (xbn−1+ 1)/xn for n odd and
xn−2 = (xcn−1+ 1)/xn for n even;
these give us a canonical way of recursively defining rational functionsxn withn <0, and indeed, it is not hard to show that
x(b,c)−n (x1, x2) =x(c,b)n+3(x2, x1) for n ∈Z. (1) So the (4,1) sequence of Laurent polynomials can be obtained from the (1,4) sequence of Laurent polynomials by running the recurrence in reverse and switching the roles of x1
and x2. Henceforth we will not consider the (4,1) recurrence; instead, we will study the (1,4) recurrence and examinexn for all integer values ofn, the negative together with the positive.
Our approach to the (1,4) case will be the same as our approach to the simpler (2,2) case: in both cases, we will utilize perfect matchings of graphs as studied in [2, 10, 11, et al.].
Definition 1. For a graph G = (V, E), which has an assignment of weights w(e) to its edges e∈E, a perfect matching of G is a subset S ⊂E of the edges of G such that each vertexv ∈V belongs to exactly one edge inS. We define theweight of a perfect matching S to be the product of the weights of its constituent edges,
w(S) =Y
e∈S
w(e).
With this definition in mind, the main result of this paper is the construction of a family of graphs {Gn} indexed by n ∈ Z\ {1,2} with weights on their edges such that the terms of the (2,2)- (resp. (1,4)-) recurrence, xn, satisfy xn =pn(x1, x2)/mn(x1, x2);
where pn(x1, x2) is the polynomial
X
S⊂E is a perfect matching of Gn
w(S),
and mn is the monomial xc11xc22 where c1 and c2 characterize the 2-skeleton of Gn. These constructions appear as Theorem 1 and Theorem 4 in sections 2 and 3, for the (2,2)- and (1,4)- cases, respectively.
Thus pn(x1, x2) may be considered a two-variable generating function for the perfect matchings of Gn, and xn(x1, x2) may be considered a generating function as well, with a slightly different definition of the weight that includes “global” factors (associated with the structure of Gn) as well as “local” factors (associated with the edges of a particular perfect matching). We note that the families Gn with n > 0 and Gn with n < 0 given in this paper are just one possible pair of families of graphs with the property that the xn(x1, x2)’s serve as their generating functions.
The plan of this article is as follows. In Section 2, we treat the case (2,2); it is simpler than (1,4), and makes a good warm-up. In Section 3, we treat the case (1,4) (which subsumes the case (4,1), since we allow n to be negative). Section 4 gives comments and open problems arising from this work.
2 The (2, 2) case
Here we study the sequence of Laurent polynomials x1, x2, x3 = (x22 + 1)/x1, etc. If we let x1 = x2 = 1, then the first few terms of sequence {xn(1,1)} for n ≥ 3 are 2,5,13,34,89, . . .. It is not too hard to guess that this sequence consists of every other Fibonacci number (and indeed this fact follows readily from Lemma 1 given on the next page).
For all n ≥1, letHn be the (edge-weighted) graph shown below for the case n= 6.
x
1 1 1 1 1 1
x x
x2 1 2 x1 2
x2 x1 x2 x1 x2
The graph G5 =H6.
That is, Hn is a 2-by-n grid in which every vertical edge has been assigned weight 1 and the horizontal edges alternate between weight x2 and weight x1, with the two leftmost horizontal edges having weightx2, the two horizontal edges adjoining them having weight
x1, the two horizontal edges adjoining them having weight x2, and so on (ending at the right with two edges of weight x2 when n is even and with two edges of weight x1 when n is odd). Let Gn = H2n−4 (so that for example the above picture shows G5), and let pn(x1, x2) be the sum of the weights of all the perfect matchings of Gn. Also let mn(x1, x2) = xn−21 xn−32 for n ≥ 3. We note the following combinatorial interpretation of this monomial: mn(x1, x2) = xi1xj2 where i is the number of square cells of Gn with horizontal edges having weight x2 and j is the number of square cells with horizontal edges having weight x1. Using these definitions we obtain
Theorem 1. For the case (b, c) = (2,2), the Laurent polynomials xn satisfy xn(x1, x2) =pn(x1, x2)/mn(x1, x2) for n6= 1,2
where pn and mn are given combinatorially as in the preceding paragraph.
E.g., for n= 3, the graphG3 =H2 has two perfect matchings with respective weights x22 and 1, so x3(x1, x2) = (x22 + 1)/x1. For n = 4, the graph G4 = H4 has five perfect matchings with respective weights x42, x22,x22, 1, and x21, so p4(x1, x2) = 1 + 2x22+x42+x21; since m4(x1, x2) = x21x2, we have p4(x1, x2)/m4(x1, x2) = (x42 + 2x22 + 1 +x21)/x21x2, as required.
Proof. We will have proved the claim if we can show that the Laurent polynomials pn(x1, x2)/mn(x1, x2) satisfy the same quadratic recurrence as the Laurent polynomials xn(x1, x2); that is,
pn(x1, x2) mn(x1, x2)
pn−2(x1, x2) mn−2(x1, x2) =
pn−1(x1, x2) mn−1(x1, x2)
2
+ 1. (2)
Proposition 1. The polynomials pn(x1, x2) satisfy the recurrence
pn(x1, x2)pn−2(x1, x2) = (pn−1(x1, x2))2+x2n−61 x2n−82 for n≥5. (3) Proof. To prove (3) we let qn(x1, x2) be the sum of the weights of the perfect matchings of the graph Hn, so that pn(x1, x2) = q2n−4(x1, x2) for n ≥ 3. Each perfect matching of Hnis either a perfect matching ofHn−1 with an extra vertical edge at the right (of weight 1) or a perfect matching of Hn−2 with two extra horizontal edges at the right (of weight x1 or weight x2, according to whether n is odd or even, respectively). We thus have
q2n = q2n−1 +x22q2n−2 (4) q2n−1 = q2n−2 +x21q2n−3 (5) q2n−2 = q2n−3 +x22q2n−4. (6) Solving the first and third equations forq2n−1 andq2n−3, respectively, and substituting the resulting expressions into the second equation, we get (q2n−x22q2n−2) = q2n−2+x21(q2n−2− x22q2n−4) or q2n = (x21+x22+ 1)q2n−2−x21x22q2n−4, so that we obtain
Lemma 1.
pn+1 = (x21+x22 + 1)pn−x21x22pn−1. (7) It is easy enough to verify that
p5p3 = ((x22+ 1)3+x41+ 2x21(x22+ 1)·(x22+ 1) =
(x22+ 1)2+x21 2
+x41x22 =p24+x41x22 so for induction we assume that
pn−1pn−3 =p2n−2+x2n−81 x2n−102 for n≥5. (8) Using Lemma 1 and (8) we are able to verify that polynomials pn satisfy the quadratic recurrence relation (3):
pnpn−2 = (x21+x22 + 1)pn−1pn−2−x21x22p2n−2 = (x21+x22+ 1)pn−1pn−2−x21x22(pn−1pn−3−x2n−81 x2n−102 ) =
pn−1((x21+x22+ 1)pn−2−x21x22pn−3) +x2n−61 x2n−82 =p2n−1+x2n−61 x2n−82 .
Since mn(x1, x2) =xn−21 xn−32 we have that recurrence (2) reduces to recurrence (3) of Proposition 1. Thuspn(x1, x2)/mn(x1, x2) satisfy the same initial conditions and recursion as the xn’s, and we have proven Theorem 1 .
An explicit formula has recently been found for thexn(x1, x2)’s by Caldero and Zelevin- sky using the geometry of quiver representations:
Theorem 2. [4, Theorem 4.1], [14, Theorem 2.2]
x−n =
x2n+21 + X
q+r≤n
n+ 1−r q
n−q r
x2q1 x2r2
xn1xn+12 (9) xn+3 =
x2n+22 + X
q+r≤n
n−r q
n+ 1−q r
x2q1 x2r2
xn+11 xn2 (10) for all n ≥0.
They also present expressions (Equations (5.16) of [4]) for the xn’s in terms of Fi- bonacci polynomials, as defined in [8], which can easily seen to be equivalent to the com- binatorial interpretation of Theorem 1. Subsequently, Zelevinsky has obtained a short elementary proof of these two results [14].
2.1 Direct combinatorial proof of Theorem 2
Here we provide yet a third proof of Theorem 2: instead of using induction as in Zelevin- sky’s elementary proof, we use a direct bijection. This proof was found after Zelevinsky’s result came to our attention. First we make precise the connection between the combina- torial interpretation of [4] and our own.
Lemma 2. The number of ways to choose a perfect matching of Hm with 2q horizontal edges labeled x2 and 2r horizontal edges labeled x1 is the number of ways to choose a subset S ⊂ {1,2, . . . , m−1} such that S contains q odd elements, r even elements, and no consecutive elements.
Notice that in the case m = 2n+ 2, this number is the coefficient of x2r−n−11 x2q−n2 in xn+3 (for n ≥ 0), and when m = 2n+ 1, this number is the coefficient of x2r−n1 x2q−n2 in sn, as defined in [4, 12, 14].
Proof. There is a bijection between perfect matchings of Hm and subsets S ⊂ {1,2, . . . , m−1}, with no two elements consecutive. We label the top row of edges of Hm from 1 to m−1 and map a horizontal edge in the top row to the label of that edge. Since horizontal edges come in parallel pairs and span precisely two vertices, we have an inverse map as well.
With this formulation we now prove
Theorem 3. The number of ways to choose a subset S ⊂ {1,2, . . . , N} such that S contains q odd elements, r even elements, and no consecutive elements is
n+ 1−r q
n−q r
if N = 2n+ 1 and
n−r q
n−q r
if N = 2n.
Proof. List the parts ofS in order of size and reduce the smallest by 0, the next smallest by 2, the next smallest by 4, and so on (so that the largest number gets reduced by 2(q+r−1)).
This will yield a multiset consisting of qnot necessarily distinct odd numbers between 1 and 2n+ 1−2(q+r−1) = 2(n−q−r+ 1) + 1 if N = 2n+ 1, and between 1 and 2(n−q−r+ 1) if N = 2n, as well asr not necessarily distinct even numbers between 1 and 2(n−q−r+ 1), regardless of whether N is 2n+ 1 or 2n.
Conversely, every such multiset, when you apply the bijection in reverse, you get a set consisting ofqodd numbers andreven numbers in{1,2, . . . ,2n}(resp. {1,2, . . . ,2n+1}), no two of which differ by less than 2.
The number of such multisets is clearly
n−q−r+1 q
× n−q−r+1r
in the first case and n−q−r+2
q
× n−q−r+1r
in the second case (since 2n+ 1 is an additional odd number), where nk
=“nmultichoosek” = n+k−1k
. Since
n−q−r+1 q
× n−q−r+1r
= n−rq n−q
r
resp.
n−q−r+2 q
× n−q−r+1r
= n+1−rq n−q
r
, the claim follows.
Once we know this interpretation for the coefficients of xn+3 (sn), we obtain a proof of the formula for the entire sum, i.e. Theorem 2 and Theorem 5.2 of [4] (Theorem 2.2 of [14]).
It is worth remarking that the extra terms x2n+21 and x2n+22 in Theorem 2 correspond to the extreme case in which one’s subset of {1,2, . . . , N} consists of all the odd numbers in that range.
2.2 Bijective proof of Lemma 1
The recurrence of Lemma 1 can also be proven bijectively by computing in two different ways the sum of the weights of the perfect matchings of the graph GntH3 (the disjoint union of Gn and H3, which has all the vertices and edges of graphs Gn and H3 and no identifications). We provide this proof since this method will be used later on in the (1,4) case.
On the one hand, the sum of the weights of the perfect matchings of Gn is the poly- nomial pn and the sum of the weights of the perfect matchings of H3 is x21 +x22 + 1, so the sum of the weights of the perfect matchings of GntH3 is (x21+x22+ 1)pn.
x
1 1 1 1 1 1 1 1 1
x x
x
x2 1 2 x1 2 1 2
x2 x1 x2 x1 x2 x1 x2
x
The sum of the weights of all perfect matchings of G5tH3 is (x21+x22+ 1)p5.
On the other hand, observe that the graph Gn+1 can be obtained from Gn t H3
by identifying the rightmost vertical edge of Gn with the leftmost vertical edge of H3. Furthermore, there is a weight-preserving bijectionφbetween the set of perfect matchings of the graphGn+1 and the set of perfect matchings of GntH3 that do not simultaneously contain the two rightmost horizontal edges of Gn and the two leftmost horizontal edges of H3 (a set that can also be described as the set of perfect matchings of GntH3 that contain either the rightmost vertical edge of Gn or the leftmost vertical edge of H3 or both). It is slightly easier to describe the inverse bijection φ−1: given a perfect matching of GntH3 that contains either the rightmost vertical edge ofGn or the leftmost vertical edge ofH3 or both, view the matching as a set of edges and push it forward by the gluing
map from GntH3 toGn+1. We obtain a multiset of edges of Gn+1 that contains either 1 or 2 copies of the third vertical edge from the right, and then delete 1 copy of this edge, obtaining a set of edges that contains either 0 or 1 copies of that edge. It is not hard to see that this set of edges is a perfect matching of Gn+1, and that every perfect matching of Gn+1 arises from this operation in a unique fashion. Furthermore, since the vertical edge that we have deleted has weight 1, the operation is weight-preserving.
The perfect matchings ofGntH3 that are not in the range of the bijectionφ are those that consist of a perfect matching ofGn that contains the two rightmost horizontal edges of Gn and a perfect matching of H3 that contains the two leftmost horizontal edges of H3. Removing these edges yields a perfect matching of Gn−1 and a perfect matching of H1. Moreover, every pair consisting of a perfect matching ofGn−1 and a perfect matching of H1 occurs in this fashion. Since the four removed edges have weights that multiply to x21x22, and H1 has just a single matching (of weight 1), we see that the perfect matchings excluded from φ have total weight x21x22pn−1 [3, c.f.].
Remark 1. We can also give a bijective proof of the quadratic recurrence relation (3) by using a technqiue known as graphical condensation which was developed by Eric Kuo [10]. He even gives the unweighted version of this example in his write-up.
Remark 2. As we showed via equation (1), there is a reciprocity that allows us to relate the cluster algebras for the (b, c)- and (c, b)-cases by running the recurrence backwards.
For the (2,2)-case, b = c so we do not get anything new when we run it backwards; we only switch the roles ofx1 andx2. This reciprocity is a special case of the reciprocity that occurs not just for 2-by-n grid graphs, but more generally in the problem of enumerating (not necessarily perfect) matchings ofm-by-n grid graphs, as seen in [1] and [11]. For the (1,4)-case, we will also encounter a type of reciprocity.
Remark 3. We have seen that the sequence of polynomialsqn(x1, x2) satisfies the relation q2n−4q2n−8 =q2n−62 +x2n−61 x2n−82 .
It is worth mentioning that the odd-indexed terms of the sequence satisfy an analogous relation
q2n−3q2n−7 =q22n−5−x2n−61 x2n−82 .
This relation can be proven via Theorem 2.3 of [10]. In fact the sequence of Laurent polynomials {q2n+1/xn1xn2 : n ≥ 0} are the collection of elements of the semicanoncial basis which are not cluster monomials, i.e. not of the form xpnxqn+1 for p, q ≥ 0. These are denoted assn in [4] and [14] and are defined asSn(s1) where Sn(x) is the normalized Chebyshev polynomial of the second kind, Sn(x/2), and s1 = (x21 +x22 + 1)/x1x2. We are thankful to Andrei Zelevinsky for alerting us to this fact. We describe an analogous combinatorial interpretation for the sn’s in the (1,4)-case in subsection 3.4.
3 The (1, 4) case
In this case we let
xn = xn−1+ 1 xn−2
forn odd
= x4n−1+ 1
xn−2 forn even
for n≥3. If we let x1 =x2 = 1, the first few terms of {xn(1,1)} forn ≥3 are:
2,17,9,386,43,8857,206,203321,987,4667522,4729, . . .
Splitting this sequence into two increasing subsequences, we get forn ≥1:
x2n+1 =an = 2,9,43,206,987,4729 (11) x2n+2 =bn = 17,386,8857,203321,4667522. (12) Furthermore, we can run the recurrence backwards and continue the sequence for negative values of n:
. . . ,386,9,17,2,1,1,2,3,41,14,937,67,21506,321,493697,1538,11333521,7369. . . whose negative terms split into two increasing subsequences (forn ≥1)
x−2n+2 =cn= 2,41,937,21506,493697,11333521 (13) x−2n+1 =dn = 3,14,67,321,1538,7369. (14) As in the (2,2)-case, it turns out that this sequence {xn(1,1)} (respectively {xn}) has a combinatorial interpretation as the number (sum of the weights) of perfect matchings in a sequence of graphs. We prove that these graphs, which we again denote as Gn, have the xn’s as their generating functions in the later subsections. We first give the unweighted version of these graphs where graph Gn contains xn(1,1) perfect matchings.
We describe how to assign weights to yield the appropriate Laurent polynomials xn in the next subsection, deferring proof of correctness until the ensuing two subsections. The proof of two recurrences, in sections 3.2 and 3.3, will conclude the proof of Theorem 4. The final subsection provides a combinatorial interpretation for elements of the semicanonical basis that are distinct from cluster monomials.
Definition 2. We will have four types of graphs Gn, one for each of the above four sequences (i.e. for an, bn, cn, and dn). Graphs in all four families are built up from squares (consisting of two horizontal and two vertical edges) and octagons (consisting of two horizontal, two vertical, and four diagonal edges), along with some extra arcs. We describe each family of graphs by type.
Firstly, G3 (a1) is a single square, and G5 (a2) is an octagon surrounded by three squares. While the orientation of this graph will not affect the number of perfect match- ings, for convenience of describing the rest of the sequence G2n+3, we assume the three
squares ofG5 are attached along the eastern, southern, and western edges of the octagon and identify G3 with the eastern square. For n ≥3 the graph associated to an+1, G2n+3, can be inductively built from the graph for an, G2n+1 by attaching a complex consisting of one octagon with two squares attached at its western edge and northern/southern edge (depending on parity). We attach this complex to the western edge of G2n+1, and ad- ditionally adjoin one arc between the northeast (resp. southeast) corner of the southern (resp. northern) square of G2n+3 \G2n+1 and the southeast (resp. northeast) corner of the northern (resp. southern) square ofG2n+1\G2n−1.
We can inductively build up the sequence of graphs corresponding to thedn’s,G−2n−1, analogously. Here G−1, consists of a single octagon with a single square attached along its northern edge. We attach the same complex (one octagon and two squares) except this time we orient it so that the squares are along the northern/southern and eastern edges of the octagon. We then attach the complex so that the eastern square attaches to G−2n+1. Lastly we adjoin one arc between the northwest (resp. southwest) corner of the southern (resp. northern) square ofG−2n−1\G−2n+1 and the southwest (resp. northwest) corner of the northern (resp. southern) square of G−2n+1\G−2n+3.
The graph corresponding to b1, G4, is one octagon surrounded by four squares while the graph corresponding to c1, G0, consists of a single octagon. As in the case of an or dn, for n ≥1, the graphs for bn+1 (G2n+4) and cn+1 (G−2n) are constructed from bn and cn (resp.), but this time we add a complex of an octagon, two squares and an arc onboth sides. Note that this gives these graphs symmetry with respect to rotation by 180◦.
The graphs G2n+2 (bn) consist of a structure of octagons and squares such that there are squares on the two ends, four squares around the center octagon, and additional arcs shifted towards the center (the vertices joined by an arc lie on the vertical edges closest to the central octagon). On the other hand, the graphs G−2n+2 (cn) have a structure of octagons and squares such that the central and two end octagons have only two squares surrounding them, and the additional arcs are shifted towards the outside.
For the reader’s convenience we illustrate these graphs for small n. In our pictures, the extra arcs are curved, and the other edges are line segments. It should be noted that all these graphs are planar, even though it is more convenient to draw them in such a way that the (curved) extra arcs cross the other (straight) edges.
n xn(1,1) Type Graph Gn
−8 493697 c5
−7 321 d4
−6 21506 c4
−5 67 d3
−4 937 c3
−3 14 d2
−2 41 c2
−1 3 d1
0 2 c1
1 1 x1
2 1 x2
3 2 a1
4 17 b1
5 9 a2
6 386 b2
7 43 a3
8 8857 b3
9 206 a4
10 203321 b4
11 987 a5
12 4667522 b5
13 4729 a6
Remark 4. As described above, the sequence of graphs corresponding to thean’s and the dn’s can both be built up inductively. In fact, if one assumes that the graphs associated with dn are “negative” then one can even construct a1 from d1 by “adding” two squares and an octagon. The negative square and octagon cancels with the positive square and octagon, leaving only a square for the graph of a1. (When we construct the graph asso- ciated to a2 from the graph fora1, we do not add an arc as in the n ≥2 case. Similarly, we omit an extra arc when we construct the graph for a1 from the graph for d1. We do not have a “principled” explanation for these exceptions, but we do note that in these two cases, the graph is sufficiently small that there are no candidate vertices to connect by such an arc.)
Comparing graphs with equal numbers of octagons, we find a nice reciprocity between the graph for x2n+3 and the graph for x−2n+1 for n ≥ 1. Namely, the two graphs are isomorphic (up to horizontal and vertical reflection) except for the fact that the graph G2n+3 contains two squares on the left and right ends while graph G−2n+1 lacks these squares. Notice that graphG3 lies outside this pattern since it contains no octagons and instead contains a single square.
Studying the other types of graphs, i.e. those corresponding tobn and cn, we see that in each pair of graphs containing the same number of octagons, there is a nice reciprocity between the two. (Compare the definitions of the graphs associated to thebn’s with those associated to the cn’s.) These two reciprocal relationships reduce into one, i.e. G−n and Gn+4 are reciprocal graphs for all integers n ≥ 0. Recall that a reciprocity also exists (between graphsG−n andGn+3) for the (2,2) case, so perhaps these reciprocities are signs of a more general phenomenon.
3.1 Weighted versions of the graphs
We now turn to the analysis of the sequence of Laurent polynomials xn(x1, x2), and give the graphsGnweights on the various edges. In this case, the denominator depends on the number of faces in the graph, ignoring extra arcs. The exponent ofx1 in the denominator will equal the number of squares while the exponent of x2 will equal the number of octagons. Because of this interpretation, for n 6= 1 or 2 we will rewrite xn as pn(x1,x2)
xsq(n)1 xoct(n)2
where sq(n) and oct(n) are both nonnegative integers. By the description of graphs Gn, we find
sq(n) =
|n−1| −1 forn odd
|2n−2| −2 forn even (15)
oct(n) =
|n2 −1| − 12 for n odd
|n−2| −1 for n even. (16)
To construct these weighted graphs, we take the graphs Gn and assign weights such that each of the squares has one edge of weight x2 and three edges of weight 1 while the octagons have weights alternating between x1 and 1. As an example, consider the following close-up of the graph associated to x10.
The graph associated tox10.
The vertical and horizontal edges colored in green are given weight x2, and the diagonal edges marked in red are given weight x1. All other edges are given weight 1. Notice that the vertical edges weighted x2 lie furthest away from the arcs and the horizontal edges weighted x2 alternate between top and bottom, starting with bottom on the righthand side.
Table of xn for small n:
n xn
−3 (x2+1)3+2xx341+3x41x2+x81 1x22
−2 (x2+1)4+3x41+8x41x2x+6x4 41x22+3x81+4x81x2+x121 1x32
−1 (x2x+1)+x41
1x2
0 x41x+12
1 x1
2 x2
3 x2x+1
1
4 (x2+1)x4 4+x41
1x2
5 (x2+1)x3 3+x41
1x2
6 (x2+1)8+3x41+16x41x2+34x41x22+36x41xx32+19x8 41x42+4x41x52+3x81+8x81x2+6x81x22+x121 1x32
7 (x2+1)5+2x41+5xx5 41x2+3x41x22+x81 1x22
We now wish to prove the following.
Theorem 4. For the case (b, c) = (1,4), the Laurent polynomials xn satisfy xn(x1, x2) =pn(x1, x2)/mn(x1, x2) for n6= 1,2
where pn is the weighted sum over all perfect matchings in Gn given in definition 2, with weighting as in the preceding paragraph; and mn = xsq(n)1 xoct(n)2 with sq(n) given by (15) and oct(n) given by (16).
In the above table, we see that Theorem 4 is true for small values ofn, thus it suffices to prove that pn(x1, x2)/xsq(n)1 xoct(n)2 satisfies the same periodic quadratic recurrences as Laurent polynomials xn. By the definition ofmn(x1, x2), it suffices to verify the following two recurrences:
p2n+1p2n+3 =p2n+2+x|4n+2|−21 x|2n|−12 (17) p2np2n+2 =p42n+1+x|8n|−41 x|4n−2|−22 . (18)
3.2 Proof of the first recurrence
We use a decomposition of superimposed graphs to prove equality (17). Unlike Kuo’s technique of graphical condensation, we will not use a central graph containing multi- matchings, but will instead use superpositions that only overlap on one edge, as in the bijective proof of Lemma 1. First, letG2n+1 be defined as in the previous subsection, and let H2n+3 (resp. H2n−1) be constructed by taking graphG2n+3 (resp. G2n−1), reflecting it horizontally, and then rotating the leftmost square upwards. For convenience of notation we will henceforth let M = 2n+ 1 so that we can abbreviate these two cases as HM±2
(Throughout this section we choose the sign of HM±2, GM±2 and GM±1 by using H2n+3, G2n+3, and G2n+2 if n ≥ 1 and H2n−1, G2n−1 and G2n if n ≤ −1.) This reflection and rotation will not change the number (or sum of the weights) of perfect matchings. Thus the sum of the weights of perfect matchings in the graph HM±2 also equals pM±2. Also, we will let K2 denote the graph consisting of two vertices and a single edge connecting them.
The graph GM±1 can be decomposed as the union of the graphs GM, HM±2 and K2 where GM and HM±2 are joined together on an overlapping edge (the rightmost edge of GM and the leftmost edge of HM±2). The graph K2 is joined to these graphs so that it connects to the bottom-right (bottom-left) vertex of the rightmost octagon of GM and the top-right (top-left) vertex of the leftmost octagon of H2n+3 (H2n−1). See the picture below for an example withG10. The blue arc in the middle representsK2. We will denote this decomposition as
GM±1 = GM ∪HM±2∪K2.
As in subsection 2.2, we let GtH be the graph formed by the disjoint union of graph Gand graphH. A perfect matching ofGM and a perfect matching ofHM±2 will meet at the edge of incidence in one of four ways (verticals meeting, horizontals meeting vertical, verticals meeting diagonals, or horizontals meeting diagonals).
In three of the cases, edges of weight 1 are utilized, and we can bijectively associate a perfect matching of GM t HM±2 to a perfect matching of GM±1 by removing an edge of weight 1 on the overlap; though it is impossible to map to a perfect matching of GM±1 that uses the edge of K2 in this way. This bijection is analogous to the one discussed in subsection 2.2. Thus we have a weight-preserving bijection between {perfect matchings ofGM±1 − K2 } and the set {perfect matchings of GM t HM±2} − {pairs with nontrivial incidence (horizontals meeting diagonals) } where by abuse of notation we here and henceforth let G−K2 refer to the subgraph of G with K2’s edge deleted (without deleting any vertices). Thus proving p2n+1p2n+3−p2n+2 = pMpM+2 −pM+1 = x|4n+2|−21 x|2n|−12 reduces to proving the following claim.
Proposition 2. The sum of the weights of all perfect matchings ofGM±1 that containsK2
isx|4n+2|−21 x|2n|−12 less than the sum of the weights of all perfect matchings ofGM t HM±2
that have nontrivial incidence.
Before giving the proof of this Proposition we introduce a new family of graphs that will allow us to write out several steps of this proof more elegantly. For n ≥1, we let ˜G2n+1
be the graph obtained from G2n+1 by deleting the outer square on the extreme right. If n ≤ −1, we let ˜G2n+1 be the graph obtained from G2n+1 by adjoining an outer square on the extreme right. For example, ˜G9 and ˜G−7 are shown below. We let ˜p2n+1 be the sum of the weights of perfect matchings in ˜G2n+1. Notice that this construction creates a reciprocity such that graphs ˜G−M = ˜G−2n−1 and ˜GM+4 = ˜G2n+5 are isomorphic.
~ G ~
G
−7
9
The polynomials p2n+1 and ˜p2n+1 are related in a very simple way.
Lemma 3.
p2n+1 = (x2 + 1)˜p2n+1−x41x2p˜2n−1 for n ≥2, (19) p2n+1 = (x41 +x2+ 1)˜p2n+3 −x41x22p˜2n+5 for n ≤ −2. (20) Proof. The proof of Lemma 3 follows the same logic as the inclusion-exclusion argument of section 2.2 that proved Lemma 1. In this case, we use the fact that we can construct G2n+1 by adjoining the graph G3 (resp. G−1) to ˜G2n+1 (resp. ˜G2n+3) on the right for n≥2 (resp. n≤ −2). It is clear thatp3 =x2+ 1 (resp. p−1 =x41+x2+ 1) and the only perfect matchings we must exclude are those that contain a pair of diagonals meeting a pair of horizontals. For the n ≤ −2 case, we must also add in those perfect matchings that use the rightmost arc ofG2n+1.
Proof. (Prop. 2) By analyzing how the inclusion of certain key edges in a perfect matching dictates how the rest of the perfect matching must look, we arrive at the expressions
x41x2(x2+ 1)p2n−1p˜2n+1+x81x22p˜2n−3p˜2n+1 for n ≥2 (21) x41x2p2n+3p˜2n+1+x41x22p˜2n+5p˜2n+1 for n ≤ −2 (22) for the sum of the weights of all perfect matchings ofGMtHM±2 with nontrivial incidence (horizontals meeting diagonals), and expressions
x41x2(x2+ 1)˜p2n−1p2n+1+x81x22p˜22n−1 for n ≥2 (23) x41x2p˜2n+3p2n+1+x41x22p˜22n+3 for n ≤ −2 (24) for the sum of the weights of all perfect matchings of GM±1 using the K2’s edge.
To prove Proposition 2, it suffices to prove (21) = (23) +x4n1 x2n−12 and (22) = (24) + x−4n−41 x−2n−12 . To do so, we prove equalities
x41x2(x2 + 1)(p2n−1p˜2n+1−p2n+1p˜2n−1) =x4n1 x2n−22 +x4n1 x2n−12 (25) x81x22(˜p22n−1−p˜2n+1p˜2n−3) =x4n1 x2n−22 (26) for n≥2 and equalities
x41x2(p2n+3p˜2n+1−p2n+1p˜2n+3) =x−4n1 x−2n2 +x−4n1 x−2n+12 (27) x41x22(˜p22n+3−p˜2n+1p˜2n+5) =x−4n1 x−2n2 (28) for n ≤ −2 and then subtract (25)−(26) and (27)−(28). After shifting indices and dividing both sides of equations (25) through (28) to normalize, we obtain that it suffices to prove
Lemma 4.
p2n−1p˜2n+1−p2n+1p˜2n−1 =x4n−41 x2n−32 for n≥2 (29)
=−x−4n1 x−2n+12 (x2+ 1) for n≤ −2 (30)
˜
p22n+1−p˜2n−1p˜2n+3 =x4n−41 x2n−22 for n≥2 (31)
=x−4n1 x−2n2 for n≤ −2. (32) We prove equations (31) and (32) simultaneously since ˜p2n+1 = ˜p−2n+3. We prove (31) by making superimposed graphs involving ˜G2n−1 and ˜G2n+3 and comparing it to the superimposed graph of ˜G2n+1 with itself. Perhaps Kuo’s technique could be adapted to prove (31), but instead we consider a superposition overlapping over one edge, as we did earlier in this proof. Our superimposed graph thus resembles ˜G4n−1, with a double edge somewhere in the middle and a missing arc. Analogous to the analysis that allowed us to reduce from recurrence (17) to Proposition 2, we reduce our attention to the cases where gluing together ˜G2n−1 and ˜G2n+3 and decomposing back into two copies of ˜G2n+1
would not be allowed (or vice versa). This entails focusing on cases where horizontals meet diagonals at the double edge, or the arc appearing exclusively in that decomposition (and not the other) appears in the matching.
After accounting for the possible perfect matchings, we find the following two expres- sions
˜
p22n−1x41x2(x2+ 1) + ˜p2n−3p˜2n+1x41x2 (33)
˜
p2n−3p˜2n+1x41x2(x2+ 1) + ˜p22n−1x41x2 (34) which represent the sum of the weights of nontrivial perfect matchings in the superpo- sitions of ˜G2n+1 and ˜G2n+1 (resp. ˜G2n−1 and ˜G2n+3). Taking the difference of these two expressions, we find that
˜
p22n+1−p˜2n−1p˜2n+3 =x41x22(˜p22n−1−p˜2n−3p˜2n+1).
So after a simple check of the base case (˜p25 − p˜3p˜7 = x41x22) we get equation (31) by induction.
We easily derive (29) from equations (19) and (31):
p2n−1p˜2n+1−p2n+1p˜2n−1 = ((x2+ 1)˜p2n−1−x41x2p˜2n−3)˜p2n+1−((x2+ 1)˜p2n+1−x41x2p˜2n−1)˜p2n−1 =
x41x2(˜p22n−1−p˜2n−3p˜2n+1) =x4n−41 x2n−32 . We can also derive (30) from (32) but we first need to prove the following Lemma:
Lemma 5.
˜
p2n+1p˜2n−1−p˜2n−3p˜2n+3 =x4n−81 x2n−42 (x41+ (x2+ 1)2) for n ≥2, (35)
˜
p2n+1p˜2n−1−p˜2n−3p˜2n+3 =x−4n1 x−2n2 (x41+ (x2+ 1)2) for n ≤ −2. (36)
