From propp@math.wisc.edu Sat Feb 9 10:37:01 2002 Date: Mon, 22 Oct 2001 19:59:31 -0500 (CDT) From: propp@math.wisc.edu To: reach@math.harvard.edu Subject: [reach] minutes for 10/16 Minutes for 10/16/01 (courtesy of Wei) -------------------- Administrative Software - go to Jim's Wisconsin webpage (linked from Harvard webpage) Writeups (for Monthly problems) - send or give to Jim ASAP Matt: wants to work on "CS side" of REACH, e.g. webpage/mailing list (but busy this week) suggestions for webpage/mailing list: mailing list - divided up by topics webpage where groups of people can post their problems/interests strip headers off of archived e-mails graph.tcl still having problems accessing Roberto's friend cannot port to other language can Matt write graph.tcl in Java? will it be useful? can we write a (graph --> Mathematica adjacency matrix) program? can we change graph.tcl a little? keystrokes making edges? is there Mathematica software for graph.tcl? (Matt Blum, who used to be an UG at MIT, wrote graph.tcl) Bridget: posted L-tilings solutions (see archive), so please comment! domino tilings of Mobius strips: 2-by-n strips, with a marked edge, reduce to three cases: 1) both top and bottom overlap 2) neither top nor bottom overlap 3) either one of top or bottom overlap on each side (for n odd) M_n = T_n + T_(n-2) + 1 + (-1)^(n+1) Jim asks: what happens for negative values of n? Gregg: writeup of Deutsch problem done - e-mail to Jim / Matt to post Matt promised to try to send an attachment to the mailing list should we have a webpage for writeups? theorem presented in 192r today: Define F(X) = sum_{n>=0} f(n) x^n G(X) = sum_{n>=1} f(-n) x^n where f(n) satisfies a linear recurrence relation (or rational function) F(1/x) = -G(x) (if you express both as rational functions) in what sense might this mean sum_{n=-infinity}^{n=infinity} f(n) x^n = 0 ? Jim suggests: check p. 206 of Stanley's book Laurent series: power series with finite number of neg-exponent terms power series in 1/x: power series from 0 to -infinity David: tilings of boards with jagged edges, connected together: G_n: graph G repeated n times P,Q sets of vertics of G R(G,n,P,Q) = G_n - (p,1) - (q,n) F(G,n,P,Q)(x) = F(G,-n,P~,Q~)(-x) = +/- F(G,-n,P~,Q~)(x) (where P~ = complement of P) intuitively makes sense, but need proof? any suggestions? Alex: Galois conjugates in generating functions Catalan numbers: (1-sqrt(1-4y))/2x not very interesting though y = sum (3n choose n) x^n (27x-4) y^3 + 3y + 1 = 0 no results yet met up with David over the weekend see the e-mail about tilings of 3-d "hyperominoes" Billy: running bowties backwards - get intuition reformulate bijection as reciprocity relation running 3-by-n graphs (minus corner) backwards --> same graph, but rotated David surprised by graph Lionel: Knuth problem Any polomino spanning a square has a "simple" form (usually) two "special" tiles step-path in between special tiles directly (straight) to square's edges outside of special tiles so fix the special tiles and count the step path binomial coefficient (k'-k+l'-l-1 choose k'-k) BUT need to deal with boundary cases and symmetries anybody think of a better way to do this?? Jim notes: to get your Monthly solution published, do something extra Trevor: Announcement: Harvard-MIT Math Tournament needs people to help!! write problems, judge, etc. (late March / early April) to prove: # of tilings of 2n-by-n rectangles is always odd equivalent to # of perfect matchings of 2n-by-n graph mod out by symmetries since we only care about parity ties in to David's problem of jagged edges? consider the parity of tilings of a mutilated rectangle? note: there exists an exact formula for the power of 2 dividing the number of tilings (2-adic considerations, generalizing parity) Ethan: F_(n-1) = 1/(x_n y_n) (F_(n+1) - z_n F_n) specializations (x_n = n, etc.) not very interesting weighted summations? Roberto: ln (1/(1+x)), ln (1/(1+1/(1+x))), ... define with continued fractions: [0,1,...,1,1/x] big matrix if expand out terms eigenvalues of top left i-by-i matrix approaching the golden ratio ln ([0,1,...,1/x]) (ith iteration) = the sum of fractions involving the Fibonacci numbers! Wei: running hexagon tilings backwards equivalent to four-color problem: four-coloring of the vertices of any two triangulations of any n-gon