Math 669: Combinatorics of Perfect Matchings

Winter 2007

Course meets: Tuesdays and Thursdays 2:30-4 in 3866 East Hall.

Office Hours: Wednesdays 1-2 PM in 1846, or by appointment. Also, feel free to knock on my door.
David Speyer

1846 East Hall

Course homepage:

Level: introductory graduate.

Prerequisites: Comfort with Linear Algebra

Student work expected: I will give problem sets every other week.

Let G be a graph, then a perfect matching of G is a collection of edges of G such that every vertex lies on exactly one edge. The study of perfect matchings goes back to McMahon in the nineteenth century and goes forward to current papers of Richard Kenyon and recent Fields medalist Andrei Okounkov. Perfect matchings occur in applied mathematics when studying the entropy of large carbon structures or the formation of crystals and, more generally, form an excellent test case for methods of statistical mechanics. In pure mathematics, perfect matchings can be related to the combinatorics of Young Tableux and to the enumerative geometry of curves in three-folds.

The first question to ask about perfect matchings is how many there are. We will introduce several techniques for answering this question in various cases. Next, we will show how to study the structure of the collection of perfect matchings, showing that it is possible to move between any two matchings via a series of simple restructuring moves and we will bound the number of moves which are needed. To do this, we will show how to put a lattice structure on the collection of perfect matchings of a planar graph and exploit it. We will show how to encode the perfect matchings of a graph into a generating function from which most statistics of matchings are easily extracted. In particular, we will be able to explain why the number of perfect matchings of families of plane graphs are often perfect powers. If time permits, we will discuss how this generating function can be used to give combinatorial proofs of various Laurentness theorems.

We will then shift from studying exact enumerative questions to studying the statistical properties of a randomly chosen perfect matching in a large graph. We will begin by presenting algorithms to efficiently and uniformly sample from the space of perfect matchings. We will then describe Kenyon and Okounkov's elegant description of the local properties of a random matching in terms of amoebae of algebraic curves (which we will define).

For most of the course, we will use nothing more than basic combinatorial arguments and some linear algebra. In the last weeks, we will use some standard facts from complex analysis.

Rough Syllabus:
This is the schedule I plan to follow; I imagine that it will have to be modified as the course develops. I'll add more detail as lectures come closer. In general, I intend to discuss exact enumerative results before spring break and asymptotic results after.
January 4: Introduction and motivating examples
January 9-11: Connections between Perfect Matchings and other Combinatorial Objects
January 16-18: Plane Partitions
January 23-25: The Lattice Structure on the Set of Matchings of a Planar Graph, and Applications Thereof
          Possible application — exact uniform sampling via Coupling from the Past.
January 30-February 1: The Urban Renewal Method and Applications
February 6-8:The Octahedron Recurrence and Applications
          Possible application — some positivity results in cluster algebras
February 13-15: Determinental Methods — Kastelyn Matrics and Pfaffians
February 20-22: To be determined later
Early March: Asymtotics of the Local Structure of Perfect Matchings, including an introduction to amoebae
Late March: Exact Sampling by Domino Shuffling, Frozen Regions and Arctic Circle Theorems
Early April: Recent Results on Asymtotics of the Global Structure of Perfect Matchings