Matchings in Lattice Graphs (Preliminary Version)

TitleMatchings in Lattice Graphs (Preliminary Version)
Publication TypeTechnical Report
Year of Publication1993
AuthorsKenyon, C., Randall D., & Sinclair A.
Other Numbers807

We study the problem of counting the number of matchings of given cardinality in a d-dimensional rectangular lattice. This problem arises in several models in statistical physics, including monomer-dimer systems and cell-cluster theory. A classical algorithms due to Fisher, Kasteleyn and Temperley counts perfect matchings exactly in two dimensions, but is not applicable in higher dimensions and does not allow one to count matchings of arbitrary cardinality. In this paper, we present the first efficient approximation algorithms for counting matchings of arbitrary cardinality in (i) d-dimensional "periodic" lattices (i.e., with wrap-around edges) in any fixed dimension-d; and (ii) two-dimensional lattices with "fixed boundary conditions" (i.e., no wrap-around edges). Our technique generalizes to approximately counting matchings in any bipartite graph that is the Cayley graph of some finite group.

Bibliographic Notes

ICSI Technical Report TR-93-019

Abbreviated Authors

C. Kenyon, D. Randall, and A. Sinclair

ICSI Publication Type

Technical Report