%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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 %% %%%%%%%%%%%%%%%%%%%%%%%% % le fichier grille \def\Grille{\setbox13=\vbox to 5mm{\hrule width 110mm\vfill} \setbox13=\vbox{\offinterlineskip \copy13\copy13\copy13\copy13\copy13\copy13\copy13\copy13 \copy13\copy13\copy13\copy13\box13\hrule width 110mm} \setbox14=\hbox to 5mm{\vrule height 65mm\hfill} \setbox14=\hbox{\copy14\copy14\copy14\copy14\copy14\copy14 \copy14\copy14\copy14\copy14\copy14\copy14\copy14\copy14 \copy14\copy14\copy14\copy14\copy14\copy14\copy14\copy14\box14} \ht14=0pt\dp14=0pt\wd14=0pt \setbox13=\vbox to 0pt{\vss\box13\offinterlineskip\box14} \wd13=0pt\box13} \def\grille{\noalign{\nointerlineskip\Grille\nointerlineskip}} %------------------------------------------------------------------ \def\fleche(#1,#2)\dir(#3,#4)\long#5{% \noalign{\nointerlineskip\leftput(#1,#2){\vector(#3,#4){#5}}\nointerlineskip}} %------------------------------------------------------------------ \def\diagram#1{\def\normalbaselines{\baselineskip=0pt\lineskip=5pt} \matrix{#1}} \def\hfl#1#2#3{\smash{\mathop{\hbox to#3{\rightarrowfill}}\limits ^{\scriptstyle#1}_{\scriptstyle#2}}} \def\gfl#1#2#3{\smash{\mathop{\hbox to#3{\leftarrowfill}}\limits ^{\scriptstyle#1}_{\scriptstyle#2}}} \def\vfl#1#2#3{\llap{$\scriptstyle #1$} \left\downarrow\vbox to#3{}\right.\rlap{$\scriptstyle #2$}} %------------------------------------------------------------------ \message{`lline' & `vector' macros from LaTeX} \catcode`@=11 \def\{{\relax\ifmmode\lbrace\else$\lbrace$\fi} \def\}{\relax\ifmmode\rbrace\else$\rbrace$\fi} \def\newcount{\alloc@0\count\countdef\insc@unt} \def\newdimen{\alloc@1\dimen\dimendef\insc@unt} \def\newwrite{\alloc@7\write\chardef\sixt@@n} \newwrite\@unused \newcount\@tempcnta \newcount\@tempcntb \newdimen\@tempdima \newdimen\@tempdimb \newbox\@tempboxa \def\@spaces{\space\space\space\space} \def\@whilenoop#1{} \def\@whiledim#1\do #2{\ifdim #1\relax#2\@iwhiledim{#1\relax#2}\fi} \def\@iwhiledim#1{\ifdim #1\let\@nextwhile=\@iwhiledim \else\let\@nextwhile=\@whilenoop\fi\@nextwhile{#1}} \def\@badlinearg{\@latexerr{Bad \string\line\space or \string\vector \space argument}} \def\@latexerr#1#2{\begingroup \edef\@tempc{#2}\expandafter\errhelp\expandafter{\@tempc}% %% error help message pieces. \def\@eha{Your command was ignored. ^^JType \space I \space to replace it with another command,^^Jor \space \space to continue without it.} \def\@ehb{You've lost some text. \space \@ehc} \def\@ehc{Try typing \space \space to proceed.^^JIf that doesn't work, type \space X \space to quit.} \def\@ehd{You're in trouble here. \space\@ehc} \typeout{LaTeX error. \space See LaTeX manual for explanation.^^J \space\@spaces\@spaces\@spaces Type \space H \space for immediate help.}\errmessage{#1}\endgroup} \def\typeout#1{{\let\protect\string\immediate\write\@unused{#1}}} % line & circle fonts \font\tenln = line10 \font\tenlnw = linew10 %\font\tencirc = circle10 %\font\tencircw = circlew10 \newdimen\@wholewidth \newdimen\@halfwidth \newdimen\unitlength \unitlength =1pt %\newbox\@picbox %\newdimen\@picht \def\thinlines{\let\@linefnt\tenln \let\@circlefnt\tencirc \@wholewidth\fontdimen8\tenln \@halfwidth .5\@wholewidth} \def\thicklines{\let\@linefnt\tenlnw \let\@circlefnt\tencircw \@wholewidth\fontdimen8\tenlnw \@halfwidth .5\@wholewidth} \def\linethickness#1{\@wholewidth #1\relax \@halfwidth .5\@wholewidth} \newif\if@negarg \def\lline(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax \@linelen=#3\unitlength \ifnum\@xarg =0 \@vline \else \ifnum\@yarg =0 \@hline \else \@sline\fi \fi} \def\@sline{\ifnum\@xarg< 0 \@negargtrue \@xarg -\@xarg \@yyarg -\@yarg \else \@negargfalse \@yyarg \@yarg \fi \ifnum \@yyarg >0 \@tempcnta\@yyarg \else \@tempcnta -\@yyarg \fi \ifnum\@tempcnta>6 \@badlinearg\@tempcnta0 \fi \setbox\@linechar\hbox{\@linefnt\@getlinechar(\@xarg,\@yyarg)}% \ifnum \@yarg >0 \let\@upordown\raise \@clnht\z@ \else\let\@upordown\lower \@clnht \ht\@linechar\fi \@clnwd=\wd\@linechar \if@negarg \hskip -\wd\@linechar \def\@tempa{\hskip -2\wd\@linechar}\else \let\@tempa\relax \fi \@whiledim \@clnwd <\@linelen \do {\@upordown\@clnht\copy\@linechar \@tempa \advance\@clnht \ht\@linechar \advance\@clnwd \wd\@linechar}% \advance\@clnht -\ht\@linechar \advance\@clnwd -\wd\@linechar \@tempdima\@linelen\advance\@tempdima -\@clnwd \@tempdimb\@tempdima\advance\@tempdimb -\wd\@linechar \if@negarg \hskip -\@tempdimb \else \hskip \@tempdimb \fi \multiply\@tempdima \@m \@tempcnta \@tempdima \@tempdima \wd\@linechar \divide\@tempcnta \@tempdima \@tempdima \ht\@linechar \multiply\@tempdima \@tempcnta \divide\@tempdima \@m \advance\@clnht \@tempdima \ifdim \@linelen <\wd\@linechar \hskip \wd\@linechar \else\@upordown\@clnht\copy\@linechar\fi} %\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi %\vrule \@height \@halfwidth \@depth \@halfwidth \@width %\@linelen \ifnum \@xarg <0 \hskip -\@linelen \fi} \def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi \vrule height \@halfwidth depth \@halfwidth width \@linelen \ifnum \@xarg <0 \hskip -\@linelen \fi} \def\@getlinechar(#1,#2){\@tempcnta#1\relax\multiply\@tempcnta 8 \advance\@tempcnta -9 \ifnum #2>0 \advance\@tempcnta #2\relax\else \advance\@tempcnta -#2\relax\advance\@tempcnta 64 \fi \char\@tempcnta} \def\vector(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax \@linelen=#3\unitlength \ifnum\@xarg =0 \@vvector \else \ifnum\@yarg =0 \@hvector \else \@svector\fi \fi} \def\@hvector{\@hline\hbox to 0pt{\@linefnt \ifnum \@xarg <0 \@getlarrow(1,0)\hss\else \hss\@getrarrow(1,0)\fi}} \def\@vvector{\ifnum \@yarg <0 \@downvector \else \@upvector \fi} \def\@svector{\@sline \@tempcnta\@yarg \ifnum\@tempcnta <0 \@tempcnta=-\@tempcnta\fi \ifnum\@tempcnta <5 \hskip -\wd\@linechar \@upordown\@clnht \hbox{\@linefnt \if@negarg \@getlarrow(\@xarg,\@yyarg) \else \@getrarrow(\@xarg,\@yyarg) \fi}% \else\@badlinearg\fi} \def\@getlarrow(#1,#2){\ifnum #2 =\z@ \@tempcnta='33\else \@tempcnta=#1\relax\multiply\@tempcnta \sixt@@n \advance\@tempcnta -9 \@tempcntb=#2\relax\multiply\@tempcntb \tw@ \ifnum \@tempcntb >0 \advance\@tempcnta \@tempcntb\relax \else\advance\@tempcnta -\@tempcntb\advance\@tempcnta 64 \fi\fi\char\@tempcnta} \def\@getrarrow(#1,#2){\@tempcntb=#2\relax \ifnum\@tempcntb < 0 \@tempcntb=-\@tempcntb\relax\fi \ifcase \@tempcntb\relax \@tempcnta='55 \or \ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta 24 \advance\@tempcnta -6 \else \ifnum #1=3 \@tempcnta=49 \else\@tempcnta=58 \fi\fi\or \ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta 24 \advance\@tempcnta -3 \else \@tempcnta=51\fi\or \@tempcnta=#1\relax\multiply\@tempcnta \sixt@@n \advance\@tempcnta -\tw@ \else \@tempcnta=#1\relax\multiply\@tempcnta \sixt@@n \advance\@tempcnta 7 \fi\ifnum #2<0 \advance\@tempcnta 64 \fi \char\@tempcnta} \def\@vline{\ifnum \@yarg <0 \@downline \else \@upline\fi} \def\@upline{\hbox to \z@{\hskip -\@halfwidth \vrule width \@wholewidth height \@linelen depth \z@\hss}} \def\@downline{\hbox to \z@{\hskip -\@halfwidth \vrule width \@wholewidth height \z@ depth \@linelen \hss}} \def\@upvector{\@upline\setbox\@tempboxa\hbox{\@linefnt\char'66}\raise \@linelen \hbox to\z@{\lower \ht\@tempboxa\box\@tempboxa\hss}} \def\@downvector{\@downline\lower \@linelen \hbox to \z@{\@linefnt\char'77\hss}} %INITIALIZATION \thinlines \newcount\@xarg \newcount\@yarg \newcount\@yyarg \newcount\@multicnt \newdimen\@xdim \newdimen\@ydim \newbox\@linechar \newdimen\@linelen \newdimen\@clnwd \newdimen\@clnht \newdimen\@dashdim \newbox\@dashbox \newcount\@dashcnt \catcode`@=12 % macros supplementaires (J.D.) \newbox\tbox \newbox\tboxa %\def\picbox(#1,#2,#3)#4{\setbox\tbox=\hbox{#4}% % \ht\tbox=#1 \wd\tbox=#2 \dp\tbox=#3 \box\tbox} \def\leftzer#1{\setbox\tbox=\hbox to 0pt{#1\hss}% \ht\tbox=0pt \dp\tbox=0pt \box\tbox} \def\rightzer#1{\setbox\tbox=\hbox to 0pt{\hss #1}% \ht\tbox=0pt \dp\tbox=0pt \box\tbox} \def\centerzer#1{\setbox\tbox=\hbox to 0pt{\hss #1\hss}% \ht\tbox=0pt \dp\tbox=0pt \box\tbox} % sytaxe: \image(hauteur totale reservee, distance % verticale de l'origine par rapport au bas de % la place reservee){materiel a inserer} % L'origine est toujours centre horizontalement % \def\image(#1,#2)#3{\vbox to #1{\offinterlineskip \vss #3 \vskip #2}} % \leftput place le materiel avec son point de reference % en #1,#2 unites \unitlength % De meme pour \centerput et \rightput \def\leftput(#1,#2)#3{\setbox\tboxa=\hbox{% \kern #1\unitlength \raise #2\unitlength\hbox{\leftzer{#3}}}% \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa} \def\rightput(#1,#2)#3{\setbox\tboxa=\hbox{% \kern #1\unitlength \raise #2\unitlength\hbox{\rightzer{#3}}}% \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa} \def\centerput(#1,#2)#3{\setbox\tboxa=\hbox{% \kern #1\unitlength \raise #2\unitlength\hbox{\centerzer{#3}}}% \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa} \unitlength=1mm \let\cput=\centerput \def\put(#1,#2)#3{\noalign{\nointerlineskip \centerput(#1,#2){$#3$} \nointerlineskip}} % fin du fichier grille -------------------- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%% %% AUTHOR ON EVEN PAGES %% %%%%%%%%%%%%%%%%%%%%%%%%%%%% \auteurcourant{\eightbf BODO LASS \hfill} %%%%%%%%%%%%%%%%%%%%%%%%%% %% TITLE ON ODD PAGES %% %%%%%%%%%%%%%%%%%%%%%%%%%% \titrecourant{\hfill\eightbf The N-dimensional matching polynomial} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \vskip 1.5cm %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%% %% TITEL %% %%%%%%%%%%%%% \centerline {\twelvebf The N-dimensional matching polynomial } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Subject Classification %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \parindent=-1mm\footnote{}{ {\it Key words:} matching polynomials, complementary graph, semi-invariants, Gaussian integrals, Wick products, Feynman diagrams, Bargmann-Segal transform } \bigskip %%%%%%%%%%% %% NAME %% %%%%%%%%%%% \centerline{\tenrm Bodo Lass} \medskip \centerline{\eightit Institut Girard Desargues (UMR 5028 du CNRS), Universit\'e Claude Bernard (Lyon 1)} \centerline{\eightit B\^at Jean Braconnier, 43, Bd du 11 Novembre 1918, F-69622 Villeurbanne Cedex, France} \centerline{\eightrm Email: lass@igd.univ-lyon1.fr} \bigskip \medskip \centerline{\it To P.~Cartier and A.~K.~Zvonkin} \bigskip \medskip %%%%%%%%%%%%%%%% %% ABSTRACT %% %%%%%%%%%%%%%%%% {\parindent=3mm \narrower {\eightrm Heilmann et Lieb ont introduit le polyn\^ome de couplage $\scs \mu(G,x)$ d'un graphe $\scs G = (V,E)$. Nous prolongeons leur d\'efinition en munissant chaque sommet de~$\scs G$ d'une forme lin\'eaire \hbox{$\scs N$-di\-men\-sionnelle} (ou bien d'un vecteur) et chaque ar\^ete d'une forme sym\'etrique bilin\'eaire. On attache donc \`a tout \hbox{$\scs r$-couplage} de~$\scs G$ le produit des formes lin\'eaires des sommets qui ne sont pas satur\'es par le couplage, multipli\'e par le produit des poids des $\scs r$ ar\^etes du couplage, o\`u le poids d'une ar\^ete est la valeur de sa forme \'evalu\'ee sur les deux vecteurs de ses extr\'emit\'es. En multipliant par $\scs (-1)^r$ et en sommant sur tous les couplages, nous ob\-te\-nons notre polyn\^ome de couplage \hbox{$\scs N$-dimensionnel}. Si $\scs N = 1$, le th\'eor\`eme principal de l'article de Heilmann et Lieb affirme que tous les z\'eros de $\scs \mu(G,x)$ sont r\'eels. Si $\scs N = 2$, cependant, nous avons trouv\'e des graphes exceptionnels o\`u il n'y a aucun z\'ero r\'eel, m\^eme si chaque ar\^ete est munie du produit scalaire canonique. Toutefois, la th\'eorie de la dualit\'e d\'evelopp\'ee dans~[12] reste valable en $\scs N$~dimensions. Elle donne notamment une nouvelle interpr\'etation \`a la trans\-formation de Bargmann-Segal, aux diagrammes de Feynman et aux produits de~Wick. Heilmann and Lieb have introduced the matching polynomial $\scs \mu(G,x)$ of a graph $\scs G = (V,E)$. We extend their definition by associating to every vertex of~$\scs G$ an \hbox{$\scs N$-dimensional} linear form (or a vector) and to every edge a symmetric bilinear form. For every \hbox{$\scs r$-matching} of~$\scs G$ we define its weight as the product of the linear forms of the vertices not covered by the matching, multiplied by the product of the weights of the $\scs r$ edges of the matching, where the weight of an edge is the value of its form evaluated at the two vectors of its end points. Multiplying by $\scs (-1)^r$ and summing over all matchings, we get our \hbox{$\scs N$-dimensional} matching polynomial. If $\scs N = 1$, the Heilmann-Lieb theorem affirms that all zeroes of $\scs \mu(G,x)$ are real. If $\scs N = 2$, however, there are exceptional graphs whithout any real zero at all, even if the canonical scalar product is associated to every edge. Nevertheless, the duality theory developed in~[12] remains valid in $\scs N$~dimensions. In particular, it brings new light to the Bargmann-Segal transform, to the Feynman diagrams, and to the Wick products. } } \vskip1.5pt \parindent=3mm \vskip 5mm %%%%%%%%%%%% %% TEXT %% %%%%%%%%%%%% \centerline{\bf 1. Introduction} \medskip Let $V$ be a finite set of cardinality~$n$. A graph $G = (V,E)$ is called simple if and only if the set of its edges~$E$ is a subset of ${V \choose 2}$, the family of all 2-element subsets of $V$. For such graphs we define the {\it complement} by $\overline{G} := (V, \overline{E})$ with $\overline{E} := {V \choose 2} \backslash E$. For every $r \ge 0$, an $r$-{\it matching} in~$G$ is a set of $r$~edges of~$G$, no two of which have a vertex in common. If $r = n/2$, then the matching is called {\it perfect}. Moreover, let us consider a Euclidean space~$\bf{R}$ of dimension~$N$, ${\bf R} = {\bb R}^N$, with its canonical scalar product $\langle x,y \rangle = \sum_{i=1}^{N} x_iy_i$ (remember that $n = |V|$ is the number of vertices of~$G$). Let $e_1, \dots, e_N$ be the canonical (orthonormal) basis of~$\bf{R}$. We use it to interpret polynomials and partial derivatives (or $\nabla$) in the usual way. Moreover, let $\langle x,y \rangle_P := \langle x,Py \rangle$, $P = P^T$ and $P > 0$, be an additional scalar product. Let us attach to each vertex $v \in V$ of our graph $G = (V,E)$ a vector $a_v \in {\bf R}$, and to each edge $\{u,v\} \in E$ the scalar product $\langle a_u,a_v \rangle_P$. We use the notation $a_PG = (aV,a_PE)$ for this ``decorated'' graph. Let us look at a matching of~$a_PG$. We multiply the product of the scalar products of the edges of our matching and the product of the scalar products $\langle x,a_v \rangle_P$, $x \in {\bf R}$, of the vertices of~$a_PG$ which are not covered by any edge of the matching. This gives a homogeneous polynomial of degree $n-2r$ ($n = |V|$), if the matching contains $r$ edges. If we multiply this polynomial by $(-1)^r$ and sum these expressions over all matchings of~$a_PG$, we get the {\it signed $N$-dimensional matching polynomial\/} $\mu(a_PG,x)$. If we do not multiply by $(-1)^r$ before summing, we get the {\it unsigned $N$-dimensional matching polynomial\/} $\overline{\mu}(a_PG,x)$. In the sequel, if we say matching polynomial without any further attribute, then we mean the signed one. Since every vector $a_v$, $v \in V$, appears in each homogeneous polynomial of degree $n-2r$ precisely once (in a factor $\langle a_u,a_v \rangle_P$ if $v$ is covered by the matching and in a factor $\langle x,a_v \rangle_P$ otherwise), the polynomials $\mu(a_PG,x)$ and $\overline{\mu}(a_PG,x)$ are linear in the vectors $a_v$ (and equal to zero, if there exists a $v \in V$ such that $a_v = 0$). Moreover, they satisfy the obvious relation $$ \mu(a_PG,x) \; = \; (-i)^n \cdot \overline{\mu}(a_PG,i \cdot x), \qquad |V| \; = \; n, \quad i \; = \; \sqrt{-1}. $$ \medskip \noindent {\sc Example 1.1.} Let $K_n = (V,{V \choose 2})$ be the complete graph on $n$~vertices such that its complementary graph $\overline{K_n} = (V,\emptyset)$ has no edge at all. Let us attach to each $v \in V$ a vector $a_v \in {\bf R}$. Then we have the following expressions for the matching polynomials of the two complementary decorated graphs $a_PK_n$ and $\overline{a_PK_n}$: $$\openup2pt\eqalign{ \mu(\overline{a_PK_n},x) \; = \; &\overline{\mu}(\overline{a_PK_n},x) \; = \; \prod_{v \in V} \langle x,a_v\rangle_P; \cr \mu(a_PK_2,x) \; = \; &\langle x,a_u\rangle_P\langle x,a_v\rangle_P - \langle a_u,a_v\rangle_P,\cr \overline{\mu}(a_PK_2,x) \; = \; &\langle x,a_u\rangle_P\langle x,a_v\rangle_P + \langle a_u,a_v\rangle_P,\cr \mu(a_PK_3,x) \; = \; &\langle x,a_u\rangle_P\langle x,a_v\rangle_P\langle x,a_w\rangle_P - \langle x,a_u\rangle_P\langle a_v,a_w\rangle_P \cr &-\langle x,a_v\rangle_P\langle a_u,a_w\rangle_P - \langle x,a_w\rangle_P\langle a_u,a_v\rangle_P, \quad \hbox{etc.}\cr }$$ \bigskip \noindent {\sc Remark 1.1.} In physics, the polynomial $\mu(a_PK_n,x)$ is called {\it Wick} (or {\it Hermite}) {\it polynomial}. It is denoted by $\Phi (x|a_1, \dots, a_n)$ or by $\,:\!\!\prod_{v \in V} \langle x,a_v\rangle_P\!\!:\,$ or by $[\prod_{v \in V} \langle x,a_v\rangle_P]^{\sharp}$ (see~[3],[6],[15]). \bigskip Let $G = (V,E)$ and $\overline{G} := (V, \overline{E})$ be {\it arbitrary} complementary graphs. Let us attach to every $v \in V$ a vector $a_v \in {\bf R}$ in order to get two complementary decorated graphs, namely $a_PG = (aV,a_PE)$ and $\overline{a_PG} = (aV,\overline{a_PE})$ (in the classical one-dimensional case, we have $a_v = 1$ for every $v \in V$ as well as $P = 1$). A priori, it is not clear at all whether the matching polynomials $\mu(\overline{a_PG},x)$ and $\overline{\mu}(\overline{a_PG},x)$ of the complementary graph $\overline{a_PG}$ are determined by the matching polynomials $\mu(a_PG,x)$ and $\overline{\mu}(a_PG,x)$ of the graph $a_PG$ itself. Lov\'asz~[14, 5.18] and Godsil~[7], [8] have established such a result in the one-dimensional case. It seems to be difficult, however, to generalize their proofs. Fortunately, the proofs presented in~[12] can be generalized almost without any modification. Indeed, we prove that $\overline{\mu}(\overline{a_PG},x)$ is the Bargmann-Segal-Wiener transform of $\mu(a_PG,x)$, and $\mu(\overline{a_PG},x)$ is the Wick transform of $\overline{\mu}(a_PG,x)$, i.e., $$ \overline{\mu}(\overline{a_PG},x) \; = \; [\mu(a_PG,x)]^{\flat}, \qquad \quad \mu(\overline{a_PG},x) \; = \; [\overline{\mu}(a_PG,x)]^{\sharp}. $$ More precisely, we establish the identities $$\openup2pt\eqalign{ \overline{\mu}(\overline{a_PG},x) \; &= \; \sum_{n=0}^{\infty} {1 \over n!} \int_{\bf{R}} \mu(a_PG,z) \cdot \mu(x_PK_n,z) \cdot e^{-\langle z,z\rangle_P/2} \cdot d_Pz \cr &= \; \int_{\bf{R}} e^{-\langle z-x,z-x\rangle_P/2} \cdot \mu(a_PG,z) \cdot d_Pz \cr &= \; e^{-\langle x,x\rangle_P/2} \cdot \mu(a_PG,\nabla_P) \cdot e^{\langle x,x\rangle_P/2} \cr &= \; \exp[\triangle_P/2] \cdot \mu(a_PG,x), \cr }$$ as well as $$\openup2pt\eqalign{ \mu(\overline{a_PG},x) \; &= \; e^{\langle x,x\rangle_P/2} \cdot \overline{\mu}(a_PG,-\nabla_P) \cdot e^{-\langle x,x\rangle_P/2} \cr &= \; \exp[- \triangle_P/2] \cdot \overline{\mu}(a_PG,x), \cr }$$ where $$ d_Pz \; := \; \sqrt{\det(P)/(2\pi)^N} \cdot d^Nz \qquad (P \; = \; 2\pi \cdot Id \quad \Rightarrow \quad d_Pz \; = \; d^Nz), $$ $$ \nabla_P \; := \; P^{-1} \nabla, \qquad \triangle_P \; := \; \langle \nabla_P,\nabla_P\rangle_P \; = \; \langle \nabla,\nabla\rangle_{P^{-1}}. $$ \medskip \noindent {\sc Remark 1.2.} The operator $\triangle_P$ is nothing else but the general form of what is called an {\it elliptic operator of second degree}. \bigskip Since the space of polynomials is generated (as a vector space) by the matching polynomials, our relations also offer an abundance of possible definitions for the Bargmann-Segal or for the Wick transformation, and one can ask the question whether all of them are well known. Indeed, during the S\'eminaire Lotharin\-gien de Combinatoire~44, Cartier~[2] has made use of the first integral formula in order to define the Bargmann-Segal transformation. He has defined the Wick transformation, however, in a totally combinatorial way with the help of the identity $\mu(a_PK_n,x) = [\prod_{v \in V} \langle x,a_v\rangle_P]^{\sharp}$. Finally, he has used the identity $\mu(a_PK_n,x) = e^{\langle x,x\rangle_P/2} \cdot \overline{\mu}(\overline{a_PK_n},-\nabla_P) \cdot e^{-\langle x,x\rangle_P/2}$ in order to define the Wick (i.e.~Hermite) polynomials. In his article~[3], which, however, treats just the one-dimensional case, he has finally proposed the second integral formula and the second differential formula in order to define the Bargmann-Segal transformation (and the second differential formula for the Wick transformation). Therefore our first differential formula is apparently new as an additional possibility to define the Bargmann-Segal transformation. At least, there cannot be any doubt that matching polynomials provide a better understanding of the respective roles of the two transformations. Last, but not least, the importance of $N$-dimensional matching polynomials is underlined by the surprising fact that the matching functions $e^{-\langle x,x\rangle_P/2}\mu(\overline{a_PG},x)$ and $e^{-\langle x,x\rangle_P/2}\mu(a_PG,x)$ are indeed Fourier transforms of each other. \medskip \noindent {\sc Example 1.2.} Let us suppose that $V = T_1 \uplus \dots \uplus T_k$, and that $K_{t_1},\dots,K_{t_k}$ are complete graphs on the vertex sets $T_1,\dots,T_k$, respectively. For the matching polynomial of the decorated graph $a_PK_{t_1} \uplus \dots \uplus o_PK_{t_k}$, we have the obvious identity $$\openup2pt\eqalign{ \mu(a_PK_{t_1} \uplus \dots \uplus o_PK_{t_k},z) \; &= \; \mu(a_PK_{t_1},z) \cdots \mu(o_PK_{t_k},z) \cr &= \; \Bigl[\prod_{v \in T_1} \langle z,a_v\rangle_P\Bigr]^{\sharp} \cdots \Bigl[\prod_{v \in T_k} \langle z,o_v\rangle_P\Bigr]^{\sharp}. \cr }$$ The case $x = 0$ of our second integral identity for the Barg\-mann-Segal transformation allows us to conclude that $$\openup2pt\eqalign{ &\overline{\mu}(\overline{a_PK_{t_1} \uplus \dots \uplus o_PK_{t_k}},0) \cr &= \; \int_{\bf{R}} \Bigl[\prod_{v \in T_1} \langle z,a_v\rangle_P\Bigr]^{\sharp} \cdots \Bigl[\prod_{v \in T_k} \langle z,o_v\rangle_P\Bigr]^{\sharp} \cdot e^{-\langle z,z\rangle_P/2} d_Pz \cr }$$ counts the (weighted) number of perfect matchings of the decorated complete multipartite graph $\overline{a_PK_{t_1} \uplus \dots \uplus o_PK_{t_k}}$. This result corresponds to Formula~3) of Section {``Diagrams''} in the recent book~[15, Chapter~2.2] and to Corollary~8.3.2 of the book~[6]. Note that the authors of these books identify all vertices of~$T_1$, all vertices of~$T_2$, \dots, and all vertices of~$T_k$, so that they have just $k$ different vertices to consider. The edges inside the blocks $T_1$, \dots, $T_k$ become loops (``self-lines'') in this way. In the main result of Section 8.3 of the book~[6] by Glimm and Jaffe, these loops carry different scalar products as described in our abstract and in Remark~3.1. The case $k = 2$ is nothing else but the orthogonality of the Wick polynomials, because the (weighted) number of perfect matchings of the decorated complete bipartite graph $\overline{a_PK_{t_1} \uplus o_PK_{t_2}}$ is equal to zero if $t_1 \ne t_2$ and is equal to the permanent per$(\langle a_u,o_v\rangle_P)$ if $t_1 = t_2$. \bigskip We prove all our main theorems with the help of the algebra of set functions. This leads to very short and conceptual proofs, whereas the classical particular cases of our results mentioned in the preceding example were established in the books by Glimm, Jaffe, Malyshev and Minlos by using partial integration, which leads to considerably longer arguments (see, for example, [15, pp.~39-41]). Set functions also contribute to a better understanding of the semi-invariants studied in probability theory, as well as of the bialgebra of partitions introduced by Lando in his article~[10]. All this is explained in the following section. Section~3, on the other hand, covers the duality theorems, which we discussed earlier in this introduction. Finally, we study the divisor div[$\mu(a_PG,x)$] in the fourth section. Originally, we had conjectured that the Heilmann--Lieb theorem affirming that all zeroes of $\mu(G,x)$ are real (if $N = 1$) can be generalized to higher dimensions. What we prove is, in fact, a theorem which imposes very restrictive conditions on the class of possible counter-examples. Although this theorem can be refined even further, by using the last theorem of~[12], there exist indeed very rare decorated graphs, the matching polynomial of which has no real zero at all, thus refuting our conjecture. We provide a family of such counter-examples. The problem of characterizing all possible counter-examples remains open. \bigskip \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%% %% Outils alg\'ebriques %% %%%%%%%%%%%%%%%%%%%%%%%%%% \centerline{\bf 2. Algebraic tools} \bigskip \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 {\it set function}, where $A$ is a {\it 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. $$ \eject \noindent 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. \bigskip \noindent {\sc Remark 2.1.} If $A$ is a field, $A[V]$ is a local Artinian ring of length~$2^{|V|}$. \bigskip \noindent {\sc Example 2.1.} The product $fg$ of two set functions $f$ and $g$ is defined, for every $V' \subseteq V$, by $$ (fg)(V') \; := \; \sum_{V' = V'' \uplus V'''} f(V'') \cdot g(V'''). $$ It follows that $$ F_{fg} (\nu) \; = \; F_f (\nu) \cdot F_g (\nu). $$ \bigskip 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 we define $$ A[V] \; := \; \lim_{\longleftarrow} A[V'], \quad V' \in F(V), $$ in order to work with the 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 indicator function of the subsets of $V$ of cardinality $1$ (the double use of $V$ for the set itself, on the one hand, and for an element of $A[V]$, on the other hand, will never cause any confusion). In the product $V^n$ each subset of cardinality $n$ occurs $n!$ times, so that $V^n/n!$ represents the indicator function of the subsets of the set $V$ of cardinality $n$. The identity $$ \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 embedding of the ring $A![[V]]$ of generating functions of exponential type (usually the variable is called $x$ instead of $V$) into our ring $A[V]$. This embedding is at the origin of (almost?) all applications of $A![[V]]$ to combinatorics, but requires the existence of an infinite combinatorial model depending just on cardinalities. Consequently, $A[V]$ gives more flexibility and allows an algebraic treatment, which perfectly reflects the classical combinatorial operations. In addition, $A[V]$ is ideally suited for computer calculations. \medskip \noindent {\sc Remark 2.2.} The ring ${\bb Z}![[V]]$ is not Noetherian, but it contains the important functions $\exp(V)$ and $\log(1+V)$. \bigskip \noindent For all $t \in A$ we put $(t \cdot \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'|} \; \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. Therefore we have an action of $A![[V]]$ on $A[V]$ via the substitution $G(F_f (\nu))$ defined for any $G \in A![[V]]$. \bigskip \noindent Finally, for every $v \in V$, we use the derivatives $\partial^v$ defined by $$ \partial^v \nu^{V'} \; := \; \openup 2pt\left\{\eqalign{ \nu^{V'}, \quad & \hbox{if} \quad v \in V', \cr 0, \; \; \quad & \hbox{otherwise.} \cr }\right. $$ The product rule $$ \partial^v [F_f (\nu) \cdot F_g (\nu)] \; = \; (\partial^v F_f (\nu)) \cdot F_g (\nu) + F_f (\nu) \cdot (\partial^v F_g (\nu)) $$ is the algebraic analogue of the most fundamental set theoretic fact: $$ v \in V' \uplus V'' \qquad \Leftrightarrow \qquad v \in V' \quad \hbox{or} \quad v \in V''. $$ The chain rule $$ \partial^v [G(F_f (\nu))] \; = \; G'(F_f (\nu)) \cdot \partial^v F_f (\nu), \quad G \in A![[V]], $$ follows immediately from the product rule. \bigskip \noindent {\sc Remark 2.3.} Under the isomorphism $A[V] \simeq A[v_1,\dots,v_n]/ \langle v_1^2,\dots,v_n^2 \rangle$, $\partial^v$ does not correspond to $\partial / \partial v_i$, but to $v_i \partial / \partial v_i$. The partial derivative $\partial / \partial v_i$ cannot be defined in $A[V]$. \eject \noindent {\sc Example 2.2.} \quad (The bialgebra of partitions) \smallskip Let $V$ be a finite set of cardinality~$n$. Lando~[10] has introduced and studied the bialgebra~$\hbox{\tengoth B}(V)$, called {\it bialgebra of partitions}. We have to associate to every $\emptyset \subset V' \subseteq V$ a variable denoted by~$(V')$. As an algebra, $\hbox{\tengoth B}(V)$ is the commutative polynomial algebra generated (over~$\bb Z$) by the $2^n - 1$ variables~$(V')$, where $e := (\emptyset)$ can be considered as a unit element. $\hbox{\tengoth B}(V)$ is graduated if we define the order of the variable~$(V')$ to be~$|V'|$. With respect to the algebra structure, the comultiplication~$\mu$ is a homomorphism, which we define by putting $$ (V')_1 \; := \; (V') \otimes e, \qquad (V')_2 \; := \; e \otimes (V'), $$ $$ \mu((V')) \; := \; (V')_1 + (V')_2 + \sum_{\emptyset \subset V'' \subset V'} (V'')_1 \, \cdot \, (V' \backslash V'')_2 $$ for every $\emptyset \subset V' \subseteq V$. An element $b \in \hbox{\tengoth B}(V)$ is called {\it primitive} if and only if $\mu(b) = b_1 + b_2 = b \otimes e + e \otimes b$. For example, $(\{v\})$ is primitive for every $v \in V$. In this context, it is very useful to consider the generating functions $$\openup2pt\displaylines{ 1 + F_V(\nu) \; := \; (\emptyset) \cdot 1 + \sum_{\emptyset \subset V' \subseteq V} (V') \cdot \nu^{V'}, \cr [ 1 + F_{V_1}(\nu) ] \; := \; [ 1 + F_V(\nu) ] \otimes e, \qquad [ 1 + F_{V_2}(\nu) ] \; := \; e \otimes [ 1 + F_V(\nu) ]. \cr }$$ They enable us to obtain an easier definition of the comultiplication, $$ \mu [ 1 + F_V(\nu) ] \; = \; [ 1 + F_{V_1}(\nu) ] \cdot [ 1 + F_{V_2}(\nu) ], $$ which allows us to conclude that $$\openup2pt\eqalign{ \mu \Bigl( \log [ 1 + F_V(\nu) ] \Bigr) \; &= \; \log \Bigl( \mu [ 1 + F_V(\nu) ] \Bigr) \; = \; \log \Bigl( [ 1 + F_{V_1}(\nu) ] \cdot [ 1 + F_{V_2}(\nu) ] \Bigr) \cr &= \; \log [ 1 + F_{V_1}(\nu) ] \, + \, \log [ 1 + F_{V_2}(\nu) ]. }$$ In other words, every coefficient of $\log [ 1 + F_V(\nu) ]$ is a primitive element of the bialgebra~$\hbox{\tengoth B}(V)$. This result is nothing else but the main theorem of the article~[10] (see also [11, Chapter~6.1.6]). \bigskip \noindent {\sc Example 2.3.} \quad (Semi-invariants) \smallskip Let $V$ be a finite set of cardinality~$n$. Let us associate to every $v \in V$ a random variable $\xi_v$, where coincidences $\xi_u = \xi_v$ for $u \ne v$ are not forbidden. In fact, they are even desirable if we want to calculate higher moments, as we will see immediately. Let us put $$ \xi V \; := \; \sum_{v \in V} \xi_v \cdot \nu^{\{v\}} \qquad \Rightarrow \qquad \exp [\xi V] \; = \; 1 + \sum_{\emptyset \subset V' \subseteq V} \Bigl( \prod_{v \in V'} \xi_v \Bigr) \cdot \nu^{V'}, $$ and let us define $$ 1+M_\xi(\nu) \; := \; \langle \exp [\xi V] \rangle \; := \; {\bb E} \bigl( \exp [\xi V] \bigr) \; = \; 1 + \sum_{\emptyset \subset V' \subseteq V} {\bb E} \Bigl( \prod_{v \in V'} \xi_v \Bigr) \cdot \nu^{V'}, $$ in order to calculate the expectations called {\it moments}. Evidently, we suppose that they are finite. We define the {\it semi-invariants} or {\it cumulants} to be the coefficients of $$ S_\xi(\nu) \; := \; \log [1+M_\xi(\nu)] $$ (see~[4, Chapter~13] or~[17, Chapter~II.12]). The reader familiar with the theory will easily see the equivalence of our definition with his own one. We remark that our algebraic tools allow us to derive some other relations between the moments and the semi-invariants, such as $$ 1+M_\xi(\nu) \; = \; \exp [S_\xi(\nu)], \qquad [1+M_\xi(\nu)] \cdot \partial^v S_\xi(\nu) \; = \; \partial^v M_\xi(\nu), $$ where the very last relation is particularly useful for efficient computer calculations. We have not found it in the literature. Suppose that $V = T_1 \uplus \dots \uplus T_k$. Let us put $\xi_{T_i} := \prod_{v \in T_i} \xi_v$ for each $i \in \{1,\dots,k\}$, and let us calculate all the moments of the family~$\{\xi_{T_i}\}$, $i = 1,\dots,k$, with the help of the semi-invariants of the family~$\{\xi_v\}$, $v \in V$. By the formula $1+M_\xi(\nu) = \exp [S_\xi(\nu)]$, we have to sum over all partitions of~$V$. Each of them consists of several {\it connected components} with respect to the partition $V = T_1 \uplus \dots \uplus T_k$, i.e., it defines a partition of the set $\{1,\dots,k\}$. Consequently, we have to sum over all partitions $\{a_1, \dots, o_1\} \uplus \dots \uplus \{a_l,\dots,o_l\} = \{1,\dots,k\}$, where the contribution of the block $\{a_1, \dots, o_1\}$, for example, is the sum over all partitions of the set $B_1 := T_{a_1} \cup \dots \cup T_{o_1}$ which are {\it connected} with respect to the partition $B_1 = T_{a_1} \uplus \dots \uplus T_{o_1}$. The contribution of the block $\{a_1, \dots, o_1\}$, however, is nothing else but one of the semi-invariants of the family~$\{\xi_{T_i}\}$, $i = 1,\dots,k$ (because of the formula $1+M_\xi(\nu) = \exp [S_\xi(\nu)]$ {\it applied to the set} $\{1,\dots,k\}$). In other words, we have established the fact that the semi-invariants of the family~$\{\xi_{T_i}\}$ can be calculated with the help of the semi-invariants of the family $\{\xi_v\}$ by summing {``over all connected partitions''}. This result was proved in~[15, pp.~30--32], by induction and some manipulation. For every $\emptyset \subset V' \subseteq V$, let us now introduce the {\it Wick polynomials} $\;:\!\!(\prod_{v \in V'} \xi_v)\!\!: \;\, = \, (\prod_{v \in V'} \xi_v)^{\sharp}\,$ by putting $$\openup2pt\eqalign{ 1 + \sum_{\emptyset \subset V' \subseteq V} \Bigl(\prod_{v \in V'} \xi_v\Bigr)^{\sharp} \cdot \nu^{V'} \; :=& \; \bigl(\exp[\xi V]\bigr)^{\sharp} \; := \; \exp[\xi V - S_\xi(\nu)] \cr =& \; {\exp[\xi V] \over 1+M_\xi(\nu)} \; = \; {\exp[\xi V] \over \langle \exp [\xi V] \rangle} \cr }$$ \eject \noindent (see~[3, Chapter~3.7] and~[15, p.~37]). It is, without doubt, the leitmotiv of this whole article to choose two set functions $E_\xi$ and $\overline{E_\xi}$ such that $$ E_\xi + \overline{E_\xi} \; = \; S_\xi(\nu). $$ The linearity of expectation implies $$\openup2pt\eqalign{ \langle \exp [\xi V - E_\xi] \rangle \; &= \; \langle \exp [\xi V] \rangle \cdot \exp[-E_\xi] \; = \; \exp[S_\xi(\nu)] \cdot \exp[- E_\xi] \cr &= \; \exp[\overline{E_\xi}]. \cr }$$ Let us suppose finally that the vector $\{\xi_v\}$ $(v \in V)$ follows a Gau\ss ian law with $\langle \xi_v \rangle = 0$ for every \hbox{$v \in V$} such that the set function $S_\xi(\nu)$ equals zero except on the subsets of~$V$ of cardinality two. Let us attach to every edge $\{u,v\}$ of the complete graph $K_n = (V,{V \choose 2})$ the weight $\langle \xi_u \xi_v \rangle$, and let us choose a partition \hbox{$E \uplus \overline{E} = {V \choose 2}$} such that $G = (V,E)$. By putting $$ E_\xi \; := \; \sum_{\{u,v\} \in E} \langle \xi_u \xi_v \rangle \cdot \nu^{\{u,v\}}, \qquad \overline{E_\xi} \; := \; \sum_{\{u,v\} \in \overline{E}} \langle \xi_u \xi_v \rangle \cdot \nu^{\{u,v\}}, $$ we get indeed $E_\xi + \overline{E_\xi} = S_\xi(\nu)$. If $E = \emptyset$, then our preceding identity implies that $\langle \prod_{v \in V} \xi_v \rangle$ counts the number of perfect matchings of the decorated graph $K_n = \big(V,{V \choose 2}\big)$. If $E$ is the set of edges both endpoints of which are in the same block of the partition $V = T_1 \uplus \dots \uplus T_k$, then $\langle \exp [\xi V - E_\xi] \rangle = \exp[\overline{E_\xi}]$ implies that $\langle (\xi_{T_1})^{\sharp} \cdots (\xi_{T_k})^{\sharp} \rangle$ counts the number of perfect matchings of the decorated complete multipartite graph $\overline{G} = (V,\overline{E})$ (see Example~1.2). These two results are nothing else but the Formulae~1) and~3) of Section {``Diagrams''} in~[15, Chapter~2.2], respectively. In the sequel, we will no longer adhere to the probabilistic vision, and we ``replace the variance--covariance matrix by a matrix of symmetric bilinear forms.'' \bigskip \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Polyn\^omes de couplage et dualit\'e % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \centerline{\bf 3. Matching polynomials and duality} \bigskip Let $a_PG = (aV,a_PE)$ and $\overline{a_PG} = (aV,\overline{a_PE})$ be two decorated complementary graphs (see the Introduction). We can now define the set functions $$ a_PE \; := \; \sum_{\{u,v\} \in E} \langle a_u,a_v \rangle_P \cdot \nu^{\{u,v\}}, \qquad \overline{a_PE} \; := \; \sum_{\{u,v\} \in \overline{E}} \langle a_u,a_v \rangle_P \cdot \nu^{\{u,v\}}. $$ We have to pay attention to the fact that, strictly speaking, the expression $$ aV \; := \; \sum_{v \in V} a_v \cdot \nu^{\{v\}} $$ does not correspond to a set function, because $\bf R$ is not a ring, but this difficulty disappears as soon as we consider scalar products such as $$ \langle x,aV\rangle_P \; = \; \sum_{v \in V} \langle x,a_v\rangle_P \cdot \nu^{\{v\}}, \qquad \langle aV,aV \rangle_P/2 \; = \; \sum_{\{u,v\} \in {V \choose 2}} \langle a_u,a_v \rangle_P \cdot \nu^{\{u,v\}} $$ ($x \in {\bf R}$). The following identity is at the origin of all results of this section. \bigskip \noindent {\sc Fundamental lemma.} {\it We have} $$\bf a_PE + \overline{a_PE} \; = \; \langle aV,aV\rangle_P/2.\qeda $$ \bigskip For $\emptyset \subset V' \subseteq V$, let us denote by $a_pG[V']$ the decorated subgraph of~$a_PG$ induced by $V'$: it is the graph the vertices of which are the elements of~$V'$ (with their associated vectors $a_v$, $v \in V'$) and the edges of which are the edges of~$a_PG$ having their two end points in~$V'$. Thus, the set function $\exp[a_PE]$ counts, for every $V' \subseteq V$, the number of perfect matchings of the decorated graph~$a_pG[V']$. Therefore the following proposition is an immediate consequence of the definitions of the matching polynomials (see the Introduction). \medskip \noindent {\sc Proposition 3.1.} {\it We have} $$\openup2pt\eqalign{ 1+\sum_{\emptyset \subset V' \subseteq V} \mu(a_PG[V'],x) \cdot v^{V'} \; &= \; \exp [\langle x,aV \rangle_P - a_PE], \cr 1+\sum_{\emptyset \subset V' \subseteq V} \overline{\mu}(a_PG[V'],x) \cdot v^{V'} \; &= \; \exp [\langle x,aV \rangle_P + a_PE].\qeda \cr }$$ \medskip The generating functions become ordinary generating functions of exponential type if and only if there is a vector $a \in {\bf R}$ such that $a_v = a$, for all $ v \in V$, and $G = K_{\infty}$ (or $G = \overline{K_{\infty}}$). \medskip \noindent {\sc Proposition 3.2.} {\it We have} $$\openup2pt\eqalign{ 1+\sum_{n=1}^{\infty} \mu(a_PK_n,x) \cdot V^n/n! \; &= \; \exp [\langle x,a \rangle_P \cdot V - \langle a,a \rangle_P \cdot V^2/2], \cr 1+\sum_{n=1}^{\infty} \overline{\mu}(a_PK_n,x) \cdot V^n/n! \; &= \; \exp [\langle x,a \rangle_P \cdot V + \langle a,a \rangle_P \cdot V^2/2].\qeda \cr }$$ \medskip Let us start by proving the $N$-dimensional analogue of Theorem~1.1 of~[7, Chapter~1]. A very special case of this theorem served in~[18, Chapter~1.1.15], as the main example to underline the usefulness of ordinary generating functions. \eject \noindent {\sc Proposition 3.3.} {\it We have} $$\openup0pt\eqalign{ \noalign{\smallskip} a)\;\;&\mu(a_PG' \uplus b_PG'',x) \; = \; \mu(a_PG',x) \cdot \mu(b_PG'',x), \cr &a_PG' \, = \, (aV',a_PE'), \quad\; b_PG'' \, = \, (bV'',b_PE''); \qquad\qquad\qquad\qquad\qquad\qquad\quad\; \cr \noalign{\medskip} b)\;\;&\mu(a_PG,x) \; = \; \mu(a_PG \backslash e,x) - \langle a_u,a_v \rangle_P \cdot \mu(a_PG \backslash uv,x), \quad e = \{u,v\} \in E; \qquad\, \cr \noalign{\medskip} c)\;\;&\mu(a_PG,x) \; = \; \langle x,a_v \rangle_P \cdot \mu(a_PG \backslash v,x) \cr &\qquad \qquad \qquad - \sum_{\{u,v\} \in E} \langle a_u,a_v \rangle_P \cdot \mu(a_PG \backslash uv,x), \quad v \in V; \cr d)\;\;&{\partial \over \partial x_i} \, \mu(a_PG,x) \; = \; \sum_{v \in V} \langle e_i,a_v \rangle_P \cdot \mu(a_PG \backslash v,x), \cr &\, \nabla_P \; \mu(a_PG,x) \; = \; \sum_{v \in V} a_v \cdot \mu(a_PG \backslash v,x), \cr &\, \triangle_P \; \mu(a_PG,x) \; = \; \sum_{u \ne v \in V} \langle a_u,a_v \rangle_P \cdot \mu(a_PG \backslash uv,x). \cr }$$ {\it The analogue for $\overline{\mu}(a_PG,x)$ is obtained by replacing all signs~$-$ by~$+$.} \bigskip {\it Proof.} $$\openup0pt\eqalign{ \noalign{\smallskip} a)\;\;&\exp[\langle x,aV'+bV''\rangle_P - a_PE' - b_PE''] \cr &= \; \exp[\langle x,aV'\rangle_P - a_PE'] \cdot \exp[\langle x,bV''\rangle_P - b_PE'']; \cr \noalign{\medskip} b)\;\;&\exp[\langle x,aV\rangle_P - a_PE] \cr &= \; \exp[\langle x,aV\rangle_P - a_P(E \backslash e)] \cdot \exp[-\langle a_u,a_v\rangle_Puv] \cr &= \; \exp[\langle x,aV\rangle_P - a_P(E \backslash e)] \cdot (1-\langle a_u,a_v\rangle_Puv) \cr &= \; \exp[\langle x,aV\rangle_P - a_P(E \backslash e)] \, - \, \langle a_u,a_v\rangle_Puv \cdot \exp[\langle x,aV\rangle_P - a_P(E \backslash e)]; \cr \noalign{\medskip} c)\;\;&\partial^v \exp[\langle x,aV\rangle_P - a_PE] \cr &= \; \exp[\langle x,aV\rangle_P - a_PE] \cdot \partial^v(\langle x,aV\rangle_P - a_PE) \cr &= \; \exp[\langle x,aV\rangle_P - a_PE] \cdot (\langle x,a_v\rangle_Pv - \!\!\!\! \sum_{\{u,v\} \in E} \!\!\! \langle a_u,a_v\rangle_Puv) \cr &= \; \langle x,a_v\rangle_Pv \cdot \exp[\langle x,aV\rangle_P - a_PE] - \!\!\!\! \sum_{\{u,v\} \in E} \!\!\! \langle a_u,a_v\rangle_Puv \cdot \exp[\langle x,aV\rangle_P - a_PE]; \cr }$$ $$\openup0pt\eqalign{ d)\;\; {\partial \over \partial x_i} \, \exp[\langle x,aV\rangle_P - a_PE] \; &= \; \exp[\langle x,aV\rangle_P - a_PE] \cdot {\partial \over \partial x_i} \langle x,aV\rangle_P \cr &= \; \langle e_i,aV\rangle_P \cdot \exp[\langle x,aV\rangle_P - a_PE], \cr \noalign{\medskip} \nabla_P \, \exp[\langle x,aV\rangle_P - a_PE] \; &= \; aV \cdot \exp[\langle x,aV\rangle_P - a_PE], \cr \noalign{\medskip} \triangle_P \, \exp[\langle x,aV\rangle_P - a_PE] \; &= \; \langle aV,aV\rangle_P \cdot \exp[\langle x,aV\rangle_P - a_PE].\qeda \qquad \qquad \;\;\, \cr }$$ \eject Let us leave the preceding recurrences in order to walk into the garden of duality theorems. \medskip \noindent {\sc Duality theorem for the matching polynomials ($\triangle$).} $$\openup2pt\eqalign{ \overline{\mu}(\overline{a_PG},x) \; &= \; \exp[\triangle_P/2] \cdot \mu(a_PG,x), \cr \mu(\overline{a_PG},x) \; &= \; \exp[- \triangle_P/2] \cdot \overline{\mu}(a_PG,x). \cr }$$ \medskip {\it Proof.} By using the very last identity of the proof of the preceding proposition, we get indeed $$\openup2pt\eqalign{ \exp[\langle x,aV\rangle_P + \overline{a_PE}] \; &= \; \exp[\langle aV,aV\rangle_P/2] \cdot \exp[\langle x,aV\rangle_P - a_PE] \cr &= \; \exp[\triangle_P/2] \cdot \exp[\langle x,aV\rangle_P - a_PE]. \cr }$$ The differential operator $\exp[-\triangle_P/2]$ is the inverse of $\exp[\triangle_P/2]$.\qeda \bigskip \medskip \noindent {\sc Duality theorem for the matching polynomials ($\nabla$).} $$\openup2pt\eqalign{ \overline{\mu}(\overline{a_PG},x) \; &= \; e^{-\langle x,x\rangle_P/2} \cdot \mu(a_PG,\nabla_P) \cdot e^{\langle x,x\rangle_P/2}, \cr \mu(\overline{a_PG},x) \; &= \; e^{\langle x,x\rangle_P/2} \cdot \overline{\mu}(a_PG,-\nabla_P) \cdot e^{-\langle x,x\rangle_P/2}. \cr }$$ \medskip {\it Proof.} By Taylor's theorem we have $$ f(x+a) \; = \; \exp[\langle \nabla,a\rangle] \cdot f(x) \; = \; \exp[\langle \nabla_P,a\rangle_P] \cdot f(x) $$ for vectors $x$, $a$ and a formal power series $f$. It follows $$\openup2pt\eqalign{ &\exp[-\langle x,x\rangle_P/2] \cdot \exp[\langle \nabla_P,aV\rangle_P - a_PE] \cdot \exp[\langle x,x\rangle_P/2] \cr &= \; \exp[-\langle x,x\rangle_P/2] \cdot \exp[-a_PE] \cdot \exp[\langle x+aV,x+aV\rangle_P/2] \cr &= \; \exp[\langle x,aV\rangle_P + \overline{a_PE}]. \cr }$$ The second identity is proved in the same way.\qeda \bigskip \noindent {\sc Example 3.1.} Let $S$ and $T$ be two disjoint sets. A bipartite graph $G = (S,T;E)$ is called simple if and only if the set of its edges $E$ is a subset of $S \times T$. For such graphs, one defines the complementary bipartite graph by $\overline{G} := (S,T;\overline{E})$, with $\overline{E} := (S \times T) \backslash E$. Let us put $N = 2$, $A = {\bb R}[s,t]$, and let us attach to each $s' \in S$ (respectively $t' \in T$) the vector $a_{s'} := {0 \choose 1}$ (respectively $a_{t'} := {1 \choose 0}$). For $x = {s \choose t}$, it follows that $$\openup2pt\displaylines{ P \; = \; P^{-1} \; = \; \pmatrix{0&1\cr 1&0\cr} \quad \Rightarrow \quad \langle a_{s'},a_{s'} \rangle_P \; = \; \langle a_{t'},a_{t'} \rangle_P \; = \; 0, \quad \langle a_{s'},a_{t'} \rangle_P \; = \; 1, \cr \textstyle \langle x,a_{s'} \rangle_P \, = \, s, \;\;\, \langle x,a_{t'} \rangle_P \, = \, t, \;\;\, \langle x,x \rangle_P/2 \, = \, st, \;\;\, \nabla_P \, = \, {d/dt \choose d/ds}, \;\;\, \triangle_P/2 \, = \, {d \over ds} {d \over dt}. }$$ Therefore the matching polynomials $\mu(a_PG,x)$ and $\overline{\mu}(a_PG,x)$ of the decorated graph $a_PG$ are nothing else but the {\it symmetric rook polynomials} $\rho(G,s,t)$ and $\overline{\rho}(G,s,t)$, introduced in~[13]. More precisely, we have $$\openup2pt\eqalign{ \mu(a_PG,x) \; &= \; \sum_{r=0}^{\min(|S|,|T|)} (-1)^r p(G,r) \cdot s^{|S|-r} t^{|T|-r} \; =: \; \rho(G,s,t), \cr \overline{\mu}(a_PG,x) \; &= \; \sum_{r=0}^{\min(|S|,|T|)} p(G,r) \cdot s^{|S|-r} t^{|T|-r} \; =: \; \overline{\rho}(G,s,t), \cr }$$ if $p(G,r)$ is the number of $r$-matchings of the bipartite graph $G = (S,T;E)$. Since $\langle a_{s'},a_{s'} \rangle_P = \langle a_{t'},a_{t'} \rangle_P = 0$ and $\langle a_{s'},a_{t'} \rangle_P = 1$, for all $s' \in S$ and $t' \in T$, the complementary decorated graph $\overline{a_PG}$ corresponds precisely to the complementary bipartite graph $\overline{G} = (S,T;\overline{E})$, and we have $$ \overline{\mu}(\overline{a_PG},x) \; = \; \overline{\rho}(\overline{G},s,t), \qquad \mu(\overline{a_PG},x) \; = \; \rho(\overline{G},s,t). $$ Consequently, our two duality theorems for the matching polynomials imply $$\openup2pt\eqalign{ \overline{\rho}(\overline{G},s,t) \; &= \; \exp \bigl[ {\textstyle {d \over ds}}{\textstyle {d \over dt}} \bigr] \cdot \rho(G,s,t) \; = \; e^{-st} \cdot \rho(G,{\textstyle {d \over dt}},{\textstyle {d \over ds}}) \cdot e^{st}, \cr \rho(\overline{G},s,t) \; &= \; \exp \bigl[ -{\textstyle {d \over ds}}{\textstyle {d \over dt}} \bigr] \cdot \overline{\rho}(G,s,t) \; = \; e^{st} \cdot \overline{\rho}(G,-{\textstyle {d \over dt}},-{\textstyle {d \over ds}}) \cdot e^{-st}. \cr }$$ These identities are nothing else but Theorems~3.1 and~3.2 of~[13]. \bigskip \bigskip Let us continue our walk through the garden of duality theorems. \bigskip \noindent {\sc Duality theorem for the matching polynomials ($\int$).} $$\openup2pt\eqalign{ \overline{\mu}(\overline{a_PG},x) \; &= \; \int_{\bf{R}} e^{-\langle z-x,z-x\rangle_P/2} \cdot \mu(a_PG,z) \cdot d_Pz \cr &= \; \sum_{n=0}^{\infty} {1 \over n!} \int_{\bf{R}} \mu(a_PG,z) \cdot \mu(x_PK_n,z) \cdot e^{-\langle z,z\rangle_P/2} \cdot d_Pz. \cr }$$ \medskip {\it Proof.} Using the invariance of the integral with respect to translations, we get: $$\openup0pt\eqalign{ &\int_{\bf{R}} \exp[-\langle z-x,z-x\rangle_P/2] \cdot \exp[\langle z,aV\rangle_P - a_PE] \cdot d_Pz \cr &= \; \int_{\bf{R}} \exp[-\langle s,s\rangle_P/2] \cdot \exp[\langle s+x,aV\rangle_P - a_PE] \cdot d_Ps \cr &= \; \exp[\langle x,aV\rangle_P + \overline{a_PE}] \cdot \int_{\bf{R}} \exp[-\langle s-aV,s-aV\rangle_P/2] \cdot d_Ps \cr &= \; \exp[\langle x,aV\rangle_P + \overline{a_PE}] \cdot \int_{\bf{R}} \exp[-\langle t,t\rangle_P/2] \cdot d_Pt \cr &= \; \exp[\langle x,aV\rangle_P + \overline{a_PE}]. \cr }$$ Let us put $V := 1$, $x := z$ and $a := x$ in Proposition~3.2: $$ 1+\sum_{n=1}^{\infty} \mu(x_PK_n,z)/n! \; = \; \exp [\langle z,x \rangle_P - \langle x,x \rangle_P/2]. $$ It follows ($\mu(x_PK_0,z) := 1$): $$\openup0pt\eqalign{ &\int_{\bf{R}} e^{-\langle z-x,z-x\rangle_P/2} \cdot \mu(a_PG,z) \cdot d_Pz \cr &= \; \int_{\bf{R}} \mu(a_PG,z) \cdot \exp[\langle z,x\rangle_P - \langle x,x\rangle_P/2] \cdot e^{-\langle z,z\rangle_P/2} \cdot d_Pz \cr &= \; \sum_{n=0}^{\infty} \frac{1}{n!} \int_{\bf{R}} \mu(a_PG,z) \cdot \mu(x_PK_n,z) \cdot e^{-\langle z,z\rangle_P/2} \cdot d_Pz.\qeda \cr }$$ \bigskip Since the space of polynomials is generated (as a vector space) by the matching polynomials, the three preceding theorems imply the following corollary (for the identity $\,\mu(x_PK_n,z) \, = \, \Phi (z|x, \dots, x) \, = \;\, :\!\!\langle z,x\rangle_P^n\!\!: \;\, = \, [\langle z,x\rangle_P^n]^{\sharp}\,$ see Remark~1.1). \medskip \noindent {\sc Corollary 3.1.} {\it Let $f(x)$ be an arbitrary polynomial, then we have for the Bargmann-Segal transform $[f(x)]^{\flat} = f^{\flat}(x)$ and for the Wick transform $[f(x)]^{\sharp} = f^{\sharp}(x)$ the following identities}: $$\openup2pt\eqalign{ f^{\flat}(x) \; &= \; \sum_{n=0}^{\infty} {1 \over n!} \int_{\bf{R}} f(z) \cdot \bigl[\langle z,x\rangle_P^n\bigr]^{\sharp} \cdot e^{-\langle z,z\rangle_P/2} \cdot d_Pz \cr &= \; \int_{\bf{R}} e^{-\langle z-x,z-x\rangle_P/2} \cdot f(z) \cdot d_Pz \cr &= \; e^{-\langle x,x\rangle_P/2} \cdot f(\nabla_P) \cdot e^{\langle x,x\rangle_P/2} \cr \noalign{\smallskip} &= \; \exp[\triangle_P/2] \cdot f(x), \cr \noalign{\bigskip} f^{\sharp}(x) \; &= \; e^{\langle x,x\rangle_P/2} \cdot f(-\nabla_P) \cdot e^{-\langle x,x\rangle_P/2} \cr \noalign{\smallskip} &= \; \exp[- \triangle_P/2] \cdot f(x).\qeda \cr }$$ \bigskip \noindent {\sc Example 3.2.} Of course, it is not necessary to restrict ourselves to polynomials. Let us put $f(x) := \sqrt{\det(Q)} \cdot e^{-\langle x,x \rangle_Q/2}$, where $\langle \cdot,\!\cdot \rangle_Q$ is a second form. The preceding corollary allows us to conclude that $$\openup2pt\eqalign{ \bigl[\sqrt{\det(Q)} \cdot e^{-\langle x,x \rangle_Q/2}\bigr]^{\flat} \; &= \; \sqrt{\det(Q)} \cdot \exp[\triangle_P/2] \cdot e^{-\langle x,x \rangle_Q/2} \cr &= \; \sqrt{\det(Q)} \cdot e^{-\langle x,x\rangle_P/2} \cdot \exp[\triangle_{PQ^{-1}P}/2] \cdot e^{\langle x,x\rangle_P/2} \cr &= \; \sqrt{\det(R)} \cdot e^{- \langle x,x \rangle_R/2}, \quad R := (P^{-1}+Q^{-1})^{-1}. \cr }$$ Indeed, we have $$\openup0pt\eqalign{ &\bigl[\sqrt{\det(Q)} \cdot e^{-\langle x,x \rangle_Q/2}\bigr]^{\flat} \cr \noalign{\smallskip} &= \; \sqrt{\det(Q)} \cdot \int_{\bf{R}} e^{-\langle z-x,z-x\rangle_P/2} \cdot e^{-\langle z,z \rangle_Q/2} \cdot d_Pz \cr &= \; \sqrt{\det(Q)} \cdot \int_{\bf{R}} \exp[-\langle z,z \rangle_{P+Q}/2 + \langle z,x \rangle_P - \langle x,x \rangle_P/2] \cdot d_Pz \cr \noalign{\smallskip} &= \; \sqrt{\det(Q)} \cdot \exp[- \langle x,x \rangle_{P-P(P+Q)^{-1}P}/2] \cdot \cr &\quad \;\;\, {\textstyle \sqrt{\det(P) \over \det(P+Q)}} \cdot \! \int_{\bf{R}} \exp\bigl[ -\bigl\langle z-(P+Q)^{-1}Px,z-(P+Q)^{-1}Px \bigr\rangle_{P+Q}/2 \bigr] \cdot d_{P+Q}z \cr &= \; {\textstyle \sqrt{\det(P) \det(Q) \over \det(P+Q)}} \cdot \exp[- \langle x,x \rangle_{P-P(P+Q)^{-1}P}/2] \cdot \int_{\bf{R}} \exp[-\langle t,t \rangle_{P+Q}/2] \cdot d_{P+Q}t \cr \noalign{\smallskip} &= \; \sqrt{\det(P^{-1}+Q^{-1})^{-1}} \cdot \exp[- \langle x,x \rangle_{(P^{-1}+Q^{-1})^{-1}}/2], \cr }$$ as $\, P - P(P+Q)^{-1}P = P(P+Q)^{-1}Q \, = \, (Q^{-1}(P+Q)P^{-1})^{-1} \, =$ \hbox{$(P^{-1} + Q^{-1})^{-1}$}. The identity $ \sqrt{\det(Q)} \cdot \exp[\triangle_P/2] \cdot e^{-\langle x,x \rangle_Q/2} \, = \, \sqrt{\det(R)} \cdot e^{- \langle x,x \rangle_R/2} $ appears in Mehta's book [16] (see the pages 87--89 there for a different proof). \bigskip \medskip We remark that polynomials have a decomposition into homogeneous parts, and each homogeneous part is uniquely determined by its values on the ellipsoid $S_P^{N-1}$ given by the equation $\langle x,x\rangle_P = 1$ . Let $f$ be homogeneous of degree $n$, i.e., $f(r \cdot \omega) = r^n \cdot f(\omega)$, $\omega \in S_P^{N-1}$, and let $d_P\omega$ be such that $d_Px = c(N) \cdot r^{N-1} \cdot dr \cdot d_P\omega$ and $\int_{S_P^{N-1}} d_P\omega = 1$. We have the following corollary. \medskip \noindent {\sc Corollary~3.2.} {\it Let $n$ be even. Then,} $$\openup0pt\eqalign{ & N \cdot (N+2) \cdot (N+4) \cdots (N+n-2) \cdot \int_{S_P^{N-1}} f(\omega) \cdot d_P\omega \cr &= \; \int_{{\bb R}^N} f(x) \cdot e^{-\langle x,x\rangle_P/2} \cdot d_Px \cr \noalign{\smallskip} &= \; f(\nabla_P) \cdot e^{\langle x,x\rangle_P/2} \Bigr|_{x=0} \cr \noalign{\medskip} &= \; \exp[\triangle_P/2] \cdot f(x) \Bigr|_{x=0}, }$$ {\it and if $f(x) = \mu(\overline{a_PK_n},x)$, the result is the number $\overline{\mu}(a_PK_n,0)$ of perfect matchings of $a_PK_n$.\qeda} \bigskip The identities of the preceding corollary are easy consequences of the results of the recent article~[5] by Folland. However, they are not stated explicitly there. In addition, we have the impression that our proofs are shorter, although Folland has used ideas of Bargmann and Nelson to simplify the proofs of the article~[1], which treats the same subject. \medskip \noindent {\sc Example~3.3.} We have $$ \int_{S^{N-1}} \langle x,\alpha\rangle^{2p} \cdot d\omega \; = \; {1 \cdot 3 \cdot 5 \cdot \dots \cdot (2p-1) \over N(N+2)(N+4) \dots (N+2p-2)} \cdot \langle \alpha,\alpha\rangle^p, $$ because every perfect matching of the graph $\alpha K_{2p}$ contains $p$ edges (to which we had attached the weight $\langle \alpha,\alpha\rangle$), and the number of perfect matchings of $K_{2p}$ equals $1 \cdot 3 \cdot 5 \cdots (2p-1)$ (see~[19, th\'eor\`eme 3.2 and 3.6]). We also have $$ \int_{S^{N-1}} \langle x,\alpha_1\rangle^2 \langle x,\alpha_2\rangle^2 \cdot d\omega \; = \; {\langle \alpha_1,\alpha_1\rangle \langle \alpha_2,\alpha_2\rangle + 2 \cdot \langle \alpha_1,\alpha_2\rangle^2 \over N \cdot (N+2)}, $$ because the complete graph $\overline{\overline{\alpha_1K_2} \uplus \overline{\alpha_2K_2}}$ contains three perfect matchings: two of weight $\langle \alpha_1,\alpha_2\rangle\langle \alpha_1,\alpha_2\rangle$ and one of weight $\langle \alpha_1,\alpha_1\rangle \langle \alpha_2,\alpha_2\rangle$ (see~[19, 6.5]). \medskip \noindent {\sc Example~3.4.} By definition, a polynomial $f(x)$ is {\it harmonic} if and only if $\triangle_P f(x) = 0$. Let $f(x)$ be a homogeneous polynomial of degree $n > 0$ which is harmonic. The preceding corollary allows us to conclude that $$ N(N+2)\cdots(N+n-2) \int_{S_P^{N-1}} f(\omega) \cdot d_P\omega \; = \; \exp[\triangle_P/2] \cdot f(x) \Bigr|_{x=0} \; = \; f(0) \; = \; 0. $$ Since every polynomial $f(x)$ is harmonic if and only if all its homogeneous components are harmonic, the classical identity $$ \int_{S_P^{N-1}} f(\omega) \cdot d_P\omega \; = \; \int_{S_P^{N-1}} f(0) \cdot d_P\omega \; = \; f(0) $$ for every harmonic polynomial follows immediately. \bigskip \medskip Let us continue our study of matching polynomials. \medskip \noindent {\sc Scalar product formula.} {\it For two decorated graphs $a_PG' = (aV',a_PE')$ and $b_PG'' = (bV'',b_PE'')$ we have} $$\openup2pt\eqalign{ \overline{\mu}(\overline{a_PG' \uplus b_PG''},0) \; &= \; \int_{\bf{R}} \mu(a_PG',x) \cdot \mu(b_PG'',x) \cdot e^{-\langle x,x\rangle_P/2} \cdot d_Px \cr &= \; \overline{\mu}(\overline{a_PG'},\nabla_P) \cdot \overline{\mu}(\overline{b_PG''},x) \Bigr|_{x=0}. \cr }$$ \medskip {\it Proof.} The first identity is an obvious consequence of the case $x = 0$ of the preceding theorem. In order to establish the second identity, we use, once again, Taylor's theorem: $$\openup2pt\eqalign{ &\exp[\langle \nabla_P,aV'\rangle_P + \overline{a_PE'}] \cdot \exp[\langle x,bV''\rangle_P + \overline{b_PE''}] \Bigr|_{x=0} \cr &= \; \exp[\overline{a_PE'}] \cdot \exp[\langle x+aV',bV''\rangle_P + \overline{b_PE''}] \Bigr|_{x=0} \cr &= \; \exp[\langle aV',bV''\rangle_P + \overline{a_PE'} + \overline{b_PE''}].\qeda \cr }$$ \bigskip \noindent {\sc Corollary~3.3.} {\it Let $f(x)$ and $g(x)$ be two polynomials and let $f^{\flat}(x)$ and $g^{\flat}(x)$ be their respective Bargmann-Segal transforms defined with the help of one of the formulae of Corollary~3.1. Then we have} $$ \int_{\bf{R}} f(x) \cdot g(x) \cdot e^{-\langle x,x\rangle_P/2} \cdot d_Px \; = \; f^{\flat}(\nabla_P) \cdot g^{\flat}(x) \Bigr|_{x=0}.\qeda $$ \bigskip \medskip The duality theorem ($\int$) implies $$ \mu(\overline{a_PG},y) \; = \; (-i)^n \cdot \overline{\mu}(\overline{a_PG},yi) \; = \; (-i)^n \cdot \int_{\bf{R}} e^{-\langle x-yi,x-yi\rangle_P/2} \cdot \mu(a_PG,x) \cdot d_Px. $$ ($|V| = n$, $i = \sqrt{-1}$). This proves the following theorem. \bigskip \medskip \noindent {\sc Duality theorem for the matching polynomial (${\bb C}$).} $$ e^{-\langle y,y\rangle_P/2} \mu(\overline{a_PG},y) \; = \; (-i)^n \cdot \int_{\bf{R}} e^{i\langle x,y\rangle_P} \cdot e^{-\langle x,x\rangle_P/2} \mu(a_PG,x) \cdot d_Px.\qeda $$ \bigskip Since the matching function $e^{-\langle x,x\rangle_P/2} \mu(a_PG,x)$ has the same parity as $n$, the last theorem of this section follows. \bigskip \medskip \noindent {\sc Duality theorem for the matching polynomial (${\bb R}$).} $$\openup2pt\eqalign{ \noalign{\smallskip} &e^{-\langle y,y\rangle_P/2} \mu(\overline{a_PG},y) \cdot (-1)^{n/2} \cr &= \; \int_{\bf{R}} \cos\langle x,y\rangle_P \cdot e^{-\langle x,x\rangle_P/2} \mu(a_PG,x) \cdot d_Px, \qquad n \quad even,\cr \noalign{\bigskip} &e^{-\langle y,y\rangle_P/2} \mu(\overline{a_PG},y) \cdot (-1)^{(n-1)/2} \cr &= \; \int_{\bf{R}} \sin\langle x,y\rangle_P \cdot e^{-\langle x,x\rangle_P/2} \mu(a_PG,x) \cdot d_Px, \qquad n \quad odd.\cr }$$ {\it In other words, the matching functions of $\overline{a_PG}$ and of $a_PG$ are, up to sign, real Fourier transforms of each other.}\qeda \eject \noindent {\sc Remark~3.1.} Since all our duality theorems rely just on the fundamental lemma $a_PE + \overline{a_PE} = \langle aV,aV\rangle_P/2$, it is natural to associate to each $\{u,v\} \in {V \choose 2}$ two scalar products $Q(\{u,v\})$ and $\overline{Q}(\{u,v\})$ such that $$ \langle a_u,a_v \rangle_{Q(\{u,v\})} + \langle a_u,a_v \rangle_{\overline{Q}(\{u,v\})} \; = \; \langle a_u,a_v \rangle_P, $$ or just two numbers $q(\{u,v\})$ and $\overline{q}(\{u,v\})$ such that $ q(\{u,v\}) + \overline{q}(\{u,v\}) = \langle a_u,a_v \rangle_P. $ We have preferred the classical context of the complementary graph because it is sufficient for most applications. Another way to extend our results consists in replacing the real coefficients of our vectors $a_v$, $v \in V$, by complex coefficients, for example. Moreover, complex coefficients are admissible for the matrix $P$ under the condition that it remains {\it symmetric}. In other words, we can have $P = R + i \cdot Q$ ($i = \sqrt{-1}$) with real symmetric matrices $R$ and $Q$. In this manner, we can see that the two identities of the duality theorems $\nabla$ and $\triangle$ can be reduced to each other by replacing $P$ by $-P$. In order to guarantee the convergence of the (real!) integrals, it is, however, indispensable that $\Re e \; P = R > 0$, i.e., the matrix $R$ must correspond to a scalar product. \bigskip \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Les zeros de $\bf \mu(a_pG,x)$ % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \centerline{\bf 4. The zeroes of $\bf \mu(a_pG,x)$ } \bigskip Let us admit weights $w_{uv} \in {\bb R} \backslash \{0\}$ (in~[9], the condition $w_{uv} > 0$ was imposed) for every edge $\{u,v\} \in E$, such that it contributes the factor $w_{uv}\langle a_u,a_v\rangle_P$ (as an edge of a matching) instead of $\langle a_u,a_v\rangle_P$, and let us denote by $a_PG_w = (aV,a_PE_w)$ the graph with these weights. Let div$[\mu(a_pG_w,x)] \in \hbox{Div}(\bf{R})$ be the (effective) divisor of $\mu(a_PG_w,x)$, but we consider it in the projective space ${\bb P}\bf{R}$ ($={\bb P}^N({\bb R})$; unless we consider it even in ${\bb P}^N({\bb C})$). The generating function of the homogenized matching polynomials $\mu(a_PG_w,x,x_0)$ can be written in the form $$ 1+\sum_{\emptyset \subset V' \subseteq V} \mu(a_PG_w[V'],x,x_0) \cdot v^{V'} \; = \; \exp [\langle x,aV\rangle_P - x_0^2a_PE_w]. $$ In the so-called improper hyperplane $x_0=0$, we have $$ \mu(a_PG_w,x,0) \; = \; 0 \qquad \Leftrightarrow \qquad \prod_{v \in V} \langle x,a_v\rangle_P \; = \; 0. $$ Since $\mu(a_PG_w,x,x_0)$ is linear in every $a_v$, $v \in V$, we can (and we will) suppose for a moment (without changing div$[\mu(a_PG_w,x,x_0)]$) that $\langle a_v,a_v\rangle_P = 1$ for every $v \in V$ (if there exists a $v \in V$ with $a_v = 0$, then $\mu(a_PG_w,x,x_0) \equiv 0$) and that there is no $u \neq v$ with $a_u = -a_v$ (we could consider the $a_v$'s, $v \in V$, as points of ${\bb P}^{N-1}({\bb R})$). Let $$ A \; = \; \{a_v|v \in V\}, \qquad \hbox{and let} \quad V \; = \; \biguplus_{a \in A} V_a $$ such that, for every $a \in A$, we have $a_v = a$ for each $v \in V_a$. Then, $$ \hbox{div}[\mu(a_PG_w,x,0)] \; = \; \sum_{a \in A} |V_a| \cdot V(\langle x,a\rangle_P). $$ Let $a^* \in A$, and let us consider $x^* \in \bf{R} \backslash \{0\}$ such that $\langle x^*,a^*\rangle_P = 0$ and $\langle x^*,a\rangle_P \neq 0$ for each $a \in A \backslash a^*$. The Taylor expansion of $\mu(a_PG_w,x,x_0)$ at $(x^*,0)$ up to the order $|V_{a^*}|$ can be written in the form $$ \mu(a_PG_w[V_{a^*}],x,x_0) \cdot \prod_{v \not\in V_{a^*}} \langle x^*,a_v\rangle_P. $$ This implies the following theorem. \medskip \noindent {\sc Theorem~4.1.} {\it If, for every $a \in A$, the one dimensional matching polynomial $\mu(G_w[V_a],x)$ has $|V_a|$ different real zeroes (for example, because all weights of the edges of the graph $G_w[V_a]$ are positive and $G_w[V_a]$ contains a Hamiltonian path, see~[9], Theorem~4.2), and if $V_i \subset \bf{R}$ are the (irreducible) components of $\hbox{\tenrm div}[\mu(a_PG_w,x)]$, then} $$ \sum_i \deg(V_i) \; = \; \deg[\mu(a_PG_w,x)] \; = \; |V|.\qeda $$ \bigskip \noindent {\sc Remark~4.1.} It is not possible to extend this theorem by continuity as in one dimension, because (${\bb R}$ is closed in ${\bb C}$ but) $\bf{R}$ is not closed in ${\bb P}\bf{R}$. More subtle conditions can be obtained by continuing the Taylor expansion (see the very last theorem of~[12]), but it seems preferable to present them in a different context. \bigskip \noindent {\sc Theorem~4.2.} {\it Every zero of $\mu(a_PG_w,x)$ is close to at least one hyperplane $V(\langle x,a_v\rangle_P)$, $v \in V$. More precisely, let $|a_PG_w|$ be the graph obtained by replacing all weights $w_{uv}\langle a_u,a_v\rangle_P$ of the edges $\{u,v\}$ by $|w_{uv}\langle a_u,a_v\rangle_P|$, let $B$ be bigger than all zeroes of the one dimensional matching polynomial $\mu(|a_PG_w|,x)$ (see~[9], Theorem~4.3, for good estimations of $B$), and suppose that \hbox{$|\langle x,a_v\rangle_P| \ge B$} for every $v \in V$. Then, for each $v \in V' \subseteq V$, we have} $$ \Biggl|{\mu(a_PG_w[V'],x) \over \mu(a_PG_w[V' \backslash v],x)}\Biggr| \; \ge \; {\mu(|a_PG_w[V']|,B) \over \mu(|a_PG_w[V' \backslash v]|,B)} $$ {\it and, in particular, $\mu(a_PG_w[V'],x) \ne 0$.} \medskip {\it Proof.} The proof (by induction) is the same as that of Theorem~4.5 in~[9].\qeda \eject Since affine regular polygons do not enjoy such a great popularity, we will put (without loss of generality!) $P = \hbox{Id}$ (and $N = 2$) for a moment. Let $w: {\bb Z}/n {\bb Z} \to {\bb R}$ be such that $w(k) = w(-k)$ for every $k \in {\bb Z}/n {\bb Z}$, $w(0) = 0$, and let $G_w = ({\bb Z}/n {\bb Z}, E_w)$ be the graph with $\{i,j\} \in E_w$ if and only if $w(i-j) \ne 0$, and, in that case, $w_{ij} := w(i-j)$, $i,j \in {\bb Z}/n {\bb Z}$. If we denote by $aG_w$ the decoration of $G_w$ given by $$ a_k \; := \; {x_k \choose y_k} = {\cos(k \cdot 2\pi/n) \choose \sin(k \cdot 2\pi/n)}, $$ for every $k \in {\bb Z}/n {\bb Z}$, then we have the following surprise. \bigskip \noindent {\sc Proposition~4.1.} {\it We have} $$ \mu(aG_w,x,y) \; = \; \prod_{k=0}^{n-1} \big\langle \hbox{${x \choose y}$},a_k\big\rangle, \qquad \hbox{{\it if n is odd.}} $$ \medskip {\it Proof.} We have indeed $$\openup2pt\eqalign{ \mu(aG_w,0,y) \; &= \; - \sum_{\{k,0\} \in E_w} w(k) \cdot \langle a_k,a_0\rangle \cdot \mu(aG_w \backslash \{k,0\},0,y) \cr &= \; 0, }$$ since the symmetry $k \longleftrightarrow -k$ preserves $w_{ij}\langle a_i,a_j\rangle$ and changes the sign of $\langle {0 \choose y},a_k\rangle$, and since the number of those last expressions is odd for every matching. It follows that $\mu(aG_w,x,y) = x \cdot p(x,y)$, and, by symmetry, $\mu(aG_w,x,y) = \prod_{k=0}^{n-1} \langle {x \choose y},a_k\rangle \cdot q(x,y)$. The proof is completed by comparing the terms of degree~$n$.\qeda \bigskip If $n$ is even, the situation becomes more complicated (because $a_k = -a_{k+n/2}$). We restrict ourselves to the case where there is just a single $(d,-d) \ne (0,0)$ with $w := w(d) = w(-d) \ne 0$. In that case, $aG_w$ is the disjoint union of $\hbox{gcd}(n,d)$ cycles, and $\mu(aG_w,x,y)$ is the product of their matching polynomials. Therefore we obtain a more readable result if we suppose $\hbox{gcd}(n,d) = 1$. \bigskip \noindent {\sc Proposition~4.2.} {\it Let $n$ be even, $n > 2$, and $\hbox{\rm gcd}(n,d) = 1$. Then} $$\openup2pt\eqalign{ \mu(aG_w,x,y) \; &= \; \prod_{k=0}^{n-1} \big\langle \hbox{${x \choose y}$},a_k\big\rangle \quad + \quad 2 \cdot (-w \cdot \langle a_d,a_0\rangle)^{n/2} \cr &= \; (-1)^{n/2} \Biggl[ \prod_{k=0}^{n/2 - 1} \big\langle \hbox{${x \choose y}$},a_k\big\rangle^2 \quad + \quad 2 \cdot [w \cdot \cos(d \cdot 2\pi/n)]^{n/2} \Biggr].\cr }$$ \eject {\it Proof.} As in the preceding proof, we use a sign-reversing involution. We have $$\openup2pt\eqalign{ \mu(aG_w,0,y) \; &= \; -w \cdot \langle a_d,a_0\rangle \cdot [\mu(aG_w \backslash \{d,0\},0,y) + \mu(aG_w \backslash \{-d,0\},0,y)] \cr &= \; 2 \cdot (-w \cdot \langle a_d,a_0\rangle)^{n/2}. }$$ Indeed, let us consider a matching of the cycle $aG_w$, and let us walk, starting from $0$, in both directions of $aG_w$ (at the same time and with the same speed!) until there will be the first vertex not covered by the matching, and let us apply the symmetry $k \longleftrightarrow -k$ for all vertices visited so far. Since there is just a single expression of the type $\langle {0 \choose y},a_k\rangle$ (for the uncovered vertex), the sign changes, and, finally, there will just remain the contributions of the two perfect matchings of $aG_w$. It follows that $\mu(aG_w,x,y) - 2 \cdot (-w \cdot \langle a_d,a_0\rangle)^{n/2} = x \cdot p(x,y)$. The symmetry $\mu(aG_w,-x,y) = \mu(aG_w,x,y)$ implies $p(-x,y) = -p(x,y)$, i.e.~$p(x,y) = x \cdot q(x,y)$; and, once again, by symmetry, we obtain $$ \mu(aG_w,x,y) - 2 \cdot (-w \cdot \langle a_d,a_0\rangle)^{n/2} \; = \; \prod_{k=0}^{n/2 - 1} \big\langle \hbox{${x \choose y}$},a_k\big\rangle^2 \quad \cdot \quad r(x,y). $$ The proof is completed by comparing the terms of degree~$n$.\qeda \bigskip The main reason for having considered the preceding propositions is the following highly surprising corollary. \medskip \noindent {\sc Corollary~4.1.} {\it For every $N > 1$ and every $P$ there exist ordinary (i.e., without weights) decorated graphs $a_PG$ (rarissime!) such that $\mu(a_PG,x) \ne 0$ for every $x \in \bf{R}$.}\qeda \bigskip \bigskip \bigskip {\it Acknowledgements.} \quad First of all, my cordial thanks go to P.~Car\-tier for his captivating introduction to the fascinating world of physics, delivered to me on a pleasant evening at the Domaine Saint-Jacques, without which the $N$-di\-men\-sional matching polynomial would not have seen the light of the day. I also express my gratitude to S.~Eliahou for having improved the clarity of two key definitions, to G.~Nebe and W.~Plesken for having invited B.~Venkov ([19] being the second motivation for the $N$ dimensions), to A.~Lascoux and V.~A.~Malyshev for their wonderful presents~[16] and~[15], and particularly to D.~Foata for all his help and assistance. Last but not least I am indebted to C.~Krattenthaler for his indispensable help with the English translation. \bigskip \bigskip \bigskip \vfill \eject %%%%%%%%%%%%%%%%%%%%%%% %% BIBLIOGRAPHIE %% %%%%%%%%%%%%%%%%%%%%%%% \centerline{\bf References} \medskip {\baselineskip=9pt\tenrm \item{[1]} J.~A.~Baker, Integration over spheres and the divergence theorem for balls, {\it American Math.~Monthly} {\bf 104} (1997), 36-47. \smallskip \item{[2]} P.~Cartier, Personal communication, S\'eminaire Lotharingien de Combinatoire 44, 2000. \smallskip \item{[3]} P.~Cartier, Mathemagics (A Tribute to L.~Euler and R.~Feynman), {\it S\'eminaire Lotharingien de Combinatoire} {\bf B44d}, 71 pages, 2000. \smallskip \item{[4]} D.~Foata and A.~Fuchs, ``Calcul des Probabilit\'es'', Dunod, Paris, 1998. \smallskip \item{[5]} G.~F.~Folland, How to integrate a polynomial over a sphere, {\it American Math. Monthly} {\bf 108} (2001), 446-448. \smallskip \item{[6]} J.~Glimm and A.~Jaffe, ``Quantum Physics, A Functional Integral Point of View'', Springer-Verlag, 1981. \smallskip \item{[7]} C.~D.~Godsil, ``Algebraic Combinatorics'', Chapman \& Hall, 1993. \smallskip \item{[8]} C.~D.~Godsil, Hermite polynomials and a duality relation for matchings polynomials, {\it Combinatorica} {\bf 1} (1981), 257-262. \smallskip \item{[9]} O.~J.~Heilmann and E.~H.~Lieb, Theory of monomer-dimer systems, {\it Comm. Math.~Physics} {\bf 25} (1972), 190-232. \smallskip \item{[10]} S.~K.~Lando, On primitive elements in the bialgebra of chord diagrams, in: Topics in Singularity Theory, V.~I.~Arnold's 60th Anniversary Collection (A. Khovanskij, A.~Varchenko, V.~Vassiliev, editors), AMS Transl.~Ser.~2 Vol.~180, {\it Advances in the Mathematical Sciences} {\bf 34} (1997), 167-174. \smallskip \item{[11]} S.~K.~Lando and A.~K.~Zvonkin, ``Graphs on Surfaces and Their Applications'', Encyclopaedia of Mathematical Sciences, Volume 141, Low-Dimensional Topo\-logy II (R.~Gamkrelidze, V.~Vassiliev, editors), Springer, 2004. \smallskip \item{[12]} B.~Lass, Matching polynomials and duality, {\it Combinatorica} {\bf 24} (2004), 427-440. \smallskip \item{[13]} B.~Lass, Variations sur le th\`eme E+$\overline{\hbox{E}}$ = XY, {\it Advances in Applied Mathematics} {\bf 29} (2002), 215-242. \smallskip \item{[14]} L.~Lov\'asz, ``Combinatorial Problems and Exercises'', Akad\'emiai Kiad\'o, 1993. \smallskip \item{[15]} V.~A.~Malyshev and R.~A.~Minlos, ``Gibbsovskie sluchajnye polja, Metod klaster\-nykh razlozhenij'', Nauka, Moskva, 1985; English version: ``Gibbs Random Fields, Cluster Expansions'', Kluwer Academic Publishers, 1991. \smallskip \item{[16]} M.~L.~Mehta, ``Matrix Theory, Selected Topics and Useful Results'', Les \'Editions de Physique, 1989. \smallskip \item{[17]} A.~N.~Shiryaev, ``{Verojatnost'}'', Hauka, Moskva, 1980. \smallskip \item{[18]} R.~P.~Stanley, ``Enumerative Combinatorics'', Volume 1, Cambridge University Press, Cambridge, 1997. \smallskip \item{[19]} B.~Venkov, R\'eseaux et designs sph\'eriques, in: R\'eseaux euclidiens, designs sph\'e\-riques et formes modulaires (J.~Martinet, \'editeur), L'Enseignement Math\'e\-ma\-tique, Monographie no.~37, 2001, 10-86. \smallskip } \end