Approximating the Number of Monomer-Dimer Coverings of a Lattice

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 n..