APPROXIMATING THE NUMBER OF MONOMER-DIMER COVERINGS OF A LATTICE

We study the problem of counting the number of coverings of a d-dimens ional rectangular lattice by a specified number of monomers and dimers . This problem arises in several models in statistical physics, and ha s been widely studied. A classical technique due to Fisher, Kasteleyn, and Temperley solves the problem exactly in two dimensions when the n umber of monomers is zero (the dimer covering problem), but is not app licable in higher dimensions or in the presence of monomers. This pape r presents the first provably polynomialtime approximation algorithms for computing the number of coverings with any specified number of mon omers in ri-dimensional rectangular lattices with periodic boundaries, for any fixed dimension ri, and in two-dimensional lattices with fixe d 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 guarantee s that do not rely on any assumptions. The method generalizes to count ing coverings of any finite vertex-transitive graph, a class which inc ludes most natural finite lattices with periodic boundary conditions.