From propp@math.wisc.edu Sat Feb 9 10:37:08 2002 Date: Mon, 15 Oct 2001 10:17:28 -0500 (CDT) From: propp@math.wisc.edu To: reach@math.harvard.edu Subject: [reach] Minutes for 10/4 Here are Matt's notes for the 10/4 meeting (slightly edited by Jim). Thanks, Matt! 10/4 REACH Professor Propp says he will get some dry-erase markers for REACH. When you have a set with ordinary elements, each element can belong to at most 1 set - with multiplicity 1 or 0 Antielements can belong 0, 1, 2, 3, etc.. but contributes a factor of -1 if it belongs to set an odd # of times. We can have a set consisting of 3 ordinary elements and 1 anti-element: Let o = ordinary element. a = anti-element ooo a : want to take subsets of size 2 how many ways? oo : 3 different ways o a : -3 aa : 1 Total # : 3 + (-3) + 1 = 1 2-element set: how many subsets of size 2?: 1. 3 elts and 1 antielts: how many subsets of size 2, counted with sign?: 1 4 elts and 2 antielts: how many subsets of size 2, counted with sign?: 1 nCk means n choose k. if # of elts - # of antielts is n and you count the # of k-elt subsets, then the # of subsets in signed enumeration is nCk. We can work with both positive sets and negative sets at the same time and understand -nCk = (-1)^k (n+k-1)Ck. One heuristic used to extend is using more variables. Encode a domino tiling completely by algebra. Instead of talking about domino tiling of 2x3 rectangle, talk about perfect matchings of graph w/ height 2, width 3 Assign to each edge a distinctive label: o--x_1--o--x_2--o | | | z_0 z_1 z_2 | | | o--y_1--o--y_2--o x_1, x_2 top edges. z_0, z_1, z_2 vert edges from left to right. y_1, y_2 bottom edges. e. g. 2x2: F_2 = x_1 y_1 + z_0 z_1 e. g. 2x3: F_3 = x_1 y_1 z_2 + z_0 x_2 y_2 + z_0 z_1 z_2 These polynomials represent the perfect matchings. Recurrence relation: 2x4: F_4 = z_3 F_3 + x_3 y_3 F_2 In general F_{n+1} = z_n F_n + x_n y_n F_{n-1} So to figure out combinatorial meaning of 2xn graph where n is negative, work with algebraic representations and take them backwards, by rewriting recurrence relation as F_{n-1} = 1/(x_n y_n) (F_{n+1} - z_n F_n) Try running recurrence backwards, see what you get You get Laurent polynomials. (Like a polynomial except you can have negative powers). These polynomials strongly monic - every coefficient equal to 1 - nice because they're representations of sets. These polynomials strongly monic - every coefficient equal to 1 - nice because they're representations of sets. F_0, F_{-1}, F_{-2}, etc. are NOT strongly monic because you can always set every variable equal to 1, which means counting the configurations, and you get the Fibonacci numbers, and you know when you run the Fibonacci sequence backwards, half the time you get a negative number -3,2,-1,1,0,1,1,2. Next best thing: when one of these is a negative integer, in the corresponding multivariate polynomial, all coefficients are -1. And when one is positive, all the corresponding coefficients are positive. We get polynomials where all coeffs. -1 or +1. And all info about combinatorics is hidden inside pattern of exponents. You could have put down all the variables you're interested in at a certain size, raise them to the 0th power if they don't contribute. Every term is governed by an array of exponents. Then think about rules governing which exponent patterns occur. One rule - The variables x_i and z_i never occur at the same time in a polynomial. This makes sense because working with matchings of graph, x_i is raised to 0th or 1st power depending on whether or not edge is present in matching. Claim: Same thing for -3, -8, -21, etc. as well as 5, 13, 34, when value of n is negative. Look at structures of polynomials, try to figure out grammar and hidden combinatorial meaning. Then you can work at level of combinatorial gadgets and not have to keep track of where they came from. But algebraic structure helps you find the combinatorial structure. Play this game with all kinds of combo. objects like the bowtie matching. A lot of the time you get really nice polynomials in which all the coeffs are +1 or -1. You see all kinds of regularities. Maple or Mathematica - you can ask - "I think all the exponents are 0 or 1. Is that always true?" for all values of n between 0 and -20. Computer algebra systems like this are great with polynomials - you don't have to allocate space for them. Jim shows how recurrence goes with Maple. Start->Programs->Math&Statistics->Maple 5 Define f := proc(n) Base cases: F_1 = z_0, F_0 = F_2 - z_1 F_1 = 1. Program: f := proc(n) if n=1 then z(0) elif n=0 then 1 else simplify(expand((f(n+2)-z(n+1)*f(n+1))/ (x(n+1)*y(n+1)))); fi; end; What Maple can't do so well is (good if someone can do this): given a multivariable polynomial, say which variables contribute to this multivariable polynomial and record all exponents in a matrix or array Another phase of project, the bowtie stuff, graph.tcl 2 things we can look at: 1. Let n vary - how many matchings of bowtie graph? multiply by x^n, sum from n to infinity 2. Take a single term of that polynomial - a number times x^n - look at that number in more detail - find a way to represent the number that takes into account the fact that it's counting different things. We do that by introducing a lot of variables, one to represent each thing. If you suspect rule has to do with how exponent of x_1 interacts w/ exponents of z_0 and exponents of z_1, good to have a different color for each exponent. - might make it easier for human to discern grammar What Jim is looking for: More complicated graphs w/ some positive stuff and some negative stuff - see how you can cancel them. Jim has stuff on his webpage about negative cardinalities and fractional cardinalities, etc. Actual mathematical facts that you can't prove w/o combo understandings: Take an axbxc brick-graph. No good exact formulas or methods for analyzing perfect matchings of hi-dimen. graphs. Paper on web site about domino tiling reciprocity - example for papers that he might want us to write. Generalization: If you hold a, b fixed, and let c vary, and count # of perf. matchings of axbxc box, that sequence of values satisfies a linear recurrence relation. If you run it backwards, it satisfies a reciprocity property. How do you prove that? Only proof Jim knows uses the combinatorial interpretation of running recurrence backwards, which he was able to derive using algebra. Jim shows graph.tcl: Snap to grid. Snap spacing: 30. OK Left-click on vertices. Use middle mouse button (left+right together) to draw edges. (right-click deletes vertex). Evaluate # of matchings. Doesn't have to be a planar graph. Bowtie minus 1 vertex = Bowtie minus 3 vertices in terms of # of matchings What graph.tcl actually does is list all the matchings using a depth-first search - reducing by one edge - how many containing edge + how many not containing edge Pfaffian is a smarter option which uses some tricks which apply to planar graphs. Saves to file untitled.mtx Graph.tcl made to work on sci. ctr. 120 machines but they can't get any edges to work because the middle mouse button simulator doesn't work. How Pfaffian works: Take the permanent of a matrix Rows = vertices A, B, C of a domino graph Columns = vertices 1, 2, 3 Entries = 0 or 1; 1 if they are adjacent. If the graph is planar, the permanent of this matrix is the determinant of some other matrix where the signs are changed. More generally, you need something called the pfaffian of an antisymmetric matrix (the square root of a determinant). The Pfaffian option creates Maple code to evaluate the pfaffian and thereby count the # of perfect matchings. We investigate some matchings of doubled-bowtie structure and its variations. Three yield 52 perfect matchings.