Approximating the Number of Monomer-Dimer Coverings in Periodic Lattices
Isabel M. Beichl, Dianne M. O'Leary, F Sullivan
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.
Physical Review E (Statistical, Nonlinear, and Soft Matter Physics)
algorithm, dimer covering problem, Monomer-dimer problem, Monte Carlo, Partition function, random walk
, O'Leary, D.
and Sullivan, F.
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)