Glossary 2003

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 Z^3: (1,1,1), (1,2,1), (1,2,5), ...
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:
  1. The cluster algebra has a family of generators called cluster variables.
  2. A cluster is a set of n cluster variables
  3. 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.
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.
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
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.