We did this two years ago, and never got too far. Might as well try
again; it was a good idea. “*Document everything*.”

- Snake Graph
- a planar graph on a square grid. It might be best for me to define this recursivly. THe smallest snake graph is the vertices at (0,0),(0,1),(1,0),(1,1) and the four edges joining (0,0) to (0,1), (0,1) to (1,1), (1,1) to (1,0), and (1,0) to (0,0). A snake graph cen be built from a smaller snake graph by adding two verices and three edges in one of two proscribed ways. If (a,b) is the top-rightmost vertex, you can add vertices at (a+1,b) and (a+1,b-1) or at (a,b+1) and (a-1,b+1). Then add one edge between the two new edges and one from each of those vertices to the nearest vertex in the old graph.
- Straight Snake Graph
- A 2-by-n square grid. The number of matchings is the F_n, the n-th Fibbonacci number.
- Staircase Snake Graph
- what is sounds like. A snake
graph where the new boxes are added alternating to the right and up. A
staircase snake graph with
*2n*vertices has*n*perfect matchings. (arithmetic progression) - perfect matching of a graph
- Each vertex is paired up with
exactly one other vertex by selecting edges in the graph.
A graph
*M*is a perfect matching of a loopless graph*G*if (1)*M*is a subgraph of*G*. (2)*M*contains all of the vertices of*G*. and (3) Each vertex of*M*is incident to exactly one edge. - Fibonacci numbers
- The sequence 1,1,2,3,5,8,13,21..., defined by F_n = F_{n-1} + F_{n-2} and F_0 = F_1 = 1.
- bijective proof
- type of combinatorial proof that shows that the size of two sets are equal by constricting a bijection between them.
- Markoff equation
- The equation: a^2 + b^2 + c^2 = 3 a b c
- Markoff triples
- solutions to the Markoff equation from
: (1,1,1), (1,2,1), (1,2,5), ...**Z**^3 - Markoff numbers
- Integers that appear in Markoff tripples: 1, 2, 5, 13, 29, 34, 89, 169, 194, ...
- Solution to markoff equation
- If
*(a,b,c)*is a solution to Markoff equation, then*(a,b,c')*is also a solution:*c' = (a^2+b^2)/c*and*c' = 3ab - c* - Domino Tiling
- another way to look at perfect matchings on a square grid. Start with a graph on a square grid. Take its dual (replace vertices with faces and faces with vertices, ignoring the unbounded face) Each matching on the original graph corresponds to tiling the new graph with 2x1 domino tiles covering two adjacent faces.
- Cluster Algebra
- A class of commutative algebra, first
described by Fomin and Zelevinsky
(arXiv:math.RT/0104151).
A cluster algebra of rank
*n*is a commutative ring with unit and no zero divisors with the following structure:- The cluster algebra has a family of generators called
*cluster variables*. - A
*cluster*is a set of*n*cluster variables - For any cluster
**x**and*x*in**x**, there is another cluster**x'**=**x**-{*x*} union {*x'*}, where*x*and*x'*are related by a mysterous*exchange relation*.

- The cluster algebra has a family of generators called
- Markoff polynomials
- suppose that
formal variables
*x,y,z*are a solution to the Markoff equation. Find other such solutions using the*c' = (a^2+b^2)/c*relation. Other solutions make up the set of Markoff polynomials, a subset of the Laurent polynomials. - Arithmetic Progression
- any sequence in
the form
*a, a+n, a+2n, a+3n, ...* - Weighted Graph
- A graph, along with a number or formal variable assigned to each edge.
- Weighted Sum of Perfect Matchings
- the sum over all perfect matching of a graph of the product of the edge weights of all the edges in the matching. If each edge has weight 1, then the weighted sum is simply the number of perfect matchings.
- generating function
- a function
*f(x) = SUM a_n x^n*, where*a_n*counts something. - Laurent polynomial
- a polynomial divided by a monomial.
- mediant
- map from rationals X rationals –> rationals. mediant(a/b, c/d) := (a+c)/(b+d). Refer to Kirillov's two jokes on this subject.
- Apollonian gasket
- ?
- triangulations of polygons
- ?
- Y-graphs
- ?
- graphical condensation
- an operation used in bijective proofs
involving perfect matchings. If you superimpose two perfect machings
of a graph, you will get a loopless multigraph where each vertex is
incident to two edges. The number of ways to decompose two graphs is
*2^k*, where*k*is the number of cycles in the doubled graph. See arXiv:math.CO/0304090 - Cube Snakes
- A three-dimensional analog of the snake graph. The smallest cube snake is the cube. Larger cube snakes can be made by adding a square in one of three positions. Note that these are still planar graphs.
- Flat Cube Snake
- A cube snake whose vertices lie in one of two planes.
- bipartite graph
- A graph where the
vertices can be partitioned into two sets
*X*and*Y*, such that all edges join a vertex from set*X*to a vertex from set*Y*. *k*-regular graph- A graph where each
vertex is incident to exactly
*k*edges. - Laurent phenomenon
- When you divide one Laurent polynomial by another, wou will not usually get another Laurent polynomial. But there are some systems where you always get another Laurent polynomial. This happens in Cluster Algebras. This a deep and mysterious thing. See arXiv:math.CO/0104241.
- cellular automata
- Mathematical system that evolves over time. There is a
function
*f*: X × T –> Y, where X is the coordinate space (maybe the integers), T is the time axis (nonnegative intigers, maybe), and Y is the possible values at each coodinate. The system evolves according to some function Φ.

*f_t*(*n*) = Φ(*f_{t-1}*(*n-1*),*f_{t-1}*(*n*),*f_{t-1}*(*n+1*))

In order for this to work, we need a starting condition*f_0*(*x*) =*g*(*x*). If Φ is only a function of a cell and its two closest neightbors, and if Y = {0,1}, then Φ is one of 2^(2^3)=256 possible values. See Wolfram's book for more one-dimentional cellular automata than any man could stand. - faithful polynimial
- A subset of the Laurent polynomials. An expression is a faithful polynomial if it is a polynomial with all coefficents equal to plus-or-minus 1 divided by a monomial with unit coefficents.