The back of the tee-shirt shows some combinatorial constructions related to Markoff numbers. These are numbers that appear in whole-number solutions to the equation x^2 + y^2 + z^2 = 3xyz. For instance, since 2^2 + 5^2 + 29^2 = 3 * 2 * 5 * 29, the numbers 2, 5, and 29 are all Markoff numbers. Markoff numbers turn up in a variety of surprising ways in number theory and geometry.

Each Markoff number is associated with a pair of whole numbers a, b having no factor in common, with a > b; for instance, the Markoff number 29 is associated with the pair a=3, b=2. The members of R.E.A.C.H. (Research Experiences in Algebraic Combinatorics at Harvard) found two different combinatorial ways to obtain a Markoff number from the associated a,b pair: the "paths model" (shown in blue) and the "matchings model" (shown in purple). Moreover they found a simple way to get from one to the other.


The first two panels demonstrate the paths model. In this model, one draws a line segment from (0,0) to (a,b) and shades in all the squares through which this line-segment passes. One divides each of these shaded squares by a northwest-to-southeast diagonal, resulting in a triangulation of the shaded region. Then one looks at all paths from the lower-left corner of the shaded region to the upper-right corner, with the property that second, fourth, sixth, etc., edges of the path pass through the interior of the shaded region. (The first, third, fifth, etc., edges of the path may either pass through the interior or lie on the boundary of the shaded region.) The number of such paths is the Markoff number associated with the pair a,b. E.g., in the example shown, there are exactly 29 paths of the specified kind.

To turn the paths model into the matchings model (which was actually discovered earlier), one starts by putting a vertex in the middle of each of the triangles (in the triangulation of the shaded region) and connecting it to all three of the corners of the triangle. (See the third panel, ignoring the edge-shading for now.) One then discards all the edges of the original triangulation, and for good measure one also discards the lower-left and upper-right vertices and the edges incident with them. (See the fourth and fifth panels.) The resulting graph is composed of parallelograms, and if one distorts the picture so that these parallelograms become squares, one obtains the "snake graph" associated with the pair a,b (see the sixth panel). The Markoff number is equal to the number of perfect matchings of this snake graph, where a perfect matching of a graph is a collection of edges with the property that every vertex of the graph lies on exactly one edge in the collection. For example, the graph shown in the sixth panel has exactly 29 perfect matchings (one of which is shown by the purple edge-shading).

The figure also shows how a specific path through the first graph (the one obtained by triangulating the set of lattice squares that intersect the path from (0,0) to (a,b)) can be associated with a perfect matching of the second graph; the path is shown by blue edges and the perfect matching by purple edges. It is easier to describe the bijection in reverse: given a purple matching, an edge in the triangulation gets to be blue if it is adjacent to either two purple edges or none at all (where a potentially-blue edge is considered adjacent to a purple edge if they lie on a tiny triangle like the ones seen in the third panel).


Tom Ace, Markoff numbers web-page; http://www.minortriad.com/markoff.html.

John Conway and Richard Guy, "The Book of Numbers".

Andy Itsara, Gregg Musiker, James Propp and Rui Viana, Combinatorial interpretations for the Markoff numbers, in progress.

Gabriel Carroll, Andy Itsara, Ian Le, and James Propp, Markov Numbers, Farey Sequences, and the Ptolemy Recurrence, in progress.