Therefore,
X
s⊂E
r(s) = Ex[det[I−iVM]] = Ex[det ˆA] Y
ij∈E
(1−vij)−1
=Z(v.∗(1−v)) Y
ij∈E
(1−vij)−1
= Z(w) ZB .
Graph polynomials from LS
7.1 Introduction
This chapter treats the Loop Series (LS) as a weighted graph characteristics called theta polynomial ΘG(β,γ). Since the LS is the ratio of the partition function and its Bethe approximation, elucidating mathematical structures of the LS are worth interest. In this chapter, we only discuss thebinary pairwisemodels.
Our motivation for the graph polynomial treatment of the LS is to “divide the problem in two parts.” The loop series is evaluated in two steps: 1. the computation ofβ= (βij)ij∈E and γ = (γi)i∈V by an LBP solution; 2. the summation of all the contributions from the sub-coregraphs. Since it seems difficult to derive strong results on the first step, we intend to focus on the second step. If there is an interesting property in the form of the loop series sum, or the Θ-polynomial, the property should be related to the behavior of the error of the partition function approximation.
For example, if the graph is a tree, the Θ-polynomial is equal to one because there are no sub-coregraphs in trees. This fact implies that the Bethe approximation gives the exact values of the partition functions on trees. Another notable success, in this line of approach, is the proof ofZ ≥ZB for attractive models with means biased in one direction [113]. The result can be understood by the property of ΘG: the coefficients of ΘG(β,γ) are non-negative. (See Subsection 6.3.2.)
Though we have not been successful in deriving properties of ΘG(β,γ) that can be used to derive unproved properties of the Bethe approximation, we show that the Θ-polynomial has an interesting property called deletion-contraction relation if the vertex weightsγi are
112
set to be the same. We further analyze the bivariate graph polynomial θG(β, γ), which is obtained as the two-variable version of ΘG(β, γ), and the univariate graph polynomial ωG(β), which is obtained from θG(β, γ) by specializing γ = 2√
−1 and eliminating a factor (1−β)|E|−|V|. We believe that our results give hints for future investigations on the Θ-polynomial.
7.1.1 Basic notations and definitions
In the first place, we review basic notations and definitions on graphs following Subsection 2.1.1. For clarity, we summarize them for the case of graphs, not hypergraphs. Let G = (V, E) be a finite graph, whereV is the set of vertices andE is the set of undirected edges.
In this chapter, a graph means a multigraph, in which loops and multiple edges are allowed.
Note that, in graph theory, aloop1 is an edge that connects a vertex to itself. A subsetsof E is identified with the spanning subgraph (V, s) of Gunless otherwise stated.
In this chapter, we use a symboleto represent an undirected edge, though it was mainly used to represent a directed edge in previous chapters. By the notation ofe=ij we mean that verticesi and j are the endpoints ofe. The number of ends of edges connecting to a vertex iis called thedegreeof iand denoted bydi.
The number of connected components of G is denoted by k(G). The nullity and the rank ofG are defined byn(G) :=|E| − |V|+k(G) and r(G) :=|V| −k(G) respectively.
For a graphG, thecoreof the graphGis given by a process of clipping vertices of degree one step by step [109]. This graph is denoted by core(G). A graphGis called a coregraph if G = core(G). In other words, a graph is a coregraph if and only if the degree of each vertex is not equal to one.
For an edge e ∈ E, the graph G\e is obtained by deleting e and G/e is obtained by contractinge. Ifeis a loop, G/eis the same as G\e. The disjoint union of graphsG1 and G2 is denoted byG1∪G2. The graph with a single vertex andnloops is called thebouquet graphand denoted byBn.
7.1.2 Graph polynomials
Partition functions studied in statistical physics have been a source of many graph polyno-mials. For example, the partition functions of the q-state Potts model and the bivariated
1The term “loop” in “ loopy belief propagation” and “loop series” has no relation to this definition of loop.
random-cluster model of Fortuin and Kasteleyn derive graph polynomials. They are known to be equivalent to the Tutte polynomial [17]. Another example is the monomer-dimer par-tition function with uniform monomer and dimer weights, which is essentially the matching polynomial [53].
The most important feature of our graph polynomials is the deletion-contraction rela-tion:
θG(β, γ) = (1−β)θG\e(β, γ) +βθG/e(β, γ), ωG(β) =ωG\e(β) +βωG/e(β),
wheree∈E is not a loop. Furthermore, these polynomials are multiplicative:
θG1∪G2 =θG1θG2 and ωG1∪G2 =ωG1ωG2.
Graph invariants that satisfy the deletion-contraction relation and the multiplicative law are studied by Tutte [120] in the name of V-function. Our graph polynomials θG and ωG are essentially examples of V-function.
Graph polynomials that satisfy deletion-contraction relations arise from wide range of problems [17, 34]. To the best of our knowledge, all of the graph polynomials that satisfy deletion-contraction relations and appear in some applications are known to be equivalent to the Tutte polynomial or obtained by its specialization. We can list the chromatic poly-nomial, the flow polynomial and the reliability polynomial for such examples. The Tutte polynomial have a reduction formula for loops, but our new graph polynomials do not have such reduction formulas for loops and are essentially different from the Tutte polynomial.
7.1.3 Overview of this chapter
This chapter discusses the following topics. First, in Section 7.2, we define the weighted graph characteristic ΘG(β,γ). An interesting property called deletion-contraction relation is shown when the vertex weights connected by the contracted edge are equal. In Section 7.3, we derive upper and lower bounds on the number of sub-coregraphs, which are at-tained by 3-regular graphs and bouquet graphs respectively. Section 7.4 is a discussion on theθ-polynomial. We see that theθ-polynomial is essentially a new interesting example of a special class of graph polynomials called V-function. Section 7.5 is devoted to investigations
of theω-polynomial including a study on the special valueβ = 1. We show that the poly-nomial coincides with the monomer-dimer partition function with weights parameterized by β. Especially, it is essentially the matching polynomial if the graph is regular.