Matchings in lattice graphs
Claire Kenyon, Dana Randall, Alistair Sinclair · 1993
We study the problem of counting the number of matchings of given cardinalitg in a d-dimensional rectangular lattice.This problem arises in several models in statistical phgsics, including monomer-dimer systems and cell-cluster theory.A classical algorithm 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 eficient approximation algorithms for counting matchings of arbitrary cardinality in (i) d-dimensional '>en"odic" 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.