11/11 - 11/18
I gave up on writing the program that would tell me how to connect units,
to create graphs with a certain number of matchings. The best approach I
found was to represent graphs by the decisions a person who was walking on
the boundary of that graph would have to make. For example, the 2-3 ladder
graph would be: (right,right,straight,right,right,straight). That way I
could (in some cases) identify isomorphic graphs, I could easily merge graphs,
and count perfect matchings. But I still generated too many graphs. There
were about 2000 graphs when I connect 4 2-3 ladder graphs together, and I
was interested in connecting 8 203 ladder graphs together. So, I gave up.
Right now, we are working on other proofs that the Markov Snakes really
work. We are very close to finish a combinatorial proof that P(C)+P(C')=K(x,y,z)*P(A)*P(B)
(refer to the simple proof of Laurentness
).
I found a third proof
, using Erik
Nuo's graphical condensation
.
~8 hrs.
11/04 - 11/11
An important fact came up. As suggested by the proof for Laurentness
for the case n=3 (the snakes), there is another bijection between snakes
given by: P(C') + P(C) = K(x,y,z) * P(A) * P(B). We do not yet have a combinatorial
proof for this fact. But note that if we fix A,x,y and z, then this is a
linear recurrence, which is much simpler to deal with. This bijection, in
the general case is P(Xn') * P(Xn) = K(y1,y2,..,yn) * P(X1)*P(X2)*...*P(Xn-1).
This suggests that Xn' is made of X1, X2, ..., Xn-1, and a extra unit. The
problem is how to connect them. So far, I've been able to generate a
few graphs
.
I'm now trying to write a program that, given a unit graph (could be
any graph), the number of times t that this unit should be repeated and a
number of matchings m, tell us how to connected the t units such that the
resulting graph has m matchings. I actually have the first version of it,
but my computer runs out of memory for very simple base cases. I need to
improve the algorithm. If I'm successful, this program could give us clues
of whether the generalized graphs (which will start calling stars, rather
than snakes) exist or not, and if they exist what they are.
~10hrs
10/28 - 11/04
I checked that Sn*Sn-a = Sum(ki * Sn-i^2) does not work for general coefficients.
As a matter of fact, it seems to work for a very specific set of ki's.
Still trying to generalize snakes. Jim told as about these graphs that
have n matchings, for any n (they could be the units that replace the square
unit of the n=3 case).
Andy came up with a way to connect units such that we can generate graphs
for the following sequence of substitutions: (1,1,1,..1,) -> (a,1,1,..,1)
-> (a,b,1,...,1) -> (c,b,1,...1) .... This gives us some hope. Otherwise
we haven't been very successful.
~7hrs
10/21 - 10/28
Some generalizations of the Markov triples were suggested. We started
looking at the possibility of Markov n-tuples.
It is easy to generalize the proof of Laurentness for the Markov n-tuples.
Started some work trying to understand what the Snakes would look like
for a general n.
~8hrs
10/14 - 10/20
I started working on the Combinatorial interpretation for the Markov
numbers over the weekend. Here's a brief summary of what I've done:
Jim mentioned that the sequence 1,1,1,2,5,29,433,37666,..., which is extracted
from the Markov triples by the recurrence s_n=(s_(n-1)^2+s_(n-2)^2)/s_(n-3),
gives the number of perfect matchings in some snake shaped graphs (with
the slope equals the golden ratio!). I wrote a little Java and Maple to
find out what those snakes are for the first few numbers in the sequence.
From there I could see what the general structure of the snake for any number
in the sequence is. I have a very informal prove for that.
Then, I tried to generalize that by assigning weights to the edges of the
snake. This should give me the polynomials generated by x,y,z,(x^2+y^2)/z,...
And finally, I tried to find the snake shaped graph that corresponds to
any polynomial in one of the Markov triples, and not just the ones generated
by the recurrence above.
I might have found the proof I wanted. Details
here
.
I found a simple proof
for the Laurentness property of Markov polynomials.
I don't really remember much of tuesday's meeting. On Thursday Gabriel
talked about Groves (it seems to be a very nice topic!).
~20hrs
10/06 - 10/13
Tuesday - solving HW in groups. 2D and 3D combinatorics.
Reading HW articles.
Thrusday - Jim presents some of the possible articles for this term.
Looking at the possible articles. The one about Markov numbers seems
interesting.
~6hrs
09/29 - 10/05
I found a brute force solution for matchings in 3xn grids, but I was
too lazy to calculate the function for it.
Tuesday - Computers can solve matchings in mxn graphs.
Reading article on reciprocity of perfect matchings.
Thursday - Combinatorical interpretation of algebraic objects.
HW - found an interpretation for the negative values of non-perfect matchings
in a 1xn grid.
~ 8 hrs
09/22 - 09/28
First meeting - Getting to know REACH and other students.
Second Meeting - Matchings in a 2xn grid solved. Homework: 1xn and 3xn
grids
Solved the 1xn case.
Calculated the generating function for the 2xn case.
Wrote a small java program
that calculates number of matchings in any grid (it doesn't have to be a
rectangular grid). I'll try to put it up here as a java applet.
~ 7 hrs
^
back to top
^