\documentclass[11pt, a4paper]{article}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\setlength{\textwidth}{6.3in} \setlength{\textheight}{8.7in}
\setlength{\topmargin}{0pt} \setlength{\headsep}{0pt}
\setlength{\headheight}{0pt} \setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{theorem}{Th\'eor\`eme}%[section]
\newtheorem{thm}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{prop}{Proposition}
\newtheorem{corollary}{Corollaire}%[section]
\newtheorem{coro}{Corollary}%[section]
\newtheorem{lemma}{Lemma}%[section]
\newtheorem{fact}{Fact}%[section]
\newtheorem{definition}{D\'efinition}%[section]
\newtheorem{example}{Example}
\newcommand\cyc{\mathop{\rm cyc}}
%\newenvironment{proof}{{\em Proof.}}{\mbox{}\hfill $\Box$\medskip}
%\newenvironment{example}{\smallskip\noindent{\bf Exemple. }}{\smallskip}
\newenvironment{remark}{\smallskip\noindent{\bf Remark.}}{\smallskip}
%binomial coefficients:\bi{#1}{#2}
\newcommand\bi[2]{{{#1}\atopwithdelims(){#2}}}
%q-binomial coefficients:\qbi{#1}{#2}{#3}
\newcommand\qbi[3]{{{#1}\atopwithdelims[]{#2}}_{#3}}
\pagestyle{plain}
\newtheorem*{theo}{Th\'eor\`eme}
\newtheorem{conj}{Conjecture}
\newtheorem{lem}{Lemme}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\catcode`\@=11
\def\Eqalign #1{\null\,\vcenter{\openup\jot\m@th\ialign{
\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
&&\quad\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$
\hfil\crcr #1\crcr}}\,}
\catcode`\@=12
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\numberwithin{equation}{section}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\refname{References}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\title{Mehler Formulae for Matching Polynomials of Graphs and Independence Polynomials of Clawfree Graphs}
\author{Bodo Lass\\
\small Universit\'e de Lyon ; Universit\'e Lyon 1 ; \\[-0.8ex]
\small INSA de Lyon, F-69621 ; Ecole Centrale de Lyon ; \\[-0.8ex]
\small CNRS, UMR5208, Institut Camille Jordan, \\[-0.8ex]
\small 43 blvd du 11 novembre 1918, \\[-0.8ex]
\small F-69622 Villeurbanne-Cedex, France \\[-0.8ex]
\small \texttt{lass} @ \texttt{math.univ-lyon1.fr}\\[-0.8ex]
}
\date{}
%\small 2000 Mathematics Subject Classification : 05A10, 33C20}

\maketitle

\centerline{\emph{\`A Dominique Foata, pour son 75-i\`eme anniversaire}}
\bigskip

\begin{abstract}
The \emph{independence polynomial} of a graph~$G$ is the polynomial
$\sum_{I} x^{|I|}$, summed over all independent subsets $I \subseteq 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~\cite{L1} and extends the combinatorial proof of the Mehler formula 
found by Foata~\cite{F}. It implies immediately that all the roots
of the independence polynomial of a clawfree graph are real, answering
a question posed by Hamidoune~\cite{H} and Stanley~\cite{S} and solved
by Chudnovsky and Seymour~\cite{CS}. We also prove a Mehler formula
for the multivariate matching polynomial, extending results of ~\cite{L1}.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{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 \emph{$r$-matching} in~$G$ is a set of $r$ edges of $G$, no two of which have a vertex in common. 
Clearly, $r \le {\lfloor n/2 \rfloor}$. Let $m_r(G)$ be the number of $r$-matchings in $G$, with 
the convention that $m_0(G) := 1.$ The \emph{matching polynomial} of $G$ is (see~\cite{Go2} or \cite{Go1}, 
chapter 1) 
\begin{equation}
M_G(x) \; := \; \sum_{r=0}^{\lfloor n/2 \rfloor} (-1)^r m_r(G) x^{n-2r}. \label{eq:class}
\end{equation}
These polynomials were introduced by Heilmann and Lieb~\cite{HL}, 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~\cite{Go1} 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~\cite{L1} 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 \emph{complete graph} 
and denoted by $G = K_n$, where $n = |V|$. Its matching polynomial $M_{K_n}(x)$ is the classical 
\emph{Hermite polynomial}. For those Hermite polynomials the famous \emph{Mehler formula} affirms that
\begin{equation*} 
1+\sum_{n=1}^{\infty} M_{K_n}(x) M_{K_n}(y) \cdot z^n/n! \; = \; 
\end{equation*}
\begin{equation}
\frac{1}{\sqrt{1-z^2}} \, \cdot \, 
\exp \left[ \left(\frac{x+y}{2}\right)^2 \cdot \frac{z}{1+z} - 
            \left(\frac{x-y}{2}\right)^2 \cdot \frac{z}{1-z} \right].
\end{equation}
Foata~\cite{F} 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~\cite{L1} we generalized the combinatorial proof found by Foata~\cite{F} 
to matching polynomials. Therefore, it seems natural to call our generalization a 
\emph{Mehler formula for matching polynomials}. We showed that it immediately 
implies that 
\begin{equation}
|M_G(x)|^2 \; \ge \; \left[(\Im m \; x)^2\right]^n + 2|E| \cdot \left[(\Im m \; x)^2\right]^{n-1}
\end{equation}
for every $x \in {\mathbb C}$, 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~\cite{L3, L4}. 

An \emph{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 $\alpha$ is the \emph{maximum number of independent points} of~$G$, then its \emph{independence polynomial} 
is the polynomial
\begin{equation}
I_G(x) \; := \; \sum_{r=0}^{\alpha} i_r(G) \cdot x^r \; = \; \sum_I x^{|I|},
\end{equation}  
where the sum is over all independent subsets $I \subseteq V$ (see for instance 
\cite{BN1, BN2, BDN, BHN, FS, Gu1, Gu2, HLi, L2, LR, LM, QDW} for work on these
polynomials). A \emph{claw} is the graph with vertex set $\{A,B,C,D\}$
and three edges $AB$, $AC$, $AD$, and its independence polynomial is
\begin{equation}
1 + 4x + 3x^2 + x^3.
\end{equation}
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 \emph{clawfree} if no induced subgraph of it is a claw. It was 
conjectured  by Hamidoune~\cite{H} and Stanley~\cite{S} and proved by
Chudnovsky and Seymour~\cite{CS} that all the roots of $I_G(x)$ are real
(and of course negative) if $G$ is clawfree. 

Given a graph~$G$, its \emph{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:
\begin{equation}
M_G(x) \; = \; x^n \cdot I_{L(G)}(-1/x^2),
\end{equation}
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~\cite{CS} 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
\begin{equation}
|I_G(x^2)|^2  \; \ge \; i_{\alpha}(G) \cdot \left[4(\Re e \; x)^2\right]^{\alpha}, \qquad
|I_G(-x^2)|^2 \; \ge \; i_{\alpha}(G) \cdot \left[4(\Im m \; x)^2\right]^{\alpha}
\end{equation}
for every $x \in {\mathbb C}$. It follows that all the roots of $I_G(x)$ are real and negative,
if $G$ is clawfree.

\bigskip

If $w$ is a real-valued function on the vertex set of the graph~$G$, 
then the \emph{weighted independence polynomial} is 
\begin{equation}
I_{G,w}(x) \; := \; \sum_I \ \prod_{v \in I} [x \cdot w(v)],
\end{equation}  
where the sum is over all independent subsets $I \subseteq V$ (if $I$ is empty, 
then the product is~$1$ by definition). Engstr\"om~\cite{E} 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 \in 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\"om~\cite{E} 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 \emph{positive} vertex weights,
one must also talk about matching polynomials with \emph{positive} edge weights,
and this is what we did already in the last section of~\cite{L1}. However, for 
matching polynomials it is not only possible to introduce positive edge weights, 
but one can also introduce additional \emph{complex vertex} weights and still get 
nice results, notably the Heilmann-Lieb theorem~\cite{HL}. 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.

\bigskip

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 \emph{"multivariate ideology"} has borne great fruit in the study of the Tutte polynomial~\cite{JS}. 
Some early examples of what can be gained by the multivariate approach to the independence polynomial 
can be found in~\cite{SS1,SS2}: notably the connection to the Lov\'asz local lemma and a simple inductive 
proof for a zero-free polydisc. Another example concerns the two simple proofs found by~\cite{COSW} of the 
multivariate Heilmann-Lieb theorem~\cite{HL}. 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~\cite{COSW} 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~\cite{F} 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.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{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 \cdot y^s$ is assigned. A natural choice is certainly the subgraph~$PCC$ of~$G$
induced by the union of our two independent sets ($PCC$ 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 $PCC$, as do the vertices labeled $y$ or $xy$; 
in particular, the vertices labeled $xy$ must be isolated vertices of~$PCC$. 
Any edge of~$PCC$ must join a vertex labeled~$x$ with a vertex labeled~$y$: 
$PCC$ is a bipartite graph. Moreover, \emph{the degree of each vertex of~$PCC$
is at most two since $G$ is clawfree} and $PCC$ is an induced subgraph. 
Therefore $PCC$ is an induced subgraph of~$G$ that is a disjoint union 
of some isolated vertices~$IV(PCC)$ labeled~$xy$, some even cycles~$EC(PCC)$ 
(of length at least~$4$) labeled alternately with~$x$ and~$y$, some even paths~$EP(PCC)$ 
(with at least two vertices) labeled alternately with~$x$ and~$y$, and, last but not least, 
some odd paths~$OP(PCC)$ (with at least one vertex) labeled alternately with~$x$ and~$y$.
We want to consider $PCC$ not only as an induced subgraph, but as an
\emph{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(PCC)$ and $OP(PCC)$ are well-defined.
The same $PCC$ appears several times in the product $I_G(x) I_G(y)$.
Indeed, $IV(PCC)$ is fixed once $PCC$ is fixed, but the variables~$x$ and~$y$ 
can still be exchanged on each path and cycle of $PCC$. Therefore $PCC$ must 
be counted with the weight
\begin{equation*}
\prod_{IV(PCC)} \left[ xy \right]
\prod_{EC(PCC)} \left[ 2 \cdot x^{|EC(PCC)|/2} y^{|EC(PCC)|/2} \right]
\prod_{EP(PCC)} \left[ 2 \cdot x^{|EP(PCC)|/2} y^{|EP(PCC)|/2} \right]
\end{equation*}
\begin{equation}
\prod_{OP(PCC)} \left[ x^{(|OP(PCC)|+1)/2} y^{(|OP(PCC)|-1)/2} + x^{(|OP(PCC)|-1)/2} y^{(|OP(PCC)|+1)/2} \right],
\end{equation}
where $|EC(PCC)|$, $|EP(PCC)|$ and $|OP(PCC)|$ denote the number of vertices of the respective cycle or path.
Note that products over empty sets are always~$1$ by definition. In particular, $PCC$ 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$.

\begin{thm} We have
\begin{eqnarray}
I_G(x) I_G(y) 
&=& \sum_{PCC} \Biggl( 
    \prod_{IV(PCC)} \left[ xy \right]
    \prod_{EC(PCC)} \left[ 2 \cdot (xy)^{|EC(PCC)|/2} \right] 
    \prod_{EP(PCC)} \left[ 2 \cdot (xy)^{|EP(PCC)|/2} \right] \nonumber\\
&&  \prod_{OP(PCC)} \left[ (x+y) \cdot (xy)^{(|OP(PCC)|-1)/2} \right] \Biggr).\qed 
\end{eqnarray}
\end{thm}

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 
\begin{equation}
e_1 \; := \; x+y, \qquad e_2 \; := \; xy
\end{equation}
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
\begin{eqnarray}
P_G(e_1,e_2)
&=& \sum_{PCC} \Biggl(
    \prod_{IV(PCC)} \left[ e_2^2 \right]
    \prod_{EC(PCC)} \left[ 2e_2^{|EC(PCC)|} \right] 
    \prod_{EP(PCC)} \left[ 2e_2^{|EP(PCC)|} \right] \nonumber\\
&&  \prod_{OP(PCC)} \left[ e_1^2e_2^{|OP(PCC)|-1} - 2e_2^{|OP(PCC)|} \right] \Biggr) \label{eq:fact} \\
&=& \sum_{OPC} \left[ \prod_{OP(OPC)} e_1^2e_2^{|OP(OPC)|-1} \right] \cdot P_{G \backslash [OPC \cup \Gamma(OPC)]}(0,e_2), 
\end{eqnarray}
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~(\ref{eq:fact}) by distributivity, $OPC$ corresponds to the odd paths for which we have chosen the term 
$e_1^2e_2^{|OP(PCC)|-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^2e_2^{|OP(PCC)|-1}$), where $H = G \backslash [OPC \cup \Gamma(OPC)]$ 
is the subgraph of~$G$ induced by all vertices of $G \backslash OPC$ which are not adjacent to any vertex of~$OPC$.
We remove $\Gamma(OPC)$ (vertices adjacent to at least one vertex of~$OPC$) because $PCC$ is an \emph{induced} 
subgraph. Note that  $P_H(0,e_2) = 1$ if $H$ is the empty graph.

\begin{lemma} For any graph~$G$, we have
\begin{equation}
P_G(0,e_2) \; = \; I_G((i\sqrt{xy})^2) I_G((-i\sqrt{xy})^2) \; = \; I_G(-e_2)^2.
\end{equation}
\end{lemma}

\begin{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.
\end{proof}

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

\begin{thm} We have
\begin{equation}
I_G(x^2) I_G(y^2) \; = \; 
\sum_{OPC} \left[ \prod_{OP(OPC)} e_1^2e_2^{|OP(OPC)|-1} \right] \cdot 
I_{G \backslash [OPC \cup \Gamma(OPC)]}(-e_2)^2,
\end{equation}
where $e_1 = x+y$ and $e_2 = xy$.\qed
\end{thm}

\begin{coro} Let $G$ be a clawfree graph with $i_{\alpha}(G)$ maximal independent sets. Then
\begin{equation}
|I_G(x^2)|^2  \; \ge \; i_{\alpha}(G) \cdot \left[4(\Re e \; x)^2\right]^{\alpha}, \qquad
|I_G(-x^2)|^2 \; \ge \; i_{\alpha}(G) \cdot \left[4(\Im m \; x)^2\right]^{\alpha}
\end{equation}
for every $x \in {\mathbb C}$. In particular, all the roots of $I_G(x)$ are real and negative.
\end{coro}  

\begin{proof}
If we replace $y$ by $\overline{x}$, then $e_1^2 = 4(\Re e \; x)^2 \ge 0$ and $e_2 = |x|^2 \ge 0$.
Therefore, every term of the sum
\begin{equation*}
|I_G(x^2)|^2 \; = \; I_G(x^2) I_G(\overline{x}^2) \; = \;
\end{equation*}
\begin{equation}
\sum_{OPC} \left[ \prod_{OP(OPC)} e_1^2e_2^{|OP(OPC)|-1} \right] \cdot 
I_{G \backslash [OPC \cup \Gamma(OPC)]}(-e_2)^2
\end{equation}
is nonnegative. In particular, each of the $i_{\alpha}(G)$ maximal independent sets of~$G$ 
is an odd-path-configuration with $\alpha$~paths of length~$1$ and contributes to the sum 
$[e_1^2e_2^0]^{\alpha} = [4(\Re e \; x)^2]^{\alpha}$, 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 \cdot x$.

Finally, if $z$ is a complex number that is neither a real negative number nor zero, 
then there exists $x \in {\mathbb C}$ such that $z = x^2$ and $\Re e \; x > 0$. 
Therefore, 
\begin{equation}
|I_G(z)|^2  \; = \; |I_G(x^2)|^2  \; \ge \; i_{\alpha}(G) \cdot \left[4(\Re e \; x)^2\right]^{\alpha} \; > \; 0.
\end{equation}
In other words, $I_G(z)$ can be zero only if $z$ is a real negative number, because $I_G(0) = 1$.
\end{proof}

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
\begin{equation}
I_{G,w}(x) \; = \; 1 \, + \,  x \cdot a \, + \, x \cdot b \, + \,  x \cdot c \, + \,  x^2 \cdot bc.
\end{equation}
An easy multiplication gives the following formula:
\begin{eqnarray}
I_{G,w}(x) I_{G,w}(y) 
&=& 1 \, + \, (x+y) \cdot a \, + \, (x+y) \cdot b \, + \, (x+y) \cdot c \, + \, 2xy \cdot ab \, + \, 2xy \cdot ac \nonumber\\
& & + \, (x+y)^2 \cdot bc \, + \, (x+y)xy \cdot abc \, + \, xy \cdot a^2 \, + \, xy \cdot b^2 \, + \, xy \cdot c^2 \nonumber\\
& & + \, xy(x+y) \cdot b^2 c \, + \, xy(x+y) \cdot c^2 b \, + \, (xy)^2 \cdot b^2 c^2. 
\end{eqnarray}
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
\begin{eqnarray}
I_{G,w}(x^2) I_{G,w}(y^2)
&=& 1 \, - \, 2e_2 \cdot a \, - \, 2e_2 \cdot b \, - \, 2e_2 \cdot c \, + \, 2e_2^2 \cdot ab \, + \, 2e_2^2 \cdot ac \nonumber\\
& & + \, 4e_2^2 \cdot bc \, - \, 2e_2^3 \cdot abc \, + \, e_2^2 \cdot a^2 \, + \, e_2^2 \cdot b^2 \, + \, e_2^2 \cdot c^2 \nonumber\\
& & - \, 2e_2^3 \cdot b^2 c \, - \, 2e_2^3 \cdot c^2 b \, + \, e_2^4 \cdot b^2 c^2 \nonumber \\
& & + \, e_1^2 \cdot b \, \cdot \, \left[ 1 \, - \, 2e_2 \cdot c \, + \, e_2^2 \cdot c^2 \right] \,
    + \, e_1^2 \cdot c \, \cdot \, \left[ 1 \, - \, 2e_2 \cdot b \, + \, e_2^2 \cdot b^2 \right] \nonumber\\
& & + \, e_1^2 \cdot a \, + \, e_1^2e_2^2 \cdot abc \, + \, e_1^4 \cdot bc \\
&=& \left[ 1 \, - \,  e_2 \cdot a \, - \, e_2 \cdot b \, - \,  e_2 \cdot c \, + \,  e_2^2 \cdot bc \right]^2 \nonumber\\
& & + \, e_1^2 \cdot b \, \cdot \, \left[ 1 \, - \, e_2 \cdot c \right]^2 \,
    + \, e_1^2 \cdot c \, \cdot \, \left[ 1 \, - \, e_2 \cdot b \right]^2 \nonumber\\
& & + \, e_1^2 \cdot a \, + \, e_1^2e_2^2 \cdot abc \, + \, e_1^4 \cdot bc. 
\end{eqnarray}
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 \cdot a - e_2 \cdot b - e_2 \cdot c + e_2^2 \cdot 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~\cite{E}):
they just make the notations slightly more complicated, but the proofs and theorems remain the same.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Mehler Formulae for Multivariate Matching Polynomials}

To state and derive our extension of the Mehler formula for matching polynomials~\cite{L1}
to allow not only nonnegative real edge weights but also \emph{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~\cite{L} 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~\cite{L1,L2,L3,L4}.

\subsection{Algebraic Preliminaries}

Let $V$ be a finite set, and let $A$ be a commutative ring with identity element.
Let $\mathcal{F}(2^V,A)$ be the $A$-algebra of functions $f: 2^V \to A$, equipped
with the multiplication 
\begin{equation} 
(fg)(W) \; = \; \sum_{W_1 \uplus W_2 = W} f(W_1) g(W_2)
\end{equation} 
(where $\uplus$ denotes disjoint union) and the obvious pointwise addition and 
scalar multiplication. 

\bigskip

\noindent
Next let $A[V]$ be the $A$-algebra of multiaffine (= square-free) polynomials
\begin{equation} 
F(\nu) \; = \; \sum_{W \subseteq V} a_W \nu^W
\end{equation} 
in indeterminates $\nu = (\nu_v)_{v \in V}$, where we use the shorthand notation
\begin{equation} 
\nu^W \; = \; \prod_{v \in W} \nu_v, \qquad \nu^{\emptyset} \; := \; 1.
\end{equation} 
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 $\nu^W$ for some $W \subseteq V$), that is
\begin{equation} 
\left( \sum_{W \subseteq V} a_W \nu^W \right) \cdot \left( \sum_{W \subseteq V} b_W \nu^W \right)
\; = \; \sum_{W \subseteq V} \sum_{W_1 \uplus W_2 = W} a_{W_1} b_{W_2} \nu^W,
\end{equation}
together with the usual addition and scalar multiplication. Note that $A[V]$ is isomorphic 
in an obvious way to the quotient algebra $A[\{\nu_v\}]/\langle\{\nu_v^2\}\rangle$.

\begin{remark}
In a more combinatorial way (see~\cite{L1,L2,L3,L4}), we could have defined the multiplication of monomials 
for all $W_1, W_2 \subseteq V$ by
\begin{equation} 
\nu^{W_1} \cdot \nu^{W_2} \; := \; \nu^{W_1+W_2}, \; \hbox{where}
\end{equation}
\begin{equation} 
W_1+W_2 \; :=  \;
\left\{ \begin{array}{cl}
W_1 \cup W_2, & \hbox{if \, $W_1 \cap W_2 =   \emptyset$,} \\
\dag,         & \hbox{if \, $W_1 \cap W_2 \ne \emptyset$, \, where}
\end{array} \right.
\end{equation}
\begin{equation} 
\dag + W \; := \; \dag, \quad \dag + \dag \; := \; \dag, \qquad \hbox{and} \qquad \nu^{\dag} \; := \; 0. 
\end{equation} 
Here $\dag$ corresponds to multisets that are systematically discarded.
\end{remark}

\bigskip

\noindent
Finally, the map $f \mapsto F_f$ that associates to each $f \in \mathcal{F}(2^V,A)$ its
generating polynomial $F_f \in A[V]$, i.e.
\begin{equation}
F_f(\nu) \; = \; \sum_{W \subseteq V} f(W) \nu^{W},
\end{equation}
is manifestly an algebra isomorphism of $\mathcal{F}(2^V,A)$ onto $A[V]$.
Many applications of $A[V]$ in different parts of enumerative graph theory
can be found in~\cite{L1}, \cite{L2}, \cite{L3} and \cite{L4}. 
See~\cite{COSW}, Section 4.7, for further results on the "multiaffine part" operator, 
and see~\cite{COSW}, Remark 4 after Theorem 10.1, for a simple proof of the multivariate
Heilmann-Lieb theorem for matching polynomials that is based on it.

\bigskip

For $|V| = \infty$ let $(2^V)_{\text{fin}}$ be the partially ordered set of finite subsets of $V$. 
We have the canonical projections $p_{W_1,W_2}: A[W_1] \to A[W_2]$ ($W_1,W_2 \in (2^V)_{\text{fin}}, 
W_1 \supseteq W_2$) and define 
\begin{equation} 
A[V] \; := \; \lim_{\longleftarrow} A[W], \quad W \in (2^V)_{\text{fin}}
\end{equation} 
with the help of the projective limit. This means nothing else 
than working with generating functions of the form 
\begin{equation} 
F(\nu) \; = \; \sum_{W \in (2^V)_{\text{fin}}} a_W \nu^W. 
\end{equation} 

\bigskip

\noindent
Now for any $V$ (finite or infinite), we consider the particular element 
\begin{equation} 
\mathcal{V} \; := \; \sum_{v \in V} \nu^{\{v\}} \; = \; \sum_{v \in V} \nu_v 
\end{equation} 
in~$A[V]$~: it is the generating function for the indicator function of the subsets of~$V$ 
of cardinality~$1$. Then, in the product $\mathcal{V}^k$ in the algebra~$A[V]$, 
each set of cardinality~$k$ occurs $k!$~times, so that $\mathcal{V}^k/k!$ 
is the generating function for the indicator function of the subsets of~$V$ 
of cardinality~$k$. 
If now $g: \mathbb{N} \to A$ is an $A$-valued function on the natural numbers, the identity 
\begin{equation} 
\sum_{k=0}^{\infty} g(k) \cdot \mathcal{V}^k/k! \; = \; \sum_{W \in (2^V)_{\text{fin}}} g(|W|) \nu^W
\end{equation} 
provides an embedding of the algebra $A![[\mathcal{V}]]$ of generating functions of exponential type 
(usually the variable is called $x$ instead of $\mathcal{V}$) into our algebra $A[V]$
\emph{if and only if} $|V| = \infty$. Indeed, if $k > |V|$, then $\mathcal{V}^k/k! = 0$.
If $|V| = \infty$, 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 \in (2^V)_{\text{fin}}$.
This embedding is at the origin of (almost?) all the applications of $A![[\mathcal{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.
 
\begin{remark} The ring ${\mathbb Z}![[\mathcal{V}]]$ is not Noetherian, 
but it contains the important functions $\exp(\mathcal{V})$ and $\log(1+\mathcal{V})$. 
\end{remark}

\begin{example} If $char \; A = 2$, then we have 
\begin{eqnarray}
(1+\mathcal{V})^{-1} &=& \sum_{k=0}^{\infty} (-1)^k k! \cdot \mathcal{V}^k/k! \\
      &\equiv& 1+\mathcal{V} \quad \hbox{and} \\
\log(1+\mathcal{V})  &=& \sum_{k=1}^{\infty} (-1)^{k-1} (k-1)! \cdot \mathcal{V}^k/k! \\
      &\equiv& \mathcal{V}+\mathcal{V}^2/2 
\end{eqnarray}
in the ring $A![[\mathcal{V}]]$. These identities are at the origin of lots of results of parity in combinatorics,
see \cite{L4}.
\end{example}

\medskip

\noindent
For all $t \in A$ we put $(t\nu)^{W} \; := \; t^{|W|} \nu^W$, $\; W \in (2^V)_{\text{fin}}$, and therefore 
\begin{equation} 
F_f(t\nu) \; = \; \sum_{W \in (2^V)_{\text{fin}}} f(W) \; t^{|W|} \nu^W,
\end{equation} 
where $f: (2^V)_{\text{fin}} \to 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 \cdot \nu) = f(\emptyset)$. 

If $F_f (0) = 0$, then $F_f(\nu)^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![[\mathcal{V}]]$ on $A[V]$ via the substitution 
$G(F_f (\nu))$ defined for any $G \in A![[\mathcal{V}]]$. 

\bigskip

\noindent
Finally, define for any $f,g: (2^V)_{\text{fin}} \to A$ the function $f*g: (2^V)_{\text{fin}} \to A$ by 
\begin{equation} 
(f*g)(W) \; := \; f(W) \cdot g(W) 
\end{equation} 
for each $W \in (2^V)_{\text{fin}}$ and define the Hadamard product to be 
\begin{equation} 
F_f (\nu) * F_g (\nu) \; := \; F_{f*g} (\nu). 
\end{equation} 


\subsection{Application to Matching Polynomials}

From now on every edge $\{u,v\} \in E$ of our finite graph $G = (V,E)$ will get a weight~$w_{\{u,v\}} \in A$ 
(we can assume that the two-element subsets of $V$ which are not edges get the weight zero). Moreover, 
every vertex $v \in V$ will get a weight~$x_v \in 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 $\mathcal{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, $\mathcal{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:
\begin{equation}
\mathcal{V}_x \; = \; \sum_{v \in V} x_v \cdot \nu^{\{v\}},  \qquad 
\mathcal{E}_w \; = \; \sum_{\{u,v\} \in E} w_{\{u,v\}} \cdot \nu^{\{u,v\}}.
\end{equation}
We define the (multivariate weighted) matching polynomial of~$G_{x,w}$ by
\begin{equation}
M_G(x,w) \; := \; \sum_{\text{matchings} \; M} 
\left( \prod_{\{u,v\} \in M} (-w_{\{u,v\}}) \right)
\left( \prod_{v \in V \backslash (\bigcup M)} x_v \right)
\end{equation}
We see that every matching is counted with respect to its weight~: 
the product of \emph{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~(\ref{eq:class}) 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. 
\begin{lemma} We have 
\begin{equation}
1+\sum_{\emptyset \subset W \subseteq V} M_{G[W]}(x,w) \cdot \nu^W \; = \; \exp [\mathcal{V}_x-\mathcal{E}_w].\qed 
\end{equation}
\end{lemma} 

\medskip

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
\begin{equation}
\mathrm{lin}(G_{x,w}) \; := \; \sum_{u,v \in V} \mathrm{lin}_{u,v}(G_{x,w}),
\end{equation}
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!$. 

\medskip 

\noindent 
Let us define for every $u,v \in V$
\begin{equation} 
\mathrm{cyc}_w(\nu) \; := \sum_{\emptyset \subset W \subseteq V} \mathrm{cyc}(G_{x,w}[W]) \cdot \nu^W, \quad 
\mathrm{lin}_{u,v,w}(\nu) \; := \sum_{\{u,v\} \subseteq W \subseteq V} \mathrm{lin}_{u,v}(G_{x,w}[W]) \cdot \nu^W,
\end{equation}
\begin{equation}
\mathrm{lin}_w(\nu) \; :=   \sum_{\emptyset \subset W \subseteq V} \mathrm{lin}(G_{x,w}[W]) \cdot \nu^W 
                  \; = \; \sum_{u,v \in V} \mathrm{lin}_{u,v,w}(\nu).
\end{equation}
Considering the infinite graph $K_{\infty}$ yields
\begin{equation} 
\sum_{n=1}^{\infty} \mathrm{cyc}(K_n) \cdot \mathcal{V}^n/n! \; = \; -\log (1-\mathcal{V}), \quad 
\sum_{n=1}^{\infty} \mathrm{lin}(K_n) \cdot \mathcal{V}^n/n! \; = \; \frac{\mathcal{V}}{1-\mathcal{V}}. \label{eq:k}
\end{equation} 
Usually (in undirected graphs) one does not distinguish between the two different directions 
of Hamiltonian cycles or paths. In this sense cyc$_w(\nu)$ and lin$_w(\nu)$ count 
them "twice". 

\bigskip

\noindent
Now we can prove our generalization of the Mehler formula. 

\begin{thm} Let $x_v$ and $y_v$ be two families of vertex weights. Using the Hadamard product $*$ we have: 
\begin{equation*}
\exp \left[ \mathcal{V}_x - \mathcal{E}_w \right] \; * \; \exp \left[ \mathcal{V}_y - \mathcal{E}_w \right] 
\; = \; \exp \left[ \frac{1}{2} \cdot \mathrm{cyc}_w(\nu) + \frac{1}{2} \cdot \mathrm{cyc}_w(-\nu) \right] \; \cdot \; 
\end{equation*}
\begin{equation}
\exp \sum_{u,v \in V} \left[ -\frac{x_u-y_u}{2}\cdot\frac{x_v-y_v}{2} \cdot \mathrm{lin}_{u,v,w}(\nu)
                             -\frac{x_u+y_u}{2}\cdot\frac{x_v+y_v}{2} \cdot \mathrm{lin}_{u,v,w}(-\nu) \right]. \label{eq:had}
\end{equation}
\end{thm}

\begin{proof}
A pair of matchings of~$G$ to be considered on the left-hand side of~(\ref{eq:had}) 
(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~(\ref{eq:had}) is equal to 
\begin{eqnarray}
&&\exp \left[\frac{\mathrm{cyc}_w(\nu) + \mathrm{cyc}_w(-\nu)}{4} \cdot 2 \right] \; \cdot \nonumber\\
&&\exp \left[\sum_{u,v \in V} \frac{\mathrm{lin}_{u,v,w}(\nu) + \mathrm{lin}_{u,v,w}(-\nu)}{4} \cdot (- x_u x_v - y_u y_v) \right] \; \cdot \nonumber\\
&&\exp \left[\sum_{u,v \in V} \frac{\mathrm{lin}_{u,v,w}(\nu) - \mathrm{lin}_{u,v,w}(-\nu)}{4} \cdot (x_u y_v + y_u x_v) \right].
\end{eqnarray} 
Indeed, if we divide $\mathrm{lin}_{u,v,w}(\nu) - \mathrm{lin}_{u,v,w}(-\nu)$ by~$2$, then we count odd paths from $u$ to $v$ once.
However, if $u$ and $v$ are different, then $\mathrm{lin}_{u,v,w}(\nu) = \mathrm{lin}_{v,u,w}(\nu)$ 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~(\ref{eq:had}), and it is evident that it is also equal to its right-hand side.
\end{proof}

\noindent
Specializing~(\ref{eq:had}) to $K_{\infty}$ and $x_v = x$, $y_v = y$ for all $v \in V$ 
and using~(\ref{eq:k}) yields the classical Mehler formula, because Hermite polynomials 
can be defined as matching polynomials of complete graphs.

\begin{coro} (Mehler). We have
\begin{equation*} 
1+\sum_{n=1}^{\infty} M_{K_n}(x) M_{K_n}(y) \cdot \mathcal{V}^n/n! \; = \; 
\end{equation*}
\begin{equation}
\frac{1}{\sqrt{1-\mathcal{V}^2}} \, \cdot \, 
\exp \left[ \left(\frac{x+y}{2}\right)^2 \cdot \frac{\mathcal{V}}{1+\mathcal{V}} - 
            \left(\frac{x-y}{2}\right)^2 \cdot \frac{\mathcal{V}}{1-\mathcal{V}} \right].\qed
\end{equation}
\end{coro}

\bigskip 

Now specialize to $A = \mathbb{C}$. Replacing the variables $y_v$ for every $v \in V$ 
in the previous theorem by the complex conjugate numbers $\overline{x_v}$ yields the 
following theorem.

\begin{thm} Let $x_v$ be a family of complex vertex weights. We have
\begin{equation*}
\exp \left[ \mathcal{V}_x - \mathcal{E}_w \right] \; * \; \exp \left[ \mathcal{V}_{\overline{x}} - \mathcal{E}_w \right] 
\; = \; \exp \left[ \frac{1}{2} \cdot \mathrm{cyc}_w(\nu) + \frac{1}{2} \cdot \mathrm{cyc}_w(-\nu) \right] \; \cdot \; 
\end{equation*}
\begin{equation}
        \exp \sum_{u,v \in V} \left[ (\Im m \; x_u)\cdot(\Im m \; x_v) \cdot \mathrm{lin}_{u,v,w}(\nu)
                                    -(\Re e \; x_u)\cdot(\Re e \; x_v) \cdot \mathrm{lin}_{u,v,w}(-\nu) \right].\qed \label{eq:had1} 
\end{equation}
\end{thm}
 
\bigskip 
 
If we replace in~(\ref{eq:had1}) $x_v$ and $\overline{x_v}$ both by $\Re e \; x_v$ for every $v \in V$, 
then $\Im m \; x_v$ becomes $0$ whereas $\Re e \; x_v$ remains unchanged. Therefore we get the identity~:
\begin{equation*}
\exp \left[ \mathcal{V}_{\Re e \; x} - \mathcal{E}_w \right] \; * \; \exp \left[ \mathcal{V}_{\Re e \; x} - \mathcal{E}_w \right]
\; = \; \exp \left[ \frac{1}{2} \cdot \mathrm{cyc}_w(\nu) + \frac{1}{2} \cdot \mathrm{cyc}_w(-\nu) \right] \; \cdot \; 
\end{equation*}
\begin{equation}
        \exp \sum_{u,v \in V} \left[ -(\Re e \; x_u)\cdot(\Re e \; x_v) \cdot \mathrm{lin}_{u,v,w}(-\nu) \right]. \label{eq:had2} 
\end{equation}
Now we can use our last identity~(\ref{eq:had2}) in order to simplify the right-hand side of~(\ref{eq:had1}).
This proves the following theorem.

\begin{thm} Let $x_v$ be a family of complex vertex weights. We have
\begin{eqnarray}
\exp \left[ \mathcal{V}_x - \mathcal{E}_w \right] \; * \; \exp \left[ \mathcal{V}_{\overline{x}} - \mathcal{E}_w \right] 
\; =&\!\!\!\!\!\!\!&\Bigl( \exp \left[ \mathcal{V}_{\Re e \; x} - \mathcal{E}_w \right] \; * \; 
                           \exp \left[ \mathcal{V}_{\Re e \; x} - \mathcal{E}_w \right] \Bigr) \; \cdot \; \nonumber \\
    &\!\!\!\!\!\!\!&\exp \left[ \sum_{u,v \in V} (\Im m \; x_u)\cdot(\Im m \; x_v) \cdot \mathrm{lin}_{u,v,w}(\nu) \right].\qed \label{eq:had3}
\end{eqnarray}
\end{thm}

\bigskip

\begin{coro} 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 $\Im m \; x_v > 0$ for every $v \in V$ or 
if $\Im m \; x_v < 0$ for every $v \in V$, then we get the inequality
\begin{equation}
|M_G(x,w)|^2 \; \ge \; \left( \prod_{v \in V} (\Im m \; x_v)^2 \right) 
                       \left( 1 \, + \sum_{\{u,v\} \in E} \frac{2 \cdot w_{\{u,v\}}}{(\Im m \; x_u)(\Im m \; x_v)} \right). \label{eq:had4}
\end{equation}
\end{coro}

\begin{proof}
Extracting the coefficient of~$\nu^V$ in the generating-function identity~(\ref{eq:had3}) we obtain
\begin{eqnarray}
|M_G(x,w)|^2 \; =&\!\!\!\!\!\!\!&\sum_{k=0}^{\infty} \frac{1}{k!} \sum_{W_0 \uplus W_1 \uplus \dots \uplus W_k = V} 
                                 M_{G[W_0]}(\Re e \; x,w)^2 \; \cdot \; \nonumber \\
                 &\!\!\!\!\!\!\!&\prod_{i=1}^k \sum_{u,v \in W_i} (\Im m \; x_u)(\Im m \; x_v)\mathrm{lin}_{u,v}(G_{x,w}[W_i]), \label{eq:had5}
\end{eqnarray}
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$,\dots,$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~(\ref{eq:had5}) are nonnegative,
so a lower bound can be obtained by taking \emph{some} of them. Here we keep only the terms where $W_0 = \emptyset$ 
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
\begin{equation}
\prod_{v \in V} (\Im m \; x_v)^2
\end{equation}
whereas in the second case, we get the contribution
\begin{equation}
\sum_{\{u,v\} \in E} (\Im m \; x_u) (\Im m \; x_v) (2 w_{\{u,v\}}) \prod_{t \in V \backslash \{u,v\}} (\Im m \; x_t)^2.
\end{equation}
The sum of those expressions is equal to the right-hand side of~(\ref{eq:had4}). This finishes the proof of this corollary.
\end{proof}

\begin{coro} (\cite{HL}) 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 $\Im m \; x_v > 0$ for every $v \in V$ or if $\Im m \; x_v < 0$ 
for every $v \in V$, then $|M_G(x,w)|^2 > 0$, i.e. the weighted matching polynomial cannot be zero in that case.\qed
\end{coro}

\begin{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. 
\end{remark}

\medskip

\noindent
\emph{Acknowledgements:} \quad 
I would like to thank most cordially Theresia Eisenk\"olbl and
the referees for many useful and stimulating remarks.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{99}
\bibitem{BN1}
J.I.~Brown and R.~Nowakowski, 
"Bounding the roots of independence polynomials", 
\emph{Ars Combin.} \textbf{58} (2001), 113-120.

\bibitem{BN2}
J.I.~Brown and R.~Nowakowski, 
"Average independence polynomials", 
\emph{J.~Combin.~Theory Ser.~B} \textbf{93} (2005), 313-318. 

\bibitem{BDN}
J.I.~Brown, K.~Dilcher and R.J.~Nowakowski, 
"Roots of independence polynomials of well-covered graphs", 
\emph{J.~Algebraic Combin.} \textbf{11} (2000), 197-210. 

\bibitem{BHN}
J.I.~Brown, C.A.~Hickman and R.J.~Nowakowski, 
"On the location of roots of independence polynomials", 
\emph{J.~Algebraic Combin.} \textbf{19} (2004), 273--282. 

\bibitem{COSW}
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,
\emph{Adv.~in Appl.~Math.} \textbf{32} (2004), 88-187.

\bibitem{CS}
M.~Chudnovsky and P.~Seymour,
"The roots of the independence polynomial of a clawfree graph",
\emph{J.~Combin.~Theory Ser.~B} \textbf{97} (2007), 350-357. 

\bibitem{E}
A.~Engstr\"om, 
"Inequalities on well-distributed point sets on circles",
\emph{JIPAM J.~Inequal.~Pure Appl.~Math.} \textbf{8} (2007), 
no.~2, Article~34, 5 pp.~(electronic). 

\bibitem{FS}
D.C.~Fisher and A.E.~Solow, 
"Dependence polynomials", 
\emph{Discrete Math.} \textbf{82} (1990), 251-258. 

\bibitem{F}
D.~Foata, 
"A combinatorial proof of the Mehler formula", 
\emph{J.~Combinatorial Theory Ser.~A} \textbf{24} (1978), 367-376. 

\bibitem{Go1}
C.D.~Godsil,
"Algebraic Combinatorics", 
Chapman \& Hall, 1993. 

\bibitem{Go2}
C.D.~Godsil,
"Hermite polynomials and a duality relation for matchings polynomials", 
\emph{Combinatorica} \textbf{1} (1981), 257-262. 

\bibitem{Gu1}
I.~Gutman, 
"An identity for the independence polynomial of trees", 
\emph{Publ.~Inst.~Math.~(Belgrade)} \textbf{50} (1991), 19-23. 

\bibitem{Gu2}
I.~Gutman, 
"Some analytic properties of the independence and matching polynomials", 
\emph{MATCH Commun.~Math.~Comput.~Chem.} \textbf{28} (1992), 139-150. 

\bibitem{H}
Y.O.~Hamidoune, 
"On the numbers of independent $k$-sets in a clawfree graph", 
\emph{J.~Combin.~Theory Ser.~B} \textbf{50} (1990), 241-244. 

\bibitem{HL}
O.J.~Heilmann and E.H.~Lieb, 
"Theory of monomer-dimer systems", 
\emph{Comm.~Math.~Phys.} \textbf{25} (1972), 190-232. 

\bibitem{HLi}
C.~Hoede and X.~Li, 
"Clique polynomials and independent set polynomials of graphs", 
\emph{Discrete Math.} \textbf{25} (1994), 219-228. 

\bibitem{JS}
B.~Jackson and A.D.~Sokal,
"Zero-free regions for multivariate Tutte polynomials 
(alias Potts-model partition functions) of graphs and matroids",
\emph{J.~Combin.~Theory Ser.~B} \textbf{99} (2009), 869-903.

\bibitem{L}
S.~Lang,
"Algebra",
\emph{Graduate Texts in Mathematics} \textbf{211},
Springer-Verlag, New York, 2002.

\bibitem{L1}
B.~Lass, 
"Matching polynomials and duality",
\emph{Combinatorica} \textbf{24} (2004), 427-440.

\bibitem{L2}
B.~Lass, 
"Orientations acycliques et le polyn\^ome chromatique", 
\emph{European J.~Combin.} \textbf{22} (2001), 1101-1123.

\bibitem{L3} 
B.~Lass, 
"The $N$-dimensional matching polynomial",
\emph{Geom.~Funct.~Anal.} \textbf{15} (2005), 453-475.

\bibitem{L4}
B.~Lass, 
"Variations sur le th\`eme $E+\overline E=XY$",
\emph{Adv.~in Appl.~Math.} \textbf{29} (2002), 215--242.

\bibitem{LR}
S.~Lavall\'ee and C.~Reutenauer,
"Characteristic polynomials of nonnegative integral square matrices and clique polynomials",
\emph{S\'em.~Lothar.~Combin.} \textbf{61A} (2009), Art.~B61Ac, 11 pp.

\bibitem{LM}
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.

\bibitem{QDW}
J.~Qian, A.~Dress and Y.~Wang, 
"On the dependence polynomial of a graph",
\emph{European J.~Combin.} \textbf{28} (2007), 337-346.

\bibitem{SS1}
A.D.~Scott and A.D.~Sokal, 
"The repulsive lattice gas, the independent-set polynomial, and the Lov\'asz local lemma",
\emph{J.~Stat.~Phys.} \textbf{118} (2005), 1151-1261. 

\bibitem{SS2}
A.D.~Scott and A.D.~Sokal, 
"On dependency graphs and the lattice gas",
\emph{Combin.~Probab. Comput.} \textbf{15} (2006), 253-279.

\bibitem{S}
R.P.~Stanley, 
"Graph colorings and related symmetric functions: 
Ideas and applications", 
\emph{Discrete Math.} \textbf{193} (1998), 267-286. 

\end{thebibliography}
\end{document}