Reciprocity theorems for enumeration of perfect matchingsJim ProppUniversity of Wisconsin
February 13,

ABSTRACT


There are many cases in which a naturallydefined 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(nc)$ for all $n$ (for some fixed integer $c$ and for some specific signrule). 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(n2)$, 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 boxproduct of any finite graph $G$ with a path of $n$ vertices. 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

