# 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.