Planar graphical models which are easy

Vladimir Y. Chernyak, Michael Chertkov

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

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
Article numberP11007
JournalJournal of Statistical Mechanics: Theory and Experiment
Volume2010
Issue number11
DOIs
Publication statusPublished - Nov 2010
Externally publishedYes

Keywords

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

Fingerprint

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

Cite this