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:
- 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.
- 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.
BACK