COMBINATORICA 24 (3) (2004) 427-440

MATCHING POLYNOMIALS AND DUALITY

BODO LASS

(Received February 20, 2001; Accepted November 29, 2001)

Let G be a simple graph on n vertices. An r-matching in G is a set of r independent edges. The number of r-matchings in G will be denoted by p(G,r). We set p(G,0)=1 and define the matching polynomial of G by μ(G,x):=∑_{r=0}^{⌊n/2⌋}(−1)^{r}·p(G,r)·x^{n−2r} and the signless matching

polynomial of G by \overline{μ}(G,x):=∑_{r=0}^{⌊n/2⌋} p(G,r)·x^{n−2r}.

It is classical that the matching polynomials of a graph G determine the matching polynomials of its complement \overline{G}. We make this statement more explicit by proving new duality theorems by the generating function method for set functions. In particular, we show that the matching functions e^{−x2/2}μ(G,x) and e^{−x2/2}μ(\overline{G},x) are, up to a sign, real Fourier transforms of each other.

Moreover, we generalize Foata’s combinatorial proof of the Mehler formula for Hermite polynomials to matching polynomials. This provides a new short proof of the classical fact that all zeros of μ(G,x) are real. The same statement is also proved for a common generalization of the matching polynomial and the rook polynomial.

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. The complement of G is the graph \overline{G} = (V, \overline{E}) with \overline{E} = \binom{V}{2}\E.

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⌋. If r = ⌊n/2⌋, then an r-matching of G is called perfect if n is even and quasi-perfect if n is odd. Let p(G, r) be the number of rmatchings in G, with the convention that p(G, 0) := 1. The matching polynomial of G is (see [3], chapter 1)

μ(G, x) := ∑_{r=0}^{⌊n/2⌋}(−1)^{r} · p(G, r) · x^{n−2r},

while the signless matching polynomial reads

\overline{μ}(G, x) := ∑_{r=0}^{⌊n/2⌋} p(G, r) · x^{n−2r}.

Mathematics Subject Classification (1991): 05 C 70; 05 A 15, 05 A 20, 12 D 10

BODO LASS

In particular, \overline{μ}(G, 0) counts the number of perfect matchings of G and \overline{μ}(G, 1) counts the number of arbitrary matchings of G.

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

We generalize the combinatorial proof of the Mehler formula for Hermite polynomials imagined by Foata (see [2]). To state and derive our extension of the Mehler formula we need an adequate algebraic tool, the algebra of generating functions for set functions. This algebra is developed in the next section. In section 4 we show that our generalization of the Mehler formula immediately implies that |μ(G, x)|^{2} ≥ [(ℑm x)^{2}]^{n} + 2|E| · [(ℑm x)^{2}]^{n−1} for every x ∈ ℂ, i.e. that all the zeros of μ(G, x) are real. Moreover, this fact holds for a common generalization of the matching polynomial and the rook polynomial.

Section 3 is entirely devoted to questions of duality. It is evident that μ(G, x) and \overline{μ}(G, x) contain the same information, a convenient relation between those polynomials being

μ(G, x) = (−i)^{n} · \overline{μ}(G, xi), |V | = n, i = \sqrt{−1}.

The observation that μ(G, x) and \overline{μ}(G, x) determine μ(\overline{G}, x) and \overline{μ}(\overline{G}, x), however, seems to have first been made by Lovász, [8] 5.18. His proof, based on the inclusionexclusion principle, does not seem to be too difficult although it is marked with an asterisk in his book. We prefer to give an explicit calculation involving several new duality theorems. In particular, we show that the matching functions e^{−x^{2}/2}μ(G,x) and e^{−x^{2}/2}μ(\overline{G},x) are, up to a sign, real Fourier transforms of each other.

Matching polynomials generalize many classical orthogonal polynomials, namely Hermite polynomials (the matching polynomials of complete graphs), Tchebycheff polynomials of both kinds (paths and cycles) and Laguerre polynomials (complete bipartite graphs), see [9] chapter 6. The complete graph K_{n} on n vertices can be defined as the complement of the edgeless graph \overline{K_{n}} on those vertices. Clearly, μ(\overline{K_{n}}, x) = \overline{μ}(\overline{K_{n}}, x) = x^{n}. The Hermite polynomials will be (by definition) the matching polynomials of the complete graphs, i.e. He_{n}(x) := μ(K_{n}, x). The reader will recognize the classical definition of the Hermite polynomials as a special case of the second equality in our duality theorem (d/dx), replacing \overline{G} by K_{n}.

MATCHING POLYNOMIALS AND DUALITY

The first step towards the duality theory developed here was the combinatorial interpretation of integrals over products of Hermite polynomials (see [9], VI-34, remark 21, or the recent book [1], chapter 6.9):

\overline{μ}(\overline{K_{n_{1}} ⊎ … ⊎ K_{n_{k}}}, 0) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−x^{2}/2} · μ(K_{n_{1}}, x) ⋯ μ(K_{n_{k}}, x) · dx,

where K_{n_{1}} ⊎ … ⊎ K_{n_{k}} denotes the vertex disjoint union of the complete graphs K_{n_{1}}, …, K_{n_{k}}. Even this formula has been neglected in physics (for instance, in [5] there is no consideration of duality at all) as can be seen from the fact that Itzykson and Zuber [6] need a whole page to solve their integral (3.5), the result being evident from the previous formula.

The second step was the realization, due to Godsil [4], that, more generally,

\overline{μ}(\overline{G}, 0) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−x^{2}/2} · μ(G, x) · dx,

the equation μ(K_{n_{1}}, x) ⋯ μ(K_{n_{k}}, x) = μ(K_{n_{1}} ⊎ … ⊎ K_{n_{k}}, x) being evident.

Finally, the last step of duality theory is the derivation of direct formulas for the matching polynomials of the complementary graph. In this context Godsil mainly proposed

μ(\overline{G}, x) = ∑_{r=0}^{⌊n/2⌋} p(G, r) · μ(K_{n−2r}, x),

but also the more explicit formula

\overline{μ}(\overline{G}, y) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−x^{2}/2} · μ(G, x + y) · dx

is a specialization of theorem 2.4 in [4], that Godsil did not reproduce in his book [3].

We propose two new duality theorems by means of differential operators, a slight modification of Godsil’s last theorem together with a scalar product formula and, finally, the Fourier transform interpretation.

Our proofs of section 3 make use of generating functions for set functions. We must say that the set function machinery developed in the next section has been the adequate tool for deriving those duality theorems.

2. Algebraic tools

Let V be a finite set and

\begin{matrix}f : 2^{V} & → A \\ V′ ⊆ V & ↦ f(V′) ∈ A \end{matrix}

be a set function, where A is a commutative ring with 1. Consider the generating function

F_{f}(ν) := ∑_{V′⊆V} f(V′) · ν^{V′}, ν^{∅} := 1,

subject to the following multiplication rules (V′, V′′ ⊆ V):

ν^{V′} · ν^{V′′} := ν^{V′+V′′}, where

V′ + V′′ := \{ \begin{matrix}V′ ∪ V′′, & if V′ ∩ V′′ = ∅, \\ †, & if V′ ∩ V′′ ≠ ∅, where \end{matrix}

† + V′ := †, † + † := †,  and  ν† := 0.

The algebra A[V] of those generating functions is not unknown. In fact, we have the isomorphism

A[V] ≃ A[v_{1}, …, v_{n}]/⟨v_{1}^{2}, …, v_{n}^{2}⟩,

if V contains n elements.

Example. For V′ ⊆ V put

(fg)(V′) := ∑_{V′=V′′⊎V′′′} f(V′′) · g(V′′′)

(f, g, fg : 2^{V} → A). Then

F_{fg}(ν) = F_{f}(ν) · F_{g}(ν).

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

A[V] := lim_{⟵} A[V′], V′ ∈ F (V)

in order to work with generating functions of the form

F_{f}(ν) = ∑_{V′∈F (V)} f(V′) · ν^{V′}.

Let

V := ∑_{v∈V} ν^{{v}}

be the generating function for the indicator function of the subsets of V of cardinality 1 (the double use of V for the set itself on the one hand and for an element of A[V] on the other hand will never cause confusion). In the product V^{n} each subset of cardinality n occurs n! times, so that V^{n}/n! represents the indicator function of the subsets of the set V of cardinality n. The identity

∑_{n=0}^{∞} f(n) · V^{n}/n! = ∑_{V′∈F (V)} f(|V′|) · ν^{V′}, f : ℕ → A,

provides an imbedding of the ring A![[V]] of generating functions of exponential type (usually the variable is called x instead of V) into our ring A[V]. It is at the origin of (almost?) all applications of A![[V]] into combinatorics, but requires the existence of an infinite combinatorial model depending just on cardinalities. Consequently, A[V] gives more flexibility and closeness to combinatorics. In addition, A[V] is ideally suited for computer calculations (for more details and lots of different applications see [7]).

Remark. The ring ℤ![[V]] is not noetherian, but it contains the important functions exp(V) and log(1 + V).

Example. If char A = 2, then we have

(1 + V)^{−1} = ∑_{n=0}^{∞}(−1)^{n}n! · V^{n}/n!
≡ 1 + V and
log(1 + V) = ∑_{n=1}^{∞}(−1)^{n−1}(n − 1)! · V^{n}/n!
≡ V + V^{2}/2

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

For all t ∈ A we put (tν)^{V′} := t^{|V′|} · ν^{V′}, V′ ⊆ V, and therefore

F_{f}(tν) = ∑_{∅⊆V′⊆V} f(V′) t^{|V′|} · ν^{V′}.

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}(ν)^{n}/n! is defined for any ring A, because a partition into n nonempty subsets can be ordered in n! 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} → A the function f ∗ g : 2^{V} → A by

(f ∗ g)(V′) := f(V′) · g(V′)

for each V′ ⊆ V and define the Hadamard product to be

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

3. Duality theorems

Let G = (V, E) be a finite simple graph and let \overline{G} = (V, \overline{E}) be its complement. We have identified V with the generating function of the indicator function of the one-element subsets of V, and we have realized that V^{2}/2 corresponds to the indicator function of the two-element subsets of V. Similarly, we identify E and \overline{E} with the generating functions of the indicator functions of E, \overline{E} ⊆ 2^{V}. Since every two-element subset of V either belongs to E or to \overline{E}, we have the following fundamental identity, valid in the ring A[V]:

E + \overline{E} = V^{2}/2.

Let p(G) be the number of perfect matchings (if |V | ≡ 0 mod 2) or quasi-perfect matchings (if |V | ≡ 1 mod 2), and let c(G) be the number of arbitrary matchings of G. We denote by G[V′] the subgraph of G induced by V′ ⊆ V, i.e. its vertices are the elements of V′ and its edges are the edges of G having both endpoints in V′. Then the perfect matchings are counted by exp[E], the quasi-perfect matchings by V · exp[E], and altogether we have the identities

\begin{aligned}1 + ∑_{∅⊂V′⊆V} p(G[V′]) · ν^{V′} & = (1 + V) · exp[E], \\ 1 + ∑_{∅⊂V′⊆V} c(G[V′]) · ν^{V′} & = exp[V + E]. \end{aligned}

The following proposition was proved in [8], 5.18, for the case of perfect matchings.

Proposition. c(\overline{G}) ≡ p(G) mod 2.

Proof. Using the previous three identities we have

exp[V + \overline{E}] = exp[V + V^{2}/2 − E] ≡ exp[log(1 + V) + E] = (1 + V) · exp[E].

From the very definitions of the matching polynomials we have the following generating functions:

\begin{aligned}1 + ∑_{∅⊂V′⊆V} μ(G[V′], x) · ν^{V′} & = exp[xV − E], \\ 1 + ∑_{∅⊂V′⊆V} \overline{μ}(G[V′], x) · ν^{V′} & = exp[xV + E]. \end{aligned}

Considering the first equality for the complete graph K_{∞} on an infinite set of vertices yields the classical generating function of exponential type for Hermite polynomials:

1 + ∑_{n=1}^{∞} μ(K_{n}, x) · V^{n}/n! = exp[xV − V^{2}/2].

We are now in a position to provide a very short proof of Godsil’s duality theorem.

Duality theorem (Godsil).

μ(\overline{G}, x) = ∑_{r=0}^{⌊n/2⌋} p(G, r) · μ(K_{n−2r}, x).

Proof. Using the set function algebra developed in section 2 we have: exp[xV − \overline{E}] = exp[xV − V^{2}/2 + E] = exp[E] · exp[xV − V^{2}/2].

We can further establish the following new identities.

Duality theorem for the matching polynomials (\frac{d^{2}}{dx^{2}} ).

\begin{aligned}\overline{μ}(\overline{G}, x) & = exp[\frac{d^{2}}{dx^{2}} /2] · μ(G, x), \\ μ(\overline{G}, x) & = exp[−\frac{d^{2}}{dx^{2}} /2] · \overline{μ}(G, x). \end{aligned}

Proof. As in the preceding proof,

exp[xV + \overline{E}] = exp[V^{2}/2] · exp[xV − E]
= exp[\frac{d^{2}}{dx^{2}} /2] · exp[xV − E],

because \frac{d}{dx} exp[xV −E] = V ·exp[xV −E]. The differential operator exp[−\frac{d^{2}}{dx^{2}} /2] is the inverse of exp[\frac{d^{2}}{dx^{2}} /2].

Duality theorem for the matching polynomials (\frac{d}{dx}).

\begin{aligned}\overline{μ}(\overline{G}, x) & = e^{−x^{2}/2} · μ(G, \frac{d}{dx}) · e^{x^{2}/2}, \\ μ(\overline{G}, x) & = e^{x^{2}/2} · \overline{μ}(G, −\frac{d}{dx}) · e^{−x^{2}/2}. \end{aligned}

Proof. By the Taylor formula we know that

f(x + a) = exp[\frac{d}{dx}a] · f(x)

for variables x, a and a formal power series f. It follows that

exp[−x^{2}/2] · exp[\frac{d}{dx}V − E] · exp[x^{2}/2]
= exp[−x^{2}/2] · exp[−E] · exp[\frac{d}{dx}V] · exp[x^{2}/2]
= exp[−x^{2}/2] · exp[−E] · exp[(x + V)^{2}/2]
= exp[xV + \overline{E}].

The second equality is proved in the same way.

Specializing the second equality of the preceding theorem to Hermite polynomials, i.e. replacing \overline{G} by K_{n}, provides the classical definition of Hermite polynomials. However, we could not find the specialization to Hermite polynomials of the first equality, i.e. the differential operator He_{n}(d/dx), in the literature.

Finally, we can prove several integral formulae.

Duality theorem for the matching polynomials (∫).

\overline{μ}(\overline{G}, y) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−(x−y)^{2}/2} · μ(G, x) · dx.

Proof. Using the invariance of the integral with respect to translations we get:

\frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} exp[−(x − y)^{2}/2] · exp[xV − E] · dx

= \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} exp[−s^{2}/2] · exp[(s + y)V − E] · ds

= exp[yV + \overline{E}] · \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} exp[−(s − V)^{2}/2] · ds

= exp[yV + \overline{E}] · \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} exp[−t^{2}/2] · dt
= exp[yV + \overline{E}].

For graphs G′ = (V′, E′) and G′′ = (V′′, E′′) we have the following result.

Scalar product formula.

\begin{aligned}\overline{μ}(\overline{G′ ⊎ G′′}, 0) & = \frac{1}{\sqrt{2π}} ∫_{−∞}^{∞} μ(G′, x) · μ(G′′, x) · e^{−x^{2}/2} · dx \\ & = \overline{μ}(\overline{G′}, \frac{d}{dx}) · \overline{μ}(\overline{G′′}, x)|_{x=0}. \end{aligned}

Proof. The first equality being evident from the previous theorem, we just have to prove the second one:

exp[\frac{d}{dx}V′ + \overline{E′}] · exp[xV′′ + \overline{E′′}]|_{x=0}
= exp[\overline{E′}] · exp[(x + V′)V′′ + \overline{E′′}]|_{x=0}
= exp[V′V′′ + \overline{E′} + \overline{E′′}].

Remark. If G′ = K_{n} and G′′ = K_{m}, then the scalar product formula counts the number of perfect matchings of the complete bipartite graph \overline{K_{n} ⊎ K_{m}}, which is equal to zero, if n ≠ m, and equal to n!, if n = m. This is the orthogonality of the Hermite polynomials.

The previous duality theorem implies μ(\overline{G}, y) = \frac{(−i)^{n}}{\sqrt{2π}} ∫_{−∞}^{∞} e^{−(x−yi)^{2}/2} ·μ(G, x)·dx. This proves the following theorem.

Duality theorem for the matching polynomial (ℂ).

e^{−y^{2}/2}μ(\overline{G}, y) = \frac{(−i)^{n}}{\sqrt{2π}} ∫_{−∞}^{∞} e^{xyi} · e^{−x^{2}/2}μ(G, x) · dx.

If we call e^{−x^{2}/2}μ(G, x) matching function of G, then this matching function is even for n even and odd for n odd.

Duality theorem for the matching polynomial (ℝ).

e^{−y^{2}/2}μ(\overline{G}, y) · (−1)^{n/2}
= \sqrt{\frac{2}{π}} · ∫_{0}^{∞} cos(xy) · e^{−x^{2}/2}μ(G, x) · dx, n even,

e^{−y^{2}/2}μ(\overline{G}, y) · (−1)^{(n−1)/2}
= \sqrt{\frac{2}{π}} · ∫_{0}^{∞} sin(xy) · e^{−x^{2}/2}μ(G, x) · dx, n odd.

Thus the matching functions of \overline{G} and G are, up to an eventual multiplication by −1, real Fourier transforms of one another.

4. Zeros

From now on every edge {u, v} ∈ E of our graph G = (V, E) will get a positive real weight w_{{u,v}} (we can assume that the two-element subsets of V which are not edges get the weight zero). This weighted graph will be denoted by G_{w} = (V, E_{w}). In particular, 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, which get their own weights. The (weighted) matching polynomial can be defined with the help of its generating function:

1 + ∑_{∅⊂V′⊆V} μ(G_{w}[V′], x) · ν^{V′} = exp[xV − E_{w}].

We see that every matching is counted with respect to its weight: the product of the weights of its edges.

A Hamiltonian cycle of G_{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_{w}) be the sum of the weights of all Hamiltonian cycles of G_{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_{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(G_{w}) be the sum of the weights of all Hamiltonian paths of G_{w}, with the convention that lin(G_{w}) = 1 if n = 1. Clearly, lin(K_{n}) = n!.

Let us put

cyc_{G_{w}}(ν) := ∑_{∅⊂V′⊆V} cyc(G_{w}[V′]) · ν^{V′}, lin_{G_{w}}(ν) := ∑_{∅⊂V′⊆V} lin(G_{w}[V′]) · ν^{V′}.

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} .

Usually (in undirected graphs) one does not distinguish between the two different directions of Hamiltonian cycles or paths. In this sense cyc_{G_{w}}(ν) and lin_{G_{w}}(ν) count them “twice”. Now we can prove our generalization of the Mehler formula.

Theorem. Using the Hadamard product ∗ we have:

exp[xV − E_{w}] ∗ exp[yV − E_{w}]
= exp[\frac{1}{2} · cyc_{G_{w}}(ν) + \frac{1}{2} · cyc_{G_{w}}(−ν)] ·
exp[−(\frac{x−y}{2} )^{2} · lin_{G_{w}}(ν)−(\frac{x+y}{2} )^{2} · lin_{G_{w}}(−ν)].

Proof. Two matchings of G_{w} to be considered in the left hand side of the theorem provide a partition of V into even Hamiltonian cycles (to be counted “twice”, because the matchings can be interchanged), even (according to the number of vertices) Hamiltonian paths (to be counted with the factor −x^{2} or −y^{2}, because the number of edges of the paths is odd) and odd Hamiltonian paths (to be counted with the factor 2xy). Thus the left hand side is equal to

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

exp[\frac{lin_{G_{w}}(ν) + lin_{G_{w}}(−ν)}{4} · (−x^{2} − y^{2})] ·

exp[\frac{lin_{G_{w}}(ν) − lin_{G_{w}}(−ν)}{4} · 2xy].

But this is precisely the right hand side of the theorem.

Specializing to K_{∞} yields the Mehler formula.

Corollary (Mehler).

1 + ∑_{n=1}^{∞} μ(K_{n}, x)μ(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} ].

Replacing y in the previous theorem by the complex conjugate number \overline{x} yields the following corollary.

Corollary.

exp[xV − E_{w}] ∗ exp[\overline{x}V − E_{w}]

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

exp[(ℑm x)^{2} · lin_{G_{w}}(ν) − (ℜe x)^{2} · lin_{G_{w}}(−ν)]

= exp[(ℑm x)^{2} · lin_{G_{w}}(ν)] · (exp[(ℜe x)V − E_{w}] ∗ exp[(ℜe x)V − E_{w}]).

Therefore |μ(G_{w}, x)|^{2} ≥ [(ℑm x)^{2}]^{n} + 2W · [(ℑm x)^{2}]^{n−1} for every x ∈ ℂ, where W is the sum of the weights of all edges of G_{w}. In particular, all zeros of μ(G_{w}, x) are real.

We finish this article by considering a common generalization of the matching polynomial and the classical rook polynomial. Thus we do not just have our weighted graph G′_{w} = (V′, E′_{w}), but also a bipartite graph G′′_{w} = (V′, V′′; E′′_{w}). In other words, we have a graph G_{w} = (V, E_{w}) with vertex set V := V′ ⊎ V′′, edge set E_{w} := E′_{w} ⊎ E′′_{w} and, in particular, no edges between vertices of V′′. The weights of the edges of G′_{w} are still assumed to be positive, whereas the weights of the edges of G′′_{w} are supposed to be such that for each v′′ ∈ V′′ the weights of the edges incident with v′′ all have the same sign, i.e. they are all positive or all negative.

Let exp[xV′ + V′′ − E′_{w} − E′′_{w}] be the generating function of our generalized matching polynomials, and let cyc_{G_{w}}(ν) count the Hamiltonian cycles “twice”. Moreover, let lin_{G_{w}}(ν), lin’_{G_{w}}(ν), lin”_{G_{w}}(ν) count the Hamiltonian paths “twice” which have both endpoints in V′, one endpoint in V′ and one endpoint in V′′, both endpoints in V′′, respectively. (Note that lin_{G_{w}}(ν) is nonnegative by our restrictions on the weights.)

Theorem.

exp[xV′ + V′′ − E′_{w} − E′′_{w}] ∗ exp[yV′ + V′′ − E′_{w} − E′′_{w}]
= exp[\frac{1}{2} · cyc_{G_{w}}(ν) + \frac{1}{2} · cyc_{G_{w}}(−ν)] ·
exp[−(\frac{x−y}{2} )^{2} · lin_{G_{w}}(ν)−(\frac{x+y}{2} )^{2} · lin_{G_{w}}(−ν)] ·
exp[−\frac{x+y}{2} · lin’_{G_{w}}(−ν)] · exp[−lin”_{G_{w}}(−ν)].

Proof. Clearly, both sides of the equality are equal to

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

exp[\frac{lin_{G_{w}}(ν) + lin_{G_{w}}(−ν)}{4} · (−x^{2} − y^{2})] · exp[\frac{lin_{G_{w}}(ν) − lin_{G_{w}}(−ν)}{4} · 2xy] ·

exp[\frac{lin’_{G_{w}}(ν) + lin’_{G_{w}}(−ν)}{4}(−x − y)] · exp[\frac{lin’_{G_{w}}(ν) − lin’_{G_{w}}(−ν)}{4}(x + y)] ·

exp[\frac{lin”_{G_{w}}(ν) + lin”_{G_{w}}(−ν)}{4} · (−2)] · exp[\frac{lin”_{G_{w}}(ν) − lin”_{G_{w}}(−ν)}{4} · 2].

Corollary.

exp[xV′ + V′′ − E′_{w} − E′′_{w}] ∗ exp[\overline{x}V′ + V′′ − E′_{w} − E′′_{w}]
= exp[\frac{1}{2} · cyc_{G_{w}}(ν) + \frac{1}{2} · cyc_{G_{w}}(−ν)] ·
exp[(ℑm x)^{2} · lin_{G_{w}}(ν) − (ℜe x)^{2} · lin_{G_{w}}(−ν)] ·
exp[−(ℜe x) · lin’_{G_{w}}(−ν)] · exp[−lin”_{G_{w}}(−ν)]
= exp[(ℑm x)^{2} · lin_{G_{w}}(ν)] ·

(exp[(ℜe x)V′ + V′′ − E′_{w} − E′′_{w}] ∗ exp[(ℜe x)V′ + V′′ − E′_{w} − E′′_{w}]).

Since lin_{G_{w}}(ν) is nonnegative, all zeros of our generalized matching polynomial are real.

Acknoledgements: First of all, I should like to thank cordially D. Foata to have made the redaction of this article possible by inviting me to the IRMA in Strasbourg and by explaining to me his combinatorial proof of the Mehler formula. His help and support are undescribable. I also want to express my gratitude to A. Frank for his recommendation of the beautiful book [3] (otherwise [7], chapter 3.1, would not exist), and especially to E. Triesch (without him [7] would not exist).

References

[1] G. E. Andrews, R. Askey, R. Roy: Special Functions, Encyclopedia of mathematics and its applications, Vol. 71, Cambridge University Press, 1999.

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

[3] C. D. Godsil: Algebraic Combinatorics, Chapman & Hall, 1993.

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

[5] O. J. Heilmann, E. H. Lieb: Theory of monomer-dimer systems, Comm. Math. Physics, 25 (1972), 190-232.

[6] C. Itzykson, J.-B. Zuber: Matrix integration and combinatorics of modular groups, Comm. Math. Physics, 134 (1990), 197-207.

[7] B. Lass: Funktionen zählen, Diplomarbeit, 1997.

[8] L. Lovász: Combinatorial Problems and Exercises, Akadémiai Kiadó, 1993.

[9] G. Viennot: Une théorie combinatoire des polynômes orthogonaux généraux, Notes de conférences données à l’Université du Québec à Montréal, 1983.

Bodo Lass Lehrstuhl II für Mathematik, RWTH Aachen, Templergraben 55, D-52062 Aachen, Germany lass@math2.rwth-aachen.de