TOTAL WORK FOR THE SPRING SEMESTER: 13 hours (current through Jan. 16)
Week of January 12, 2003
January 13
I played around with Gabriel's Mathematica notebook for groves.
I'm trying to get a better feel for how they work. -1.5 hours
January 14
REACH meeting. Ilya has generated an example that shows that
you might not get integers from running a linear recurrence backwards.
I'll incorporate the example on Thursday and post it. Nick found
that Lemma 2 is false as stated. We need to make it more specific
to the case of box products. -2 hours
January 15
Played with Mathematica a little more. Trying to get comfortable
enough to run some numerical trials on groves. -1.5 hours
January 16
REACH meeting. Posted draft with Ilya's example. -3 hours
TOTAL FOR THE WEEK: 8 HOURS
Week of January 5, 2003
January 7
REACH meeting. Nick and I looked over the paper and some of the
graphics he'd done for it. After the meeting I posted Nick's draft of the
paper with some of the illustrations done. -3 hours
January 9
REACH meeting. Nick and I looked at some more of his illustrations.
I also started reading Gabriel's paper. -2 hours
TOTAL FOR THE WEEK: 5 HOURS
TOTAL WORK FOR THE FALL SEMESTER: 95 hours
Week of December 1, 2002
December 2
Updated my web page. Finally. -.5 hour
Week of November 24, 2002
November 26
REACH meeting. Worked on paper and discussed ideas for matrix
encoding. -2 hours
November 27
Worked on the paper, got most of a first draft completed. -3
hours
TOTAL FOR THE WEEK: 5 hours
Week of November 17, 2002
November 19
Reach meeting. Presented our ideas to the rest of the group (i.e.
walked everyone through my web page). -2 hours
November 21
Meeting. Talked with Jim about wanting to work on "circles in
groves" for next semester. Worked on paper. -2 hours
TOTAL FOR THE WEEK: 4 hours
Week of November 10, 2002
November 12
Discussed what we want to include in the formal paper, e.g. cylinder,
mobius strip, honeycombs... Walked through Speyer's paper and thought
about how to apply it to our situation. -2 hours
November 14
Decided that we can use our method to state and prove a reciprocity
for box product graphs, but perhaps not more. John came up with an
adjunction to make the honeycomb graph work. -2 hours
TOTAL FOR THE WEEK: 4 hours
Week of November 3, 2002
November 5
Showed the guys what I put up on my web page and discussed it.
-2 hours
November 7
Talked with Jim about what we'd come up with, and got ideas for what
else to include in the formal paper. -2 hours
TOTAL FOR THE WEEK: 4 hours
Week of October 27, 2002
October 27
I was still not quite satisfied with the combinatorial picture that
we had developed. I thought that by counting the difference between
two types of matchings meant that we we really counting some subset of
the larger set of types. To make a long story short, I thought that
perhaps what we were really counting was some invariant subset of the matchings.
After drawing some examples, I guessed that it was matchings invariant
under rotation by 180 degrees. - 2 hours
October 28
I wrote some Maple code that helped me to find the numbers of matchings
of 1 by n and 2 by n grids that were invariant under 180 degree rotation.
The numbers were different than what I wanted, though they did show up
in the encyclopedia of integer sequences. I still couldn't explain
the (-1)^mn term except to say that we throw in a -1 if the total number
of vertices is odd. Why? - 2 hours
October 29
REACH meeting today. Talked with John, Nick, and Ilya about what
we've all thought about. We decided that we're "pretty close" with
the combinatorial model, but not quite. Adjunction doesn't seem to
make good sense yet. We shared our progress with Jim. He suggested
that perhaps all anti-vertices contribute weight -1 to matchings.
I preferred to think that they contribute weight -1 when they are alone,
since that would correspond better to monomer-dimer tilings. Jim
also helped us line up three different avenues for approaching the problem.
(1) a unified combinatorial model, i.e one in which adjunction works for
all values of n. (2) generating functions, similar to Stanley's method.
(3) an interpretation of Speyer's idea for encoding matchings in a matrix.
-2 hours
October 30
Today I think I figured out how the model is going to work. I
ran some polynomials backwards with weights on vertices that appear alone,
and the picture is exactly the same as before. I was trying to make
adjunction work somehow when I decided there must be another type of vertex
that we weren't really seeing - the empty vertex. The empty vertex
was defined to be "needy" in the sense that one of the edges incident with
it MUST appear in a matching. In a sense it fixes certain edges in
a graph, explaining our pictures for G(m, 0) and G(m,n) with n<0.
I couldn't show that adjunction had to work, but I did some examples and
they all worked out. I made a pretty good entry in my notebook defining
things and writing down all the theorems we need to prove now. -8 hours
October 31
At our REACH meeting, I showed the guys what I'd come up with.
We all started thinking of how to prove adjunction worked. We were
able to prove a few cases, though nothing in general. After the meeting,
I played around with some ideas a bit more, and proved a couple of lemmas
(one that John had come up with at the meeting) that enabled me to prove
(quite nicely I think) adjunction in general. I sent out an email
to the guys saying so. -4 hours
November 1
I worked on putting together a summary of my results from this week
on my web page. -2 hours
November 2
Worked some more on building a web document to show what I've done.
-4 hours
TOTAL FOR THE WEEK: 24 hours
Week of October 20, 2002
October 20
I came across Dean's interpretation of the 1 by n monomer-dimer recurrence.
I got the same algebraic recurrence and drew the same pictures, but I have
a slightly different story to fit the results. Once I sorted out
the 1 by n case, I tried to use Maple to help me get the polynomials for
the 2 by n case. I lacked some sophistication there, so I gave up
with the programming and browsed through some of the online articles.
-3 hours
October 21
I played around with the 2 by n polynomials, but was having trouble
with Maple. I knew it was silly to do it by hand, so I asked Jim
if he had any software that could help. He said he would send it
to me. -1 hour
October 22
I got the maple code from Jim and played around with it going forward.
We had a REACH meeting without Jim. John Baldwin is also working
on the same problem, so he and I talked about what we'd found: mainly the
combinatorial story for 1 by n and 2 by n. We went to the computer
room and used Jim's code to get polynomials going in reverse. Based
on the polynomials and the pictures we'd drawn, we were able to get a better
handle on the general combinatorial story and make our first reciprocity
conjecture: T(m, -n-2) = "signed"T(m, n). -3.5 hours
October 23
Via email, John and I did some work on the 3 by n case, to make sure
it fit our story. It didn't quite, so now the modified conjecture
is T(m, -n-2) = (-1)^{mn}"signed"T(m,n). i.e. there is a minus sign
when the number of vertices is odd. In other words, I think that
T(m,n) when n is negative gives the absolute value of the difference: (#of
matchings with an even number of vertical edges) - (#of matchings with
an odd number of vertical edges). The (-1)^{mn} reflects the 'fact'
that when there are an odd number of vertices, the there are more matchings
with an odd number of vertical edges than with an even number of vertical
edges. We agreed to try to generate the polynomials for 3 by n just
to confirm what we were seeing with the pictures and the numbers.
This turned out to be quite a mind-numbing task. -3 hours
October 24
I didn't do any work until the REACH meeting. John, Ilya, Nick,
and I went to the computer room, and I tried to get Nick and Ilya up to
speed. By 5 o'clock we had found a bug in my Maple code, and were
able to get the 3 by n polynomials going forward. I emailed everybody
the code and we all agreed to try to get the polynomials going backwards.
-2 hours
October 25
I thought that maybe it was a bit redundant for all four of us to investigate
the same thing, so I sent an email to Nick and Ilya suggesting that maybe
they start work on the Cylinder or Mobius strip problems. I worked
on reversing some of the recurrences for the 3 by n polynomials. - 1 hour
October 26
I spent some time reversing all the recurrences in my polynomial generator,
but it doesn't work. I think the problem is that at one point to
calculate F(n) you need to calculate something that depends on F(n-1),
which is no good when n is negative! So I think I need to do something
clever to patch it up. Instead of spending more time working on it
alone, I thought I'd save it for Tuesday and work on other aspects of the
problem. Besides, I think we have the right conjecture, we should
probably start trying to prove it. I read Speyer's article recip5.pdf
. It looks bad on the browser, but it was fine when I printed it
out. I think we might be able to do something like what Speyer does.
To count less-than-perfect matchings, you just take the case where all
the vertices of the graph are "hooks". I don't know yet how we'll
handle what happens when there are an odd number of vertices, since he
requires the number of left hooks to be equal to the number of right hooks.
But then that seems to be a running theme with this problem. -4 hours
TOTAL FOR THE WEEK: 17.5
WEEK OF OCTOBER 13, 2002
October 15
Meeting today. I've decided to try to write the monomer-dimer
reciprocity paper and possibly the cylinder/mobius strip/projective plane
tilings paper. I won't be able to really get started until the weekend.
I thought about less-than-perfect matchings of an m x n strip being closely
related to perfect matchings of a m x n x 2 rectangular solid. My
hope was that perfect matchings in three dimensions might be easier to
count than less than perfect matchings in two dimensions, but Jim seemed
to think the problem wouldn't get much easier. In the computer room
I generated some data for perfect matchings of a cylinder.
a(m,n) = perfect matchings of an m x n cylinder
a(i, j) 1 2 3 4 5 6 7 8 9 10 11 12 13
1 0 1 0 2 0 2 0 2 0 2 0 2 0
2 1 2 4 9 11 20 29 49 76 125 199 324 521
3 0 3 0 32 0 108 0 392 0 1452 0 5408 0
4 1 5 19 121 176 725 1471
It looks like perhaps a(2, 2k) = a(2, 2k-1) + a(2, 2k-2) and that a(2, 2k+1) = f(2k+1) + f(2k-1) where f(k) is the kth Fibonacci number. -3 hours
October 17
Meeting today. I spent most of today working on a combinatorial
interpretation of less than perfect matchings (monomer-dimer tilings) going
backwards. -2 hours
October 18
Updated the log. Worked a bit more on a combinatorial story for
monomer-dimer tilings. -1 hour
TOTAL FOR THE WEEK: 6 hours
WEEK OF OCTOBER 6, 2002
October 7
I worked on a combinatorial interpretation for 1 x n non-perfect matchings
going backward with anti-vertices and anti-edges. -1 hour
October 8
Reach meeting today. I was the note-taker. We talked about
some questions with reciprocity formulas, and what happens when you have
a non-linear recurrence. Jim hinted at some research problems. -2
hours
October 9
Spent a long time typing up the notes so that they would be readable.
-2 hours
October 10
Meeting today. Jim showed us some of his ideas for directions
the work can take. We went to the computer lab where he showed us
our unwritten articles and some tools for counting matchings of a graph.
I'm exciting about tilings of cylinders and mobius strips.
Also maybe running non-perfect m x n matchings backwards. I'd like
to get started, but classes are bogging me down right now. -2 hours
October 11
Updated log, played with matching tools. -1 hour
TOTAL FOR THE WEEK: 8 hours
WEEK OF SEPTEMBER 29, 2002
September 29
Reconfirmed primitive power series coefficients, decided to wait and
talk to Jim about it before wasting any more time. Worked on web
page a bit. -2 hours
September 30
I took some recurrences for the 3 x n matchings, got generating functions
and had Maple do some linear algebra for me. I got a degree six rational
function. Anton came to me with a cool idea for a matrix that concatenates
3 x 2 primitives with 3 x 2 primitives. We could use the sum of the
entries of the matrix to get all 3 x 3 primitive matchings, and sum the
entries of A^n-2 to get all 3 x n primitives. I thought that the
idea could maybe generalize to getting m x n matchings using 2 x 2 units,
but I didn't develop the idea. -3 hours
October 1
We had our meeting today. Learned about the Cayley-Hamilton method
for getting recurrences. Seems very slick. Very similar to
Anton's idea as well. Jim gave us homework-to read one of his papers.
-2 hours
October 2
Read "A reciprocity theorem for domino tilings" by Jim. Inspired,
I tried to work on a generating function for a_(m,n) = number of matchings
for an m x n grid. I got a 5 x 5 x 5 array with E, L, R, T, B as
the labels. Every time you place a new dot on a grid (working left
to right, top to bottom to fill out an m x n grid) it receives a label:
E, L, R, T, B. But what it receives depends on the label on the dot
to the left of it and above it. For example suppose we want to place
a new dot in the second row, third column, or place (2,3). Say (2,2)
= E, (1,3)= R. Then (2,3) can be anything but R or B. But there
are problems. Say (2,2) = L and (1,3) = T. Then there is no
possible choice for (2,3). So it seems that in "building up" a labelled
grid like this, label(m,n) depends on things to the left, top and top-right.
After thinking about problems like this, I lost track of what I was counting with my 3 dimensional array, and I wasn't sure quite what to do with it. I decided to leave this idea alone for a while. Is it worthwhile to a recurrence for a_(m,n) where neither m nor n is fixed? -3 hours
October 3
Had our meeting today. I'm note-taker on Tuesday. We talked
a little bit about bijections, and we looked at what happens when you run
recurrences backwards as in Jim's paper. We also talked about assigning
formal variables to the edges in a matching. Homework is to assign
variables to edges for partial matchings...then run the recurrence backward.
-2 hours
TOTAL FOR THE WEEK: 12 hours
WEEK OF SEPTEMBER 22, 2002
September 24
Had our first REACH meeting at Harvard. Learned about the 2 x
n matching problem. -2 hours
Worked on matching problem recurrence - 1 hour
September 25
Put together web page and proved recurrence for 2 x n matching problem
-1 hour
September 26
Second REACH meeting. Saw several different proofs of 2 x n recurrence.
Especially liked generating function versions. -2 hours
Did homework Jim gave us, save the 3 x n recurrence. -2 hours
September 27
Tried an approach to the 3 x n lattice matching problem using primitives.
Got the first five coefficients for the power series of the primitives,
but gave up trying to find the sixth. So far: P(x) = 1 + 3*x
+ 13*x^2 + 26*x^3 + 70*x^4 + ... -2 hours
TOTAL FOR THE WEEK: 10 hours