Skip to Main content Skip to Navigation
Conference papers

A Reciprocity Theorem for Monomer-Dimer Coverings

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 \mathbb{Z}$, 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) = \varepsilon_{m,n} N(m,n)$ where $\varepsilon_{m,n}=1$ unless $m \equiv 2(\mod 4)$ and $n$ is odd, in which case $\varepsilon_{m,n}=-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 \mathbb{Z}$, 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.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01183312
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 12, 2015 - 10:07:13 AM
Last modification on : Tuesday, August 6, 2019 - 11:38:50 AM
Long-term archiving on: : Friday, November 13, 2015 - 11:34:52 AM

File

dmAB0115.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01183312, version 1

Collections

Citation

Nick Anzalone, John Baldwin, Ilya Bronshtein, Kyle Petersen. A Reciprocity Theorem for Monomer-Dimer Coverings. Discrete Models for Complex Systems, DMCS'03, 2003, Lyon, France. pp.179-194. ⟨hal-01183312⟩

Share

Metrics

Record views

133

Files downloads

910