Planar graphical models which are easy

Vladimir Y. Chernyak, Michael Chertkov

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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 it is 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.

Original languageEnglish (US)
Article numberP11007
JournalJournal of Statistical Mechanics: Theory and Experiment
Volume2010
Issue number11
DOIs
StatePublished - Nov 2010
Externally publishedYes

Keywords

  • Analysis of algorithms
  • Gauge theories
  • Rigorous results in statistical mechanics

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint

Dive into the research topics of 'Planar graphical models which are easy'. Together they form a unique fingerprint.

Cite this