Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Approximating the Number of Monomer-Dimer Coverings in Periodic Lattices

Published

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

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 December 4, 2023)
Created July 1, 2001, Updated February 17, 2017