Martin's Fall 2003 SSL Page
This is a list of stuff that I've done as a member of
SSL, the Spatial Systems
Lab, run by Professor Jim Propp,
for the Fall 2003 semester.
First I will present a list of main topics documents, followed by a reverse
chronological diary of my thoughts on those topics.
Journal entries
- January 5: Updated Fibonacci topics document.
- December 3: More Markoff graph stuff. Have made some
code available. Have some conjectures about the
exact number of triples on the field modulo p (it is proportional to
p2) and the number of triples which map to themselves with the exchange
relation (proportional to p) for both the normal Markoff relation as well
as "Markoff's brothers".
- November 18: Have been reading more stuff. Jim gave us an idea regarding
expander graphs. Implemented a couple of cluster
algebra-related things in Maple. Function f is the Musiker sequence,
function q calculates the Markoff graph on the field mod p, given p as input.
Currently it just returns the connectivity of the graph, which we don't want
to drop below a certain threshhold. q(2) = 1, q(3) = 6, q(5) = q(7) = q(11)
= q(13) = 4. Appears to be wrong as the graph of q(3) is a cube which should
have connectivity no greater than 3 since it has minimum degree 3. Currently
working on a standalone version using high-quality libraries which will
be faster and ignore Maple's sluggish, buggy procedures.
- November 11: Updated webpage. Accidentally stumbled across question of
efficient
planarity testing while looking up another reference.
- November 10: Skimmed Musiker-Propp paper. Tried counting a few different
sequences of octogon/square tilings (both matchings and trees of grids and
solid staircases) in an attempt to find the (1,4) case hidden inside. (I
would think that a 2 dimensional structure would be necessary to get rid of
those ugly crossing edges.)
Unsuccessful (but noted that none of these sequences seemed to be in
Sloane's database). Noticed that graph.tcl can find weighted matchings with
symbolic weights if Maple formula is output. Slightly modified
graph.tcl and planemaple.pl to
work better for me.
- November 8: Read some of Kuich-Salomaa book "Semirings, Automata,
Languages" on much the same topic as Salomaa-Soittola book. Presentation
seems much clearer. Started getting ideas for how to resurrect topic document
on formal power series/generating function - formal language/complexity class
connections.
This
paper appears to be the latest one on this topic.
- November 6: Tried to attack Salomaa-Soittola book "Automata-Theoretic
Aspects of Formal Power Series." Unsuccessful in making much headway as
very little intuition is given and I don't have much intuition on algebraic
structure beyond the applied approach in 491.
- November 4: Updated graphs.pdf to include proof
of equivalence of alternating square/twice square sequence and straight cube
snake recurrence. Also included proof from a 491 homework of a relationship
between the two alternating sequences; one is a sum of the other. The
proof seems to be flawed so I will attempt to fix it at some point.
- October 23: Abby engineered a (large) transfer matrix to represent the
number of matchings of a cube snake of length n. Wrote up a
maple thing to prove that Abby's matrix was correct
(it represents the same generating function as Paul's, modulo the first term.)
- October 17: Wrote a maple program to try to find
transfer matrix which represented matchings of cube snakes. Wanted to
find 0-1 matrix C such that the sum of the entries of Cn
equalled the number of matchings of a cube snake of length n.
Overnight, program exhaustively searched and found no 4 by 4 matrices. Spent
over a week searching 5 by 5 and did not find any before machine was finally
taken offline.
- October 14: Tried to find a relation between the individual entries of
the A, B matrices and matchings of snakes. Decided that there wasn't much
significance and wrote this up in graphs.pdf. Later
that day, Emilie's presentation in class was enlightening.
- October 6: Learned that one of my topics documents is an entirely solved
problem (sadly, the one I was most interested in), so it has been removed.
More work on topics documents...
- October 5: Set up this web space, started topics documents. Wanted to
convert to HTML using LaTeX2HTML, but
this caused unfortunate black borders to appear around $math$ stuff.
Following the directions here did
not alleviate the situation. PDF seems like an acceptable alternative.
- October 1: Transcribed notes of SSL session of September 30.
Considered bijections between hex snakes and square snakes. Seems to have
some kind of rotational relation.
- September 30: Considered a possible connection between sequences generated
by recurrence relations and the number of strings of a given length which
are members of regular languages. Brought this up in SSL meeting, Jim
had an idea of where this could go.
- September 29: Considered matchings of 2 by 2n+1 rectangle graphs.
Appears to be isomorphic to 3 by 2n rectangle tiling.