Some REACH Research Topics for Spring 2003 (last revised: March 13, 2003) Here are some ideas for topics that merit exploration. See which ones interest you, and ask me questions if you want to know more! Since REACH will be folding up its tent at the end of the semester, after April 1 your focus should be on writing up what you've done: either an article that can be submitted for publication (or at least to the xxx e-print archive) or a summary of your efforts that'll enable other people to pick up where you left off. But this is only a general time-table, not a hard and fast rule. If in mid-April you're still on the trail of something neat, keep at it. The descriptions that appear below are not intended to be complete; if I tried to explain ALL the terms that appear below, I'd end up writing a book, not a 1000-line email memo (which is long enough as it is)!. But I hope to give you enough information to enable you to decide what follow-up questions to ask me, and maybe enough information to help you decide what project you want to work on. If you have an idea for a project of your own, let me know. I don't mean for this list to substitute for your own creativity. --------------------------- A. RECIPROCITY 1. There are some natural one-parameter families of connected graphs (like the family __ __ __ __ /\ /\ / /\ /\ /\ /\ / /__\ /__\/ /__\/__\ /__\/__\/ .... discussed during the first meeting of REACH this semester) for which one can count the spanning trees in the nth graph in the family when n is positive, with the a priori knowledge that the resulting sequence must satisfy a linear recurrence relation. If the recurrence relation is "monic" (side question: are there general conditions under which this is guaranteed to happen?), then one can extend this recurrence in reverse and still get integers. Do these new numbers have any combinatorial meaning, and do they relate in any systematic way to the numbers we began with? Note that this is reminiscent of the work that has been done in REACH before, except that instead of the dimer model (aka perfect matchings) or the monomer-dimer model, we're looking at the spanning tree model. Incidentally, there's a connection between spanning trees and perfect matchings that might be relevant here. The original case is due to Temperley, but it generalizes to spanning trees of arbitrary planar graphs. E.g., the spanning trees of the fourth graph given above correspond bijectively to perfect matchings of o - - - - - o - - - - - o - - - - - o / \ | / \ | / \ | / \ | / \ | / \ | / \ o / \ o / \ / \ / \ / \ o o o o o / \ / \ / \ / \ / / o \ / o \ / / | \ / | \ / / | \ / | \ / / | \ / | \ / o - - - - - o - - - - - o - - - - - o - - - - - o See the article "Trees and Matchings", available at http://www.combinatorics.org/Volume_7/Abstracts/v7i1r25.html 2. It seems that reciprocity operations sometimes don't commute with each other; I'd like to understand this better. Here are two examples: (a) There's a natural way to extend the domain of definition of the binomial coefficents C(n,k) so that n can be any integer (indeed any real number): C(n,k) = n(n-1)(n-2)...(n-k+1)/k!. But we run into problems when we try to extend (n choose k) such that both n and k are arbitrary integers. We'd like to define C(n,k) for all integers n and k so that C(n,k)=(-1)^k C(-n+k-1,k) (since this equation hold for our original definition when both sides of an equation are defined). Likewise for the equation C(n,k)=C(n,n-k). But these equations are incompatible, since applying these two transformations alternately three times we get C(n,k) = -C(n,k): C(n, k) = (-1)^k C(-n + k - 1, k) = (-1)^k C(-n + k - 1, -n - 1) = (-1)^(n+k+1) C(-k - 1, -n - 1) = (-1)^(n+k+1) C(-k - 1, -k + n) = -C(n, -k + n) = -C(n, k). (b) Let T(m,n) be the number of domino tilings of a rectangle of height m and width n. For fixed m, the numbers T(m,n) satisfy a linear recurrence, which we can use to define T(m,n) with n<0. This for instance lets us define T(1,-2), T(2,-2,), T(3,-2), ... But these numbers too satisfy a recurrence, which we can run in reverse to define (say) T(-3,-2). The problem is, we don't get the same answer if we define T(-3,-2) by looking at the numbers T(-3,0), T(-3,2), T(-3,4), ... and running *that* recurrence backwards. What's going on? I think that the generating-functions view of reciprocity is going to reveal a big part of the answer here; see Kyle's article on reciprocity relations for monomer-dimer enumeration. 3. The physicists Lu and Wu have looked at enumeration of perfect matchings on variants of the square grid, obtained by putting the graph on a manifold (or manifold with boundary). The simplest case with non-trivial topology is the square grid on a cylinder, but other possibilities are the Mobius strip, the Klein bottle, and the cross-cap. See cond-mat/0110035 (like all such references, this is a short-hand for xxx.lanl.gov/abs/cond-mat/0110035). Interestingly, the cross-cap case has not been tackled at all, as far as I know. That is: Consider graphs like | | | | -A---B---C---D- | | | | -E---F---F---G- | | | | -I---J---K---L- | | | | -M---N---O---P- | | | | in which the extra edges connect A to P (twice), B to O, C to N, D to M (twice), G to I, and L to E. We'd like to count perfect matchings of such a graph. Kasteleyn came up with a general procedure for counting perfect matchings on graphs imbedded in surfaces of small genus. You can use his method to express the number of matchings in terms of a handful of determinants (four, I think). Kasteleyn matrices typically have nice eigenvalues that you can express in closed form, allowing you to calculate the determinant as the product of the eigenvalues. Not only are the eigenvalues nice --- the eigenvectors are nice too. In fact, the way you find the eigenvalues is by finding the eigenvectors at the same time, by thinking of the eigenvectors as eigenfunctions of a graph-theoretic analogue of the Laplacian operator and doing a simplified form of discrete Fourier analysis. It isn't very combinatorial, but I've calculated some Kasteleyn determinants in my day and can certainly offer advice and pointers to the relevant literature (much of which is fairly accessible). At the end of the day, I'd want a formula for counting the perfect matchings on the m-by-n cross-cap, which would let us verify (or refute!) that for each fixed m, the sequence whose nth term is the number of perfect matchings of the m-by-n cross-cap satisfies a recurrence which, if run in reverse, has the sort of symmetry (up to a predictable sign factor) that I've been calling "reciprocity". Even if you don't feel like mastering the Fourier apparatus, it'd be good to have some numbers that would give us at least a preliminary indication of whether reciprocity holds or not. This would involve doing computer experiments with software that can count perfect matchings of non-planar graphs. The existing software isn't going to let you get very far, since it uses a brute-force approach to enumeration. What someone might do is write some Maple code that, for each m and n, computes the number of matchings via Kasteleyn determinants. See also topic C2, which is related. 4. We could try to extend our work on reciprocity beyond perfect matchings (and beyond spanning trees: see topic A1) and into the broader domain of tiling. I think ribbon-tilings are a natural place to look. E.g., consider the four tiles _ _ _ _ |_| _ _ _ _|_| |_|_| |_| |_|_|_| , |_|_| , |_| , |_| . These are the ribbon tiles of size 3. We know that for any fixed m, the sequence whose nth term is the number of tilings of an m-by-n rectangle using ribbon tiles of size 3 satisfies a linear recurrence, and if it's monic (as I've observed in the cases m=2 and m=3) we can run it in reverse to get a two-sided integer sequence (some of whose terms might be negative). What can be said here? If we use a multivariate version of the recurrence, do we observe "coherence" when we pass to the n<0 regime (that is, do we observe that for each fixed n, all the terms that contribute have the same sign)? Do we have strong monicity (all the coefficients are equal to one another)? If so, then the algebra is hiding a combinatorial interpretation, which we should bring to light. Speaking of ribbon tilings: Can we use Scott Sheffield's height-functions to generate random ribbon tilings of finite regions? The big obstacle is that there isn't a nice one-dimensional height-function that turns the set of tilings into a nice distributive lattice. Consequently, the method of coupling-from-the-past that David Wilson and I developed back in the 1990s cannot be applied without some extra work. This would be a challenge but it might be do-able. If nothing else, one might do a naive Monte Carlo simulation that randomizes a ribbon tiling (using the moves that Moore and Pak have studied) until it "seems random", to see if interesting boundary effects crop up. 5. A very broad question is, for what sorts of tile-sets does it appear to be the case that the sequence whose nth term counts tilings of the m-by-n rectangle satisfies a linear recurrence which, if run in reverse, gives INTEGERS? There are two ways in which this can fail. First, it's possible that the sequence resembles the sequence 1,1,2,3,4,5,... in the sense that the governing recurrence only kicks in eventually, and not at the start; in this case, there's no natural way to extend backward. Second, it's possible that the sequence resembles that sequence 1,2,4,8,... in the sense that when you run the recurrence in reverse, you get fractions. (Generating functions give a natural language for talking about these two cases, by the way.) I don't know if there are any big theorems to be proved here, but one could play around with the strip-tiling program using various sorts of tile-sets to look for patterns. The outcome of this exploration would be various nice tile-sets that my students at Wisconsin can look at in more detail next year, in search of reciprocity phenomena. 6. The strip-tiling program is very good at what it does, but if one is trying to find reciprocity phenomena, it does too much (it actually finds the generating function explicitly, which isn't always needed) and too little (it doesn't handle the multivariate polynomials which one needs if one really wants the algebra to "carry" the combinatorics). Someone could write some software tailored to the task of finding multivariate recurrences associated with tiling problems and extending them backwards. --------------------------- B. TWO-DIMENSIONAL RECURRENCES 1. Label the vertices of a convex n-gon with numbers from 1 to n, and let [ij] denote the edge or diagonal joining distinct vertices i and j (I'll say "line" instead of "edge or diagonal" from now on). We are going to look at ways of assigning quantities Q(i,j) to all the lines [ij] in such a way that Q(i,j) = Q(j,i) for all i,j (so that Q(i,j) only depends on the endpoints of the line and not on the order in which we write them) and, more importantly, (*) Q(a,b) Q(c,d) + Q(b,c) Q(a,d) = Q(a,c) Q(b,d) whenever a,b,c,d are in cyclic order --- that is, whenever the points form an inscribed quadrilateral with sides [a,b],[b,c],[c,d],[a,d] and diagonals [a,c] and [b,d]. Some of the Q's will be formal variables; the rest will be rational functions of the formal variables. More specifically, dissect the n-gon into triangles by n-2 non-crossing diagonals, and assign a formal variable x[i,j] to each edge of the polygon or diagonal of the triangulation. This set of variables will be called the basis. (E.g., for n=5: 3 * v / / \ \ w / / \ \ 2 / / \ \ 4 * / \ * \ z / \ y / \ / \ / u \ / \ / x \ / \ / \ / \ / *-----------* 1 t 5 Here I write t = x[1,5], u=x[1,2], v=x[2,3], w=x[3,4], x=x[4,5], y=x[3,5], and z=x[1,3] for short.) Then there is a unique way of writing down all the other Q(i,j)'s in terms of our basis, so that the rule (*) is satisfied. (E.g., Q[1,4] must equal (Q[1,3]Q[4,5]+Q[3,4]Q[1,5])/Q[3,5] = (zx+wt)/y and Q[2,5] must equal (Q[1,2]Q[3,5]+Q[2,3]Q[1,5])/Q[1,3] = (uy+vt)/z. We can compute Q[2,4] as either (Q[1,2]Q[3,4]+Q[2,3]Q[1,4])/Q[1,3] or (Q[2,3]Q[4,5]+Q[3,4]Q[2,5])/Q[3,5]; both expressions reduce to (uwy+vxz+vwt)/yz.) Each Q[ij] is a Laurent polynomial, and Dylan Thurston conjectures that in which every coefficient equals 1. Can you prove this and give a combinatorial recipe for these Laurent polynomials, relating them to the combinatorics of the tiling? If you want to work on this, you might want to read the original Conway and Coxeter article on frieze patterns, which inspired this example. Also, if you like this problem, you might want to do a little digging to see if the answer is already known. 2. Consider the infinite array formed by taking two infinite rows of formal variables ... x(-2) x(-1) x(0) x(1) x(2) ... ... y(-2) y(-1) y(0) y(1) y(2) ... and adding infinitely many rows beneath, where each new entry is determined from four earlier (higher) entries according to the rule AE=BD+CC, where A, B, C, D, and E are as shown below: A B C D E (E.g., the entry below y(0) is (y(0)^2 + y(-1) y(1)) / x(0). Every other entry in the third row looks like this, with its indices shifted by some fixed amount. We call it the central entry in the third row.) What Laurent monomials occur in the central entry in the nth row? Can one say how many such monomials there are? (And what if one changes the plus-sign in the recurrence to a minus-sign?) Gabriel did some work on this a year ago, but never wrote it up. (Ask him to tell you about "dugongs".) 3. What if we start our two-dimensional recurrence with four rows, and require each tilted 3-by-3 subdeterminant to equal 1? That is, we start with ... a b c d e f ... ... g h i j k ... ... l m n o ... ... p q r ... and then expand to ... a b c d e f ... ... g h i j k ... ... l m n o ... ... p q r ... ... s t ... ... u ... ... by requiring that the matrices [c i n] [d j o] [i n r] [h m q] [i n r] [m q t] [l p s], [m q t], [p s u], ... all have determinant 1. Dylan noticed that the new entries s,t,u,... can be expressed as Laurent polynomials not in the original variables but in a new collection of variables, consisting of: ..., g, h, i, j, k, ... (the entries in the second row); ..., l, m, n, o, ... (the entries in the third row); ..., bl-gh, cm-hi, dn-ij, eo-jk, ... (the determinants of the 2-by-2 matrices that lie in the first through third rows); and ..., hp-lm, iq-mn, jr-no, ... (the determinants of the 2-by-2 matrices that lie in the second through fourth rows). When we write the new entries in this way, do we always get a Laurent polynomial in which every coefficient is 1? Can we find a nice combinatorial interpretation? By the way, Dylan showed me that there's a nice way to see this as a degenerate case of Kuo condensation, in much the same way as the frieze recurrence f(n,k) = (f(n-1,k-1) f(n-1,k+1) + 1) / f(n-2,k). Just as the frieze recurrence related to perfect matchings of the 2-by-2n grid (viewed as sitting inside an Aztec diamond), so does this new recurrence relate to perfect matchings of graphs that look like *---*---*---* | | | | *---*---*---*---*---* | | | | | | *---*---*---*---*---* So there's likely to be a generalization of this that'll tie in nicely with the work that the Aztec octagons team is doing (see C1). 4. David Speyer and Reid Barton, independently of one another, have studied a hybrid between friezes and walls (dubbed "number fences"), governed by the recurrence rule AE=BD+C, where A, B, C, D, and E are as shown below: A B C D E (Cf. topic B2.) A related recurrence is A B C D E (a tilted version of former recurrence). In both cases, all entries below the initial rows are Laurent polynomials (this was proved by Speyer for the former case, and it is empirically true in the second case and probably not too hard to prove); moreover, it appears that all the coefficients are 1. If this is true, then these Laurent polynomials encode objects that provide combinatorial interpretations to the sequences 1, 1, 2, 6, 21, 77, ... and 1,1,1,1,2,3,5,13,22,41,111,191,... , satisfying the respective recurrence relations f(n) = (f(n-1)^2 + f(n-1)) / f(n-2) and f(n) = (f(n-1) f(n-3) + f(n-2)) / f(n-4). (The latter of these was invented by Dana Scott, and is mentioned in the original David Gale article on Somos sequences.) For more on David Speyer's work, see http://www.math.harvard.edu/~propp/reach/speyer/stuff.ps (or you can change "stuff.ps" to "stuff.pdf" if you prefer PDF files). For more on Reid's work, see http://web.mit.edu/rwbarton/www/reach/ . 5. The system of joint recurrences S_{n,k} * S_{n-2,k} = S_{n-1,k-1} S_{n-1,k+1} + 1 T_{n,k} * S_{n-2,k} = T_{n-1,k-1} S_{n-1,k+1} + 1 M_{n,k} * S_{n-2,k} = T_{n-1,k-1} T_{n-1,k+1} + 1 (with S_{n,k}, T_{n,k}, M_{n,k} equal to formal indeterminates for n = 0 or 1) appear to give rise to Laurent polynomials with all oefficients equal to 1. Can you prove this (and give a combinatorial interpretation)? Trevor Bass was planning to look into this at some point, as he has an interest in the recurrences s_n(a) * s_{n-2}(a) = s_{n-1}(a)^2 + 1 t_n(a) * s_{n-2}(a) = t_{n-1}(a) * s_{n-1}(a) + 1 m_n(a) * s_{n-2}(a) = t_{n-1}(a)^2 + 1 I imagine that there are a lot of ways to exploit the basic gimmick of this problem to discover many other systems of joint recurrences exhibiting the Laurent property. --------------------------- C. MATCHINGS OF SQUARE GRIDS 1. Kuo condensation, applied to suitably weighted Aztec diamonds (with some edges having weight 1 and others having weight 0) gives a formula expressing the number of perfect matchings of an m-by-n rectangle in terms of six numbers that count perfect matchings of various subgraphs. (See http://www.cs.berkeley.edu/~ekuo/condensation.ps for the current version of Eric Kuo's write-up.) Kuo condensation also gives a formula expressing the number of perfect matchings of these subgraphs in terms of various sub-sub-graphs. Treating this formula as a recurrence relation and iterating it, we find that the real picture is in some ways five-dimensional. Specifically, there are regions called "Aztec octagons" (which simultaneously generalize both rectangles and Aztec diamonds) that are described by five parameters, and Kuo condensation gives a way to count the matchings of an Aztec octagon in terms of the number of matchings of smaller Aztec octagons, via a quadratic recurrence. One can apply the quadratic recurrence in reverse, and count the perfect matchings of a small Aztec octagon in terms of the number of matchings of larger Aztec octagons. One context in which this might be useful is in the study of reciprocity. Specifically, we might want to see whether the recurrence gives us a natural way to extrapolate the number of perfect matchings of m-by-n rectangles into the regime where m and n are both negative. Does this procedure work, or does it run into a wall of some kind? 2. This is kind of a long shot, but: is there anything like Kuo condensation for matchings on a square grid on a cylinder or a torus? Even if this can't be achieved, it would be good to have a purely combinatorial understanding of reciprocity for perfect matchings of square grids on a cylinder or torus. (See topic A3.) David Speyer did some work on this; it would be good to perfect and publish it. 3. Generalized domino shuffling as described in http://front.math.ucdavis.edu/math.CO/0111034 is a general approach to the study of perfect matchings of weighted Aztec diamonds, for purposes of enumeration, probabilistic analysis, and random generation. It is a consequence of a basic lemma called "urban renewal". (In fact, performing the urban renewal transformation everywhere exactly once is equivalent to one round of shuffling.) Kuo condensation is another approach to the study of perfect matchings of weighted Aztec diamonds. I ask: What is the precise nature of the relationship between domino shuffling and Kuo condensation? For a long time, I've felt that there's a unified story, in which generalized domino shuffling is a bottom-up description of the story and Kuo condensation is a top-down description of the story. But I've had some trouble figuring out what this story is. One way to piece this together would be to get an exact formula for the edge-weights of a graph derived by several rounds of domino shuffling. Perhaps this question is best approached if one broadens it, so that "several rounds of domino shuffling" becomes "several applications of local urban renewal" (where the number of applications of the urban renewal transformation can differ in different parts of the graph). I think this is all a part of the crosses-and-wrenches picture, so perhaps my question has already been answered. But if so, the answer deserves to be written up. 4. Hal Canary, while an undergraduate at the University of Wisconsin, did a study of certain sorts of domino tilings of Aztec diamonds, and succeeded in proving that the tilings in question are in bijection with what are called "Baxter permutations". More specifically, if we write a domino tiling of an Aztec diamond as a compatible pair of alternating sign matrices (as described in http://www.math.wisc.edu/~propp/aztec.ps.gz), then the special tilings studied by Canary are those for which the two ASMs are just permutation matrices. If you prefer, you can think of the octahedron recurrence run on standard initial conditions, resulting in Laurent polynomials with 2^(n(n+1)/2) terms. Each term involves at least 2n+1 variables; the ones that involve exactly 2n+1 variables are the ones that corerspond to Baxter permutations. (I won't define Baxter permutations for you, but you can easily find the definition on the internet.) I'd like to see this work get published, so one of you could explore the possibility of teaming up with Hal to get it finished. While you're at it, you might explore a number of related issues. E.g., is there an analogous story for the cube recurrence? or for tilted versions of the octahedron recurrence (e.g. the ones that are associated with Somos sequences)? I can send a copy of Hal's article to anyone who's interested in working on this. 5. There exist unique Laurent polynomials P(-1), Q(-1), P(0), Q(0), P(1), Q(1), P(2), Q(2), etc. (in the variables x, y, z, and w), satisfying the initial conditions P_{-1} = x, P_{0} = y, Q_{-1} = z, Q_{0} = w and the linked recurrences P_n * P_n + d * Q_n * Q_n P_{n+1} = ------------------------- P_{n-1} P_n * P_n + e * Q_n * Q_n Q_{n+1} = ------------------------- Q_{n-1} (with initial conditions P_{-1} = x, P_{0} = y, Q_{-1} = 1, Q_{0} = 1). These Laurent polynomials have a combinatorial interpretation in terms of the dimer model on a square grid. I've taken a stab at writing down what it looks like (details available on request), but someone should really write this up, and also make a more detailed study of linked recurrences of this kind. 6. Kuo condensation gives a recurrence relation for weighted perfect matchings of Aztec diamond graphs; it's an extension of the octahedron recurrence. Indeed, if we're enumerating perfect matchings of Aztec diamond graphs using a "face-weighting scheme", the Kuo condensation is just the standard octahedron recurrence. On the other hand, if we're using an "edge-weighting scheme", then Kuo condensation is a variant of the octahedron recurrence. Someone should try to generalize all of the above to the context of diabolo tilings of fortresses (or rather perfect matchings of the associated dual graphs, which are built up from octagons and squares). This should yield interesting variants of the octahedron recurrence, which could in turn give rise to different combinatorial objects if we ran the variant recurrences with different initial conditions. Note that there's a standard operation for turning problems about perfect matchings of fortress-graphs into problems about perfect matchings of weighted Aztec diamond graphs, and this would fit into the picture. A different problem with a similar flavor is coming up with edge- and face-variable recurrences for lozenge tilings of diabolos, or (equivalently) perfect matchings of "honeycomb hexagons". Note that quadratic recurrences for honeycomb hexagons are already known (in fact, two different ones are known; see page 25 of http://www.math.wisc.edu/~propp/FOR.pdf). I would be particularly interested in seeing what the quadratic recurrence for q-weighted honeycomb hexagons is, since I plan to cite this formula at a talk that I'll be giving at a conference in Florida next month. Whoever can find this formula for me will certainly be thanked during my talk! Also, as in topic C1, we can try to run these recurrences in reverse, so see if they lead to any algebraically natural extrapolations of combinatorial functions into the negative regime. 7. Can we put Randall-paths into an algebraic setting, via recurrences? Or is this sort of not-quite-local information a tiling inherently not amenable to these sort of urban-renewal-ish algebraic relations? --------------------------- D. MARKOV TRIPLES AND BEYOND 1. Past members of REACH have come to a fairly good understanding of the sorts of Laurent polynomials that result from iterating the operations (x,y,z) -> (x',y,z) (x,y,z) -> (x,y',z) (x,y,z) -> (x,y,z') where (*) xx'=yy+zz, yy'=xx+zz, and zz'=xx+yy . (If "yy" looks weird to you, just think of it as y^2. Etc.) What about (**) xx'=yy-zz, yy'=zz-xx, zz'=xx-yy ? Note that if we count the Laurent monomials in (*), we get the nicely Fibonacci-ish sequence 1,2,4,9,21,51,127,322,826,2135,..., each of whose terms is either the square of a Fibonacci number or the product of two Fibonacci numbers (was this ever explained by the Markov numbers group?). On the other hand, if we count the Laurent monomials in (**), we get get the different (but also Fibonacci-ish) sequence 1,2,4,10,25,65,169,442,1156,..., whose nth term is given by (F(2n-1) + F(n+1))/2 where F(n) is a Fibonacci number. 2. Another cluster-algebra we could try to understand combinatorially is the one given by xx'=yy+yz+zz, yy'=xx+xz+zz, and zz'=xx+xy+yy. 3. There's also xx' = yy+zz+y+z, yy' = xx+zz+x+z, and zz' = xx+yy+x+y. --------------------------- E. THREE-TERM GALE-ROBINSON This section is devoted to sequences arising as solutions to recurrences of the form a(n) a(n-m) = a(n-i) a(n-m+i) + a(n-j) a(n-m+j) (with m, i, j fixed and n going from 0 to infinity, or even from minus infinity to plus infinity). 1. In Spring 2002, David Speyer showed how the terms of such a sequence (with initial conditions 1,1,...,1) can be understood combinatorially, via perfect matchings of suitable graphs or, equivalently, arrays of numbers satisfying certain equations and inequalities (though the description of the equations and inequalities is only implicit, and could use some clarification). Actually, the second interpretation came first, chronologically: David derived the matchings interpretation from the arrays-of-numbers interpretation.) David's approach was very general in principle (applying to a wide variety of initial conditions for the octahedron recurrence, and not just the tilted slabs that correspond to three-term Gale-Robinson recurrences), but in some respects unwieldy; although the method can be applied successfully to any particular three-term Gale-Robinson recurrence, a combinatorial understanding of three-term Gale-Robinson recurrences in general came out of the more focussed investigation of Mireille Bousquet-Melou and Julian West. (For an example of the sorts of graphs that arise, see the Spring 2002 REACH tee-shirt, which you can access from the REACH home-page.) Once the Bousquet-Melou, Propp, and West article gets written, an urgent task will be to bring these two streams of research together, and to show how they relate to one another. In particular, someone should interpret the "pinecone graphs" of Bousquet-Melou and West in terms of the crosses-and-wrenches operation of Carroll and Speyer, and connect the matchings picture with the numerical picture of arrays of numbers satisfying certain constraints on "wedge-sums". While we are studying these wedge-sums, it might be interesting for us to understand these arrays as overlays, in much the same way as the arrays representing domino tilings of Aztec diamonds can (and often should!) be viewed as pairs of "compatible" alternating sign matrices, superimposed. One open (or sort-of open) issue connected with Gale-Robinson recurrence that is slightly embarrassing to me has to do with positivity of coefficients of Laurent polynomials associated with the recurrence. One can replace a(n) a(n-m) = a(n-i) a(n-m+i) + a(n-j) a(n-m+j) by a(n) a(n-m) = x a(n-i) a(n-m+i) + y a(n-j) a(n-m+j) and use a(1) = u_1, a(2) = u_2, ..., a(m) = u_m as one's initial conditions (instead of a(1) = a(2) = ... = a(m) = 1); then it turns out (and has indeed been proved) that a(m+1), a(m+2), etc. can all be expressed as Laurent polynomials in the variables x, y, u_1, u_2, ..., u_m. What _hasn't_ been proved (but appears to be true) is that all the coefficients of these Laurent polynomials are positive. I claimed over a year ago that "my students and I have proved positivity of these coefficients" (or words to that effect), but no proof has been written down! Finding a proof requires nothing more than finding combinatorial interpretations of the coefficients of these polynomials. I have a sense of what this will look like: x and y will be something like edge-weights and u_1 through u_m will be something like face-weights. But someone needs to dig in and work out the details. 2. While we're interpreting these (Laurent) polynomials combinatorially, we should also exploit this combinatorial understanding to give us ways to think about the polynomials. One sort of question is, how many terms does the polynomial contain, and which monomials contribute (and which do not)? In this regard, it's worthwhile pointing out that in many cases, there's a nice exact formula for the number of monomials that occur in the polynomial (as n varies). In fact, in some cases it's very easy to conjecture which monomials occur, namely, those whose exponent-sequence lies inside a certain easily-described polytope. What's more, for exponent-sequences that lie on the boundary of the polytope, there's often a simple formula for the coefficient of the associated monomial. These things should be studied systematically. I expect that this study will have links with non-homogeneous quadratic recurrences of the form a(n) a(n-m) = a(n-i) a(n-m+i) + 1 as studied in REACH last year by Gregg Musiker. 3. A particular case of interest is the 3-term Gale-Robinson recurrence with m=4, i=1, j=2, also known as the Somos-4 recurrence. If one runs the recurrence a(n) a(n-4) = x a(n-1) a(n-3) + x a(n-2) a(n-2) with initial conditions a(1) = a(2) = a(3) = a(4) = 1, one gets the following polynomials: 2 x , 2 2 x + x , 3 2 6 x + x , 5 4 3 16 x + 6 x + x , 7 6 5 4 16 x + 32 x + 10 x + x , 9 8 7 6 176 x + 112 x + 24 x + 2 x , 12 11 10 9 8 7 512 x + 560 x + 336 x + 104 x + 16 x + x , 15 14 13 12 11 10 9 512 x + 3328 x + 2960 x + 1152 x + 232 x + 24 x + x , ... There are some interesting patterns here. If we record, for each polynomial in the sequence, the degree of the highest-degree monomial, we get the integer sequence 0 1 2 3 5 7 9 12 15 18 22 26 30 35 40 45 51 57 63 70 77 84 92 This is a quadratic quasipolynomial with period 3 and leading term 1/6; its nth term is equal to the closest integer to n(n+3)/6. If instead we record, for each polynomial in the sequence, the degree of the lowest- degree monomial, and divide by two, we get the integer sequence 1 1 2 3 4 6 7 9 11 13 16 18 21 24 27 31 34 38 42 46 51 55 This is a quadratic quasipolynomial with period 5 and leading term 1/10; its nth term is equal to the closest integer to n(n+1)/10. Most intriguingly (for me), if we record, for each polynomial, the coefficient of the highest-degree monomial, we get the integer sequence 1 2 2 6 16 16 176 512 512 22016 65536 65536 Two thirds of these terms are powers of two. The other third are of the form (power of two) times (number of domino tilings of a 3-by-n rectangle)! Why should 3-by-n rectangles be relevant here?! It would be good to have a combinatorial understanding of these numbers, though any sort of understanding would be an improvement over the purely empirical state of my knowledge right now! More broadly, the Somos-4 and Somos-5 recurrences deserve to be studied in depth, and to have their combinatorial structure explored deeply. I believe that all three-term Gale-Robinson sequences are NOT alike, and that interesting phenomena will emerge from looking at particular examples (Somos-4 and Somos-5 being among the simplest). 4. To emphasize that not all three-term Gale-Robinson sequences are alike, I bring to your attention the recurrence a(n)=(a(n-1)*a(n-6)+a(n-3)*a(n-4))/a(n-7) (which I learned about from Michael Somos). If you run it with "standard initial conditions" (i.e., 1,1,1,1,1,1,1), you'll find that all terms are of the form 2^a 3^b 5^c! (It's not hard to get an exact formula for a, b, and c in terms of n, after the fact, and to prove it by induction. But it's not at all clear to me why such a formula should exist in the first place.) Are there other examples like this? Is there a combinatorial way to understand them? 5. If we define a(0) = a(1) = a(2) = a(3) = 1 and put a(n) = (a(n-1) * a(n-3) + (-1)^n * a(n-2)^2) / a(n-4) and compute terms e.g. via the Maple program a := proc(n) option remember; if n < 0 then 1 else simplify( (a(n-1)*a(n-3)+(-1)^n*a(n-2)^2)/a(n-4) ); fi; end; we get an integer sequence whose terms are all perfect squares! Why? (The particular integers we get are the squares of 1, 3, 2, 11, 29, 21, 305, 764, 3761, 26829, 20827, 1044667, ... respectively. Does this sequence have a direct combinatorial meaning?) 6. What does a random perfect matching of a large pinecone graph look like? Does it exhibit frozen and temperate zones? Might it even exhibit shielded ("tropical") zones? One way to approach this question is via generating functions that encode information about random perfect matchings of a graph. E.g., consider the graph o---o | | o---o In a random perfect matching of this graph, each of the edges of the graph has a probability of 1/2 of being present in the matching, and we can summarize this information by the picture 1/2 1/2 1/2 1/2 Think of these numbers as being associated with the lattice-points (1,0), (-1,0), (0,1), and (0,-1), and represent the probability p at location (i,j) by the monomial p x^i y^j. Thus the above table of probabilities would be represented by the polynomial (1/2) (x) + (1/2) (1/x) + (1/2) (y) + (1/2) (1/y) Polynomials like this can be a big help in understanding the asymptotics of perfect matchings of large graphs; see for instance my article with Cohn and Elkies (available from my homepage). Something like this ought to be feasible for pinecone graphs as well. 7. Someone should write a crosses-and-wrenches applet! This would help newcomers to the group understand what the method is about, and it would help publicize the group's work in a very attractive way. --------------------------- F. FOUR-TERM GALE-ROBINSON This section is devoted to sequences arising as solutions to recurrences of the form a(n) a(n-m) = a(n-i) a(n-m+i) + a(n-j) a(n-m+j) + a(n-k) a(n-m+k) (with m, i, j, k fixed and n varying). Actually, it's not really devoted to these sequences; it's about the cube recurrence. But the cube recurrence is what's at the root of the four-term Gale-Robinson sequences. 1. The bilinear forum archive begins with a message from me about the cube recurrence, and a number of empirical observations. Can all of these observations now be explained in terms of groves with standard initial conditions (or as some of you like to say "standard initials")? If so, it'd be good to write this up and post it to the forum! 2. It'd be good to write up the combinatorial models associated with the cube-recurrence and variants like Somos-6 and Somos-7 in terms of exponent-arrays whose wedge-sums satisfy certain constraints. 3. How many groves of order n possess various sorts of symmetry? If the analogy between TOADs (Tilings Of Aztec Diamonds) and groves holds, then we should expect some of these symmetry constraints to yield interesting (and challenging!) enumeration conjectures. 4. As we did in topic E6 for perfect matchings, one can also create polynomials for groves that represent (via coefficients of speific terms) the probability that a given edge or other feature (indexed by the exponents of the variables) will be present in a grove chosen uniformly at random from the set of groves of order n. David Speyer worked out the details of this, and in particular he showed that the sequence of these polynomials satisfies a linear recurrence relation which allows one to write down a rational generating function that encodes all the information. Kyle, in consultation with Robin Pemantle, hopes to exploit this generating function. Meanwhile, someone should write down the derivation! 5. Old-fashioned grove-shuffling (the kind that looks only at the primal graph, not the dual) should be studied in a context more general than groves. If you have any essential spanning forest on a triangular grid (i.e., a forest in which each non-boundary vertex has a path to the boundary), then it is possible to perform grove-shuffling; what sort of essential spanning forest results? In particular, what connectivity properties are preserved by the operation? This is probably related to the next question. 6. We still don't know how to shuffle groves, exactly (and I'd put this on the list if I didn't know that several of you worked quite hard on this question last year and didn't make too much progress). But we can do urban renewal for trees on triangular grids, as described in an article by Colbourn et al. that I handed out in late February (the "wye-delta operation"). This may give us a lot of new insights into groves. There are links between this topic and C3. 7. This is more speculative, but: can we do some sort of urban renewal for trees on _square_ grids? 8. It would be good to have software that generates random groves under various conditions. (We already know how to generate random perfect matchings of bipartite planar graph, e.g. random objects of Somos-4 and Somos-5 type. But for Somos-6 and Somos-7 we need something new that does for the cube recurrence what the shuffling-based random generation algorithm does for the octahedron recurrence. --------------------------- G. MISCELLANEOUS 1. Apropos of topic E1 (which envisions matchings as arrays that give the exponents of all the variables in the monomial associated with the matching, and which characterizes the monomials that occur in terms of constraints on the sums of various subsets of the set of exponents), could there be a version of condensation for other sorts of sum-constrained arrays? E.g., one could label the edges of the 2-by-n grid (or Aztec diamond) with 0's, 1's, and 2's such that the labels at each vertex sum to 2. Do such arrays satisfy some sort of condensation? 2. What is the right way to add/multiply two Somos sequences? If you take a rational point on an elliptic curve and call it 0, then you can define an addition-law on the curve, and for any other rational point P you can form an infinite sequence of points P, 2P=P+P, 3P=P+P+P, ...; if you write each point nP as a pair (x_n,y_n) of rational numbers, then the numerators and denominators of x_n and y_n typically grow at quadratic exponential rate, and by looking at them more closely one can find Somos sequences and things like them. (There's a whole topic called "elliptic divisibility sequences" arising from this avenue of study.) It's clear that there's a natural way to add two sesquences of the form P, 2P, 3P, ...; specifically, the sum of P, 2P, 3P, ... and Q, 2Q, 3Q, ... must be (P+Q), 2(P+Q), 3(P+Q), ... . Does this correspond to anything nice on the level of Somos sequences? and can this sort of addition be given some kind of combinatorial interpretation? 3. Topics B5 and C5 suggest a wealth of related liftings one could study, in which a k-dimensional recurrence (with k=1, 2, or 3) gets lifted another, "slightly bigger" k-dimensional recurrence by first creating some independent copies of the recurrence and then allowing them to talk to each other. In situations where the original recurrence gives rise to Laurent polynomials in which all coefficients are 1, you won't get anything really new out of this (assuming that Laurentness holds at all). But it might be good at splitting apart coefficients that are bigger than 1, if you can't find a way to lift all the way up to k+1 dimensions. 4. Someone should read the article in the April 2002 isue of the American Mathematical Monthly and show that the rank-4 cluster algebra for Appolonian packings _is_ a cluster algebra, and that it satisfies Laurentness and positivity, as was suggested by some preliminary experiments I did last spring. Is there a combinatorial interpretation? 5. A very general issue for the study of algebraic recurrences with the Laurent property is as follows: How do we know the "combinatorially correct" way to write a Laurent polynomial? E.g., there are cases in which the Laurent polynomial x should be viewed as 1/(x^{-1}). In Fomin and Zelevinsky's work, it turns out that a good rule is to write Laurent polynomials in the form (A+B+...)/M, where A,B,... are polynomials with gcd 1. (This condition on A,B,... forces a particular choice of the Laurent monomial M.) Can this be principle be useful to us when we try to extract combinatorial interpretations from multivariate generating functions? As I recall, the gcd-equals-1 prescription isn't a panacea; e.g. it doesn't take into account the fact that for perfect matchings of the 2-by-n grid graph, with n negative, there are forced edges, and that gcd(A,B,...) should be, not 1, but the product of the weights of the forced edges. So we need more refined heuristics for figuring out what the combinatorially correct denominator M should be. It's possible that each project within REACH, insofar as "denominator-ology" is concerned, is a question unto itself, but it's also believable that there are some general rules governing this issue. So we might want to compare notes about this, with informaiton coming from a variety of contexts. 6. If we put s(1) = x and s(2) = y and define s(n) = (s(n-1)^1 + 1) / s(n-2) for n = 3,5,7,... s(n) = (s(n-1)^4 + 1) / s(n-2) for n = 4,6,8,..., (the "(1,4) recurrence"), the sequence of degrees of the numerators of s(1), s(2), s(3), ... goes 1, 1, 1, 4, 4, 12, 8, 20, 12, 28, 16, 36, 20, 44, 24, 52, 28, 60, 32, 68, ..., which (leaving aside the first two terms) consists of two interleaved arithmetic progressions; likewise, the sequence of degrees of the denominators goes 0, 0, 1, 5, 4, 11, 7, 17, 10, 23, 13, 29, 16, 35, 19, 41, 22, 47, 25, 53, ..., which (leaving aside the first two terms) consists of two interleaved arithmetic progressions. This is highly reminiscent of the situation for the recurrence s(n) = (s(n-1)^2 + 1) / s(n-2) for n = 3,4,5,6,7,8,... (the "(2,2) recurrence"): the exponents in the recurrence are big enough to prevent periodicity, but not so big as to cause the degrees of the numerator and denominator to increase exponentially. Also, if we put s(1)=x=1 and s(2)=y=1, the terms of the sequence become (*) 1, 1, 2, 17, 9, 386, 43, 8857, 206, 203321, 987, 4667522, 4729, ... . (These numbers plays the role that the alternating Fibonacci numbers 1, 2, 5, 13, 34, ... play for the s(n) = (s(n-1)^2 + 1) / s(n-2).) Superseeker gives us good news about the sequence (*): the subsequence 1, 2, 9, 43, 206, 987, 4729, ... obtained by omitting every second term satisfies the recurrence a(n) = 5 a(n-1) - a(n-2), while the complementary subsequence 1, 17, 386, 8857, 203321, 4667522, ... satisfies the more complicated recurrence b(n) = 24 b(n-1) - 24 b(n-2) + b(n-3) . This is encouraging. But I have no idea how to lift the one-dimensional (1,4)-recurrence into higher dimensions (or introduce new variables in some other fashion) so as to "pulverize the coefficients" and reveal what the underlying combinatorial structures are that these two sequences enumerate! If we put s(1) = x and s(2) = y and define s(n) = (s(n-1)^4 + 1) / s(n-2) for n = 3,5,7,... s(n) = (s(n-1)^1 + 1) / s(n-2) for n = 4,6,8,..., we get the same sort of patterns. Presumably these two sequences of Laurent polynomials need to be understood in tandem somehow. If instead of taking every other term of the number-sequence we take every other term of the original sequence of polynomials, obtaining x, (y+1)/x, (y^3+3*y^2+3*y+1+x^4)/(x^3*y), ... we find that this sequence of Laurent polynomials satisfies the recurrence s(2*n+1) = ((y^2+2*y+x^4+1)/(x^2*y))*s(2*n-1) - s(2*n-3). This linear recurrence relation (which I assume follows from quadratic recurrence relation without too much work) implies Laurentness (which we already knew from Fomin and Zelevinsky) but not positivity of the coefficients (which is still merely conjectural). Gregg Musiker has been working on this problem, so anyone who's interested in working on it should get contact him (so that we don't end up with duplication of effort). (last revised: March 13, 2003)