NOTES FOR 10/17 Notetaker: Daniel Zaharopol Promises: The notetaker for next time is Anna. Homework: Think of what you want to do. Read previews What you want to do should be a preview of something, or at least as specific. Look at each others' web pages to see what everyone else is doing. Feel free to dive into projects. Put project preference in a visible spot on your web page. Meeting time will be scheduled later (starting 3 vs. starting 3:15) Jim asks: How do we run a research group with this many people when the supervisor can only put in 10 hours per week? - Members should team up with others to proofread proofs - Jim will take suggestions on how to keep everyone contributing. - We should time the drafts we give to Jim to read so that we only give them to him during critical stages of research, and the later stages of research. Rui has extensive solution to Markov numbers, which is being put up on his web page. Jim says that there are still a family of 2-parameter recurrences still to solve, so there's more to do in this area. It's likely that we can apply similar techniques. Gabriel got up to present his notes on the cube recurrence. As opposed to a detailed presentation, this is mostly to get a flavor for the research. (everything that follows was said by Gabriel unless otherwise noted) - The cube recurrence was a major theme of last spring. - This was developed mainly by Gabriel and David Speyer. Consider tiling 3-space with cubes: f ------- b /: /| With the recurrence: g /_:___/c| ag = bh + ce + df | : | | | ...|..| | /e | / a |/____|/ h d Then with f_{i,j,k} representing rational functions of initial conditions given for -1 <= i + j + k <= 1, we get a recurrence that can be solved at each point of the 3-D lattice created by this tiling: f_{i,j,k} = f_{i-1,j,k} f_{i,j-1,k-1} + f_{i,j-1,k} f_{i-1,j,k-1} + f_{i,j,k-1} f_{i-1,j-1,k} -------------------------------- f_{i-1,j-1,k-1} Thus, everything we get is a rational function in terms of our starting parameters. It turns out that we get something better, though: everything that comes out is a Laurent polynomial in terms of what we started with. This was proved by Fomin and Zelevinsky. Now, the related octahedral recurrence had a nice combinatorial interpretation (proven by Speyer). We'd like to try to get something similar for the cube recurrence. Let's consider the lattice formed by these points, | | | | | | | | | | | |/ \|/ \|/ \|/ \|/ \| |\ /|\ /|\ /|\ /|\ /| | | | | | | | | | | | \|/ \|/ \|/ \|/ \|/ /|\ /|\ /|\ /|\ /|\ | | | | | | | | | | | |/ \|/ \|/ \|/ \|/ \| and so on (picture them as cubes). Gabriel and David plugged it into Mathematica, to see what it said about the polynomials. It occurred to them to look at individual monomials in the Laurent polynomials and to take sums of the exponents corresponding to variables in particular regions. Certain sums were always 1 or 0. They finally came to the conclusion of drawing a graph, with the vertices the points with sum of coordinates 0. The edges of these graphs were determined by the sums of exponents of monomials; it turned out that the Laurent polynomials from the recurrences were the sum of all such edge configurations, given certain conditions. Specifically, they ended up getting forests with nice connectivity even with vertices farther out. * * * * * * * / / \ \ \ * *---* * * * / \ \ The boundary vertices are * *---*---* * connected to "opposite" / \ vertices. * * * * / \ / \ * * * *---* * The sum of the exponents determines if you draw an edge. Monomials turned out to be in bijection with these forests --- called "simplified groves." There was also a formula for converting groves to monomials. The formula was, for each vertex, to raise it to a power equal to its degree in the graph minus 2, unless it was on the edge of the triangular lattice, in which case it gets raised to its degree minus 1, or just the degree (0) for a corner of the triangle. Each of the other variables corresponded to a unit triangle in the triangular lattice, and it was raised to the power of 1 minus the number of surrounding edges used in the graph. They could also put in other variables besides those associated just with the vertices. The cube recurrence corresponds to all possible monomials in a certain region. They also came up with the idea of "dual groves." If we go back to the diagram from before, | | | | | | | | | | | |/ \|/ \|/ \|/ \|/ \| |\ /|\ /|\ /|\ /|\ /| | | | | | | | | | | | \|/ \|/ \|/ \|/ \|/ /|\ /|\ /|\ /|\ /|\ | | | | | | | | | | | |/ \|/ \|/ \|/ \|/ \| and we mark all of the points whose coordinate sums are zero, this leaves a number of points unused. Note how each face of a cube has a long diagonal and a short diagonal with the perspective in the picture; now we fill in the short diagonal whenever the long diagonal is not filled in. This creates a graph among the points which are the complement of those whose coordinate sums are zero. We call this a "dual grove." "Dual groves" look like groves in many ways. They are acyclic, and have connectivity conditions similar to those of groves. The vertices of the dual groves also conform to their exponent being the degree of the vertex minus 2, except for boundary cases. If we want this formula to look nicer, we can extend edges outwards so that the formula for the exponent will always be degree - 2. We now add variables for the edges. f_{i,j,k} = b_{i,k} c_{i,j} f_{i-1,j,k} f_{i,j-1,k-1} + a_{j,k} c_{i,j} f_{i,j-1,k} f_{i-1,j,k-1} + a_{j,k} b_{i,k} f_{i,j,k-1} f_{i-1,j-1,k} ---------------------------------------------- f_{i-1,j-1,k-1} Again, we find that we get Laurent polynomials. The a's, b'c, and c's correspond to edges from the groves. We can also ask what happens if we start with different sets of starting variables. We can restrict our set of initial conditions by cutting it with the xy-, yz-, and xz-planes, so that we now only have initial conditions at (i,j,k) for suitable i, j, k <= 0; if we run the cube recurrence, f_0,0,0 still has the same value as before. Think of both the groves and dual groves as a single graph. For all the diamonds outside the interesting region, we just extend straight lines out from the graph. We can reformulate our connectivity conditions in terms of points on a triangle "very far out," which gives basically the same connectivity requirements, but allows for different shapes of initial conditions. f_{i,j,k} = \Sum m(G), where m(G) are monomials associated with groves. Jim conjectured Laurent polynomials are strongly monic (all coefficients are 1); it turns out that this pops out of the definition of groves. For standard initial conditions (-1 <= i+j+k <= 1), f_{i,j,k} has 3^{Floor[(i + j + k)^2/4]} groves. Rui asks: What do polynomials look like with different initial conditions? Answer: there are algebraic relations between them. Laurentness still holds. The draft of the paper that covers this is at: http://www.people.fas.harvard.edu/~gcarroll/math/gtpreach/cubeart.pdf or http://www.people.fas.harvard.edu/~gcarroll/math/gtpreach/cubeart.ps Can also look through old e-mails, but warning: the terminology has changed since then. More, including unsolved problems, will be presented next time. Gabriel finished his presentation, and Jim announced that there would be a break and we'd meet back up in the computer lab. At the computer lab: ------------------- Rui has a Java applet he wrote while thinking of graphs. http://web.mit.edu/~ruilov/www/reach/matchingsApplet/MatchingsApplet.html Allows you to add nodes and forbidden edges. Calculates number of matchings, not perfect matchings. If graph gets bigger than 15 vertices, takes a long time. Good for base cases. Algorithm: just looks for one possible edge, and either adds edge in or stipulates the edge is forbidden. Recurses. Jim presents tiling applets, at: http://jamespropp.org/tiling/www/applets/index.html Applets generate random tilings. E.g. hexagon translates random rhombus tilings of hexagon. Starts with two extreme tilings, one with lowest height possible, another with highest height possible. Random walk allows the two to "mutate in tandem," until stopping rule that stops when probability of all tilings is equal. Idea is that you keep starting at earlier times, but using the same mutations at the end. That is, you see if histories "coalesce" by time zero starting at time = -100. If they don't, start at time = -200, but must use same patterns once at time = -100. Continue until patterns coalesce; at that point, we have a random tiling. This works for the other patterns as well. Jim went to look for an applet. "TOAD Shuffling" program --- TOAD is a tiling of an Aztec diamond. Applet at http://jamespropp.org/SSL/toadshuffle/index.html Applet goes through step-by-step, deleting "bad blocks" as you go along. Bad blocks are blue on top of yellow, green to the left of red. Red dominos go one step to the left, yellow one step up, green one step to the right, blue one step down. Remaining regions are randomly filled. Eliminate bad blocks, go on. Each possible domino tiling has same probability of occurring with this algorithm. For example, there's positive probability that right/left edge blocks will have horizontal blocks, but they're very unlikely (because you'd basically have to generate only horizontal blocks). Can click "Show FPL." Jim could't remember what that stands for (though afterwards he remembered: it's "Fully Packed Loops"). We can look at a tiling of an Aztec diamond of order n, and alternating sign matrices of order n and n + 1. There's a bijection given certain conditions; this shows us these matrices. (an alternating sign matrix is made up of 1s, 0s, and -1s, with the property that all non-zero entries in each row and column alternate sign, and each row/column contains at least one non-zero entry, and the first and last non-zero entries in each row or column are 1s) We'll elaborate on that. Consider a 4x4 grid: | | * * * *--- Edges sticking out alternate present/not present ---* * * * Each vertex must lie on two edges. * * * *--- ---* * * * | | ======================This choice was arbitrary, but then many : others were forced. : |8 |7 : * *---* *--- ==>| | | 6 ---* *---*---* 1 *---*---* *--- | | | 5 ---* *---* * 2 |3 |4 It turns out that these correspond to alternating sign matrices. The number of possible alternating sign matrices are: 1, 2, 7, 42, etc. Now, how many FPLs that join edges: 1-8, 2-3, 4-5, 6-7? It's 7, the previous (3rd) number! "Show FPL" on the computer shows that FPLs that correspond to the alternating sign matrices. Note that random alternating sign matrices also have bias to orientation of edges. Generating alternating sign matrices from Aztec diamonds gives a bias. If we look at a random alternating sign matrix of order n, we see a square where the outer part is orderly and a circular-looking region inside that is disorderly. There is a conjecture that this region is round, but Jim doesn't think so. Then, Jim demonstrated some groves of various orders. Again, they were orderly at corners, chaotic in the middle.