Claire Kenyon - Dana Randall - Alistair Sinclair
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.
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