The N-dimensional matching polynomial

Bodo Lass

Institut Girard Desargues (UMR 5028 du CNRS), Université Claude Bernard (Lyon 1) Bât Jean Braconnier, 43, Bd du 11 Novembre 1918, F-69622 Villeurbanne Cedex, France

Email: lass@igd.univ-lyon1.fr

To P. Cartier and A. K. Zvonkin

Heilmann et Lieb ont introduit le polynôme de couplage μ(G,x) d’un graphe G=(V,E). Nous prolongeons leur définition en munissant chaque sommet de G d’une forme linéaire N-dimensionnelle (ou bien d’un vecteur) et chaque arête d’une forme symétrique bilinéaire. On attache donc à tout r-couplage de G le produit des formes linéaires des sommets qui ne sont pas saturés par le couplage, multiplié par le produit des poids des r arêtes du couplage, où le poids d’une arête est la valeur de sa forme évaluée sur les deux vecteurs de ses extrémités. En multipliant par (−1)^{r} et en sommant sur tous les couplages, nous obtenons notre polynôme de couplage N-dimensionnel. Si N=1, le théorème principal de l’article de Heilmann et Lieb affirme que tous les zéros de μ(G,x) sont réels. Si N=2, cependant, nous avons trouvé des graphes exceptionnels où il n’y a aucun zéro réel, même si chaque arête est munie du produit scalaire canonique. Toutefois, la théorie de la dualité développée dans [12] reste valable en N dimensions. Elle donne notamment une nouvelle interprétation à la transformation de Bargmann-Segal, aux diagrammes de Feynman et aux produits de Wick.

Heilmann and Lieb have introduced the matching polynomial μ(G,x) of a graph G=(V,E). We extend their definition by associating to every vertex of G an N-dimensional linear form (or a vector) and to every edge a symmetric bilinear form. For every r-matching of G we define its weight as the product of the linear forms of the vertices not covered by the matching, multiplied by the product of the weights of the r edges of the matching, where the weight of an edge is the value of its form evaluated at the two vectors of its end points. Multiplying by (−1)^{r} and summing over all matchings, we get our N-dimensional matching polynomial. If N=1, the Heilmann-Lieb theorem affirms that all zeroes of μ(G,x) are real. If N=2, however, there are exceptional graphs whithout any real zero at all, even if the canonical scalar product is associated to every edge. Nevertheless, the duality theory developed in [12] remains valid in N dimensions. In particular, it brings new light to the Bargmann-Segal transform, to the Feynman diagrams, and to the Wick products.

1. Introduction

Let V be a finite set of cardinality n. A graph G = (V, E) is called simple if and only if the set of its edges E is a subset of \binom{V}{2}, the family of all 2-element subsets of V. For such graphs we define the complement by \overline{G} := (V, \overline{E}) with \overline{E} := \binom{V}{2}\E.

BODO LASS

Key words: matching polynomials, complementary graph, semi-invariants, Gaussian integrals, Wick products, Feynman diagrams, Bargmann-Segal transform For every r ≥ 0, an r-matching in G is a set of r edges of G, no two of which have a vertex in common. If r = n/2, then the matching is called perfect.

Moreover, let us consider a Euclidean space R of dimension N, R = ℝ^{N}, with its canonical scalar product ⟨x, y⟩ = ∑_{i=1}^{N} x_{i}y_{i} (remember that n = |V | is the number of vertices of G). Let e_{1}, …, e_{N} be the canonical (orthonormal) basis of R. We use it to interpret polynomials and partial derivatives (or ∇) in the usual way. Moreover, let ⟨x, y⟩_{P} := ⟨x, P y⟩, P = P^{T} and P > 0, be an additional scalar product.

Let us attach to each vertex v ∈ V of our graph G = (V, E) a vector a_{v} ∈ R, and to each edge {u, v} ∈ E the scalar product ⟨a_{u}, a_{v}⟩_{P}. We use the notation a_{P} G = (aV, a_{P} E) for this “decorated” graph. Let us look at a matching of a_{P} G. We multiply the product of the scalar products of the edges of our matching and the product of the scalar products ⟨x, a_{v}⟩_{P}, x ∈ R, of the vertices of a_{P} G which are not covered by any edge of the matching. This gives a homogeneous polynomial of degree n − 2r (n = |V |), if the matching contains r edges. If we multiply this polynomial by (−1)^{r} and sum these expressions over all matchings of a_{P} G, we get the signed N-dimensional matching polynomial μ(a_{P} G, x). If we do not multiply by (−1)^{r} before summing, we get the unsigned N-dimensional matching polynomial \overline{μ}(a_{P} G, x). In the sequel, if we say matching polynomial without any further attribute, then we mean the signed one. Since every vector a_{v}, v ∈ V, appears in each homogeneous polynomial of degree n − 2r precisely once (in a factor ⟨a_{u}, a_{v}⟩_{P} if v is covered by the matching and in a factor ⟨x, a_{v}⟩_{P} otherwise), the polynomials μ(a_{P} G, x) and \overline{μ}(a_{P} G, x) are linear in the vectors a_{v} (and equal to zero, if there exists a v ∈ V such that a_{v} = 0). Moreover, they satisfy the obvious relation

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

Example 1.1. Let K_{n} = (V, \binom{V}{2}) be the complete graph on n vertices such that its complementary graph \overline{K_{n}} = (V, ∅) has no edge at all. Let us attach to each v ∈ V a vector a_{v} ∈ R. Then we have the following expressions for the matching polynomials of the two complementary decorated graphs a_{P} K_{n} and \overline{a_{P} K_{n}}:

μ(\overline{a_{P} K_{n}}, x) = \overline{μ}(\overline{a_{P} K_{n}}, x) = ∏_{v∈V} ⟨x, a_{v}⟩_{P};
μ(a_{P} K_{2}, x) = ⟨x, a_{u}⟩_{P} ⟨x, a_{v}⟩_{P} − ⟨a_{u}, a_{v}⟩_{P} ,
\overline{μ}(a_{P} K_{2}, x) = ⟨x, a_{u}⟩_{P} ⟨x, a_{v}⟩_{P} + ⟨a_{u}, a_{v}⟩_{P} ,
μ(a_{P} K_{3}, x) = ⟨x, a_{u}⟩_{P} ⟨x, a_{v}⟩_{P} ⟨x, a_{w}⟩_{P} − ⟨x, a_{u}⟩_{P} ⟨a_{v}, a_{w}⟩_{P}
− ⟨x, a_{v}⟩_{P} ⟨a_{u}, a_{w}⟩_{P} − ⟨x, a_{w}⟩_{P} ⟨a_{u}, a_{v}⟩_{P} , etc.

Remark 1.1. In physics, the polynomial μ(a_{P} K_{n}, x) is called Wick (or Hermite) polynomial. It is denoted by Φ(x|a_{1}, …, a_{n}) or by :∏_{v∈V} ⟨x, a_{v}⟩_{P}: or by [∏_{v∈V} ⟨x, a_{v}⟩_{P}]^{♯} (see [3],[6],[15]).

Let G = (V, E) and \overline{G} := (V, \overline{E}) be arbitrary complementary graphs. Let us attach to every v ∈ V a vector a_{v} ∈ R in order to get two complementary decorated graphs, namely a_{P} G = (aV, a_{P} E) and \overline{a_{P} G} = (aV, \overline{a_{P} E}) (in the classical onedimensional case, we have a_{v} = 1 for every v ∈ V as well as P = 1). A priori, it is not clear at all whether the matching polynomials μ(\overline{a_{P} G}, x) and \overline{μ}(\overline{a_{P} G}, x) of the complementary graph \overline{a_{P} G} are determined by the matching polynomials μ(a_{P} G, x) and \overline{μ}(a_{P} G, x) of the graph a_{P} G itself. Lovász [14, 5.18] and Godsil [7],

[8] have established such a result in the one-dimensional case. It seems to be difficult, however, to generalize their proofs. Fortunately, the proofs presented in [12] can be generalized almost without any modification. Indeed, we prove that \overline{μ}(\overline{a_{P} G}, x) is the Bargmann-Segal-Wiener transform of μ(a_{P} G, x), and μ(\overline{a_{P} G}, x) is the Wick transform of \overline{μ}(a_{P} G, x), i.e.,

\overline{μ}(\overline{a_{P} G}, x) = [μ(a_{P} G, x)]^{♭}, μ(\overline{a_{P} G}, x) = [\overline{μ}(a_{P} G, x)]^{♯}.

More precisely, we establish the identities

\overline{μ}(\overline{a_{P} G}, x) = ∑_{n=0}^{∞} \frac{1}{n!} ∫_{R} μ(a_{P} G, z) · μ(x_{P} K_{n}, z) · e^{−⟨z,z⟩_{P} /2} · d_{P} z

= ∫_{R} e^{−⟨z−x,z−x⟩_{P} /2} · μ(a_{P} G, z) · d_{P} z
= e^{−⟨x,x⟩_{P} /2} · μ(a_{P} G, ∇_{P}) · e^{⟨x,x⟩_{P} /2}
= exp[△_{P} /2] · μ(a_{P} G, x),

as well as

\begin{aligned}μ(\overline{a_{P} G}, x) & = e^{⟨x,x⟩_{P} /2} · \overline{μ}(a_{P} G, −∇_{P}) · e^{−⟨x,x⟩_{P} /2} \\ & = exp[−△_{P} /2] · \overline{μ}(a_{P} G, x), \end{aligned}

where

d_{P} z := \sqrt{det(P)/(2π)^{N}} · d^{N}z (P = 2π · Id ⇒ d_{P} z = d^{N}z),
∇_{P} := P^{−1}∇, △_{P} := ⟨∇_{P} , ∇_{P} ⟩_{P} = ⟨∇, ∇⟩_{P^{−1}}.

Remark 1.2. The operator △_{P} is nothing else but the general form of what is called an elliptic operator of second degree.

Since the space of polynomials is generated (as a vector space) by the matching polynomials, our relations also offer an abundance of possible definitions for the Bargmann-Segal or for the Wick transformation, and one can ask the question whether all of them are well known. Indeed, during the Séminaire Lotharingien de Combinatoire 44, Cartier [2] has made use of the first integral formula in order to define the Bargmann-Segal transformation. He has defined the Wick transformation, however, in a totally combinatorial way with the help of the identity μ(a_{P} K_{n}, x) = [∏_{v∈V} ⟨x, a_{v}⟩_{P}]^{♯}. Finally, he has used the identity μ(a_{P} K_{n}, x) = e^{⟨x,x⟩_{P} /2}·\overline{μ}(\overline{a_{P} K_{n}}, −∇_{P})·e^{−⟨x,x⟩_{P} /2} in order to define the Wick (i.e. Hermite) polynomials. In his article [3], which, however, treats just the one-dimensional case, he has finally proposed the second integral formula and the second differential formula in order to define the Bargmann-Segal transformation (and the second differential formula for the Wick transformation). Therefore our first differential formula is apparently new as an additional possibility to define the Bargmann-Segal transformation. At least, there cannot be any doubt that matching polynomials provide a better understanding of the respective roles of the two transformations.

Last, but not least, the importance of N-dimensional matching polynomials is underlined by the surprising fact that the matching functions e^{−⟨x,x⟩_{P} /2}μ(\overline{a_{P} G}, x) and e^{−⟨x,x⟩_{P} /2}μ(a_{P} G, x) are indeed Fourier transforms of each other.

Example 1.2. Let us suppose that V = T_{1} ⊎ … ⊎ T_{k}, and that K_{t_{1}}, …, K_{t_{k}} are complete graphs on the vertex sets T_{1}, …, T_{k}, respectively. For the matching polynomial of the decorated graph a_{P} K_{t_{1}} ⊎ … ⊎ o_{P} K_{t_{k}}, we have the obvious identity

\begin{aligned}μ(a_{P} K_{t_{1}} ⊎ … ⊎ o_{P} K_{t_{k}}, z) & = μ(a_{P} K_{t_{1}}, z) ⋯ μ(o_{P} K_{t_{k}}, z) \\ & = [ ∏_{v∈T_{1}}⟨z, a_{v}⟩_{P} ]^{♯} ⋯ [ ∏_{v∈T_{k}}⟨z, o_{v}⟩_{P} ]^{♯}. \end{aligned}

The case x = 0 of our second integral identity for the Bargmann-Segal transformation allows us to conclude that

\begin{matrix}\overline{μ}(\overline{a_{P} K_{t_{1}} ⊎ … ⊎ o_{P} K_{t_{k}}}, 0) \\ = ∫_{R}[ ∏_{v∈T_{1}}⟨z, a_{v}⟩_{P} ]^{♯} ⋯ [ ∏_{v∈T_{k}}⟨z, o_{v}⟩_{P} ]^{♯} · e^{−⟨z,z⟩_{P} /2}d_{P} z \end{matrix}

counts the (weighted) number of perfect matchings of the decorated complete multipartite graph \overline{a_{P} K_{t_{1}} ⊎ … ⊎ o_{P} K_{t_{k}}}. This result corresponds to Formula 3) of Section “Diagrams” in the recent book [15, Chapter 2.2] and to Corollary 8.3.2 of the book [6]. Note that the authors of these books identify all vertices of T_{1}, all vertices of T_{2}, …, and all vertices of T_{k}, so that they have just k different vertices to consider. The edges inside the blocks T_{1}, …, T_{k} become loops (“selflines”) in this way. In the main result of Section 8.3 of the book [6] by Glimm and Jaffe, these loops carry different scalar products as described in our abstract and in Remark 3.1. The case k = 2 is nothing else but the orthogonality of the Wick polynomials, because the (weighted) number of perfect matchings of the decorated complete bipartite graph \overline{a_{P} K_{t_{1}} ⊎ o_{P} K_{t_{2}}} is equal to zero if t_{1} ≠ t_{2} and is equal to the permanent per(⟨a_{u}, o_{v}⟩_{P}) if t_{1} = t_{2}.

We prove all our main theorems with the help of the algebra of set functions. This leads to very short and conceptual proofs, whereas the classical particular cases of our results mentioned in the preceding example were established in the books by Glimm, Jaffe, Malyshev and Minlos by using partial integration, which leads to considerably longer arguments (see, for example, [15, pp. 39-41]). Set functions also contribute to a better understanding of the semi-invariants studied in probability theory, as well as of the bialgebra of partitions introduced by Lando in his article [10]. All this is explained in the following section. Section 3, on the other hand, covers the duality theorems, which we discussed earlier in this introduction.

Finally, we study the divisor div[μ(a_{P} G, x)] in the fourth section. Originally, we had conjectured that the Heilmann–Lieb theorem affirming that all zeroes of μ(G, x) are real (if N = 1) can be generalized to higher dimensions. What we prove is, in fact, a theorem which imposes very restrictive conditions on the class of possible counter-examples. Although this theorem can be refined even further, by using the last theorem of [12], there exist indeed very rare decorated graphs, the matching polynomial of which has no real zero at all, thus refuting our conjecture. We provide a family of such counter-examples. The problem of characterizing all possible counter-examples remains open.

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.

Remark 2.1. If A is a field, A[V] is a local Artinian ring of length 2^{|V |}.

Example 2.1. The product fg of two set functions f and g is defined, for every V′ ⊆ V, by

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

It follows that

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 we define

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

in order to work with the generating functions of the form

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

Let

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

be 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 any 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 embedding 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]. This embedding is at the origin of (almost?) all applications of A![[V]] to combinatorics, but requires the existence of an infinite combinatorial model depending just on cardinalities. Consequently, A[V] gives more flexibility and allows an algebraic treatment, which perfectly reflects the classical combinatorial operations. In addition, A[V] is ideally suited for computer calculations.

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

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. Therefore we have an action of A![[V]] on A[V] via the substitution G(F_{f}(ν)) defined for any G ∈ A![[V]].

Finally, for every v ∈ V, we use the derivatives ∂^{v} defined by

∂^{v}ν^{V′} := \{ \begin{matrix}ν^{V′}, & if v ∈ V′, \\ 0, & otherwise. \end{matrix}

The product rule

∂^{v}[F_{f}(ν) · F_{g}(ν)] = (∂^{v}F_{f}(ν)) · F_{g}(ν) + F_{f}(ν) · (∂^{v}F_{g}(ν))

is the algebraic analogue of the most fundamental set theoretic fact:

v ∈ V′ ⊎ V′′  ⇔  v ∈ V′ or v ∈ V′′.

The chain rule

∂^{v}[G(F_{f}(ν))] = G′(F_{f}(ν)) · ∂^{v}F_{f}(ν), G ∈ A![[V]],

follows immediately from the product rule.

Remark 2.3. Under the isomorphism A[V] ≃ A[v_{1}, …, v_{n}]/⟨v_{1}^{2}, …, v_{n}^{2}⟩, ∂^{v} does not correspond to ∂/∂v_{i}, but to v_{i}∂/∂v_{i}. The partial derivative ∂/∂v_{i} cannot be defined in A[V].

Example 2.2. (The bialgebra of partitions)

Let V be a finite set of cardinality n. Lando [10] has introduced and studied the bialgebra 𝔅(V), called bialgebra of partitions. We have to associate to every ∅ ⊂ V′ ⊆ V a variable denoted by (V′). As an algebra, 𝔅(V) is the commutative polynomial algebra generated (over ℤ) by the 2^{n} − 1 variables (V′), where e := (∅) can be considered as a unit element. 𝔅(V) is graduated if we define the order of the variable (V′) to be |V′|. With respect to the algebra structure, the comultiplication μ is a homomorphism, which we define by putting

(V′)_{1} := (V′) ⊗ e, (V′)_{2} := e ⊗ (V′),

μ((V′)) := (V′)_{1} + (V′)_{2} + ∑_{∅⊂V′′⊂V′}(V′′)_{1} · (V′\V′′)_{2}

for every ∅ ⊂ V′ ⊆ V. An element b ∈ 𝔅(V) is called primitive if and only if μ(b) = b_{1} + b_{2} = b ⊗ e + e ⊗ b. For example, ({v}) is primitive for every v ∈ V.

In this context, it is very useful to consider the generating functions

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

[1 + F_{V_{1}}(ν)] := [1 + F_{V} (ν)] ⊗ e, [1 + F_{V_{2}}(ν)] := e ⊗ [1 + F_{V} (ν)].

They enable us to obtain an easier definition of the comultiplication,

μ[1 + F_{V} (ν)] = [1 + F_{V_{1}}(ν)] · [1 + F_{V_{2}}(ν)],

which allows us to conclude that

μ(log[1 + F_{V} (ν)]) = log(μ[1 + F_{V} (ν)]) = log([1 + F_{V_{1}}(ν)] · [1 + F_{V_{2}}(ν)])
= log[1 + F_{V_{1}}(ν)] + log[1 + F_{V_{2}}(ν)].

In other words, every coefficient of log[1 + F_{V} (ν)] is a primitive element of the bialgebra 𝔅(V). This result is nothing else but the main theorem of the article [10] (see also [11, Chapter 6.1.6]).

Example 2.3. (Semi-invariants)

Let V be a finite set of cardinality n. Let us associate to every v ∈ V a random variable ξ_{v}, where coincidences ξ_{u} = ξ_{v} for u ≠ v are not forbidden. In fact, they are even desirable if we want to calculate higher moments, as we will see immediately. Let us put

ξV := ∑_{v∈V} ξ_{v} · ν^{{v}}  ⇒  exp[ξV] = 1 + ∑_{∅⊂V′⊆V} ( ∏_{v∈V′} ξ_{v}) · ν^{V′},

and let us define

1 + M_{ξ}(ν) := ⟨exp[ξV]⟩ := 𝔼(exp[ξV]) = 1 + ∑_{∅⊂V′⊆V} 𝔼( ∏_{v∈V′} ξ_{v}) · ν^{V′},

in order to calculate the expectations called moments. Evidently, we suppose that they are finite. We define the semi-invariants or cumulants to be the coefficients of

S_{ξ}(ν) := log[1 + M_{ξ}(ν)]

(see [4, Chapter 13] or [17, Chapter II.12]). The reader familiar with the theory will easily see the equivalence of our definition with his own one. We remark that our algebraic tools allow us to derive some other relations between the moments and the semi-invariants, such as

1 + M_{ξ}(ν) = exp[S_{ξ}(ν)], [1 + M_{ξ}(ν)] · ∂^{v}S_{ξ}(ν) = ∂^{v}M_{ξ}(ν),

where the very last relation is particularly useful for efficient computer calculations. We have not found it in the literature.

Suppose that V = T_{1}⊎…⊎T_{k}. Let us put ξ_{T_{i}} := ∏_{v∈T_{i}} ξ_{v} for each i ∈ {1, …, k}, and let us calculate all the moments of the family {ξ_{T_{i}}}, i = 1, …, k, with the help of the semi-invariants of the family {ξ_{v}}, v ∈ V. By the formula 1 + M_{ξ}(ν) = exp[S_{ξ}(ν)], we have to sum over all partitions of V. Each of them consists of several connected components with respect to the partition V = T_{1} ⊎ … ⊎ T_{k}, i.e., it defines a partition of the set {1, …, k}. Consequently, we have to sum over all partitions {a_{1}, …, o_{1}} ⊎ … ⊎ {a_{l}, …, o_{l}} = {1, …, k}, where the contribution of the block {a_{1}, …, o_{1}}, for example, is the sum over all partitions of the set B_{1} := T_{a_{1}} ∪ … ∪ T_{o_{1}} which are connected with respect to the partition B_{1} = T_{a_{1}} ⊎ … ⊎ T_{o_{1}}. The contribution of the block {a_{1}, …, o_{1}}, however, is nothing else but one of the semi-invariants of the family {ξ_{T_{i}}}, i = 1, …, k (because of the formula 1 + M_{ξ}(ν) = exp[S_{ξ}(ν)] applied to the set {1, …, k}). In other words, we have established the fact that the semi-invariants of the family {ξ_{T_{i}}} can be calculated with the help of the semi-invariants of the family {ξ_{v}} by summing “over all connected partitions”. This result was proved in [15, pp. 30–32], by induction and some manipulation.

For every ∅ ⊂ V′ ⊆ V, let us now introduce the Wick polynomials :(∏_{v∈V′} ξ_{v}): = (∏_{v∈V′} ξ_{v})^{♯} by putting

1 + ∑_{∅⊂V′⊆V} ( ∏_{v∈V′} ξ_{v})^{♯} · ν^{V′} := (exp[ξV])^{♯} := exp[ξV − S_{ξ}(ν)]

= \frac{exp[ξV]}{1 + M_{ξ}(ν)} = \frac{exp[ξV]}{⟨exp[ξV]⟩}

(see [3, Chapter 3.7] and [15, p. 37]). It is, without doubt, the leitmotiv of this whole article to choose two set functions E_{ξ} and \overline{E_{ξ}} such that

E_{ξ} + \overline{E_{ξ}} = S_{ξ}(ν).

The linearity of expectation implies

⟨exp[ξV − E_{ξ}]⟩ = ⟨exp[ξV]⟩ · exp[−E_{ξ}] = exp[S_{ξ}(ν)] · exp[−E_{ξ}]
= exp[\overline{E_{ξ}}].

Let us suppose finally that the vector {ξ_{v}} (v ∈ V) follows a Gaußian law with ⟨ξ_{v}⟩ = 0 for every v ∈ V such that the set function S_{ξ}(ν) equals zero except on the subsets of V of cardinality two. Let us attach to every edge {u, v} of the complete graph K_{n} = (V, \binom{V}{2}) the weight ⟨ξ_{u}ξ_{v}⟩, and let us choose a partition E ⊎ \overline{E} = \binom{V}{2} such that G = (V, E). By putting

E_{ξ} := ∑_{\{u,v\}∈E}⟨ξ_{u}ξ_{v}⟩ · ν^{\{u,v\}}, \overline{E_{ξ}} := ∑_{\{u,v\}∈\overline{E}}⟨ξ_{u}ξ_{v}⟩ · ν^{\{u,v\}},

we get indeed E_{ξ} + \overline{E_{ξ}} = S_{ξ}(ν). If E = ∅, then our preceding identity implies that ⟨∏_{v∈V} ξ_{v}⟩ counts the number of perfect matchings of the decorated graph K_{n} = (V, \binom{V}{2}). If E is the set of edges both endpoints of which are in the same block of the partition V = T_{1} ⊎ … ⊎ T_{k}, then ⟨exp[ξV − E_{ξ}]⟩ = exp[\overline{E_{ξ}}] implies that ⟨(ξ_{T_{1}})^{♯} ⋯ (ξ_{T_{k}})^{♯}⟩ counts the number of perfect matchings of the decorated complete multipartite graph \overline{G} = (V, \overline{E}) (see Example 1.2). These two results are nothing else but the Formulae 1) and 3) of Section “Diagrams” in [15, Chapter 2.2], respectively.

In the sequel, we will no longer adhere to the probabilistic vision, and we “replace the variance–covariance matrix by a matrix of symmetric bilinear forms.”

3. Matching polynomials and duality

Let a_{P} G = (aV, a_{P} E) and \overline{a_{P} G} = (aV, \overline{a_{P} E}) be two decorated complementary graphs (see the Introduction). We can now define the set functions

a_{P} E := ∑_{\{u,v\}∈E}⟨a_{u}, a_{v}⟩_{P} · ν^{\{u,v\}}, \overline{a_{P} E} := ∑_{\{u,v\}∈\overline{E}}⟨a_{u}, a_{v}⟩_{P} · ν^{\{u,v\}}.

We have to pay attention to the fact that, strictly speaking, the expression

aV := ∑_{v∈V} a_{v} · ν^{{v}}

does not correspond to a set function, because R is not a ring, but this difficulty disappears as soon as we consider scalar products such as

⟨x, aV ⟩_{P} = ∑_{v∈V}⟨x, a_{v}⟩_{P} · ν^{\{v\}}, ⟨aV, aV ⟩_{P} /2 = ∑_{\{u,v\}∈\binom{V}{2}}⟨a_{u}, a_{v}⟩_{P} · ν^{\{u,v\}}

(x ∈ R). The following identity is at the origin of all results of this section.

Fundamental lemma. We have

a_{P}E + \overline{a_{P}E} = ⟨aV, aV⟩_{P}/2.

For ∅ ⊂ V′ ⊆ V, let us denote by a_{p}G[V′] the decorated subgraph of a_{P} G induced by V′: it is the graph the vertices of which are the elements of V′ (with their associated vectors a_{v}, v ∈ V′) and the edges of which are the edges of a_{P} G having their two end points in V′. Thus, the set function exp[a_{P} E] counts, for every V′ ⊆ V, the number of perfect matchings of the decorated graph a_{p}G[V′]. Therefore the following proposition is an immediate consequence of the definitions of the matching polynomials (see the Introduction).

Proposition 3.1. We have

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

The generating functions become ordinary generating functions of exponential type if and only if there is a vector a ∈ R such that a_{v} = a, for all v ∈ V, and G = K_{∞} (or G = \overline{K_{∞}}).

Proposition 3.2. We have

\begin{aligned}1 + ∑_{n=1}^{∞} μ(a_{P} K_{n}, x) · V^{n}/n! & = exp[⟨x, a⟩_{P} · V − ⟨a, a⟩_{P} · V^{2}/2], \\ 1 + ∑_{n=1}^{∞} \overline{μ}(a_{P} K_{n}, x) · V^{n}/n! & = exp[⟨x, a⟩_{P} · V + ⟨a, a⟩_{P} · V^{2}/2]. \end{aligned}

Let us start by proving the N-dimensional analogue of Theorem 1.1 of [7, Chapter 1]. A very special case of this theorem served in [18, Chapter 1.1.15], as the main example to underline the usefulness of ordinary generating functions.

Proposition 3.3. We have

a) μ(a_{P} G′ ⊎ b_{P} G′′, x) = μ(a_{P} G′, x) · μ(b_{P} G′′, x),

a_{P} G′ = (aV′, a_{P} E′), b_{P} G′′ = (bV′′, b_{P} E′′);

b) μ(a_{P} G, x) = μ(a_{P} G\e, x) − ⟨a_{u}, a_{v}⟩_{P} · μ(a_{P} G\uv, x), e = {u, v} ∈ E;
c) μ(a_{P} G, x) = ⟨x, a_{v}⟩_{P} · μ(a_{P} G\v, x)

− ∑_{{u,v}∈E}⟨a_{u}, a_{v}⟩_{P} · μ(a_{P} G\uv, x), v ∈ V;

d) \frac{∂}{∂x_{i}} μ(a_{P} G, x) = ∑_{v∈V}⟨e_{i}, a_{v}⟩_{P} · μ(a_{P} G\v, x),

∇_{P} μ(a_{P} G, x) = ∑_{v∈V} a_{v} · μ(a_{P} G\v, x),

△_{P} μ(a_{P} G, x) = ∑_{u≠v∈V} ⟨a_{u}, a_{v}⟩_{P} · μ(a_{P} G\uv, x).

The analogue for \overline{μ}(a_{P} G, x) is obtained by replacing all signs − by +.

Proof.

a) exp[⟨x, aV′ + bV′′⟩_{P} − a_{P} E′ − b_{P} E′′]

= exp[⟨x, aV′⟩_{P} − a_{P} E′] · exp[⟨x, bV′′⟩_{P} − b_{P} E′′];

b) exp[⟨x, aV ⟩_{P} − a_{P} E]

= exp[⟨x, aV ⟩_{P} − a_{P} (E\e)] · exp[−⟨a_{u}, a_{v}⟩_{P} uv] = exp[⟨x, aV ⟩_{P} − a_{P} (E\e)] · (1 − ⟨a_{u}, a_{v}⟩_{P} uv) = exp[⟨x, aV ⟩_{P} − a_{P} (E\e)] − ⟨a_{u}, a_{v}⟩_{P} uv · exp[⟨x, aV ⟩_{P} − a_{P} (E\e)];

c) ∂^{v} exp[⟨x, aV ⟩_{P} − a_{P} E]

= exp[⟨x, aV ⟩_{P} − a_{P} E] · ∂^{v}(⟨x, aV ⟩_{P} − a_{P} E)

= exp[⟨x, aV ⟩_{P} − a_{P} E] · (⟨x, a_{v}⟩_{P} v − ∑_{{u,v}∈E}⟨a_{u}, a_{v}⟩_{P} uv)

= ⟨x, a_{v}⟩_{P} v · exp[⟨x, aV ⟩_{P} − a_{P} E] − ∑_{{u,v}∈E}⟨a_{u}, a_{v}⟩_{P} uv · exp[⟨x, aV ⟩_{P} − a_{P} E];

d) \frac{∂}{∂x_{i}} exp[⟨x, aV ⟩_{P} − a_{P} E] = exp[⟨x, aV ⟩_{P} − a_{P} E] · \frac{∂}{∂x_{i}} ⟨x, aV ⟩_{P}
= ⟨e_{i}, aV ⟩_{P} · exp[⟨x, aV ⟩_{P} − a_{P} E],
∇_{P} exp[⟨x, aV ⟩_{P} − a_{P} E] = aV · exp[⟨x, aV ⟩_{P} − a_{P} E],
△_{P} exp[⟨x, aV ⟩_{P} − a_{P} E] = ⟨aV, aV ⟩_{P} · exp[⟨x, aV ⟩_{P} − a_{P} E].

Let us leave the preceding recurrences in order to walk into the garden of duality theorems.

Duality theorem for the matching polynomials (△).

\begin{aligned}\overline{μ}(\overline{a_{P} G}, x) & = exp[△_{P} /2] · μ(a_{P} G, x), \\ μ(\overline{a_{P} G}, x) & = exp[−△_{P} /2] · \overline{μ}(a_{P} G, x). \end{aligned}

Proof. By using the very last identity of the proof of the preceding proposition, we get indeed

exp[⟨x, aV ⟩_{P} + \overline{a_{P} E}] = exp[⟨aV, aV ⟩_{P} /2] · exp[⟨x, aV ⟩_{P} − a_{P} E]
= exp[△_{P} /2] · exp[⟨x, aV ⟩_{P} − a_{P} E].

The differential operator exp[−△_{P} /2] is the inverse of exp[△_{P} /2].

Duality theorem for the matching polynomials (∇).

\begin{aligned}\overline{μ}(\overline{a_{P} G}, x) & = e^{−⟨x,x⟩_{P} /2} · μ(a_{P} G, ∇_{P}) · e^{⟨x,x⟩_{P} /2}, \\ μ(\overline{a_{P} G}, x) & = e^{⟨x,x⟩_{P} /2} · \overline{μ}(a_{P} G, −∇_{P}) · e^{−⟨x,x⟩_{P} /2}. \end{aligned}

Proof. By Taylor’s theorem we have

f(x + a) = exp[⟨∇, a⟩] · f(x) = exp[⟨∇_{P} , a⟩_{P}] · f(x)

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

exp[−⟨x, x⟩_{P} /2] · exp[⟨∇_{P} , aV ⟩_{P} − a_{P} E] · exp[⟨x, x⟩_{P} /2]
= exp[−⟨x, x⟩_{P} /2] · exp[−a_{P} E] · exp[⟨x + aV, x + aV ⟩_{P} /2]
= exp[⟨x, aV ⟩_{P} + \overline{a_{P} E}].

The second identity is proved in the same way.

Example 3.1. Let S and T be two disjoint sets. A bipartite graph G = (S, T; E) is called simple if and only if the set of its edges E is a subset of S × T. For such graphs, one defines the complementary bipartite graph by \overline{G} := (S, T; \overline{E}), with \overline{E} := (S × T)\E. Let us put N = 2, A = ℝ[s, t], and let us attach to each s′ ∈ S (respectively t′ ∈ T) the vector a_{s′} := \binom{0}{1} (respectively a_{t′} := \binom{1}{0}). For x = \binom{s}{t}, it follows that

P = P^{−1} = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ⇒ ⟨a_{s′}, a_{s′}⟩_{P} = ⟨a_{t′}, a_{t′}⟩_{P} = 0, ⟨a_{s′}, a_{t′}⟩_{P} = 1,

⟨x, a_{s′}⟩_{P} = s, ⟨x, a_{t′}⟩_{P} = t, ⟨x, x⟩_{P} /2 = st, ∇_{P} = \binom{d/dt}{d/ds}, △_{P} /2 = \frac{d}{ds} \frac{d}{dt}.

Therefore the matching polynomials μ(a_{P} G, x) and \overline{μ}(a_{P} G, x) of the decorated graph a_{P} G are nothing else but the symmetric rook polynomials ρ(G, s, t) and \overline{ρ}(G, s, t), introduced in [13]. More precisely, we have

\begin{aligned}μ(a_{P} G, x) & = ∑_{r=0}^{min(|S|,|T |)}(−1)^{r}p(G, r) · s^{|S|−r}t^{|T |−r} =: ρ(G, s, t), \\ \overline{μ}(a_{P} G, x) & = ∑_{r=0}^{min(|S|,|T |)} p(G, r) · s^{|S|−r}t^{|T |−r} =: \overline{ρ}(G, s, t), \end{aligned}

if p(G, r) is the number of r-matchings of the bipartite graph G = (S, T; E). Since ⟨a_{s′}, a_{s′}⟩_{P} = ⟨a_{t′}, a_{t′}⟩_{P} = 0 and ⟨a_{s′}, a_{t′}⟩_{P} = 1, for all s′ ∈ S and t′ ∈ T, the complementary decorated graph \overline{a_{P} G} corresponds precisely to the complementary bipartite graph \overline{G} = (S, T; \overline{E}), and we have

\overline{μ}(\overline{a_{P} G}, x) = \overline{ρ}(\overline{G}, s, t), μ(\overline{a_{P} G}, x) = ρ(\overline{G}, s, t).

Consequently, our two duality theorems for the matching polynomials imply

\begin{aligned}\overline{ρ}(\overline{G}, s, t) & = exp[\frac{d}{ds} \frac{d}{dt}] · ρ(G, s, t) = e^{−st} · ρ(G, \frac{d}{dt}, \frac{d}{ds}) · e^{st}, \\ ρ(\overline{G}, s, t) & = exp[−\frac{d}{ds} \frac{d}{dt}] · \overline{ρ}(G, s, t) = e^{st} · \overline{ρ}(G, −\frac{d}{dt}, −\frac{d}{ds}) · e^{−st}. \end{aligned}

These identities are nothing else but Theorems 3.1 and 3.2 of [13].

Let us continue our walk through the garden of duality theorems.

Duality theorem for the matching polynomials (∫).

\begin{aligned}\overline{μ}(\overline{a_{P} G}, x) & = ∫_{R} e^{−⟨z−x,z−x⟩_{P} /2} · μ(a_{P} G, z) · d_{P} z \\ & = ∑_{n=0}^{∞} \frac{1}{n!} ∫_{R} μ(a_{P} G, z) · μ(x_{P} K_{n}, z) · e^{−⟨z,z⟩_{P} /2} · d_{P} z. \end{aligned}

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

∫_{R} exp[−⟨z − x, z − x⟩_{P} /2] · exp[⟨z, aV ⟩_{P} − a_{P} E] · d_{P} z
= ∫_{R} exp[−⟨s, s⟩_{P} /2] · exp[⟨s + x, aV ⟩_{P} − a_{P} E] · d_{P} s
= exp[⟨x, aV ⟩_{P} + \overline{a_{P} E}] · ∫_{R} exp[−⟨s − aV, s − aV ⟩_{P} /2] · d_{P} s
= exp[⟨x, aV ⟩_{P} + \overline{a_{P} E}] · ∫_{R} exp[−⟨t, t⟩_{P} /2] · d_{P} t
= exp[⟨x, aV ⟩_{P} + \overline{a_{P} E}].

Let us put V := 1, x := z and a := x in Proposition 3.2:

1 + ∑_{n=1}^{∞} μ(x_{P} K_{n}, z)/n! = exp[⟨z, x⟩_{P} − ⟨x, x⟩_{P} /2].

It follows (μ(x_{P} K_{0}, z) := 1):

∫_{R} e^{−⟨z−x,z−x⟩_{P} /2} · μ(a_{P} G, z) · d_{P} z

= ∫_{R} μ(a_{P} G, z) · exp[⟨z, x⟩_{P} − ⟨x, x⟩_{P} /2] · e^{−⟨z,z⟩_{P} /2} · d_{P} z

= ∑_{n=0}^{∞} \frac{1}{n!} ∫_{R} μ(a_{P} G, z) · μ(x_{P} K_{n}, z) · e^{−⟨z,z⟩_{P} /2} · d_{P} z.

Since the space of polynomials is generated (as a vector space) by the matching polynomials, the three preceding theorems imply the following corollary (for the identity μ(x_{P} K_{n}, z) = Φ(z|x, …, x) = :⟨z, x⟩_{P}^{n}: = [⟨z, x⟩_{P}^{n}]^{♯} see Remark 1.1).

Corollary 3.1. Let f(x) be an arbitrary polynomial, then we have for the Bargmann-Segal transform [f(x)]^{♭} = f^{♭}(x) and for the Wick transform [f(x)]^{♯} = f^{♯}(x) the following identities:

f^{♭}(x) = ∑_{n=0}^{∞} \frac{1}{n!} ∫_{R} f(z) · [⟨z, x⟩_{P}^{n} ]^{♯} · e^{−⟨z,z⟩_{P} /2} · d_{P} z

= ∫_{R} e^{−⟨z−x,z−x⟩_{P} /2} · f(z) · d_{P} z
= e^{−⟨x,x⟩_{P} /2} · f(∇_{P}) · e^{⟨x,x⟩_{P} /2}
= exp[△_{P} /2] · f(x),

f^{♯}(x) = e^{⟨x,x⟩_{P} /2} · f(−∇_{P}) · e^{−⟨x,x⟩_{P} /2}
= exp[−△_{P} /2] · f(x).

Example 3.2. Of course, it is not necessary to restrict ourselves to polynomials. Let us put f(x) := \sqrt{det(Q)} · e^{−⟨x,x⟩_{Q}/2}, where ⟨·,·⟩_{Q} is a second form. The preceding corollary allows us to conclude that

[\sqrt{det(Q)} · e^{−⟨x,x⟩_{Q}/2}]^{♭} = \sqrt{det(Q)} · exp[△_{P} /2] · e^{−⟨x,x⟩_{Q}/2}

= \sqrt{det(Q)} · e^{−⟨x,x⟩_{P} /2} · exp[△_{P Q^{−1}P} /2] · e^{⟨x,x⟩_{P} /2}

= \sqrt{det(R)} · e^{−⟨x,x⟩_{R}/2}, R := (P^{−1} + Q^{−1})^{−1}.

Indeed, we have

[\sqrt{det(Q)} · e^{−⟨x,x⟩_{Q}/2}]^{♭}

= \sqrt{det(Q)} · ∫_{R} e^{−⟨z−x,z−x⟩_{P} /2} · e^{−⟨z,z⟩_{Q}/2} · d_{P} z

= \sqrt{det(Q)} · ∫_{R} exp[−⟨z, z⟩_{P +Q}/2 + ⟨z, x⟩_{P} − ⟨x, x⟩_{P} /2] · d_{P} z

= \sqrt{det(Q)} · exp[−⟨x, x⟩_{P −P (P +Q)^{−1}P} /2]·

\sqrt{\frac{det(P)}{det(P +Q)}} ·∫_{R} exp[−⟨z − (P + Q)^{−1}P x, z − (P + Q)^{−1}P x⟩_{P +Q}/2] · d_{P +Q}z

= \sqrt{\frac{det(P) det(Q)}{det(P +Q)}} · exp[−⟨x, x⟩_{P −P (P +Q)^{−1}P} /2] · ∫_{R} exp[−⟨t, t⟩_{P +Q}/2] · d_{P +Q}t

= \sqrt{det(P^{−1} + Q^{−1})^{−1}} · exp[−⟨x, x⟩_{(P^{−1}+Q^{−1})^{−1}}/2],

as P −P (P +Q)^{−1}P = P (P +Q)^{−1}Q = (Q^{−1}(P +Q)P^{−1})^{−1} = (P^{−1} + Q^{−1})^{−1}. The identity \sqrt{det(Q)} · exp[△_{P} /2] · e^{−⟨x,x⟩_{Q}/2} = \sqrt{det(R)} · e^{−⟨x,x⟩_{R}/2} appears in Mehta’s book [16] (see the pages 87–89 there for a different proof).

We remark that polynomials have a decomposition into homogeneous parts, and each homogeneous part is uniquely determined by its values on the ellipsoid S_{P}^{N−1} given by the equation ⟨x, x⟩_{P} = 1 . Let f be homogeneous of degree n, i.e., f(r·ω) = r^{n}·f(ω), ω ∈ S_{P}^{N−1}, and let d_{P} ω be such that d_{P} x = c(N)·r^{N−1}·dr·d_{P} ω and ∫_{S_{P}^{N−1}} d_{P} ω = 1. We have the following corollary.

Corollary 3.2. Let n be even. Then,

N · (N + 2) · (N + 4) ⋯ (N + n − 2) · ∫_{S_{P}^{N−1}} f(ω) · d_{P} ω
= ∫_{ℝ^{N}} f(x) · e^{−⟨x,x⟩_{P} /2} · d_{P} x
= f(∇_{P}) · e^{⟨x,x⟩_{P} /2}|_{x=0}
= exp[△_{P} /2] · f(x)|_{x=0},

and if f(x) = μ(\overline{a_{P} K_{n}}, x), the result is the number \overline{μ}(a_{P} K_{n}, 0) of perfect matchings of a_{P} K_{n}.

The identities of the preceding corollary are easy consequences of the results of the recent article [5] by Folland. However, they are not stated explicitly there. In addition, we have the impression that our proofs are shorter, although Folland has used ideas of Bargmann and Nelson to simplify the proofs of the article [1], which treats the same subject.

Example 3.3. We have

∫_{S^{N−1}}⟨x, α⟩^{2p} · dω = \frac{1 · 3 · 5 · . . . · (2p − 1)}{N(N + 2)(N + 4) … (N + 2p − 2)} · ⟨α, α⟩^{p},

because every perfect matching of the graph αK_{2p} contains p edges (to which we had attached the weight ⟨α, α⟩), and the number of perfect matchings of K_{2p} equals 1 · 3 · 5 ⋯ (2p − 1) (see [19, théorème 3.2 and 3.6]). We also have

∫_{S^{N−1}}⟨x, α_{1}⟩^{2}⟨x, α_{2}⟩^{2} · dω = \frac{⟨α_{1}, α_{1}⟩⟨α_{2}, α_{2}⟩ + 2 · ⟨α_{1}, α_{2}⟩^{2}}{N · (N + 2)} ,

because the complete graph \overline{\overline{α_{1}K_{2}} ⊎ \overline{α_{2}K_{2}}} contains three perfect matchings: two of weight ⟨α_{1}, α_{2}⟩⟨α_{1}, α_{2}⟩ and one of weight ⟨α_{1}, α_{1}⟩⟨α_{2}, α_{2}⟩ (see [19, 6.5]).

Example 3.4. By definition, a polynomial f(x) is harmonic if and only if △_{P} f(x) = 0. Let f(x) be a homogeneous polynomial of degree n > 0 which is harmonic. The preceding corollary allows us to conclude that

N(N + 2) ⋯ (N + n − 2) ∫_{S_{P}^{N−1}} f(ω) · d_{P} ω = exp[△_{P} /2] · f(x)|_{x=0} = f(0) = 0.

Since every polynomial f(x) is harmonic if and only if all its homogeneous components are harmonic, the classical identity

∫_{S_{P}^{N−1}} f(ω) · d_{P} ω = ∫_{S_{P}^{N−1}} f(0) · d_{P} ω = f(0)

for every harmonic polynomial follows immediately.

Let us continue our study of matching polynomials.

Scalar product formula. For two decorated graphs a_{P} G′ = (aV′, a_{P} E′) and b_{P} G′′ = (bV′′, b_{P} E′′) we have

\begin{aligned}\overline{μ}(\overline{a_{P} G′ ⊎ b_{P} G′′}, 0) & = ∫_{R} μ(a_{P} G′, x) · μ(b_{P} G′′, x) · e^{−⟨x,x⟩_{P} /2} · d_{P} x \\ & = \overline{μ}(\overline{a_{P} G′}, ∇_{P}) · \overline{μ}(\overline{b_{P} G′′}, x)|_{x=0}. \end{aligned}

Proof. The first identity is an obvious consequence of the case x = 0 of the preceding theorem. In order to establish the second identity, we use, once again, Taylor’s theorem:

exp[⟨∇_{P} , aV′⟩_{P} + \overline{a_{P} E′}] · exp[⟨x, bV′′⟩_{P} + \overline{b_{P} E′′}]|_{x=0}
= exp[\overline{a_{P} E′}] · exp[⟨x + aV′, bV′′⟩_{P} + \overline{b_{P} E′′}]|_{x=0}
= exp[⟨aV′, bV′′⟩_{P} + \overline{a_{P} E′} + \overline{b_{P} E′′}].

Corollary 3.3. Let f(x) and g(x) be two polynomials and let f^{♭}(x) and g^{♭}(x) be their respective Bargmann-Segal transforms defined with the help of one of the formulae of Corollary 3.1. Then we have

∫_{R} f(x) · g(x) · e^{−⟨x,x⟩_{P} /2} · d_{P} x = f^{♭}(∇_{P}) · g^{♭}(x)|_{x=0}.

The duality theorem (∫) implies

μ(\overline{a_{P} G}, y) = (−i)^{n} · \overline{μ}(\overline{a_{P} G}, yi) = (−i)^{n} · ∫_{R} e^{−⟨x−yi,x−yi⟩_{P} /2} · μ(a_{P} G, x) · d_{P} x.

(|V | = n, i = \sqrt{−1}). This proves the following theorem.

Duality theorem for the matching polynomial (ℂ).

e^{−⟨y,y⟩_{P} /2}μ(\overline{a_{P} G}, y) = (−i)^{n} · ∫_{R} e^{i⟨x,y⟩_{P}} · e^{−⟨x,x⟩_{P} /2}μ(a_{P} G, x) · d_{P} x.

Since the matching function e^{−⟨x,x⟩_{P} /2}μ(a_{P} G, x) has the same parity as n, the last theorem of this section follows.

Duality theorem for the matching polynomial (ℝ).

e^{−⟨y,y⟩_{P} /2}μ(\overline{a_{P} G}, y) · (−1)^{n/2}
= ∫_{R} cos⟨x, y⟩_{P} · e^{−⟨x,x⟩_{P} /2}μ(a_{P} G, x) · d_{P} x, n even,

e^{−⟨y,y⟩_{P} /2}μ(\overline{a_{P} G}, y) · (−1)^{(n−1)/2}
= ∫_{R} sin⟨x, y⟩_{P} · e^{−⟨x,x⟩_{P} /2}μ(a_{P} G, x) · d_{P} x, n odd.

In other words, the matching functions of \overline{a_{P} G} and of a_{P} G are, up to sign, real Fourier transforms of each other.

Remark 3.1. Since all our duality theorems rely just on the fundamental lemma a_{P} E + \overline{a_{P} E} = ⟨aV, aV ⟩_{P} /2, it is natural to associate to each \{u, v\} ∈ \binom{V}{2} two scalar products Q(\{u, v\}) and \overline{Q}(\{u, v\}) such that

⟨a_{u}, a_{v}⟩_{Q(\{u,v\})} + ⟨a_{u}, a_{v}⟩_{\overline{Q}(\{u,v\})} = ⟨a_{u}, a_{v}⟩_{P} ,

or just two numbers q(\{u, v\}) and \overline{q}(\{u, v\}) such that q(\{u, v\}) + \overline{q}(\{u, v\}) = ⟨a_{u}, a_{v}⟩_{P} . We have preferred the classical context of the complementary graph because it is sufficient for most applications.

Another way to extend our results consists in replacing the real coefficients of our vectors a_{v}, v ∈ V, by complex coefficients, for example. Moreover, complex coefficients are admissible for the matrix P under the condition that it remains symmetric. In other words, we can have P = R + i · Q (i = \sqrt{−1}) with real symmetric matrices R and Q. In this manner, we can see that the two identities of the duality theorems ∇ and △ can be reduced to each other by replacing P by −P. In order to guarantee the convergence of the (real!) integrals, it is, however, indispensable that ℜe P = R > 0, i.e., the matrix R must correspond to a scalar product.

4. The zeroes of μ(a_{p}G, x)

Let us admit weights w_{uv} ∈ ℝ\{0} (in [9], the condition w_{uv} > 0 was imposed) for every edge {u, v} ∈ E, such that it contributes the factor w_{uv}⟨a_{u}, a_{v}⟩_{P} (as an edge of a matching) instead of ⟨a_{u}, a_{v}⟩_{P}, and let us denote by a_{P} G_{w} = (aV, a_{P} E_{w}) the graph with these weights.

Let div[μ(a_{p}G_{w}, x)] ∈ Div(R) be the (effective) divisor of μ(a_{P} G_{w}, x), but we consider it in the projective space ℙR (= ℙ^{N}(ℝ); unless we consider it even in ℙ^{N}(ℂ)). The generating function of the homogenized matching polynomials μ(a_{P} G_{w}, x, x_{0}) can be written in the form

1 + ∑_{∅⊂V′⊆V} μ(a_{P} G_{w}[V′], x, x_{0}) · v^{V′} = exp[⟨x, aV ⟩_{P} − x_{0}^{2}a_{P} E_{w}].

In the so-called improper hyperplane x_{0} = 0, we have

μ(a_{P} G_{w}, x, 0) = 0  ⇔  ∏_{v∈V} ⟨x, a_{v}⟩_{P} = 0.

Since μ(a_{P} G_{w}, x, x_{0}) is linear in every a_{v}, v ∈ V, we can (and we will) suppose for a moment (without changing div[μ(a_{P} G_{w}, x, x_{0})]) that ⟨a_{v}, a_{v}⟩_{P} = 1 for every v ∈ V (if there exists a v ∈ V with a_{v} = 0, then μ(a_{P} G_{w}, x, x_{0}) ≡ 0) and that there is no u ≠ v with a_{u} = −a_{v} (we could consider the a_{v}’s, v ∈ V, as points of ℙ^{N−1}(ℝ)). Let

A = {a_{v}|v ∈ V }, and let V = ⨄_{a∈A} V_{a}

such that, for every a ∈ A, we have a_{v} = a for each v ∈ V_{a}. Then,

div[μ(a_{P} G_{w}, x, 0)] = ∑_{a∈A} |V_{a}| · V (⟨x, a⟩_{P}).

Let a^{∗} ∈ A, and let us consider x^{∗} ∈ R\{0} such that ⟨x^{∗}, a^{∗}⟩_{P} = 0 and ⟨x^{∗}, a⟩_{P} ≠ 0 for each a ∈ A\a^{∗}. The Taylor expansion of μ(a_{P} G_{w}, x, x_{0}) at (x^{∗}, 0) up to the order |V_{a^{∗}}| can be written in the form

μ(a_{P} G_{w}[V_{a^{∗}}], x, x_{0}) · ∏_{v∉V_{a^{∗}}}⟨x^{∗}, a_{v}⟩_{P} .

This implies the following theorem.

Theorem 4.1. If, for every a ∈ A, the one dimensional matching polynomial μ(G_{w}[V_{a}], x) has |V_{a}| different real zeroes (for example, because all weights of the edges of the graph G_{w}[V_{a}] are positive and G_{w}[V_{a}] contains a Hamiltonian path, see [9], Theorem 4.2), and if V_{i} ⊂ R are the (irreducible) components of div[μ(a_{P} G_{w}, x)], then

∑_{i} deg(V_{i}) = deg[μ(a_{P} G_{w}, x)] = |V |.

Remark 4.1. It is not possible to extend this theorem by continuity as in one dimension, because (ℝ is closed in ℂ but) R is not closed in ℙR. More subtle conditions can be obtained by continuing the Taylor expansion (see the very last theorem of [12]), but it seems preferable to present them in a different context.

Theorem 4.2. Every zero of μ(a_{P} G_{w}, x) is close to at least one hyperplane V (⟨x, a_{v}⟩_{P}), v ∈ V. More precisely, let |a_{P} G_{w}| be the graph obtained by replacing all weights w_{uv}⟨a_{u}, a_{v}⟩_{P} of the edges {u, v} by |w_{uv}⟨a_{u}, a_{v}⟩_{P} |, let B be bigger than all zeroes of the one dimensional matching polynomial μ(|a_{P} G_{w}|, x) (see [9], Theorem 4.3, for good estimations of B), and suppose that |⟨x, a_{v}⟩_{P} | ≥ B for every v ∈ V. Then, for each v ∈ V′ ⊆ V, we have

|\frac{μ(a_{P} G_{w}[V′], x)}{μ(a_{P} G_{w}[V′\v], x)}| ≥ \frac{μ(|a_{P} G_{w}[V′]|, B)}{μ(|a_{P} G_{w}[V′\v]|, B)}

and, in particular, μ(a_{P} G_{w}[V′], x) ≠ 0.

Proof. The proof (by induction) is the same as that of Theorem 4.5 in [9].

Since affine regular polygons do not enjoy such a great popularity, we will put (without loss of generality!) P = Id (and N = 2) for a moment. Let w : ℤ/nℤ → ℝ be such that w(k) = w(−k) for every k ∈ ℤ/nℤ, w(0) = 0, and let G_{w} = (ℤ/nℤ, E_{w}) be the graph with {i, j} ∈ E_{w} if and only if w(i − j) ≠ 0, and, in that case, w_{ij} := w(i − j), i, j ∈ ℤ/nℤ. If we denote by aG_{w} the decoration of G_{w} given by

a_{k} := \binom{x_{k}}{y_{k}} = \binom{cos(k · 2π/n)}{sin(k · 2π/n)},

for every k ∈ ℤ/nℤ, then we have the following surprise.

Proposition 4.1. We have

μ(aG_{w}, x, y) = ∏_{k=0}^{n−1} ⟨\binom{x}{y}, a_{k}⟩, if n is odd.

Proof. We have indeed

\begin{aligned}μ(aG_{w}, 0, y) & = − ∑_{\{k,0\}∈E_{w}} w(k) · ⟨a_{k}, a_{0}⟩ · μ(aG_{w}\\{k, 0\}, 0, y) \\ & = 0, \end{aligned}

since the symmetry k ⟷ −k preserves w_{ij}⟨a_{i}, a_{j}⟩ and changes the sign of ⟨\binom{0}{y}, a_{k}⟩, and since the number of those last expressions is odd for every matching. It follows that μ(aG_{w}, x, y) = x · p(x, y), and, by symmetry, μ(aG_{w}, x, y) = ∏_{k=0}^{n−1}⟨\binom{x}{y}, a_{k}⟩·q(x, y). The proof is completed by comparing the terms of degree n.

If n is even, the situation becomes more complicated (because a_{k} = −a_{k+n/2}). We restrict ourselves to the case where there is just a single (d, −d) ≠ (0, 0) with w := w(d) = w(−d) ≠ 0. In that case, aG_{w} is the disjoint union of gcd(n, d) cycles, and μ(aG_{w}, x, y) is the product of their matching polynomials. Therefore we obtain a more readable result if we suppose gcd(n, d) = 1.

Proposition 4.2. Let n be even, n > 2, and gcd(n, d) = 1. Then

\begin{aligned}μ(aG_{w}, x, y) & = ∏_{k=0}^{n−1} ⟨\binom{x}{y}, a_{k}⟩ + 2 · (−w · ⟨a_{d}, a_{0}⟩)^{n/2} \\ & = (−1)^{n/2}[ ∏_{k=0}^{n/2−1} ⟨\binom{x}{y}, a_{k}⟩^{2} + 2 · [w · cos(d · 2π/n)]^{n/2}]. \end{aligned}

Proof. As in the preceding proof, we use a sign-reversing involution. We have

\begin{aligned}μ(aG_{w}, 0, y) & = −w · ⟨a_{d}, a_{0}⟩ · [μ(aG_{w}\\{d, 0\}, 0, y) + μ(aG_{w}\\{−d, 0\}, 0, y)] \\ & = 2 · (−w · ⟨a_{d}, a_{0}⟩)^{n/2}. \end{aligned}

Indeed, let us consider a matching of the cycle aG_{w}, and let us walk, starting from 0, in both directions of aG_{w} (at the same time and with the same speed!) until there will be the first vertex not covered by the matching, and let us apply the symmetry k ⟷ −k for all vertices visited so far. Since there is just a single expression of the type ⟨\binom{0}{y}, a_{k}⟩ (for the uncovered vertex), the sign changes, and, finally, there will just remain the contributions of the two perfect matchings of aG_{w}. It follows that μ(aG_{w}, x, y)−2·(−w·⟨a_{d}, a_{0}⟩)^{n/2} = x·p(x, y). The symmetry μ(aG_{w}, −x, y) = μ(aG_{w}, x, y) implies p(−x, y) = −p(x, y), i.e. p(x, y) = x · q(x, y); and, once again, by symmetry, we obtain

μ(aG_{w}, x, y) − 2 · (−w · ⟨a_{d}, a_{0}⟩)^{n/2} = ∏_{k=0}^{n/2−1} ⟨\binom{x}{y}, a_{k}⟩^{2} · r(x, y).

The proof is completed by comparing the terms of degree n.

The main reason for having considered the preceding propositions is the following highly surprising corollary.

Corollary 4.1. For every N > 1 and every P there exist ordinary (i.e., without weights) decorated graphs a_{P} G (rarissime!) such that μ(a_{P} G, x) ≠ 0 for every x ∈ R.

Acknowledgements. First of all, my cordial thanks go to P. Cartier for his captivating introduction to the fascinating world of physics, delivered to me on a pleasant evening at the Domaine Saint-Jacques, without which the N-dimensional matching polynomial would not have seen the light of the day. I also express my gratitude to S. Eliahou for having improved the clarity of two key definitions, to G. Nebe and W. Plesken for having invited B. Venkov ([19] being the second motivation for the N dimensions), to A. Lascoux and V. A. Malyshev for their wonderful presents [16] and [15], and particularly to D. Foata for all his help and assistance. Last but not least I am indebted to C. Krattenthaler for his indispensable help with the English translation.

References

[1] J. A. Baker, Integration over spheres and the divergence theorem for balls, American Math. Monthly 104 (1997), 36-47.

[2] P. Cartier, Personal communication, Séminaire Lotharingien de Combinatoire 44, 2000.

[3] P. Cartier, Mathemagics (A Tribute to L. Euler and R. Feynman), Séminaire Lotharingien de Combinatoire B44d, 71 pages, 2000.

[4] D. Foata and A. Fuchs, “Calcul des Probabilités”, Dunod, Paris, 1998.

[5] G. F. Folland, How to integrate a polynomial over a sphere, American Math. Monthly 108 (2001), 446-448.

[6] J. Glimm and A. Jaffe, “Quantum Physics, A Functional Integral Point of View”, Springer-Verlag, 1981.

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

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

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

[10] S. K. Lando, On primitive elements in the bialgebra of chord diagrams, in: Topics in Singularity Theory, V. I. Arnold’s 60th Anniversary Collection (A. Khovanskij, A. Varchenko, V. Vassiliev, editors), AMS Transl. Ser. 2 Vol. 180, Advances in the Mathematical Sciences 34 (1997), 167-174.

[11] S. K. Lando and A. K. Zvonkin, “Graphs on Surfaces and Their Applications”, Encyclopaedia of Mathematical Sciences, Volume 141, Low-Dimensional Topology II (R. Gamkrelidze, V. Vassiliev, editors), Springer, 2004.

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

[13] B. Lass, Variations sur le thème E+\overline{E} = XY, Advances in Applied Mathematics 29 (2002), 215-242.

[14] L. Lovász, “Combinatorial Problems and Exercises”, Akadémiai Kiadó, 1993.

[15] V. A. Malyshev and R. A. Minlos, “Gibbsovskie sluchajnye polja, Metod klasternykh razlozhenij”, Nauka, Moskva, 1985; English version: “Gibbs Random Fields, Cluster Expansions”, Kluwer Academic Publishers, 1991.

[16] M. L. Mehta, “Matrix Theory, Selected Topics and Useful Results”, Les Éditions de Physique, 1989.

[17] A. N. Shiryaev, “Verojatnost’”, Hauka, Moskva, 1980.

[18] R. P. Stanley, “Enumerative Combinatorics”, Volume 1, Cambridge University Press, Cambridge, 1997.

[19] B. Venkov, Réseaux et designs sphériques, in: Réseaux euclidiens, designs sphériques et formes modulaires (J. Martinet, éditeur), L’Enseignement Mathématique, Monographie no. 37, 2001, 10-86.