Planar Graphical Models which are Easy
arXiv:0902.0320 · doi:10.1088/1742-5468/2010/11/P11007
Abstract
We describe a rich family of binary variables statistical mechanics models on a given planar graph which are equivalent to Gaussian Grassmann Graphical models (free fermions) defined on the same graph. Calculation of the partition function (weighted counting) for such a model is easy (of polynomial complexity) as reducible to evaluation of a Pfaffian of a matrix of size equal to twice the number of edges in the graph. In particular, this approach touches upon Holographic Algorithms of Valiant and utilizes the Gauge Transformations discussed in our previous works.
27 pages, 11 figures; misprints corrected
References in corpus (7)
- Matrix product states represent ground states faithfully
- Loop series for discrete statistical models on graphs
- Dimers on surface graphs and spin structures. II
- Loop Calculus in Statistical Physics and Information Science
- Dimers on surface graphs and spin structures. I
- Fermions and Loops on Graphs. I. Loop Calculus for Determinant
- Fermions and Loops on Graphs. II. Monomer-Dimer Model as Series of Determinants