Publication Details
Title: Matchings in Lattice Graphs (Preliminary Version)
Author: C. Kenyon, D. Randall, and A. Sinclair
Group: ICSI Technical Reports
Date: March 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-019.pdf
Overview:
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 Information:
ICSI Technical Report TR-93-019
Bibliographic Reference:
C. Kenyon, D. Randall, and A. Sinclair. Matchings in Lattice Graphs (Preliminary Version). ICSI Technical Report TR-93-019, March 1993
Author: C. Kenyon, D. Randall, and A. Sinclair
Group: ICSI Technical Reports
Date: March 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-019.pdf
Overview:
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 Information:
ICSI Technical Report TR-93-019
Bibliographic Reference:
C. Kenyon, D. Randall, and A. Sinclair. Matchings in Lattice Graphs (Preliminary Version). ICSI Technical Report TR-93-019, March 1993