Reciprocity theorems for enumeration of perfect matchings

Jim Propp

University of Wisconsin

February 13,
refreshments at 3:45pm


There are many cases in which a naturally-defined sequence of graphs $G_1,G_2,\dots$ has the property that if one defines $f(n)$ as the number of perfect matchings of $G_n$ and extends the function $f$ in a natural way so that its domain contains all the integers, the resulting extension satisfies a reciprocity relation of the form $f(-n)=\pm f(n-c)$ for all $n$ (for some fixed integer $c$ and for some specific sign-rule).

I will survey known results of this type, some of which can be explained by Ehrhart reciprocity but most of which cannot.

For example, let $G_n$ denote the $m$-by-$n$ grid, with $m$ fixed. The associated numbers $f(n)$ satisfy a linear recurrence relation, and so may be extrapolated to negative values of $n$; these extrapolated values satisfy the relation $f(-n)=\epsilon_{m,n}f(n-2)$, where $\epsilon_{m,n}=-1$ if $m \equiv 2$ (mod 4) and $n$ is odd, and $\epsilon_{m,n}=+1$ otherwise. This result was proved algebraically by Stanley in 1985, but a new, combinatorial proof yields a generalization to the case where $G_n$ is the box-product of any finite graph $G$ with a path of $n$ vertices.

Speaker's Contact Info: propp(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on February 07, 2002 at 02:57 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.