Matchings in Lattice Graphs (Preliminary Version)
| Title | Matchings in Lattice Graphs (Preliminary Version) |
| Publication Type | Technical Report |
| Year of Publication | 1993 |
| Authors | Kenyon, C., Randall D., & Sinclair A. |
| Other Numbers | 807 |
| Abstract | 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. |
| URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-019.pdf |
| Bibliographic Notes | ICSI Technical Report TR-93-019 |
| Abbreviated Authors | C. Kenyon, D. Randall, and A. Sinclair |
| ICSI Publication Type | Technical Report |