Mehler Formulae for Matching Polynomials of Graphs and Independence Polynomials of Clawfree Graphs

Bodo Lass

Université de Lyon ; Université Lyon 1 ; INSA de Lyon, F-69621 ; Ecole Centrale de Lyon ; CNRS, UMR5208, Institut Camille Jordan, 43 blvd du 11 novembre 1918, F-69622 Villeurbanne-Cedex, France

                               lass @ math.univ-lyon1.fr

À Dominique Foata, pour son 75-ième anniversaire

Abstract

The independence polynomial of a graph G is the polynomial ∑_{I} x^{|I|}, summed over all independent subsets I ⊆ V (G). We show that if G is clawfree, then there exists a Mehler formula for its independence polynomial. This was proved for matching polynomials in [19] and extends the combinatorial proof of the Mehler formula found by Foata [9]. It implies immediately that all the roots of the independence polynomial of a clawfree graph are real, answering a question posed by Hamidoune [14] and Stanley [28] and solved by Chudnovsky and Seymour [6]. We also prove a Mehler formula for the multivariate matching polynomial, extending results of [19].

1 Introduction

Let V be a finite set of vertices, n = |V |, and let G = (V, E) be a simple graph, i.e. E, the set of edges, is a subset of \binom{V}{2}, the family of all 2-element subsets of V.

An r-matching in G is a set of r edges of G, no two of which have a vertex in common. Clearly, r ≤ ⌊n/2⌋. Let m_{r}(G) be the number of r-matchings in G, with the convention that m_{0}(G) := 1. The matching polynomial of G is (see [11] or [10], chapter 1)

M_{G}(x) := ∑_{r=0}^{⌊n/2⌋}(−1)^{r}m_{r}(G)x^{n−2r}.  (1.1)

These polynomials were introduced by Heilmann and Lieb [15], who, motivated by statistical physics, mainly studied their roots. They obtained many estimations on the locations of those roots and provided several different proofs for their main theorem that all roots of M_{G}(x) are real. Another proof of this theorem was obtained by Godsil, which he reproduced in his book [10] together with all the classical proofs. However, all those proofs rely on a recursive approach (via the deletion of a vertex) towards the matching polynomial. One of the purposes of our paper [19] was to give a short proof that avoids this traditional deletion technique.

If G = (V, \binom{V}{2}), i.e. E = \binom{V}{2}, then G is called a complete graph and denoted by G = K_{n}, where n = |V |. Its matching polynomial M_{K_{n}}(x) is the classical Hermite polynomial. For those Hermite polynomials the famous Mehler formula affirms that

1 + ∑_{n=1}^{∞} M_{K_{n}}(x)M_{K_{n}}(y) · z^{n}/n! =

\frac{1}{\sqrt{1 − z^{2}}} · exp [(\frac{x + y}{2} )^{2} · \frac{z}{1 + z} − (\frac{x − y}{2} )^{2} · \frac{z}{1 − z} ] .  (1.2)

Foata [9] had the idea to prove this formula in a combinatorial way. He showed the very surprising result that the Mehler formula, from a combinatorial point of view, reflects nothing more than the easy and classical fact that the union of two matchings of a complete graph forms several cycles and paths. This was the beginning of the combinatorial studies of orthogonal polynomials. In our paper [19] we generalized the combinatorial proof found by Foata [9] to matching polynomials. Therefore, it seems natural to call our generalization a Mehler formula for matching polynomials. We showed that it immediately implies that

|M_{G}(x)|^{2} ≥ [(ℑm x)^{2}]^{n} + 2|E| · [(ℑm x)^{2}]^{n−1}  (1.3)

for every x ∈ ℂ, i.e. that all the roots of M_{G}(x) are real. Moreover, this fact holds for a common generalization of the matching polynomial and the rook polynomial, see [21, 22].

An independent set in a finite simple graph G = (V, E) is a set of pairwise non-adjacent vertices. Let i_{r}(G) be the number of independent sets with r vertices, in particular i_{1}(G) = |V | and i_{0}(G) = 1. If α is the maximum number of independent points of G, then its independence polynomial is the polynomial

I_{G}(x) := ∑_{r=0}^{α} i_{r}(G) · x^{r} = ∑_{I} x^{|I|},  (1.4)

where the sum is over all independent subsets I ⊆ V (see for instance [1, 2, 3, 4, 8, 12, 13, 16, 20, 23, 24, 25] for work on these polynomials). A claw is the graph with vertex set {A, B, C, D} and three edges AB, AC, AD, and its independence polynomial is

1 + 4x + 3x^{2} + x^{3}.  (1.5)

Since this polynomial does not have three real roots, it cannot be affirmed that all the roots of any independence polynomial I_{G}(x) are real. A graph G, however, is said to be clawfree if no induced subgraph of it is a claw. It was conjectured by Hamidoune [14] and Stanley [28] and proved by Chudnovsky and Seymour [6] that all the roots of I_{G}(x) are real (and of course negative) if G is clawfree.

Given a graph G, its line graph L(G) is the graph whose vertex set is the set of edges of G, and two vertices are adjacent if they share an end in G. If G is simple, then L(G) is also simple. Moreover, the matchings in G are in bijection with the independent sets in L(G), i.e. the sets of pairwise non-adjacent vertices. Not every simple graph, however, is the line graph of another simple graph G: if we take an edge of G sharing an end with three other edges, then two of them must share the same end with it, i.e. those two do not form a matching. Therefore line graphs are always clawfree. Moreover, the matching polynomial of G and the independence polynomial of its line graph L(G) are related by the following identity:

M_{G}(x) = x^{n} · I_{L(G)}(−1/x^{2}),  (1.6)

which proves that all roots of M_{G}(x) are real if and only if all roots of I_{L(G)}(x) are real and negative.

Since Chudnovsky and Seymour [6] showed that all roots of I_{G}(x) are real and negative as soon as G is clawfree, it is natural to conjecture that a Mehler formula might hold for the independence polynomial of any clawfree graph. This conjecture is indeed true: it is the purpose of the first section of this article to prove such a formula, which implies immediately that

|I_{G}(x^{2})|^{2} ≥ i_{α}(G) · [4(ℜe x)^{2}]^{α} ,  |I_{G}(−x^{2})|^{2} ≥ i_{α}(G) · [4(ℑm x)^{2}]^{α}  (1.7)

for every x ∈ ℂ. It follows that all the roots of I_{G}(x) are real and negative, if G is clawfree.

If w is a real-valued function on the vertex set of the graph G, then the weighted independence polynomial is

I_{G,w}(x) := ∑_{I} ∏_{v∈I}[x · w(v)],  (1.8)

where the sum is over all independent subsets I ⊆ V (if I is empty, then the product is 1 by definition). Engström [7] showed that if w is nonnegative and G is clawfree, then all the roots of I_{G,w}(x) are real (and of course negative). His proof is in three steps, first for integer weights, then rational and finally for real weights. More precisely, if w(v) is a positive integer for every vertex, then it is a classical operation of substitution to replace each v ∈ V by a clique (complete graph) of size w(v) and to join vertices of different cliques if and only if the original vertices of G were joined. It is easy to see that this new graph G(w) is still clawfree and that I_{G(w)}(x) = I_{G,w}(x). Last but not least, Engström [7] had to give some approximation arguments to complete his proof. We will show at the end of the first section by means of an example that our Mehler formula approach works perfectly in this weighted case as well. We could have started directly with the weighted generalization, but preferred not to do so, because we think it is easier to understand the arguments for the first time on the most important special case.

When talking about independence polynomials with positive vertex weights, one must also talk about matching polynomials with positive edge weights, and this is what we did already in the last section of [19]. However, for matching polynomials it is not only possible to introduce positive edge weights, but one can also introduce additional complex vertex weights and still get nice results, notably the Heilmann-Lieb theorem [15]. We will show in our last section that even a Mehler formula holds in this most general context and that it implies this and other classical theorems. In particular, the most radical specialization gives the Mehler formula for Hermite polynomials, explaining finally the name of this article.

Of course, one can obtain the univariate polynomials from the multivariate ones by suitable specializations. But the multivariate polynomials are, despite being more general, in many ways simpler objects to work with: for instance, they are multiaffine (i.e. of degree 1 in each variable separately); and a multiaffine polynomial in many variables is in some respects easier to work with than a general polynomial in one variable (e.g. it may permit simple proofs by induction on the number of variables). For this and other reasons, the multivariate extension of a single variable result is sometimes much easier to prove than its single-variable specialization; and much additional insight can often be gained by studying the multivariate polynomial, even if one is ultimately interested in the univariate specialization. This ”multivariate ideology” has borne great fruit in the study of the Tutte polynomial [17]. Some early examples of what can be gained by the multivariate approach to the independence polynomial can be found in [26, 27]: notably the connection to the Lovász local lemma and a simple inductive proof for a zero-free polydisc. Another example concerns the two simple proofs found by [5] of the multivariate Heilmann-Lieb theorem [15]. The first proof is by induction on the number of vertices and is based on a recursion relation associated to deletion of a vertex; it is a slight simplification/improvement of the inductive proof given by Heilmann-Lieb (in that proof the deletion was limited to certain special vertices). The second proof is very different and is based on the fact that the ”multiaffine part” operator preserves the half-plane property. In short, the multivariate result is the natural Heilmann-Lieb theorem, and has two very simple and elegant proofs. The univariate result that is most often quoted as ”the” Heilmann-Lieb theorem is a mere corollary. (The situation here is quite analogous to that concerning the Lee-Yang theorem for ferromagnetic Ising models. There, too, the univariate corollary is frequently quoted, but it is the multivariate result that is fundamental. Indeed, the proof of the Lee-Yang theorem imagined in [5] is very closely analogous to their second proof of the Heilmann-Lieb theorem.)

However, we think that the combinatorics underlying those results can be hidden behind the many variables. It was Foata’s idea [9] that the classical Mehler formula for Hermite polynomials has a very simple combinatorial explanation: the union of two matchings of a graph forms several cycles and paths. It is the aim of this article to show that the same idea allows to obtain more general results, in one or many variables. It seems natural to us to call those generalizations also Mehler formulae. In the last section of this article we will see how everything specializes to the classical Mehler formula for Hermite polynomials.

2 Mehler Formulae for Independence Polynomials of Clawfree Graphs

Finding a Mehler formula for the independence polynomial of a clawfree graph G means that we have to be able to interpret combinatorially the product I_{G}(x)I_{G}(y). In other words, if the variable x is assigned to each vertex of one independent set of G of cardinality r and if the variable y is assigned to each vertex of another independent set of G of cardinality s, then we must identify a combinatorial object to which the product x^{r} · y^{s} is assigned. A natural choice is certainly the subgraph P CC of G induced by the union of our two independent sets (P CC shall suggest ”path-cycle-configuration”) together with a labeling of its vertices as x, y or xy. The vertices labeled x or xy form an independent set of vertices of P CC, as do the vertices labeled y or xy; in particular, the vertices labeled xy must be isolated vertices of P CC. Any edge of P CC must join a vertex labeled x with a vertex labeled y: P CC is a bipartite graph. Moreover, the degree of each vertex of P CC is at most two since G is clawfree and P CC is an induced subgraph. Therefore P CC is an induced subgraph of G that is a disjoint union of some isolated vertices IV (P CC) labeled xy, some even cycles EC(P CC) (of length at least 4) labeled alternately with x and y, some even paths EP (P CC) (with at least two vertices) labeled alternately with x and y, and, last but not least, some odd paths OP (P CC) (with at least one vertex) labeled alternately with x and y. We want to consider P CC not only as an induced subgraph, but as an induced subgraph of G with marked isolated vertices in order to be able to distinguish isolated vertices from odd paths of length 1. Therefore IV (P CC) and OP (P CC) are well-defined. The same P CC appears several times in the product I_{G}(x)I_{G}(y). Indeed, IV (P CC) is fixed once P CC is fixed, but the variables x and y can still be exchanged on each path and cycle of P CC. Therefore P CC must be counted with the weight

∏_{IV (P CC)} [xy] ∏_{EC(P CC)} [2 · x^{|EC(P CC)|/2}y^{|EC(P CC)|/2}] ∏_{EP (P CC)} [2 · x^{|EP (P CC)|/2}y^{|EP (P CC)|/2}]

∏_{OP (P CC)} [x^{(|OP (P CC)|+1)/2}y^{(|OP (P CC)|−1)/2} + x^{(|OP (P CC)|−1)/2}y^{(|OP (P CC)|+1)/2}] ,  (2.1)

where |EC(P CC)|, |EP (P CC)| and |OP (P CC)| denote the number of vertices of the respective cycle or path. Note that products over empty sets are always 1 by definition. In particular, P CC can be the empty graph (a pointless concept): its weight is 1. We have proved our main theorem, a Mehler formula for the independence polynomial of any clawfree graph G.

Theorem 1. We have

I_{G}(x)I_{G}(y) = ∑_{P CC}( ∏_{IV (P CC)} [xy] ∏_{EC(P CC)} [2 · (xy)^{|EC(P CC)|/2}] ∏_{EP (P CC)} [2 · (xy)^{|EP (P CC)|/2}]

∏_{OP (P CC)} [(x + y) · (xy)^{(|OP (P CC)|−1)/2}]).  (2.2)

The formula becomes easier if we replace x and y by x^{2} and y^{2}, respectively. Moreover, we can express I_{G}(x^{2})I_{G}(y^{2}) with the help of the elementary symmetric polynomials

e_{1} := x + y,  e_{2} := xy  (2.3)

by putting P_{G}(e_{1}, e_{2}) := I_{G}(x^{2})I_{G}(y^{2}). The identity x^{2} + y^{2} = e_{1}^{2} − 2e_{2} implies

P_{G}(e_{1}, e_{2}) = ∑_{P CC}( ∏_{IV (P CC)} [e_{2}^{2}] ∏_{EC(P CC)} [2e_{2}^{|EC(P CC)|}] ∏_{EP (P CC)} [2e_{2}^{|EP (P CC)|}]

∏_{OP (P CC)} [e_{1}^{2}e_{2}^{|OP (P CC)|−1} − 2e_{2}^{|OP (P CC)|}])  (2.4)

= ∑_{OP C} [ ∏_{OP (OP C)} e_{1}^{2}e_{2}^{|OP (OP C)|−1}] · P_{G\[OP C∪Γ(OP C)]}(0, e_{2}),  (2.5)

where the last sum is over all odd-path-configurations, i.e. over all induced subgraphs of G that are formed by a disjoint union of some odd paths. Indeed, if we develop the last product of (2.4) by distributivity, OP C corresponds to the odd paths for which we have chosen the term e_{1}^{2}e_{2}^{|OP (P CC)|−1}. This must be multiplied by P_{H}(0, e_{2}) (we have replaced e_{1} by 0 in order to forbid any further appearances of the term e_{1}^{2}e_{2}^{|OP (P CC)|−1}), where H = G\[OP C ∪ Γ(OP C)] is the subgraph of G induced by all vertices of G\OP C which are not adjacent to any vertex of OP C. We remove Γ(OP C) (vertices adjacent to at least one vertex of OP C) because P CC is an induced subgraph. Note that P_{H}(0, e_{2}) = 1 if H is the empty graph.

Lemma 1. For any graph G, we have

P_{G}(0, e_{2}) = I_{G}((i\sqrt{xy})^{2})I_{G}((−i\sqrt{xy})^{2}) = I_{G}(−e_{2})^{2}.  (2.6)

Proof. If we want to replace e_{1} by 0 (leaving e_{2} unchanged), then we have to replace x and y by i\sqrt{xy} and −i\sqrt{xy}, respectively.

If we apply our lemma to our induced subgraphs H we get the following theorem.

Theorem 2. We have

I_{G}(x^{2})I_{G}(y^{2}) = ∑_{OP C} [ ∏_{OP (OP C)} e_{1}^{2}e_{2}^{|OP (OP C)|−1}] · I_{G\[OP C∪Γ(OP C)]}(−e_{2})^{2},  (2.7)

where e_{1} = x + y and e_{2} = xy.

Corollary 1. Let G be a clawfree graph with i_{α}(G) maximal independent sets. Then

|I_{G}(x^{2})|^{2} ≥ i_{α}(G) · [4(ℜe x)^{2}]^{α} ,  |I_{G}(−x^{2})|^{2} ≥ i_{α}(G) · [4(ℑm x)^{2}]^{α}  (2.8)

for every x ∈ ℂ. In particular, all the roots of I_{G}(x) are real and negative.

Proof. If we replace y by \overline{x}, then e_{1}^{2} = 4(ℜe x)^{2} ≥ 0 and e_{2} = |x|^{2} ≥ 0. Therefore, every term of the sum

|I_{G}(x^{2})|^{2} = I_{G}(x^{2})I_{G}(\overline{x}^{2}) =
∑_{OP C} [ ∏_{OP (OP C)} e_{1}^{2}e_{2}^{|OP (OP C)|−1}] · I_{G\[OP C∪Γ(OP C)]}(−e_{2})^{2}  (2.9)

is nonnegative. In particular, each of the i_{α}(G) maximal independent sets of G is an odd-path-configuration with α paths of length 1 and contributes to the sum [e_{1}^{2}e_{2}^{0}]^{α} = [4(ℜe x)^{2}]^{α}, because I_{H}(−e_{2})^{2} = P_{H}(0, e_{2}) = 1 if H is the empty graph. This proves the first inequality. The second one follows immediately if we replace x by i · x.

Finally, if z is a complex number that is neither a real negative number nor zero, then there exists x ∈ ℂ such that z = x^{2} and ℜe x > 0. Therefore,

|I_{G}(z)|^{2} = |I_{G}(x^{2})|^{2} ≥ i_{α}(G) · [4(ℜe x)^{2}]^{α} > 0.  (2.10)

In other words, I_{G}(z) can be zero only if z is a real negative number, because I_{G}(0) = 1.

Let us finally consider an example, namely the graph with vertex set {A, B, C} and two edges AB and AC. Moreover, we want to attach the weights a, b and c to its vertices A, B and C, respectively. As explained in the introduction, if a, b and c are positive integers, this corresponds to replacing the vertices A, B and C by cliques (complete graphs) of sizes a, b and c, respectively, where all vertices of the clique of size a are joined with the vertices of the cliques of sizes b and c, but there are no edges between the cliques of sizes b and c. In general, however, a, b and c can be arbitrary positive (or even nonnegative) real numbers (if a number is 0, it corresponds to the fact that the vertex is deleted). The weighted independence polynomial of this graph is

I_{G,w}(x) = 1 + x · a + x · b + x · c + x^{2} · bc.  (2.11)

An easy multiplication gives the following formula:

I_{G,w}(x)I_{G,w}(y) = 1 + (x + y) · a + (x + y) · b + (x + y) · c + 2xy · ab + 2xy · ac
+ (x + y)^{2} · bc + (x + y)xy · abc + xy · a^{2} + xy · b^{2} + xy · c^{2}
+ xy(x + y) · b^{2}c + xy(x + y) · c^{2}b + (xy)^{2} · b^{2}c^{2}.  (2.12)

Here a corresponds to an odd path of length 1, ab corresponds to an even path of length 2, bc corresponds to two odd paths of length 1, abc corresponds to an odd path of length 3, a^{2} corresponds to an isolated vertex, b^{2}c corresponds to an isolated vertex and an odd path of length 1 and b^{2}c^{2} corresponds to two isolated vertices. Altogether, this reflects exactly our first theorem. To go on, we put e_{1} = x + y and e_{2} = xy and obtain

I_{G,w}(x^{2})I_{G,w}(y^{2}) = 1 − 2e_{2} · a − 2e_{2} · b − 2e_{2} · c + 2e_{2}^{2} · ab + 2e_{2}^{2} · ac
+ 4e_{2}^{2} · bc − 2e_{2}^{3} · abc + e_{2}^{2} · a^{2} + e_{2}^{2} · b^{2} + e_{2}^{2} · c^{2}
− 2e_{2}^{3} · b^{2}c − 2e_{2}^{3} · c^{2}b + e_{2}^{4} · b^{2}c^{2}
+ e_{1}^{2} · b · [1 − 2e_{2} · c + e_{2}^{2} · c^{2}] + e_{1}^{2} · c · [1 − 2e_{2} · b + e_{2}^{2} · b^{2}]
+ e_{1}^{2} · a + e_{1}^{2}e_{2}^{2} · abc + e_{1}^{4} · bc  (2.13)
= [1 − e_{2} · a − e_{2} · b − e_{2} · c + e_{2}^{2} · bc]^{2}
+ e_{1}^{2} · b · [1 − e_{2} · c]^{2} + e_{1}^{2} · c · [1 − e_{2} · b]^{2}
+ e_{1}^{2} · a + e_{1}^{2}e_{2}^{2} · abc + e_{1}^{4} · bc.  (2.14)

Here bc corresponds to two odd paths of length 1, abc corresponds to an odd path of length 3, a corresponds to an odd path of length 1 and b corresponds to an odd path of length 1 which must be multiplied by the square of the weighted independence polynomial of C evaluated at −e_{2}. Last but not least, 1 − e_{2} · a − e_{2} · b − e_{2} · c + e_{2}^{2} · bc is the weighted independence polynomial of the whole graph evaluated at −e_{2}. Altogether, this reflects our second theorem.

As we see, it causes no problem to introduce nonnegative real multiplicative weights for every vertex (see [7]): they just make the notations slightly more complicated, but the proofs and theorems remain the same.

3 Mehler Formulae for Multivariate Matching Polynomials

To state and derive our extension of the Mehler formula for matching polynomials [19] to allow not only nonnegative real edge weights but also complex vertex weights, we need an adequate algebraic tool, the algebra of generating functions for set functions. We introduce them in the following subsection without supposing any knowledge of algebra at all. When we use some classical expressions such as A-algebra or projective limit (see [18] for definitions), it is only for the convenience of readers knowing them. Everything can also be understood easily without knowing them, because we define all our objects in our concrete setting explicitly.

Finally, we study the applications to multivariate matching polynomials of this algebraic formalism, which was already very useful in [19, 20, 21, 22].

3.1 Algebraic Preliminaries

Let V be a finite set, and let A be a commutative ring with identity element. Let F(2^{V} , A) be the A-algebra of functions f : 2^{V} → A, equipped with the multiplication

(fg)(W) = ∑_{W_{1}⊎W_{2}=W} f(W_{1})g(W_{2})  (3.1)

(where ⊎ denotes disjoint union) and the obvious pointwise addition and scalar multiplication.

Next let A[V] be the A-algebra of multiaffine (= square-free) polynomials

F (ν) = ∑_{W ⊆V} a_{W} ν^{W}  (3.2)

in indeterminates ν = (ν_{v})_{v∈V}, where we use the shorthand notation

ν^{W} = ∏_{v∈W} ν_{v},  ν^{∅} := 1.  (3.3)

This algebra is equipped with the usual multiplication of polynomials followed by extraction of the multiaffine part (i.e. discarding all monomials that are not of the form ν^{W} for some W ⊆ V), that is

( ∑_{W ⊆V} a_{W} ν^{W} ) · ( ∑_{W ⊆V} b_{W} ν^{W} ) = ∑_{W ⊆V} ∑_{W_{1}⊎W_{2}=W} a_{W_{1}}b_{W_{2}}ν^{W} ,  (3.4)

together with the usual addition and scalar multiplication. Note that A[V] is isomorphic in an obvious way to the quotient algebra A[{ν_{v}}]/⟨{ν_{v}^{2}}⟩. Remark. In a more combinatorial way (see [19, 20, 21, 22]), we could have defined the multiplication of monomials for all W_{1}, W_{2} ⊆ V by

ν^{W_{1}} · ν^{W_{2}} := ν^{W_{1}+W_{2}}, where  (3.5)
W_{1} + W_{2} := \{ \begin{matrix}W_{1} ∪ W_{2}, & if W_{1} ∩ W_{2} = ∅, \\ †, & if W_{1} ∩ W_{2} ≠ ∅, where \end{matrix}  (3.6)
† + W := †, † + † := †,  and  ν^{†} := 0.  (3.7)

Here † corresponds to multisets that are systematically discarded.

Finally, the map f ↦ F_{f} that associates to each f ∈ F(2^{V} , A) its generating polynomial F_{f} ∈ A[V], i.e.

F_{f}(ν) = ∑_{W ⊆V} f(W)ν^{W} ,  (3.8)

is manifestly an algebra isomorphism of F(2^{V} , A) onto A[V]. Many applications of A[V] in different parts of enumerative graph theory can be found in [19], [20], [21] and [22]. See [5], Section 4.7, for further results on the ”multiaffine part” operator, and see [5], Remark 4 after Theorem 10.1, for a simple proof of the multivariate Heilmann-Lieb theorem for matching polynomials that is based on it.

For |V | = ∞ let (2^{V})_{fin} be the partially ordered set of finite subsets of V. We have the canonical projections p_{W_{1},W_{2}} : A[W_{1}] → A[W_{2}] (W_{1}, W_{2} ∈ (2^{V})_{fin}, W_{1} ⊇ W_{2}) and define

A[V] := lim_{⟵} A[W], W ∈ (2^{V})_{fin}  (3.9)

with the help of the projective limit. This means nothing else than working with generating functions of the form

F (ν) = ∑_{W ∈(2^{V} )_{fin}} a_{W} ν^{W} .  (3.10)

Now for any V (finite or infinite), we consider the particular element

V := ∑_{v∈V} ν^{{v}} = ∑_{v∈V} ν_{v}  (3.11)

in A[V] : it is the generating function for the indicator function of the subsets of V of cardinality 1. Then, in the product V^{k} in the algebra A[V], each set of cardinality k occurs k! times, so that V^{k}/k! is the generating function for the indicator function of the subsets of V of cardinality k. If now g : ℕ → A is an A-valued function on the natural numbers, the identity

∑_{k=0}^{∞} g(k) · V^{k}/k! = ∑_{W ∈(2^{V} )_{fin}} g(|W |)ν^{W}  (3.12)

provides an embedding of the algebra A![[V]] of generating functions of exponential type (usually the variable is called x instead of V) into our algebra A[V] if and only if |V | = ∞. Indeed, if k > |V |, then V^{k}/k! = 0. If |V | = ∞, the image of this embedding is the subalgebra of A[V] consisting of generating functions F_{f} of set functions f where the value depends only on the cardinality of the set, i.e. f(W) = g(|W |) for every W ∈ (2^{V})_{fin}. This embedding is at the origin of (almost?) all the applications of A![[V]] in combinatorics, but it requires the existence of an infinite combinatorial model depending just on cardinalities. Consequently, A[V] provides more flexibility and closeness to combinatorics; it is also ideally suited for computer calculations. Remark. The ring ℤ![[V]] is not Noetherian, but it contains the important functions exp(V) and log(1 + V).

Example 1. If char A = 2, then we have

(1 + V)^{−1} = ∑_{k=0}^{∞}(−1)^{k}k! · V^{k}/k!  (3.13)
≡ 1 + V and  (3.14)
log(1 + V) = ∑_{k=1}^{∞}(−1)^{k−1}(k − 1)! · V^{k}/k!  (3.15)
≡ V + V^{2}/2  (3.16)

in the ring A![[V]]. These identities are at the origin of lots of results of parity in combinatorics, see [22].

For all t ∈ A we put (tν)^{W} := t^{|W |}ν^{W}, W ∈ (2^{V})_{fin}, and therefore

F_{f}(tν) = ∑_{W ∈(2^{V} )_{fin}} f(W) t^{|W |}ν^{W} ,  (3.17)

where f : (2^{V})_{fin} → A is an arbitrary set function. It is evident that this definition is compatible with the addition and the multiplication. Most important are the special cases t = −1 and t = 0: F_{f}(0) = F_{f}(0 · ν) = f(∅).

If F_{f}(0) = 0, then F_{f}(ν)^{k}/k! is defined for any ring A, because a partition into k nonempty subsets can be ordered in k! different ways. Thus we have an operation of A![[V]] on A[V] via the substitution G(F_{f}(ν)) defined for any G ∈ A![[V]].

Finally, define for any f, g : (2^{V})_{fin} → A the function f ∗ g : (2^{V})_{fin} → A by

(f ∗ g)(W) := f(W) · g(W)  (3.18)

for each W ∈ (2^{V})_{fin} and define the Hadamard product to be

F_{f}(ν) ∗ F_{g}(ν) := F_{f∗g}(ν).  (3.19)

3.2 Application to Matching Polynomials

From now on every edge {u, v} ∈ E of our finite graph G = (V, E) will get a weight w_{{u,v}} ∈ A (we can assume that the two-element subsets of V which are not edges get the weight zero). Moreover, every vertex v ∈ V will get a weight x_{v} ∈ A. As always, A is a commutative ring with identity element. This weighted graph will be denoted by G_{x,w} = (V_{x}, E_{w}). Now E_{w} will be identified with the generating function of the set function which attributes the value 0 to all subsets of V with the only exception of the edges of G_{x,w}, which get their own weights. Moreover, V_{x} will be identified with the generating function of the set function which attributes the value 0 to all subsets of V with the only exception of the vertices of G_{x,w} (subsets of cardinality 1), which get their own weights. Of course, we have the following identities:

V_{x} = ∑_{v∈V} x_{v} · ν^{{v}},  E_{w} = ∑_{{u,v}∈E} w_{{u,v}} · ν^{{u,v}}.  (3.20)

We define the (multivariate weighted) matching polynomial of G_{x,w} by

M_{G}(x, w) := ∑_{matchings M} ( ∏_{{u,v}∈M}(−w_{{u,v}})) ( ∏ ; v∈V \(⋃ M) x_{v})  (3.21)

We see that every matching is counted with respect to its weight : the product of minus the weights of its edges multiplied by the product of the weights of the vertices which are not covered by the matching. The classical matching polynomial (1.1) is obtained if all variables x_{v} equal x whereas all variables w_{{u,v}} equal 0 or 1. For every induced subgraph of G_{x,w}, and in particular for G_{x,w} itself, the (weighted) matching polynomial can be calculated with the help of its generating function.

Lemma 2. We have

1 + ∑_{∅⊂W ⊆V} M_{G[W]}(x, w) · ν^{W} = exp[V_{x} − E_{w}].  (3.22)

A Hamiltonian cycle of G_{x,w} is a cyclic order of V and its weight is the product of the weights of its n = |V | edges corresponding to two consecutive vertices in the cyclic order. In particular, if the edge corresponding to two consecutive vertices in the cyclic order does not belong to the graph (equivalently, has weight zero), then the weight of that ”Hamiltonian cycle” is equal to zero. Let cyc(G_{x,w}) be the sum of the weights of all Hamiltonian cycles of G_{x,w}, with the convention that cyc(G_{w}) = 1 if n = 1. We assume that the weight of each edge in the complete graph K_{n} is equal to 1, so that cyc(K_{n}) = (n − 1)!.

A Hamiltonian path of G_{x,w} is a linear order of V and its weight is the product of the weights of its n − 1 edges corresponding to two consecutive vertices in the linear order. Let lin_{u,v}(G_{x,w}) be the sum of the weights of all Hamiltonian paths of G_{x,w} from u to v (u is the first vertex of the linear order whereas v is its last one). We use the convention that lin_{u,u}(G_{x,w}) = 1 if n = 1. Moreover, we define

lin(G_{x,w}) := ∑_{u,v∈V} lin_{u,v}(G_{x,w}),  (3.23)

i.e. lin(G_{x,w}) is the sum of the weights of all Hamiltonian paths of G_{x,w}. Clearly, lin(K_{n}) = n!.

Let us define for every u, v ∈ V

cyc_{w}(ν) := ∑_{∅⊂W ⊆V} cyc(G_{x,w}[W]) · ν^{W} , lin_{u,v,w}(ν) := ∑_{{u,v}⊆W ⊆V} lin_{u,v}(G_{x,w}[W]) · ν^{W} , (3.24)

lin_{w}(ν) := ∑_{∅⊂W ⊆V} lin(G_{x,w}[W]) · ν^{W} = ∑_{u,v∈V} lin_{u,v,w}(ν).  (3.25)

Considering the infinite graph K_{∞} yields

∑_{n=1}^{∞} cyc(K_{n}) · V^{n}/n! = − log(1 − V), ∑_{n=1}^{∞} lin(K_{n}) · V^{n}/n! = \frac{V}{1 − V} .  (3.26)

Usually (in undirected graphs) one does not distinguish between the two different directions of Hamiltonian cycles or paths. In this sense cyc_{w}(ν) and lin_{w}(ν) count them ”twice”.

Now we can prove our generalization of the Mehler formula.

Theorem 3. Let x_{v} and y_{v} be two families of vertex weights. Using the Hadamard product ∗ we have:

exp [V_{x} − E_{w}] ∗ exp [V_{y} − E_{w}] = exp [\frac{1}{2} · cyc_{w}(ν) + \frac{1}{2} · cyc_{w}(−ν)] ·

exp ∑_{u,v∈V} [−\frac{x_{u} − y_{u}}{2} · \frac{x_{v} − y_{v}}{2} · lin_{u,v,w}(ν) − \frac{x_{u} + y_{u}}{2} · \frac{x_{v} + y_{v}}{2} · lin_{u,v,w}(−ν)] .  (3.27)

Proof. A pair of matchings of G to be considered on the left-hand side of (3.27) (one with weights x, w and the other with weights y, w) provides a partition of V into even cycles (to be counted ”twice”, because the matchings can be interchanged), even (according to the number of vertices) paths between u and v (to be counted with the factor −x_{u}x_{v} or −y_{u}y_{v}, because the number of edges of the paths is odd) and odd paths (to be counted with the factor x_{u}y_{v} or y_{u}x_{v}). These cycles and paths become Hamiltonian cycles and paths for the corresponding induced subgraphs. Thus the left-hand side of (3.27) is equal to

exp [\frac{cyc_{w}(ν) + cyc_{w}(−ν)}{4} · 2] ·

exp [ ∑_{u,v∈V} \frac{lin_{u,v,w}(ν) + lin_{u,v,w}(−ν)}{4} · (−x_{u}x_{v} − y_{u}y_{v})] ·

exp [ ∑_{u,v∈V} \frac{lin_{u,v,w}(ν) − lin_{u,v,w}(−ν)}{4} · (x_{u}y_{v} + y_{u}x_{v})] .  (3.28)

Indeed, if we divide lin_{u,v,w}(ν) − lin_{u,v,w}(−ν) by 2, then we count odd paths from u to v once. However, if u and v are different, then lin_{u,v,w}(ν) = lin_{v,u,w}(ν) and we have to divide by 4 before multiplying with x_{u}y_{v} +y_{u}x_{v}. If u = v, then we have to divide by 2 only before multiplying with x_{u}y_{u} (there are no matchings to be interchanged), but this is of course equivalent to dividing by 4 and multiplying with x_{u}y_{u} + y_{u}x_{u}. So in every case the preceding expression is correct for the left-hand side of (3.27), and it is evident that it is also equal to its right-hand side.

Specializing (3.27) to K_{∞} and x_{v} = x, y_{v} = y for all v ∈ V and using (3.26) yields the classical Mehler formula, because Hermite polynomials can be defined as matching polynomials of complete graphs.

Corollary 2. (Mehler). We have

1 + ∑_{n=1}^{∞} M_{K_{n}}(x)M_{K_{n}}(y) · V^{n}/n! =

\frac{1}{\sqrt{1 − V^{2}}} · exp [(\frac{x + y}{2} )^{2} · \frac{V}{1 + V} − (\frac{x − y}{2} )^{2} · \frac{V}{1 − V} ] .  (3.29)

Now specialize to A = ℂ. Replacing the variables y_{v} for every v ∈ V in the previous theorem by the complex conjugate numbers \overline{x_{v}} yields the following theorem.

Theorem 4. Let x_{v} be a family of complex vertex weights. We have

exp [V_{x} − E_{w}] ∗ exp [V\overline{x} − E_{w}] = exp [\frac{1}{2} · cyc_{w}(ν) + \frac{1}{2} · cyc_{w}(−ν)] ·

exp ∑_{u,v∈V} [(ℑm x_{u}) · (ℑm x_{v}) · lin_{u,v,w}(ν) − (ℜe x_{u}) · (ℜe x_{v}) · lin_{u,v,w}(−ν)] .  (3.30)

If we replace in (3.30) x_{v} and \overline{x_{v}} both by ℜe x_{v} for every v ∈ V, then ℑm x_{v} becomes 0 whereas ℜe x_{v} remains unchanged. Therefore we get the identity :

exp [V_{ℜe x} − E_{w}] ∗ exp [V_{ℜe x} − E_{w}] = exp [\frac{1}{2} · cyc_{w}(ν) + \frac{1}{2} · cyc_{w}(−ν)] ·

exp ∑_{u,v∈V} [−(ℜe x_{u}) · (ℜe x_{v}) · lin_{u,v,w}(−ν)] .  (3.31)

Now we can use our last identity (3.31) in order to simplify the right-hand side of (3.30). This proves the following theorem.

Theorem 5. Let x_{v} be a family of complex vertex weights. We have

exp [V_{x} − E_{w}] ∗ exp [V\overline{x} − E_{w}] = (exp [V_{ℜe x} − E_{w}] ∗ exp [V_{ℜe x} − E_{w}]) ·
exp [ ∑_{u,v∈V} (ℑm x_{u}) · (ℑm x_{v}) · lin_{u,v,w}(ν)] .  (3.32)

Corollary 3. Let M_{G}(x, w) be the weighted matching polynomial with complex vertex weights x_{v} and nonnegative real edge weights w_{{u,v}}. If ℑm x_{v} > 0 for every v ∈ V or if ℑm x_{v} < 0 for every v ∈ V, then we get the inequality

|M_{G}(x, w)|^{2} ≥ ( ∏_{v∈V} (ℑm x_{v})^{2}) (1 + ∑_{\{u,v\}∈E} \frac{2 · w_{\{u,v\}}}{(ℑm x_{u})(ℑm x_{v})}) .  (3.33)

Proof. Extracting the coefficient of ν^{V} in the generating-function identity (3.32) we obtain

|M_{G}(x, w)|^{2} = ∑_{k=0}^{∞} \frac{1}{k!} ∑_{W_{0}⊎W_{1}⊎···⊎W_{k}=V} M_{G[W_{0}]}(ℜe x, w)^{2} ·

∏_{i=1}^{k} ∑_{u,v∈W_{i}}(ℑm x_{u})(ℑm x_{v})lin_{u,v}(G_{x,w}[W_{i}]),  (3.34)

where 1/k! comes from the exponential function and reflects the fact that there are k! possibilities to permute the necessarily nonempty sets W_{1},…,W_{k} (W_{0} can be empty). (Indeed, lin on the empty set is 0, whereas every matching polynomial on the empty set is 1.)

Under the given hypotheses on x and w, all the contributions on the right-hand side of (3.34) are nonnegative, so a lower bound can be obtained by taking some of them. Here we keep only the terms where W_{0} = ∅ and consider the two cases in which V is partitioned either into n = |V | paths of length 1, or n − 2 paths of length 1 and one path of length 2. In the first case, we get the contribution

∏_{v∈V} (ℑm x_{v})^{2}  (3.35)

whereas in the second case, we get the contribution

∑_{{u,v}∈E}(ℑm x_{u})(ℑm x_{v})(2w_{{u,v}}) ∏_{t∈V \{u,v}}(ℑm x_{t})^{2}.  (3.36)

The sum of those expressions is equal to the right-hand side of (3.33). This finishes the proof of this corollary.

Corollary 4. ([15]) Let M_{G}(x, w) be the weighted matching polynomial with complex vertex weights x_{v} and nonnegative real edge weights w_{{u,v}}. If ℑm x_{v} > 0 for every v ∈ V or if ℑm x_{v} < 0 for every v ∈ V, then |M_{G}(x, w)|^{2} > 0, i.e. the weighted matching polynomial cannot be zero in that case.

Remark. The complex vertex variables of the weighted matching polynomial could be hidden in the edge variables but could also be recovered from them by multiplying and dividing edge weights alternatingly along odd cycles. Therefore it does not seem possible to obtain a beautiful generalization of the complex vertex variables for clawfree graphs.

Acknowledgements: I would like to thank most cordially Theresia Eisenkölbl and the referees for many useful and stimulating remarks.

References

[1] J.I. Brown and R. Nowakowski, ”Bounding the roots of independence polynomials”, Ars Combin. 58 (2001), 113-120.

[2] J.I. Brown and R. Nowakowski, ”Average independence polynomials”, J. Combin. Theory Ser. B 93 (2005), 313-318.

[3] J.I. Brown, K. Dilcher and R.J. Nowakowski, ”Roots of independence polynomials of wellcovered graphs”, J. Algebraic Combin. 11 (2000), 197-210.

[4] J.I. Brown, C.A. Hickman and R.J. Nowakowski, ”On the location of roots of independence polynomials”, J. Algebraic Combin. 19 (2004), 273–282.

[5] Y.B. Choe, J.G. Oxley, A.D. Sokal and D.G. Wagner, ”Homogeneous multivariate polynomials with the half-plane property”, Special issue on the Tutte polynomial, Adv. in Appl. Math. 32 (2004), 88-187.

[6] M. Chudnovsky and P. Seymour, ”The roots of the independence polynomial of a clawfree graph”, J. Combin. Theory Ser. B 97 (2007), 350-357.

[7] A. Engström, ”Inequalities on well-distributed point sets on circles”, JIPAM J. Inequal. Pure Appl. Math. 8 (2007), no. 2, Article 34, 5 pp. (electronic).

[8] D.C. Fisher and A.E. Solow, ”Dependence polynomials”, Discrete Math. 82 (1990), 251-258.

[9] D. Foata, ”A combinatorial proof of the Mehler formula”, J. Combinatorial Theory Ser. A 24 (1978), 367-376.

[10] C.D. Godsil, ”Algebraic Combinatorics”, Chapman & Hall, 1993.

[11] C.D. Godsil, ”Hermite polynomials and a duality relation for matchings polynomials”, Combinatorica 1 (1981), 257-262.

[12] I. Gutman, ”An identity for the independence polynomial of trees”, Publ. Inst. Math. (Belgrade) 50 (1991), 19-23.

[13] I. Gutman, ”Some analytic properties of the independence and matching polynomials”, MATCH Commun. Math. Comput. Chem. 28 (1992), 139-150.

[14] Y.O. Hamidoune, ”On the numbers of independent k-sets in a clawfree graph”, J. Combin. Theory Ser. B 50 (1990), 241-244.

[15] O.J. Heilmann and E.H. Lieb, ”Theory of monomer-dimer systems”, Comm. Math. Phys. 25 (1972), 190-232.

[16] C. Hoede and X. Li, ”Clique polynomials and independent set polynomials of graphs”, Discrete Math. 25 (1994), 219-228.

[17] B. Jackson and A.D. Sokal, ”Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids”, J. Combin. Theory Ser. B 99 (2009), 869-903.

[18] S. Lang, ”Algebra”, Graduate Texts in Mathematics 211, Springer-Verlag, New York, 2002.

[19] B. Lass, ”Matching polynomials and duality”, Combinatorica 24 (2004), 427-440.

[20] B. Lass, ”Orientations acycliques et le polynôme chromatique”, European J. Combin. 22 (2001), 1101-1123.

[21] B. Lass, ”The N-dimensional matching polynomial”, Geom. Funct. Anal. 15 (2005), 453-475.

[22] B. Lass, ”Variations sur le thème E + \overline{E} = XY ”, Adv. in Appl. Math. 29 (2002), 215–242.

[23] S. Lavallée and C. Reutenauer, ”Characteristic polynomials of nonnegative integral square matrices and clique polynomials”, Sém. Lothar. Combin. 61A (2009), Art. B61Ac, 11 pp.

[24] V.E. Levit and E. Mandrescu, ”The independence polynomial of a graph - a survey”, Proceedings of the 1st International Conference on Algebraic Informatics, Aristotle Univ. Thessaloniki, Thessaloniki, 2005, 233-254.

[25] J. Qian, A. Dress and Y. Wang, ”On the dependence polynomial of a graph”, European J. Combin. 28 (2007), 337-346.

[26] A.D. Scott and A.D. Sokal, ”The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma”, J. Stat. Phys. 118 (2005), 1151-1261.

[27] A.D. Scott and A.D. Sokal, ”On dependency graphs and the lattice gas”, Combin. Probab. Comput. 15 (2006), 253-279.

[28] R.P. Stanley, ”Graph colorings and related symmetric functions: Ideas and applications”, Discrete Math. 193 (1998), 267-286.