%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \magnification=1200 \overfullrule=0pt %%%%%%%%%%%%%%% %\catcode`@=11 %---> FOURTEENPOINT %\newfam\gothfam %\newfam\gothbfam %\newfam\bbfam %\newskip\ttglue %\def\twelvepoint{\def\rm{\fam0\twelverm}% %\textfont0=\fourteenrm \scriptfont0=\twelverm \scriptscriptfont0=\ninerm %\textfont1=\fourteeni \scriptfont1=\twelvei \scriptscriptfont1=\ninei %\textfont2=\fourteensy \scriptfont2=\twelvesy \scriptscriptfont2=\ninesy %\textfont3=\tenex \scriptfont3=\tenex \scriptscriptfont3=\tenex %\textfont\itfam=\fourteenit \def\it{\fam\itfam\fourteenit}% %\textfont\slfam=\fourteensl \def\sl{\fam\slfam\fourteensl}% %\textfont\ttfam=\fourteentt \def\tt{\fam\ttfam\fourteentt}% %\textfont\bffam=\fourteenbf \scriptfont\bffam=\twelvebf \scriptscriptfont\bffam=\ninebf % \def\bf{\fam\bffam\fourteenbf}% %\textfont\gothfam=\fourteeneufm \scriptfont\gothfam=\twelveeufm \scriptscriptfont\gothfam=\nineeufm % \def\goth{\fam\gothfam\fourteeneufm}% %\textfont\gothbfam=\fourteeneufb \scriptfont\gothbfam=\twelveeufb \scriptscriptfont\gothbfam=\nineeufb % \def\gthb{\fam\gothbfam\fourteeneufb}% %\textfont\bbfam=\fourteenbb \scriptfont\bbfam=\twelvebb \scriptscriptfont\bbfam=\ninebb % \def\bb{\fam\bbfam\fourteenbb}% %\tt\ttglue=0.8em plus .5em minus .3em %\normalbaselineskip=18pt %\setbox\strutbox=\hbox{\vrule height15pt depth6pt width0pt}% %\font\sc=cmcsc10 scaled\magstep2 %\normalbaselines\rm}%\fourteenpoint %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % MACRO % \font\eighttt=cmtt8 % \font\eightsl=cmsl8 % \font\eightex=cmex10 at 8pt %%%%%%%%%%%%%%%% %% FONT CMR %% %%%%%%%%%%%%%%%% % \font\fiverm=cmr5 % \font\sixrm=cmr6 \font\seventeenrm=cmr17 \font\fourteenrm=cmr12 at 14pt \font\twelverm=cmr12 \font\ninerm=cmr10 at 9pt \font\eightrm=cmr8 \font\sixrm=cmr10 at 6pt % \textfont0=\tenrm \scriptfont0=\sevenrm \scriptscriptfont0=\fiverm \def\rm{\fam0\tenrm} %%%%%%%%%%%%%%%% %% FONT CMM %% %%%%%%%%%%%%%%%% % % \font\sixi=cmmi6 % \font\eighti=cmmi8 % \font\ninei=cmmi9 % \font\twelvei=cmmi12 % \font\fourteeni=cmmi10 at 14pt % \font\teni=cmmi10 \font\seveni=cmmi7 \font\fivei=cmmi5 \textfont1=\teni \scriptfont1=\seveni \scriptscriptfont1=\fivei \def\mit{\fam1} \def\oldstyle{\fam1\teni} %%%%%%%%%%%%%%%%% %% FONT CMSY %% %%%%%%%%%%%%%%%%% % \font\fivesy=cmsy6 at 5pt \font\sixsy=cmsy6 \font\sevensy=cmsy7 \font\eightsy=cmsy8 \font\ninesy=cmsy9 \font\tensy=cmsy10 \font\twelvesy=cmsy10 at 12pt \font\fourteensy=cmsy10 at 14pt %%%%%%%%%%%%%%%%% %% FONT CMTI %% %%%%%%%%%%%%%%%%% % \font\nineit=cmti10 at 9pt \font\eightit=cmti8 \font\sevenit=cmti7 %%%%%%%%%%%%%%%%%%% %% FONT CMBFTI %% %%%%%%%%%%%%%%%%%%% % \font\eightbfti=cmbxti10 at 8pt \font\bfti=cmbxti10 \font\twelvebfti=cmbxti10 at 12pt \font\fourteenbfti=cmbxti10 at 14pt %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% FONT CMCSC (Petites capitales) %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \font\sc=cmcsc10 %%%%%%%%%%%%%%%%% %% FONT MSBM %% %%%%%%%%%%%%%%%%% \font\sixbboard=msbm7 at 6pt % \font\ninebb=msbm9 % msbm10 at 9pt % \font\eightbb=msbm8 % msbm10 at 8pt % \font\sixbb=msbm6 % msbm10 at 6pt % \font\sixbboard=msbm7 at 6pt % \font\tenbb=msbm10 \font\sevenbb=msbm7 \font\fivebb=msbm5 \newfam\bbfam \textfont\bbfam=\tenbb \scriptfont\bbfam=\sevenbb \scriptscriptfont\bbfam=\fivebb \def\bb{\fam\bbfam\tenbb} \let\oldbb=\bb \def\bb #1{{\oldbb #1}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% FONT EUFM (Gothique) %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \font\sixgoth=eufm5 at 6pt \font\eightgoth=eufm7 at 8pt % \font\tengoth=eufm10 \font\sevengoth=eufm7 \font\fivegoth=eufm5 \newfam\gothfam \textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth \scriptscriptfont\gothfam=\fivegoth \def\goth{\fam\gothfam\tengoth} % %%%%%%%%%%%%%%%%% %% FONT CMBX %% %%%%%%%%%%%%%%%%% % % \font\eightbf=cmbx10 at 8pt \font\twelvebf=cmbx12 \font\fourteenbf=cmbx10 at 14pt % \font\ninebf=cmbx9 \font\eightbf=cmbx8 % \font\sevenbf=cmbx10 at 7pt \font\sixbf=cmbx5 at 6pt % \font\sixbf=cmbx5 % \font\fivebf=cmbx10 at 5pt \font\tenbf=cmbx10 \font\sevenbf=cmbx7 \font\fivebf=cmbx5 \newfam\bffam \textfont\bffam=\tenbf \scriptfont\bffam=\sevenbf \scriptscriptfont\bffam=\fivebf \def\bf{\fam\bffam\tenbf} % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% HAUT-DE-PAGE (EX. : AUTEUR COURANT ET TITRE COURANT) %% %% BAS-DE-BAGE %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newif\ifpagetitre \pagetitretrue \newtoks\hautpagetitre \hautpagetitre={\hfil} \newtoks\baspagetitre \baspagetitre={\hfil} \newtoks\auteurcourant \auteurcourant={\hfil} \newtoks\titrecourant \titrecourant={\hfil} \newtoks\hautpagegauche \hautpagegauche={\hfil\the\auteurcourant\hfil} \newtoks\hautpagedroite \hautpagedroite={\hfil\the\titrecourant\hfil} \newtoks\baspagegauche \baspagegauche={\hfil\tenrm\folio\hfil} \newtoks\baspagedroite \baspagedroite={\hfil\tenrm\folio\hfil} \headline={\ifpagetitre\the\hautpagetitre \else\ifodd\pageno\the\hautpagedroite \else\the\hautpagegauche\fi\fi } \footline={\ifpagetitre\the\baspagetitre \global\pagetitrefalse \else\ifodd\pageno\the\baspagedroite \else\the\baspagegauche\fi\fi } \def\nopagenumbers{\def\folio{\hfil}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% UN SEMBLANT DES GUILLEMETS FRANCAIS %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\og{\leavevmode\raise.3ex \hbox{$\scriptscriptstyle\langle\!\langle$~}} \def\fg{\leavevmode\raise.3ex \hbox{~$\!\scriptscriptstyle\,\rangle\!\rangle$}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% TRUC AVEC MACHIN AU-DESSUS ET BIDULE AU-DESSOUS %% %% (MODE MATHEMATIQUE) %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\build #1_#2^#3{\mathrel{\mathop{\kern 0pt #1} \limits_{#2}^{#3}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\scs{\scriptstyle} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% FLECHES HORIZONTALES ET VERTICALES AVEC TRUC %% %% AU-DESSUS ET MACHIN AU-DESSOUS (MODE MATH) %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\hfl[#1][#2][#3]#4#5{\kern -#1 \sumdim=#2 \advance\sumdim by #1 \advance\sumdim by #3 \smash{\mathop{\hbox to \sumdim {\rightarrowfill}} \limits^{\scriptstyle#4}_{\scriptstyle#5}} \kern-#3} \def\vfl[#1][#2][#3]#4#5% {\sumdim=#1 \advance\sumdim by #2 \advance\sumdim by #3 \setbox1=\hbox{$\left\downarrow\vbox to .5\sumdim {}\right.$} \setbox1=\hbox{\llap{$\scriptstyle #4$}\box1 \rlap{$\scriptstyle #5$}} \vcenter{\kern -#1\box1\kern -#3}} \def\Hfl #1#2{\hfl[0mm][12mm][0mm]{#1}{#2}} \def\Vfl #1#2{\vfl[0mm][12mm][0mm]{#1}{#2}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% DIAGRAMMES COMMUTATIFS %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newdimen\sumdim \def\diagram#1\enddiagram {\vcenter{\offinterlineskip \def\tvi{\vrule height 10pt depth 10pt width 0pt} \halign{&\tvi\kern 5pt\hfil$\displaystyle##$\hfil\kern 5pt \crcr #1\crcr}}} %% SYNTAXE %% $$ %% \diagram %% ... & & ... & \cr %% ... & & ... & \cr %% ................. %% ... & & ... & \cr %% \enddiagram %% $$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\def\Doteq{\build{=}_{\scriptscriptstyle\bullet}^{\scriptscriptstyle\bullet}} \def\Doteq{\build{=}_{\hbox{\bf .}}^{\hbox{\bf .}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% ESPACE VERTICAL EN MODE MATH %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\vspace[#1]{\noalign{\vskip #1}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%% %% ENCADREMENT %% %%%%%%%%%%%%%%%%%%% \def\boxit [#1]#2{\vbox{\hrule\hbox{\vrule \vbox spread #1{\vss\hbox spread #1{\hss #2\hss}\vss}% \vrule}\hrule}} \def\carre{\boxit[5pt]{}} %% INDIQUE LA FIN D'UNE PREUVE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\font\tengoth=eufm10 \font\tenbboard=msbm10 %\font\eightrm=cmr8 \font\eighti=cmmi8 %\font\eightsy=cmsy8 \font\eightbf=cmbx8 % \font\eighttt=cmtt8 \font\eightit=cmti8 % \font\eightsl=cmsl8 \font\eightgoth=eufm7 % \font\eightbboard=msbm7 \font\eightex=cmex10 at 8pt %\font\eightgoth=eufm7 \font\sevenbboard=msbm7 % \font\sixrm=cmr6 \font\sixi=cmmi6 %\font\sixsy=cmsy6 \font\sixbf=cmbx6 % \font\sixgoth=eufm5 at 6pt \font\sixbboard=msbm7 at 6pt %\font\fivegoth=eufm5 \font\fivebboard=msbm5 \vsize= 18.5cm \hsize= 12.5cm \hoffset=3mm \voffset=3mm %%%%%%%%%%%%%%%%% %% DEFINITIONS %% %%%%%%%%%%%%%%%%% \def\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt \vfill\hrule}\vrule}} \def\qeda{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt height9pt \vfill\hrule}\vrule}} \def\arti#1#2{\setbox50=\null\ht50=#1\dp50=#2\box50} \def\tend_#1^#2{\mathrel{ \mathop{\kern 0pt\hbox to 1cm{\rightarrowfill}} \limits_{#1}^{#2}}} \def\tendps{\tend_{n\to\infty}^{\hbox{p.s.}}} \def\lfq{\leavevmode\raise.3ex\hbox{$\scriptscriptstyle \langle\!\langle$}\thinspace} \def\rfq{\leavevmode\thinspace\raise.3ex\hbox{$\scriptscriptstyle \rangle\!\rangle$}} \font\msamten=msam10 \font\msamseven=msam7 \newfam\msamfam \textfont\msamfam=\msamten \scriptfont\msamfam=\msamseven \def\ams {\fam\msamfam\msamten} \def\hexnumber #1% {\ifcase #1 0\or 1\or 2\or 3\or 4\or 5 \or 6\or 7\or 8\or 9\or A\or B\or C\or D\or E\or F \fi} \mathchardef\leadsto="3\hexnumber\msamfam 20 \def\frac #1#2{{#1\over #2}} %%%%%%%%%%%%%%%%%%%%%%%% %% END OF DEFINITIONS %% %%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%% %% AUTHOR ON EVEN PAGES %% %%%%%%%%%%%%%%%%%%%%%%%%%%%% \auteurcourant{\eightbf BODO LASS \hfill} %%%%%%%%%%%%%%%%%%%%%%%%%% %% TITLE ON ODD PAGES %% %%%%%%%%%%%%%%%%%%%%%%%%%% \titrecourant{\hfill\eightbf MATCHING POLYNOMIALS AND DUALITY} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% {\parindent=0pt\eightbf COMBINATORICA 24 (3) (2004) 427-440 \vskip 1.5cm %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%% %% TITEL %% %%%%%%%%%%%%% \centerline{\fourteenbf MATCHING POLYNOMIALS AND DUALITY } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Subject Classification %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \parindent=-1mm\footnote{}{ Mathematics Subject Classification (1991): 05 C 70; 05 A 15, 05 A 20, 12 D 10 } \vskip 15pt %%%%%%%%%%% %% NAME %% %%%%%%%%%%% \centerline{\twelvebf BODO LASS} \vskip 10pt \medskip %%%%%%%%%%%%%%%% %% RECEIVED %% %%%%%%%%%%%%%%%% \centerline{(Received February 20, 2001; Accepted November 29, 2001)} } \vskip10pt \vskip3pt %%%%%%%%%%%%%%%% %% ABSTRACT %% %%%%%%%%%%%%%%%% {\eightrm Let $\scs G$ be a simple graph on $\scs n$ vertices. An $\scs r$-matching in $\scs G$ is a set of $\scs r$ independent edges. The number of $\scs r$-matchings in $\scs G$ will be denoted by $\scs p(G,r)$. We set $\scs p(G,0) = 1$ and define the matching polynomial of $\scs G$ by $\scs \mu(G,x) := \sum_{r=0}^{\lfloor n/2 \rfloor} (-1)^r \cdot p(G,r) \cdot x^{n-2r} $ and the signless matching polynomial of $\scs G$ by $\scs \overline{\mu}(G,x) := \sum_{r=0}^{\lfloor n/2 \rfloor} p(G,r) \cdot x^{n-2r}. $ It is classical that the matching polynomials of a graph $\scs G$ determine the matching polynomials of its complement $\scs \overline{G}$. We make this statement more explicit by proving new duality theorems by the generating function method for set functions. In particular, we show that the matching functions $\scs e^{-x^2/2}\mu(G,x)$ and $\scs e^{-x^2/2}\mu(\overline{G},x)$ are, up to a sign, real Fourier transforms of each other. Moreover, we generalize Foata's combinatorial proof of the Mehler formula for Hermite polynomials to matching polynomials. This provides a new short proof of the classical fact that all zeros of $\scs \mu(G,x)$ are real. The same statement is also proved for a common generalization of the matching polynomial and the rook polynomial. } \vskip1.5pt \medskip \parindent=3mm \vskip 5mm %%%%%%%%%%%% %% TEXT %% %%%%%%%%%%%% \centerline{\bf 1. Introduction} \medskip 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 ${V \choose 2}$, the family of all 2-element subsets of $V$. The {\it complement} of $G$ is the graph $\overline{G} = (V, \overline{E})$ with $\overline{E} = {V \choose 2} \backslash E$. An {\it $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}$. If $r = {\lfloor n/2 \rfloor}$, then an $r$-matching of $G$ is called {\it perfect} if $n$ is even and {\it quasi-perfect} if $n$ is odd. Let $p(G,r)$ be the number of $r$-matchings in $G$, with the convention that $p(G,0) := 1.$ The matching polynomial of $G$ is (see~[3], chapter 1) $$ \mu(G,x) := \sum_{r=0}^{\lfloor n/2 \rfloor} (-1)^r \cdot p(G,r) \cdot x^{n-2r}, $$ while the signless matching polynomial reads $$ \overline{\mu}(G,x) := \sum_{r=0}^{\lfloor n/2 \rfloor} p(G,r) \cdot x^{n-2r}. $$ In particular, $\overline{\mu}(G,0)$ counts the number of perfect matchings of $G$ and $\overline{\mu}(G,1)$ counts the number of arbitrary matchings of $G$. These polynomials were introduced by Heilmann and Lieb~[5], who, motivated by statistical physics, mainly studied their zeros. They obtained many estimations on the locations of those zeros and provided several different proofs for their main theorem that all zeros of $\mu(G,x)$ are real. Another proof of this theorem was obtained by Godsil, which he reproduced in his recent book~[3] together with all the classical proofs. However, all those proofs rely on a recursive approach (via the deletion of a special vertex) towards the matching polynomial. One of the purposes of this paper is to give a short proof that avoids this traditional deletion technique. We generalize the combinatorial proof of the Mehler formula for Hermite polynomials imagined by Foata (see~[2]). To state and derive our extension of the Mehler formula we need an adequate algebraic tool, the algebra of generating functions for set functions. This algebra is developed in the next section. In section 4 we show that our generalization of the Mehler formula immediately implies that $|\mu(G,x)|^2 \; \ge \; [(\Im m \; x)^2]^n + 2|E|\cdot[(\Im m \; x)^2]^{n-1}$ for every $x \in {\bb C}$, i.e.~that all the zeros of $\mu(G,x)$ are real. Moreover, this fact holds for a common generalization of the matching polynomial and the rook polynomial. \medskip Section 3 is entirely devoted to questions of duality. It is evident that $\mu(G,x)$ and $\overline{\mu}(G,x)$ contain the same information, a convenient relation between those polynomials being $$ \mu(G,x) = (-i)^n \cdot \overline{\mu}(G,xi), \qquad |V| = n, \quad i = \sqrt{-1}. $$ The observation that $\mu(G,x)$ and $\overline{\mu}(G,x)$ determine $\mu(\overline{G},x)$ and $\overline{\mu}(\overline{G},x)$, however, seems to have first been made by Lov\'asz,~[8]~5.18. His proof, based on the inclusion-exclusion principle, does not seem to be too difficult although it is marked with an asterisk in his book. We prefer to give an explicit calculation involving several new duality theorems. In particular, we show that the matching functions $\scs e^{-x^2/2}\mu(G,x)$ and $\scs e^{-x^2/2}\mu(\overline{G},x)$ are, up to a sign, real Fourier transforms of each other. Matching polynomials generalize many classical orthogonal polynomials, namely Hermite polynomials (the matching polynomials of complete graphs), Tchebycheff polynomials of both kinds (paths and cycles) and Laguerre polynomials (complete bipartite graphs), see~[9] chapter~6. The complete graph $K_n$ on $n$ vertices can be defined as the complement of the edgeless graph $\overline{K_n}$ on those vertices. Clearly, $\mu(\overline{K_n},x) = \overline{\mu}(\overline{K_n},x) = x^n$. The Hermite polynomials will be (by definition) the matching polynomials of the complete graphs, i.e.~$He_n(x) := \mu(K_n,x)$. The reader will recognize the classical definition of the Hermite polynomials as a special case of the second equality in our duality theorem ($d/dx$), replacing $\overline{G}$ by $K_n$. \medskip The first step towards the duality theory developed here was the combinatorial interpretation of integrals over products of Hermite polynomials (see~[9], VI-34, remark 21, or the recent book [1], chapter 6.9): $$ \overline{\mu}(\overline{ K_{n_1} \uplus \dots \uplus K_{n_k} },0) \; = \; \hbox{$\frac{1}{\sqrt{2\pi}}$} \int_{-\infty}^{\infty} e^{-x^2/2} \cdot \mu(K_{n_1},x) \cdots \mu(K_{n_k},x) \cdot dx, $$ where $K_{n_1} \uplus \dots \uplus K_{n_k}$ denotes the vertex disjoint union of the complete graphs $K_{n_1},\dots,K_{n_k}$. Even this formula has been neglected in physics (for instance, in [5] there is no consideration of duality at all) as can be seen from the fact that Itzykson and Zuber~[6] need a whole page to solve their integral~(3.5), the result being evident from the previous formula. The second step was the realization, due to Godsil~[4], that, more generally, $$ \overline{\mu}(\overline{G},0) \; = \; \hbox{$\frac{1}{\sqrt{2\pi}}$} \int_{-\infty}^{\infty} e^{-x^2/2} \cdot \mu(G,x) \cdot dx, $$ the equation $\mu(K_{n_1},x) \cdots \mu(K_{n_k},x) = \mu(K_{n_1} \uplus \dots \uplus K_{n_k},x)$ being evident. Finally, the last step of duality theory is the derivation of direct formulas for the matching polynomials of the complementary graph. In this context Godsil mainly proposed $$ \mu(\overline{G},x) \; = \; \sum_{r=0}^{\lfloor n/2 \rfloor} p(G,r) \cdot \mu(K_{n-2r},x), $$ but also the more explicit formula $$ \overline{\mu}(\overline{G},y) \; = \; \hbox{$\frac{1}{\sqrt{2\pi}}$} \int_{-\infty}^{\infty} e^{-x^2/2} \cdot \mu(G,x+y) \cdot dx $$ is a specialization of theorem~2.4 in~[4], that Godsil did not reproduce in his book~[3]. \medskip We propose two new duality theorems by means of differential operators, a slight modification of Godsil's last theorem together with a scalar product formula and, finally, the Fourier transform interpretation. Our proofs of section 3 make use of generating functions for set functions. We must say that the set function machinery developed in the next section has been the adequate tool for deriving those duality theorems. %%%%%%%%%%%%%%%%%%%%% % %% % Algebraic tools %% % % %%%%%%%%%%%%%%%%%%%%% \bigskip \centerline{\bf 2. Algebraic tools} \medskip \noindent Let $V$ be a finite set and $$\openup2pt\eqalign{ f: 2^V & \to A \cr V' \subseteq V & \mapsto f(V') \in A \cr }$$ be a set function, where $A$ is a commutative ring with $1$. Consider the generating function $$ F_f(\nu) := \sum_{V' \subseteq V} f(V') \cdot \nu^{V'}, \qquad \nu^{\emptyset} := 1, $$ subject to the following multiplication rules ($V',V'' \subseteq V$): $$ \nu^{V'} \cdot \nu^{V''} := \nu^{V'+V''}, \quad \hbox{where} $$ $$ V'+V'' := \openup 2pt\left\{\eqalign{ V' \cup V'', \quad & \hbox{if} \quad V' \cap V'' = \emptyset, \cr \dag, \; \; \quad \quad & \hbox{if} \quad V' \cap V'' \ne \emptyset, \quad \hbox{where} \cr }\right. $$ $$ \dag + V' := \dag, \quad \dag + \dag := \dag, \qquad \hbox{and} \qquad \nu^{\dag} := 0. $$ The algebra $A[V]$ of those generating functions is not unknown. In fact, we have the isomorphism $$ A[V] \simeq A[v_1,\dots,v_n]/ \langle v_1^2,\dots,v_n^2 \rangle, $$ if $V$ contains $n$ elements. \medskip \noindent {\bf Example.} For $V' \subseteq V$ put $$ (fg)(V') := \sum_{V' = V'' \uplus V'''} f(V'') \cdot g(V''') $$ ($f,g,fg: 2^V \to A$). Then $$ F_{fg} (\nu) = F_f (\nu) \cdot F_g (\nu). $$ \medskip For $|V| = \infty$ let $F(V)$ be the partially ordered set of finite subsets of $V$. We have the canonical projections $p_{V',V''}: A[V'] \to A[V'']$ ($V',V'' \in F(V), V' \supseteq V''$) and define $$ A[V] := \lim_{\longleftarrow} A[V'], \quad V' \in F(V) $$ in order to work with generating functions of the form $$ F_f (\nu) = \sum_{V' \in F(V)} f(V') \cdot \nu^{V'}. $$ Let $$ V := \sum_{v \in V} \nu^{\{v\}} $$ be the generating function for the indicator function of the subsets of $V$ of cardinality~$1$ (the double use of $V$ for the set itself on the one hand and for an element of $A[V]$ on the other hand will never cause confusion). In the product $V^n$ each subset of cardinality~$n$ occurs $n!$~times, so that $V^n/n!$ represents the indicator function of the subsets of the set $V$ of cardinality $n$. The identity $$ \sum_{n=0}^{\infty} f(n) \cdot V^n/n! \; = \sum_{V' \in F(V)} f(|V'|) \cdot \nu^{V'}, \quad f: {\bb N} \to A, $$ provides an imbedding of the ring $A![[V]]$ of generating functions of exponential type (usually the variable is called $x$ instead of $V$) into our ring $A[V]$. It is at the origin of (almost?) all applications of $A![[V]]$ into combinatorics, but requires the existence of an infinite combinatorial model depending just on cardinalities. Consequently, $A[V]$ gives more flexibility and closeness to combinatorics. In addition, $A[V]$ is ideally suited for computer calculations (for more details and lots of different applications see~[7]). \medskip \noindent {\bf Remark.} The ring ${\bb Z}![[V]]$ is not noetherian, but it contains the important functions $\exp(V)$ and $\log(1+V)$. \medskip \noindent {\bf Example.} If $char \; A = 2$, then we have $$\openup2pt\eqalign{ (1+V)^{-1} \; & = \; \sum_{n=0}^{\infty} (-1)^n n! \cdot V^n/n! \cr & \equiv \; 1+V \quad \hbox{and} \cr \log(1+V) \; & = \; \sum_{n=1}^{\infty} (-1)^{n-1} (n-1)! \cdot V^n/n! \cr & \equiv \; V+V^2/2 \cr }$$ in the ring $A![[V]]$. These identities are at the origin of lots of results of parity in combinatorics. \medskip \noindent For all $t \in A$ we put $(t\nu)^{V'} \; := \; t^{|V'|} \cdot \nu^{V'}$, $\; V' \subseteq V$, and therefore $$ F_f(t\nu) \; = \; \sum_{\emptyset \subseteq V' \subseteq V} f(V') \; t^{|V'|} \cdot \nu^{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 \cdot \nu) = f(\emptyset)$. If $F_f (0) = 0$, then $F_f(\nu)^n/n!$ is defined for any ring $A$, because a partition into $n$ nonempty subsets can be ordered in $n!$ different ways. Thus we have an operation of $A![[V]]$ on $A[V]$ via the substitution $G(F_f (\nu))$ defined for any $G \in A![[V]]$. \medskip \noindent Finally, define for any $f,g: 2^V \to A$ the function $f*g: 2^V \to A$ by $$ (f*g)(V') := f(V') \cdot g(V') $$ for each $V' \subseteq V$ and define the Hadamard product to be $$ F_f (\nu) * F_g (\nu) := F_{f*g} (\nu). $$ \eject %%%%%%%%%%%%%%%%%%%%%% % % % Duality theorems % % %% %%%%%%%%%%%%%%%%%%%%%% \centerline{\bf 3. Duality theorems} \medskip Let $G = (V,E)$ be a finite simple graph and let $\overline{G} = (V,\overline{E})$ be its complement. We have identified $V$ with the generating function of the indicator function of the one-element subsets of $V$, and we have realized that $V^2/2$ corresponds to the indicator function of the two-element subsets of $V$. Similarly, we identify $E$ and $\overline{E}$ with the generating functions of the indicator functions of $E,\overline{E} \subseteq 2^V$. Since every two-element subset of $V$ either belongs to $E$ or to $\overline{E}$, we have the following fundamental identity, valid in the ring $A[V]$: $$\bf E + \overline{E} \; = \; V^2/2. $$ Let $p(G)$ be the number of perfect matchings (if $|V| \equiv 0 \bmod 2$) or quasi-perfect matchings (if $|V| \equiv 1 \bmod 2$), and let $c(G)$ be the number of arbitrary matchings of $G$. We denote by $G[V']$ the subgraph of $G$ induced by $V' \subseteq V$, i.e.~its vertices are the elements of $V'$ and its edges are the edges of $G$ having both endpoints in $V'$. Then the perfect matchings are counted by $\exp[E]$, the quasi-perfect matchings by $V \cdot \exp[E]$, and altogether we have the identities $$\openup2pt\eqalign{ 1+\sum_{\emptyset \subset V' \subseteq V} p(G[V']) \cdot \nu^{V'} \; & = \; (1+V) \cdot \exp [E], \cr 1+\sum_{\emptyset \subset V' \subseteq V} c(G[V']) \cdot \nu^{V'} \; & = \; \exp [V+E]. }$$ The following proposition was proved in~[8],~5.18, for the case of perfect matchings. \medskip \noindent {\bf Proposition.} \quad $c(\overline{G}) \; \equiv \; p(G) \; \bmod 2$. \medskip \noindent {\bf Proof.} Using the previous three identities we have $$ \exp [V+\overline{E}] \; = \; \exp [V+V^2/2-E] \; \equiv \; \exp [\log (1+V) + E] \; = \; (1+V) \cdot \exp [E].\qeda $$ \medskip From the very definitions of the matching polynomials we have the following generating functions: $$\openup2pt\eqalign{ 1+\sum_{\emptyset \subset V' \subseteq V} \mu(G[V'],x) \cdot \nu^{V'} \; & = \; \exp [xV-E], \cr 1+\sum_{\emptyset \subset V' \subseteq V} \overline{\mu}(G[V'],x) \cdot \nu^{V'} \; & = \; \exp [xV+E]. \cr }$$ Considering the first equality for the complete graph $K_\infty$ on an infinite set of vertices yields the classical generating function of exponential type for Hermite polynomials: $$ 1+\sum_{n=1}^{\infty} \mu(K_n,x) \cdot V^n/n! \; = \; \exp [xV-V^2/2]. $$ \medskip We are now in a position to provide a very short proof of Godsil's duality theorem. \medskip \noindent {\bf Duality theorem (Godsil).} $$ \mu(\overline{G},x) \; = \; \sum_{r=0}^{\lfloor n/2 \rfloor} p(G,r) \cdot \mu(K_{n-2r},x). $$ \medskip \noindent {\bf Proof.} Using the set function algebra developed in section 2 we have: $$ \exp[xV-\overline{E}] \; = \; \exp[xV-V^2/2+E] \; = \; \exp[E] \cdot \exp[xV-V^2/2].\qeda $$ \bigskip We can further establish the following new identities. \medskip \noindent {\bf Duality theorem for the matching polynomials ($\frac{d^2}{dx^2}$).} $$\openup2pt\eqalign{ \overline{\mu}(\overline{G},x) \; & = \; \exp \bigl[\hbox{$\frac{d^2}{dx^2}$}/2 \bigr] \cdot \mu(G,x), \cr \mu(\overline{G},x) \; & = \; \exp \bigl[- \hbox{$\frac{d^2}{dx^2}$}/2 \bigr] \cdot \overline{\mu}(G,x). \cr }$$ \medskip \noindent {\bf Proof.} As in the preceding proof, $$\openup2pt\eqalign{ \exp[xV+\overline{E}] \; & = \; \exp[V^2/2] \cdot \exp[xV-E] \cr & = \; \exp[\hbox{$\frac{d^2}{dx^2}$}/2] \cdot \exp[xV-E], \cr }$$ because $\frac{d}{dx} \exp[xV-E] \; = \; V \cdot \exp[xV-E]$. The differential operator $\exp \bigl[-\frac{d^2}{dx^2}/2 \bigr]$ is the inverse of $\exp \bigl[\frac{d^2}{dx^2}/2 \bigr]$.\qeda \bigskip \noindent {\bf Duality theorem for the matching polynomials ($\frac{d}{dx}$).} $$\openup2pt\eqalign{ \overline{\mu}(\overline{G},x) \; & = \; e^{-x^2/2} \cdot \mu(G,\hbox{$\frac{d}{dx}$}) \cdot e^{x^2/2}, \cr \mu(\overline{G},x) \; & = \; e^{x^2/2} \cdot \overline{\mu}(G,- \hbox{$\frac{d}{dx}$}) \cdot e^{-x^2/2}. \cr }$$ \medskip \noindent {\bf Proof.} By the Taylor formula we know that $$ f(x+a) \; = \; \exp[\hbox{$\frac{d}{dx}$} a] \cdot f(x) $$ for variables $x,a$ and a formal power series $f$. It follows that $$\openup2pt\eqalign{ & \exp[-x^2/2] \cdot \exp[\hbox{$\frac{d}{dx}$} V - E] \cdot \exp[x^2/2] \cr & = \; \exp[-x^2/2] \cdot \exp[-E] \cdot \exp[\hbox{$\frac{d}{dx}$} V] \cdot \exp[x^2/2] \cr & = \; \exp[-x^2/2] \cdot \exp[-E] \cdot \exp[(x+V)^2/2] \cr & = \; \exp[xV + \overline{E}]. \cr }$$ The second equality is proved in the same way.\qeda \bigskip Specializing the second equality of the preceding theorem to Hermite polynomials, i.e.~replacing $\overline{G}$ by $K_n$, provides the classical definition of Hermite polynomials. However, we could not find the specialization to Hermite polynomials of the first equality, i.e.~the differential operator $He_n(d/dx)$, in the literature. \eject Finally, we can prove several integral formulae. \medskip \noindent {\bf Duality theorem for the matching polynomials ($\int$).} $$ \overline{\mu}(\overline{G},y) \; = \; \hbox{$\frac{1}{\sqrt{2\pi}}$} \int_{-\infty}^{\infty} e^{-(x-y)^2/2} \cdot \mu(G,x) \cdot dx. $$ \medskip \noindent {\bf Proof.} Using the invariance of the integral with respect to translations we get: $$\openup2pt\eqalign{ & \hbox{$\frac{1}{\sqrt{2\pi}}$} \int_{-\infty}^{\infty} \exp[-(x-y)^2/2] \cdot \exp[xV-E] \cdot dx \cr & = \; \hbox{$\frac{1}{\sqrt{2\pi}}$} \int_{-\infty}^{\infty} \exp[-s^2/2] \cdot \exp[(s+y)V-E] \cdot ds \cr & = \; \exp[yV+\overline{E}] \cdot \hbox{$\frac{1}{\sqrt{2\pi}}$} \int_{-\infty}^{\infty} \exp[-(s-V)^2/2] \cdot ds \cr & = \; \exp[yV+\overline{E}] \cdot \hbox{$\frac{1}{\sqrt{2\pi}}$} \int_{-\infty}^{\infty} \exp[-t^2/2] \cdot dt \cr & = \; \exp[yV+\overline{E}].\qeda \cr }$$ \bigskip For graphs $G' = (V',E')$ and $G'' = (V'',E'')$ we have the following result. \medskip \noindent {\bf Scalar product formula.} $$\openup2pt\eqalign{ \overline{\mu}(\overline{G' \uplus G''},0) \; & = \; \hbox{$\frac{1}{\sqrt{2\pi}}$} \int_{-\infty}^{\infty} \mu(G',x) \cdot \mu(G'',x) \cdot e^{-x^2/2} \cdot dx \cr & = \; \overline{\mu}(\overline{G'},\hbox{$\frac{d}{dx}$}) \cdot \overline{\mu}(\overline{G''},x) \Bigr|_{x=0}. \cr }$$ \medskip \noindent {\bf Proof.} The first equality being evident from the previous theorem, we just have to prove the second one: $$\openup2pt\eqalign{ & \exp [ \hbox{$\frac{d}{dx}$} V' + \overline{E'} ] \cdot \exp [ x V'' + \overline{E''} ] \Bigr|_{x=0} \cr & = \; \exp [ \overline{E'} ] \cdot \exp [ (x+V') V'' + \overline{E''} ] \Bigr|_{x=0} \cr & = \; \exp [ V'V'' + \overline{E'} + \overline{E''} ].\qeda \cr }$$ \medskip \noindent {\bf Remark.} If $G' = K_n$ and $G'' = K_m$, then the scalar product formula counts the number of perfect matchings of the complete bipartite graph $\overline{K_n \uplus K_m}$, which is equal to zero, if $n \ne m$, and equal to $n!$, if $n = m$. This is the orthogonality of the Hermite polynomials. \bigskip \noindent The previous duality theorem implies $ \mu(\overline{G},y) = \hbox{$\frac{(-i)^n}{\sqrt{2\pi}}$} \int_{-\infty}^{\infty} e^{-(x-yi)^2/2} \cdot \mu(G,x) \cdot dx. $ This proves the following theorem. \medskip \noindent {\bf Duality theorem for the matching polynomial (${\bb C}$).} $$ e^{-y^2/2} \mu(\overline{G},y) \; = \; \hbox{$\frac{(-i)^n}{\sqrt{2\pi}}$} \int_{-\infty}^{\infty} e^{xyi} \cdot e^{-x^2/2}\mu(G,x) \cdot dx.\qeda $$ \medskip If we call $e^{-x^2/2}\mu(G,x)$ matching function of $G$, then this matching function is even for $n$ even and odd for $n$ odd. \bigskip \noindent {\bf Duality theorem for the matching polynomial (${\bb R}$).} $$\openup2pt\eqalign{ & e^{-y^2/2}\mu(\overline{G},y) \cdot (-1)^{n/2} \cr \; & = \; \hbox{$\sqrt{\frac{2}{\pi}}$} \cdot \int_{0}^{\infty} \cos(xy) \cdot e^{-x^2/2}\mu(G,x) \cdot dx, \qquad n \quad even, \cr & \cr & e^{-y^2/2}\mu(\overline{G},y) \cdot (-1)^{(n-1)/2} \cr \; & = \; \hbox{$\sqrt{\frac{2}{\pi}}$} \cdot \int_{0}^{\infty} \sin(xy) \cdot e^{-x^2/2}\mu(G,x) \cdot dx, \qquad n \quad odd. \cr }$$ {\it Thus the matching functions of $\overline{G}$ and $G$ are, up to an eventual multiplication by $-1$, real Fourier transforms of one another.\qeda} \bigskip %%%%%%%%%%% % % % Zeros % % %% %%%%%%%%%%% \bigskip \centerline{\bf 4. Zeros} \medskip From now on every edge $\{u,v\} \in E$ of our graph $G = (V,E)$ will get a positive real weight~$w_{\{u,v\}}$ (we can assume that the two-element subsets of $V$ which are not edges get the weight zero). This weighted graph will be denoted by $G_w = (V,E_w)$. In particular, $E_w$ will be identified with the generating function of the set function which attributes the value $0$ to all subsets of $V$ with the only exception of the edges of $G$, which get their own weights. The (weighted) matching polynomial can be defined with the help of its generating function: $$ 1+\sum_{\emptyset \subset V' \subseteq V} \mu(G_w[V'],x) \cdot \nu^{V'} \; = \; \exp [xV-E_w]. $$ We see that every matching is counted with respect to its weight: the product of the weights of its edges. \medskip A Hamiltonian cycle of $G_w$ is a cyclic order of $V$ and its weight is the product of the weights of its $n = |V|$ edges corresponding to two consecutive vertices in the cyclic order. In particular, if the edge corresponding to two consecutive vertices in the cyclic order does not belong to the graph (equivalently, has weight zero), then the weight of that ``Hamiltonian cycle'' is equal to zero. Let cyc$(G_w)$ be the sum of the weights of all Hamiltonian cycles of $G_w$, with the convention that cyc$(G_w) = 1$ if $n = 1$. We assume that the weight of each edge in the complete graph $K_n$ is equal to $1$, so that cyc$(K_n) = (n-1)!$. A Hamiltonian path of $G_w$ is a linear order of $V$ and its weight is the product of the weights of its $n-1$ edges corresponding to two consecutive vertices in the linear order. Let lin$(G_w)$ be the sum of the weights of all Hamiltonian paths of $G_w$, with the convention that lin$(G_w) = 1$ if $n = 1$. Clearly, lin$(K_n) = n!$. \medskip \noindent Let us put $$ \hbox{cyc}_{G_w}(\nu) \; := \sum_{\emptyset \subset V' \subseteq V} \hbox{cyc}(G_w[V']) \cdot \nu^{V'}, \quad \hbox{lin}_{G_w}(\nu) \; := \sum_{\emptyset \subset V' \subseteq V} \hbox{lin}(G_w[V']) \cdot \nu^{V'}. $$ Considering the infinite graph $K_{\infty}$ yields $$ \sum_{n=1}^{\infty} \hbox{cyc}(K_n) \cdot V^n/n! \; = \; -\log (1-V), \quad \sum_{n=1}^{\infty} \hbox{lin}(K_n) \cdot V^n/n! \; = \; \frac{V}{1-V}. $$ Usually (in undirected graphs) one does not distinguish between the two different directions of Hamiltonian cycles or paths. In this sense cyc$_{G_w}(\nu)$ and lin$_{G_w}(\nu)$ count them ``twice''. Now we can prove our generalization of the Mehler formula. \medskip \noindent {\bf Theorem.} Using the Hadamard product $*$ we have: $$\openup2pt\eqalign{ &\exp \bigl[ xV-E_w \bigr] \; * \; \exp \bigl[ yV-E_w \bigr] \cr &= \; \exp \bigl[ \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(\nu) + \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(-\nu) \bigr] \; \cdot \; \cr & \quad \;\, \exp \bigl[ \hbox{$-(\frac{x-y}{2})^2$} \cdot \hbox{lin}_{G_w}(\nu) \hbox{$-(\frac{x+y}{2})^2$} \cdot \hbox{lin}_{G_w}(-\nu) \bigr]. \cr }$$ \medskip \noindent {\bf Proof.} Two matchings of $G_w$ to be considered in the left hand side of the theorem provide a partition of $V$ into even Hamiltonian cycles (to be counted ``twice'', because the matchings can be interchanged), even (according to the number of vertices) Hamiltonian paths (to be counted with the factor $-x^2$ or $-y^2$, because the number of edges of the paths is odd) and odd Hamiltonian paths (to be counted with the factor $2xy$). Thus the left hand side is equal to $$\openup2pt\eqalign{ &\exp \biggl[\frac{\hbox{cyc}_{G_w}(\nu) + \hbox{cyc}_{G_w}(-\nu)}{4} \cdot 2 \biggr] \; \cdot \cr &\exp \biggl[\frac{\hbox{lin}_{G_w}(\nu) + \hbox{lin}_{G_w}(-\nu)}{4} \cdot (-x^2-y^2) \biggr] \; \cdot \cr &\exp \biggl[\frac{\hbox{lin}_{G_w}(\nu) - \hbox{lin}_{G_w}(-\nu)}{4} \cdot 2xy \biggr]. \cr }$$ But this is precisely the right hand side of the theorem.\qeda \eject \noindent Specializing to $K_{\infty}$ yields the Mehler formula. \medskip \noindent {\bf Corollary (Mehler).} $$ 1+\sum_{n=1}^{\infty} \mu(K_n,x)\mu(K_n,y) \cdot V^n/n! \; = \; \hbox{$\frac{1}{\sqrt{1-V^2}}$} \cdot \exp \bigl[ \hbox{$(\frac{x+y}{2})^2$} \cdot \hbox{$\frac{V}{1+V}$} - \hbox{$(\frac{x-y}{2})^2$} \cdot \hbox{$\frac{V}{1-V}$} \bigr].\qeda $$ \bigskip \noindent Replacing $y$ in the previous theorem by the complex conjugate number $\overline{x}$ yields the following corollary. \medskip \noindent {\bf Corollary.} $$\openup2pt\eqalign{ &\exp \bigl[ xV-E_w \bigr] \; * \; \exp \bigl[ \overline{x}V-E_w \bigr] \cr &= \; \exp \bigl[ \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(\nu) + \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(-\nu) \bigr] \; \cdot \; \cr & \quad \;\, \exp \bigl[ (\Im m \; x)^2 \cdot \hbox{lin}_{G_w}(\nu) -(\Re e \; x)^2 \cdot \hbox{lin}_{G_w}(-\nu) \bigr] \cr &= \; \exp \bigl[ (\Im m \; x)^2 \cdot \hbox{lin}_{G_w}(\nu) \bigr] \; \cdot \; \Bigl( \exp \bigl[ (\Re e \; x)V-E_w \bigr] \; * \; \exp \bigl[ (\Re e \; x)V-E_w \bigr] \Bigr). \cr }$$ {\it Therefore $|\mu(G_w,x)|^2 \; \ge \; [(\Im m \; x)^2]^n + 2W\cdot[(\Im m \; x)^2]^{n-1}$ for every $x \in {\bb C}$, where $W$ is the sum of the weights of all edges of $G_w$. In particular, all zeros of $\mu(G_w,x)$ are real.\qeda} \bigskip We finish this article by considering a common generalization of the matching polynomial and the classical rook polynomial. Thus we do not just have our weighted graph $G'_w = (V',E'_w)$, but also a bipartite graph $G''_w = (V',V'';E''_w)$. In other words, we have a graph $G_w = (V,E_w)$ with vertex set $V := V' \uplus V''$, edge set $E_w := E'_w \uplus E''_w$ and, in particular, no edges between vertices of $V''$. The weights of the edges of $G'_w$ are still assumed to be positive, whereas the weights of the edges of $G''_w$ are supposed to be such that for each $v'' \in V''$ the weights of the edges incident with $v''$ all have the same sign, i.e.~they are all positive or all negative. Let $\exp[xV'+V''-E'_w-E''_w]$ be the generating function of our generalized matching polynomials, and let cyc$_{G_w}(\nu)$ count the Hamiltonian cycles ``twice''. Moreover, let lin$_{G_w}(\nu)$, lin'$_{G_w}(\nu)$, lin''$_{G_w}(\nu)$ count the Hamiltonian paths ``twice'' which have both endpoints in $V'$, one endpoint in $V'$ and one endpoint in $V''$, both endpoints in $V''$, respectively. (Note that lin$_{G_w}(\nu)$ is nonnegative by our restrictions on the weights.) \medskip \noindent {\bf Theorem.} $$\openup2pt\eqalign{ &\exp \bigl[ xV'+V''-E'_w-E''_w \bigr] \; * \; \exp \bigl[ yV'+V''-E'_w-E''_w \bigr] \cr &= \; \exp \bigl[ \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(\nu) + \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(-\nu) \bigr] \; \cdot \; \cr & \quad \;\, \exp \bigl[ \hbox{$-(\frac{x-y}{2})^2$} \cdot \hbox{lin}_{G_w}(\nu) \hbox{$-(\frac{x+y}{2})^2$} \cdot \hbox{lin}_{G_w}(-\nu) \bigr] \; \cdot \; \cr & \quad \;\, \exp \bigl[ \hbox{$-\frac{x+y}{2}$} \cdot \hbox{lin'}_{G_w}(-\nu) \bigr] \; \cdot \; \exp \bigl[-\hbox{lin''}_{G_w}(-\nu) \bigr]. \cr }$$ \medskip \noindent {\bf Proof.} Clearly, both sides of the equality are equal to $$\openup2pt\eqalign{ &\exp \biggl[\frac{\hbox{cyc}_{G_w}(\nu) + \hbox{cyc}_{G_w}(-\nu)}{4} \cdot 2 \biggr] \; \cdot \cr &\exp \biggl[\frac{\hbox{lin}_{G_w}(\nu) + \hbox{lin}_{G_w}(-\nu)}{4} \cdot (-x^2-y^2) \biggr] \; \cdot \; \exp \biggl[\frac{\hbox{lin}_{G_w}(\nu) - \hbox{lin}_{G_w}(-\nu)}{4} \cdot 2xy \biggr] \; \cdot \; \cr &\exp \biggl[\frac{\hbox{lin'}_{G_w}(\nu) + \hbox{lin'}_{G_w}(-\nu)}{4} (-x-y) \biggr] \; \cdot \; \exp \biggl[\frac{\hbox{lin'}_{G_w}(\nu) - \hbox{lin'}_{G_w}(-\nu)}{4} (x+y) \biggr] \; \cdot \; \cr &\exp \biggl[\frac{\hbox{lin''}_{G_w}(\nu) + \hbox{lin''}_{G_w}(-\nu)}{4} \cdot (-2) \biggr] \; \cdot \; \exp \biggl[\frac{\hbox{lin''}_{G_w}(\nu) - \hbox{lin''}_{G_w}(-\nu)}{4} \cdot 2 \biggr].\qeda \cr }$$ \bigskip \medskip \noindent {\bf Corollary.} $$\openup2pt\eqalign{ &\exp \bigl[ xV'+V''-E'_w-E''_w \bigr] \; * \; \exp \bigl[ \overline{x}V'+V''-E'_w-E''_w \bigr] \cr &= \; \exp \bigl[ \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(\nu) + \hbox{$\frac{1}{2}$} \cdot \hbox{cyc}_{G_w}(-\nu) \bigr] \; \cdot \; \cr & \quad \;\, \exp \bigl[ (\Im m \; x)^2 \cdot \hbox{lin}_{G_w}(\nu) -(\Re e \; x)^2 \cdot \hbox{lin}_{G_w}(-\nu) \bigr] \; \cdot \; \cr & \quad \;\, \exp \bigl[-(\Re e \; x) \cdot \hbox{lin'}_{G_w}(-\nu) \bigr] \; \cdot \; \exp \bigl[-\hbox{lin''}_{G_w}(-\nu) \bigr] \cr &= \; \exp \bigl[ (\Im m \; x)^2 \cdot \hbox{lin}_{G_w}(\nu) \bigr] \; \cdot \; \cr & \quad \;\; \Bigl( \exp \bigl[ (\Re e \; x)V'+V''-E'_w-E''_w \bigr] \; * \; \exp \bigl[ (\Re e \; x)V'+V''-E'_w-E''_w \bigr] \Bigr). \cr }$$ {\it Since} $\hbox{lin}_{G_w}(\nu)$ {\it is nonnegative, all zeros of our generalized matching polynomial are real.\qeda} \bigskip \bigskip \noindent {\it Acknoledgements:} \quad First of all, I should like to thank cordially D.~Foata to have made the redaction of this article possible by inviting me to the IRMA in Strasbourg and by explaining to me his combinatorial proof of the Mehler formula. His help and support are undescribable. I also want to express my gratitude to A.~Frank for his recommendation of the beautiful book [3] (otherwise [7], chapter 3.1, would not exist), and especially to E.~Triesch (without him [7] would not exist). \vfill \eject %%%%%%%%%%%%%%%%%%%%%%% %% BIBLIOGRAPHIE %% %%%%%%%%%%%%%%%%%%%%%%% \centerline{\tenbf References} \bigskip \medskip {\baselineskip=9pt\tenrm \item{[1]} {\sc G.~E.~Andrews, R.~Askey, R.~Roy:} {\it Special Functions,} Encyclopedia of mathematics and its applications, Vol.~71, Cambridge University Press, 1999. \smallskip \item{[2]} {\sc D.~Foata:} A combinatorial proof of the Mehler formula, {\it J.~Combinatorial Theory Ser.~A,} {\bf 24} (1978), 367-376. \smallskip \item{[3]} {\sc C.~D.~Godsil:} {\it Algebraic Combinatorics,} Chapman \& Hall, 1993. \smallskip \item{[4]} {\sc C.~D.~Godsil:} Hermite polynomials and a duality relation for matchings polynomials, {\it Combinatorica,} {\bf 1} (1981), 257-262. \smallskip \item{[5]} {\sc O.~J.~Heilmann, E.~H.~Lieb:} Theory of monomer-dimer systems, {\it Comm. Math.~Physics,} {\bf 25} (1972), 190-232. \smallskip \item{[6]} {\sc C.~Itzykson, J.-B.~Zuber:} Matrix integration and combinatorics of modular groups, {\it Comm.~Math.~Physics,} {\bf 134} (1990), 197-207. \smallskip \item{[7]} {\sc B.~Lass:} {\it Funktionen z\"{a}hlen,} Diplomarbeit, 1997. \smallskip \item{[8]} {\sc L.~Lov\'asz:} {\it Combinatorial Problems and Exercises,} Akad\'emiai Kiad\'o, 1993. \smallskip \item{[9]} {\sc G.~Viennot:} {\it Une th\'eorie combinatoire des polyn\^omes orthogonaux g\'en\'eraux,} Notes de con\-f\'erences donn\'ees \`a l'Universit\'e du Qu\'ebec \`a Montr\'eal, 1983. \smallskip } \bigskip \bigskip \bigskip \noindent{\bf Bodo Lass} \vskip 6pt {\parindent=0mm {\it Lehrstuhl II f\"{u}r Mathematik, RWTH Aachen, Templergraben 55, D-52062 Aachen, Germany} \medskip lass@math2.rwth-aachen.de \par} \end