REACH Diary <meta name = "keyword" content = "John Baldwin, John A. Baldwin, John Arthur Baldwin">

My REACH Diary

9.24.02: Spent 2.0 hrs. at REACH meeting. Spent about .1 hrs solving HW problem.
9.27.02: Spent 1.0 hrs. reading minutes from 9.26 and solving HW problems.
9.28.02: Spent 2.0 hrs. finding the recurrence for matchings of a 3 by n graph using primitive matchings.

10.1.02: Spent 2.0 hrs. at REACH meeting.
10.2.02: Spent 1.0 hrs. thinking about the "monic-ness" of the first and last coefficients in the recurrence for matchings of a k by n graph.
10.4.02: Spent .75 hrs. reading article on reciprocity of Domino tilings.
10.5.02: Spent .5 hrs. reading the bijective proofs in integrality.html and symmetry.html.
10.6.02: Spent 2.0 hrs. solving recurrence P_n for polynomials enumerating the matchings of a 1 by n graph, and attempting to find a recurrence for the 2 by n graph. I used Maple extensively for symbolic manipulation, and actually got a recurrence of order 6. However, the recurrence cannot be correct because when I substitute 1 for all of the variables, I get a recurrence for the number of matchings that is not correct. However, it is almost correct: it is off by 1 term, which indicates that I made a careless mistake somewhere.

10.8.02: Spent 2.0 hrs at REACH meeting.
10.9.02: Spent .5 hrs reading domino posting on bilinear forum.
10.10.02: Spent 2.0 hrs at REACH meeting.
10.12.02: Spent 1.5 hrs thinking about combinatorial interpretation of reciprocity in monomer-dimer coverings, and reading 1 page paper intros.

10.15.02: Spent 2.0 hrs at REACH meeting.
10.17.02: Spent 2.0 hrs at REACH meeting.
10.18.02: Spent 2.5 hrs thinking about possible bijections between not-necessarily perfect matching of 2 by n grid and perfect matchings of higher dimensional lattice figures. This was, of course, motivated by the bijection between perfect matchings of a 2 by n grid and the partial matchings of a 1 by n grid. The whole goal, of course, is to find such figures whose perfect matchings (when n is negative) correspond 1-1 with matchings of a 2 by n grid. While I found a few such figures, counting perfect matchings when n is negative (in a variety of schemes using anti-nodes/edges) didn't generate the numbers that seem "tweakable" to the sequence 3,2,11,14,45,... So I think that this is a wrong approach.
10.20.02: Spent 1.5 hrs generating the multivariate polynomial corresponding to matchings of a 2 by n grid, and running the recurrence backwards. I still need to try to interpret the results.

10.22.02: Spent 2.0 hrs at REACH meeting. Kyle and I worked together, running the Laurent Polynomials for matchings of a 2 by n grid backwards, and found a that we were counting signed matchings. We conjectured that f(-n-2) = g(n) = signed number of matchings of a 2 by n, where the sign of a matching is (-1)^(# vertical edges in a matching).
Spent 2.0 hrs proving this conjecture for the 2 by n grid and generating recurrence for matchings (signed and otherwise) of 3 by n grid.
10.23.02: Spent 1.25 hrs running recurrence for signed matchings of 3 by n grid, and trying to find the multivariate polynomial recurrence for matchings of a 3 by n. Exchanged several emails with Kyle who ran the recurrence for the number of matchings of a 3 by n grid backwards. We concluded that if f(n) is the number of matchings of a 3 by n grid, g(n) is the signed number of matchings, that f(-n-2) = (-1)^n * g(n).
10.24.02: Spent 2.0 hrs at REACH meeting working with Kyle and others in the computer lab attempting to find the (minute) error in Kyle's multivariate polynomial recurrence for the number of matchings of a 3 by n, in the hope of discovering where the (-1)^n factor comes from. We conjectured that if f_k (n) is the number of matchings of a k by n grid, g_k (n) is the number of signed matchings, that f_k (-n-2) = (-1)^(nk) * g_k (n).
Spent 1.0 going over article on reciprocity of domino tilings to see what we need to prove for the case of not-necessarily perfect matchings. This weekend and next week are probably the busiest of the semester for me, so I won't be able to devote as much time to REACH as I would like, but I think that I will just go ahead and try to tackle to proof of our conjecture. It seems like it will be really annoying to run the polynomial recurrence for matchings of a 3 by n backwards, and I believe our conjecture anyway.

10.29.02: Spent 2.0 hrs at REACH meeting. Kyle and I worked on trying to show where the (-1)^nk factor comes from. Jim suggested that we give each anti-vertex weight -1. Kyle suggested the alternate, but equivalent interpretation that each monomer covering an anti-vertex gets weighted -1. This explains the sign factor. I mentioned the fact that the outermost 4 vertices in the graph for f_k(-n) are not really antivertices, but are empty - there is no vertex there. And yet, we had noticed earlier that the horizontal anti-edges connecting these vertices to the rest of the graph must always be in the graph. This set the stage for Kyle's more general picture.
10.30.02: Spent 2.0 hrs trying to incorporate the empty edges into the combinatorial picture. Tried assigning imaginary weights i, -i, to the outermost 4 edges of the graph corresponding to f_k(-n) in order to explain away the fact that these edges seemingly need to be in the graph. I gave up after little success and consideration of the fact that there was no indication that anything like this would be helpful since it wasn't indicated in the polynomial recurrence, and imaginary numbers are hard to understand combinatorially
10.31.02: Spent 2.0 hrs at REACH meeting. Kyle presented his framework consisting of vertices, anti-vertices, empty vertices, hedges, vedges, and empty edges. In order to have coherent combinatorial model for our bi-infinite sequence, we need adjunction. We quickly showed that M(G(m,n)G(m,n')) = M(G(m,n+n')), where M(G) denotes the number of signed matchings of G, and G(m,n)G(m,n') is the graph obtained from joining the two graphs by hedges, and n, n' are positive. Then I proved adjunction for the negative-negative case: M(G(m,-n)G(m,-n')) = M(G(m,-n-n')), where n, n' are positive. All that remained was the positive-negative case.
11.1.02: Spent 1.0 hrs thinking about the remaining problem with adjunction.
11.3.02: Kyle solved adjunction, I spent 1.0 hrs attempting to reconstruct the proof.

11.5.02: Spent 2.0 hrs at REACH meeting. Most of our time was spent going over Kyle's proof of adjunction. We also talked to Jim about the next step to take. Jim proposed that we might obtain the same reciprocity result for monomer-dimer covers of the box product G box P_n, which, for n positive, is n copies of G, G_1,...,G_n, in which the corresponding vertices of G_i are attached to those of G_(i+1) by hedges.
11.6.02: Spent 2.0 hrs working on this generalization. We get the reciprocity relationship by letting G box P_(-n) be n copies of G in which all of the edges in G are vedges with weight -1, and all of the vertices are anti-vertices. We attach adjacent copies of G by connecting corresponding vertices with hedges. In addition, for the outermost two copies of G, we attach to each vertex an edge connected on the other end to an empty vertex. This is just a generalization of reciprocity for the m by n grid graph. To prove that the reciprocity relationship that we obtained earlier (f_k (-n-2) = (-1)^(nk) * f'_k (n), where f' denotes signed matchings as described above) holds for this box product, it is sufficient to prove adjunction. The positive-positive (p-p) and negative-negative (n-n) cases follow easily by the same method we used for the grid graph. I am still working on the n-p case.
11.7.02: Spent 2.0 hrs at REACH meeting. The group figured out how to extend our result to the box product graphs G box P_n. In particular, we cleared up what to do about n-p adjunction (see previous entry) in a generalization of Kyle's Lemma 2.

11.12.02: Spent 2.0 hrs at REACH meeting, 2.5 hrs outside of REACH. We thought about adjunction versus concatenation, or more generally, Speyer's method of tackling reciprocity using matrices. Since Speyer's method is much more general, especially when you want to look at the polynomials associated with matchings (giving edges and vertices weights), the next step was to extend this to not necessarily perfect matchings. At first, I thought that our method of adjuction was probably more generally useful than the other group members thought. And I came up with a way of applying adjunction to the hexagonal graphs in one of Speyer's examples. Previously we had just used horizontal edges for adjoining graphs. This required a different gadget. To adjoin the following two graphs:
/\ /\
| | | |
\/ \/
in such a way that the resulting graph has the same number of matchings as the graph formed by the concatenation:
/\ /\
| | |
\/ \/
we can use the following gadget to adjoin them:
*---@---()
|
*---@---()
where * is a normal vertex, @ is an empty vertex, () is a negative vertex, and there is a vedge of weight -1 connecting the two negative vertices - NOT the two positive vertices as it may appear in some browsers. It was hard to draw this and have it come out looking correct in HTML. So, to see what's going on, check the source code. This turned out to work in all of the cases (n-n, p-p, and n-p, p-n).
11.14.02: Spent 2.0 hrs at REACH meeting. Kyle and others thought about extending Speyer's matrix methods and I thought about this explanation of our reciprocity relationship as it applies to graphs like the previous one that are formed by concatenation. I sort of convinced myself that we could use a similar gadget to rephrase a lot of problems involving concatenation in terms of adjunction problems, and I was successful in several cases. We tried to use the adjunction interpretation to figure out how to properly modify Speyer's method to no avail.
11.16.02: Spent 2.5 hrs trying to extend this "concatenation via adjunction" idea as far as I could take it. I realized (something I should have realized much earlier) that this idea can only be applied if the graph that you are concatenating with itself is symmetric through a vertical line. So I decided that while this was a neat trick that worked for some (and I think all) graphs that are bilaterally symmetric, it wasn't general enough to warrant spending more time on it.

11.19.02: Spent 2.0 hrs at REACH meeting, 1.5 hrs outside of meeting. We went to the computer lab so that Kyle could work on the writeup. We sort of agreed on how to divide the writing responsibilities. I set out to work on extending Speyer's method, which I was able to do. If G is a graph, and we designate left and right hooks, we simply let M(G)_PQ = the number of (not necessarily perfect) matchings of the subgraph G' of G where all the vertices in P are removed, all the vertices not in Q are removed, and the vertices in Q are covered by dimers. If the left and right hooks are disjoint subsets, then multiplication of matrices definitely works and all of Speyers results follow, including (I think) reciprocity for not necessarily perfect matchings of cylinder and mobius graphs. However, Speyer doesn't take into account vertex weights, so in order to recover the weighted number of not necessarily perfect matchings of G_1 * G_2 * ... * G_n (where * denotes concatenation - left hooks identified with right hooks, and so on), we have to multiply the entries in the first row of M(G_1) * M(G_2) * ... * M(G_n) by weights that correct for weights of vertices among the left hooks of G_1 and the right hooks of G_n. This is not something that is only necessary for not necessarily perfect matchings. Speyer just didn't consider vertex weights in his method.
11.21.02: Spent 2.0 hrs at REACH meeting. Most of the time, I spent explaining this result to the other guys in the group and we started working through some examples. While working through the examples, I realized that I'm not sure what to do in the case that the left and right hooks are not disjoint.
11.22.02: Spent .5 hrs thinking about what to do in the case that the left and right hooks are not disjoint - I'm pretty sure that this will be easily resolved, I just haven't spent much time oin it.

12.03.02: Spent 2.0 hrs at REACH meeting. Working on our writeup. I am going to write the section on recurrence relations which justifies why our adjunction theorems suffice to prove the reciprocity we conjectured for the recurrence relation counting matchings. I am also writing up the last section in which I explain how adjunction can be applied to establish reciprocity relations for graphs which cannot be expressed as box products. I'll also include in this section my extension of Speyer's method for keeping track of matchings for graphs that are formed through concatenation. I also plan to spend a lot of time editing and making things more precise and consistent. I might draw some pictures as well.