TY - JOUR

T1 - Fermions and loops on graphs

T2 - II. A monomer-dimer model as a series of determinants

AU - Chernyak, Vladimir Y.

AU - Chertkov, Michael

PY - 2008

Y1 - 2008

N2 - We continue the discussion of the fermion models on graphs that started in the first paper of the series. Here we introduce a graphical gauge model (GGM) and show that: (a)it can be stated as an average/sum of a determinant defined on the graph over a (binary) gauge field; (b)it is equivalent to the monomer-dimer (MD) model on the graph; (c)the partition function of the model allows an explicit expression in terms of a series over disjoint directed cycles, where each term is a product of local contributions along the cycle and the determinant of a matrix defined on the remainder of the graph (excluding the cycle). We also establish a relation between the MD model on the graph and the determinant series, discussed in the first paper - however, considered using simple non-belief propagation choice of the gauge. We conclude with a discussion of possible analytic and algorithmic consequences of these results, as well as related questions and challenges.

AB - We continue the discussion of the fermion models on graphs that started in the first paper of the series. Here we introduce a graphical gauge model (GGM) and show that: (a)it can be stated as an average/sum of a determinant defined on the graph over a (binary) gauge field; (b)it is equivalent to the monomer-dimer (MD) model on the graph; (c)the partition function of the model allows an explicit expression in terms of a series over disjoint directed cycles, where each term is a product of local contributions along the cycle and the determinant of a matrix defined on the remainder of the graph (excluding the cycle). We also establish a relation between the MD model on the graph and the determinant series, discussed in the first paper - however, considered using simple non-belief propagation choice of the gauge. We conclude with a discussion of possible analytic and algorithmic consequences of these results, as well as related questions and challenges.

KW - Gauge theories

KW - Message-passing algorithms

KW - Rigorous results in statistical mechanics

UR - http://www.scopus.com/inward/record.url?scp=65549128561&partnerID=8YFLogxK

U2 - 10.1088/1742-5468/2008/12/P12012

DO - 10.1088/1742-5468/2008/12/P12012

M3 - Article

AN - SCOPUS:65549128561

VL - 2008

JO - Journal of Statistical Mechanics: Theory and Experiment

JF - Journal of Statistical Mechanics: Theory and Experiment

SN - 1742-5468

IS - 12

M1 - P12012

ER -