Approximating the Number of Monomer-Dimer
Coverings of a Lattice

Claire Kenyon - Dana Randall - Alistair Sinclair

Abstract:

The paper studies the problem of counting the number of coverings of a d-dimensional rectangular lattice by a specified number of monomers and dimers. This problem arises in several models in statistical physics, and has been widely studied. A classical technique due to Fisher, Kasteleyn and Temperley solves the problem exactly in two dimensions when the number of monomers is zero (the dimer covering problem), but is not applicable in higher dimensions or in the presence of monomers. This paper presents the first provably polynomial time approximation algorithms for computing the number of coverings with any specified number of monomers in d-dimensional rectangular lattices with periodic boundaries, for any fixed dimension d, and in two-dimensional lattices with fixed boundaries. The algorithms are based on Monte Carlo simulation of a suitable Markov chain, and, in contrast to most Monte Carlo algorithms in statistical physics, have rigorously derived performance guarantees that do not rely on any assumptions. The method generalizes to counting coverings of any finite vertex-transitive graph, a class which includes most natural finite lattices with periodic boundary conditions.

Keywords: monomer-dimer problem, dimer coverings, lattice statistics, Monte Carlo methods, relaxation time, mixing time, approximation algorithm, Fisher-Kasteleyn-Temperley algorithm, perfect matchings, monomer-dimer correlations, vertex-transitive graphs.

About this document ...

Approximating the Number of Monomer-Dimer
Coverings of a Lattice

This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -dir /users/algo/kenyon/WWW/Publis/ -split 0 jsp-abstract.tex.

The translation was initiated by Claire Kenyon on 3/19/1998

Footnotes

...Lattice

A preliminary version of this paper appeared under the title ``Matchings in lattice graphs'' in the Proceedings of the 25th ACM Symposium on Theory of Computing, San Diego, May 1993, ACM Press, pp. 738-746.

...Kenyon

CNRS, Ecole Normale Supérieure de Lyon, France. Part of this work was done while the author was visiting ICSI, Berkeley. E-mail: kenyon@lip.ens-lyon.fr.

...Randall

Department of Computer Science, Princeton University. This work was done while the author was at the University of California at Berkeley. Supported in part by an AT&T PhD Fellowship and by NSF grant CCR92-01092. E-mail: randall@cs.princeton.edu.

...Sinclair

Computer Science Division, University of California at Berkeley. Part of this work was done while the author was visiting ICSI, Berkeley, on leave from the University of Edinburgh. Supported in part by grant GR/F 90363 of the UK Science and Engineering Research Council, by Esprit Working Group ``RAND'', and by NSF grant CCR95-05448. E-mail: sinclair@icsi.berkeley.edu.