Nick Anzalone ; John Baldwin ; Ilya Bronshtein ; Kyle Petersen - A Reciprocity Theorem for Monomer-Dimer Coverings

dmtcs:2305 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03) - https://doi.org/10.46298/dmtcs.2305
A Reciprocity Theorem for Monomer-Dimer CoveringsArticle

Authors: Nick Anzalone 1; John Baldwin 2,3; Ilya Bronshtein 4; Kyle Petersen 4

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.


Volume: DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03)
Section: Proceedings
Published on: January 1, 2003
Imported on: November 21, 2016
Keywords: linear recurrences,monomer-dimer coverings,reciprocity,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[NLIN.NLIN-CG] Nonlinear Sciences [physics]/Cellular Automata and Lattice Gases [nlin.CG]

2 Documents citing this article

Consultation statistics

This page has been seen 442 times.
This article's PDF has been downloaded 218 times.