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.
Instructor:
David Speyer
1846 East Hall
speyer@umich.edu
Course homepage: http://www.math.lsa.umich.edu/~speyer/669.html
Level: introductory graduate.
Prerequisites: Comfort with Linear Algebra
Student work expected: I will give problem sets every other week.
Summary:
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
SPRING BREAK
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