DMTCS Proceedings, Discrete Models for Complex Systems, DMCS'03

Font Size:  Small  Medium  Large

A Reciprocity Theorem for Monomer-Dimer Coverings

Nick Anzalone, John Baldwin, Ilya Bronshtein, T. Kyle Petersen

Abstract


The problem of counting monomer-dimer coverings of a lattice is a longstanding problem in statistical mechanics. It has only been exactly solved for the special case of dimer coverings in two dimensions ([Ka61], [TF61]). In earlier work, Stanley [St85] proved a reciprocity principle governing the number N(m,n) of dimer coverings of an m by n rectangular grid (also known as perfect matchings), where m is fixed and n is allowed to vary. As reinterpreted by Propp [P01], Stanley's result concerns the unique way of extending N(m,n) to n < 0 so that the resulting bi-infinite sequence, N(m,n) for n in ZZ, satisfies a linear recurrence relation with constant coefficients. In particular, Stanley shows that N(m,n) is always an integer satisfying the relation N(m,-2-n) = epsilon N(m,n) where epsilon = 1 unless m = 2(mod 4) and n is odd, in which case epsilon = -1. Furthermore, Propp's method was applicable to higher-dimensional cases. This paper discusses similar investigations of the numbers M(m,n), of monomer-dimer coverings, or equivalently (not necessarily perfect) matchings of an m by n rectangular grid. We show that for each fixed m there is a unique way of extending M(m,n) to n < 0 so that the resulting bi-infinite sequence, M(m,n) for n in ZZ, satisfies a linear recurrence relation with constant coefficients. We show that M(m,n), a priori a rational number, is always an integer, using a generalization of the combinatorial model offered by Propp. Lastly, we give a new statement of reciprocity in terms of multivariate generating functions from which Stanley's result follows.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional