Approximating the Number of Monomer-Dimer Coverings in Periodic Lattices

Published

July 1, 2001

Author(s)

Isabel M. Beichl, Dianne M. O'Leary, F Sullivan

Abstract

Our starting point is an algorithm of Kenyon, Randall, and Sinclair, which built upon the ideas of Jerrum and Sinclair, giving an approximation to crucial parameters of the monomer-dimer covering problem in polynomial time. We make two key improvements to their algorithm: we greatly reduce the number of simulations that must be run by estimating good values of the generating function parameter, and we greatly reduce the number of steps that must be taken in each simulation by aggregating to a simulation with at most five states. The result is an algorithm that is computationally feasible for modestly-sized meshes. We use our algorithm on two and three-dimensional problems, computing approximations to the coefficients of the generating function and some limiting values.

Citation

Physical Review E (Statistical, Nonlinear, and Soft Matter Physics)

Volume

64

Issue

1

Pub Type

Journals

Download Paper

Local Download

Keywords

algorithm, dimer covering problem, Monomer-dimer problem, Monte Carlo, Partition function, random walk

Citation

Beichl, I. , O'Leary, D. and Sullivan, F. (2001), Approximating the Number of Monomer-Dimer Coverings in Periodic Lattices, Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=150809 (Accessed October 8, 2025)