%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \magnification=1100 \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= 22.5cm \hsize= 14.0cm \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 Orientations acycliques} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% {\parindent=0pt\eightbf Europ.~J.~Combinatorics~22, 1101--1123, 2001 } \vskip 1.5cm %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%% %% TITEL %% %%%%%%%%%%%%% \centerline {\fourteenbf Orientations acycliques et le polyn\^ome chromatique } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Subject Classification %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \parindent=-1mm\footnote{}{ {\it Mots cl\'es:} graphe, polyn\^ome chromatique, orientation acyclique, source, puits, invariant de Crapo} \vskip 20pt %%%%%%%%%%% %% NAME %% %%%%%%%%%%% \centerline{\bf BODO LASS} \bigskip \medskip %%%%%%%%%%%%%%%% %% ABSTRACT %% %%%%%%%%%%%%%%%% \noindent {\eightrm On attache \`a tout graphe $\scs G$ son polyn\^ome chromatique $\scs \chi_G(\lambda)$, qui d\'enombre ses colorations r\'eguli\`eres avec $\scs \lambda$ couleurs. D'apr\`es Stanley, on sait que $\scs |\chi_G(-1)|$ est \'egal au nombre d'orientations acycliques du graphe, un r\'esultat qui fut raffin\'e par Greene et Zaslavsky. Nous nous proposons de l'affiner davantage en interpr\'etant, avec l'aide de certaines orientations acycliques, les coefficients de $\scs \chi_G(\lambda)$ d\'evelopp\'e en puissances de $\scs \lambda$ et surtout en puissances de $\scs (\lambda-1)$. L'utilisation syst\'ematique des fonctions g\'en\'eratrices des fonctions d'ensembles permet d'avoir des d\'emonstrations tr\`es courtes et explicatives. Elles se veulent une r\'eponse \`a la suggestion faite par Gebhard et Sagan, qui ont d\'ej\`a trouv\'e des d\'emonstrations combinatoires de deux r\'esultats de Greene et Zaslavsky. Les fonctions d'ensembles permettent aussi d'\'etablir une s\'erie d'interpr\'etations nouvelles de l'invariant~$\scs \beta_G$ de Crapo. Cet article donne \'egalement un nouvel \'eclat aux r\'esultats classiques de Cartier, Foata, Viennot, Brenti, Gessel et Stanley.} \medskip \noindent {\eightrm The chromatic polynomial $\scs \chi_G(\lambda)$, which is associated with each graph $\scs G$, enumerates its regular colorations with $\scs \lambda$ colors. Stanley showed that $\scs |\chi_G(-1)|$ is equal to the number of acyclic orientations of the graph, a result that was refined by Greene and Zaslavsky. The purpose of the paper is to show that a further refinement can be obtained by interpreting each coefficient of $\scs \chi_G(\lambda)$, when the polynomial is developed with respect to powers of $\scs \lambda$ and $\scs (\lambda-1)$. A systematic use of the generating functions for set functions enables us to have very short and instructive proofs. Gebhard and Sagan, who had already found combinatorial proofs of two results by Greene and Zaslavsky, suggested that further proofs were to be found. Finally, the set functions algebra allows us to establish a series of new interpretations for Crapo's $\scs \beta_G$ invariant. This paper also brings a new light to the classical results due to Cartier, Foata, Viennot, Brenti, Gessel and Stanley.} \vskip1.5pt \parindent=3mm \vskip 5mm %%%%%%%%%%%% %% TEXT %% %%%%%%%%%%%% \centerline{\bf 1. Introduction} \medskip Soit $G = (V,E)$ un graphe fini non-orient\'e. Une {\it orientation} de $G$ est un graphe orient\'e obtenu \`a partir de $G$ en rempla\c cant chaque ar\^ete $e \in E$ par un des deux arcs (i.~e.~ar\^etes orient\'ees) possibles. L'orientation est {\it acyclique} si elle ne contient pas de cycles orient\'es. \'Evidemment, le nombre d'orientations acycliques est \'egal \`a z\'ero si $G$ contient une boucle (et \'egal \`a 1 si $G$ ne contient aucune ar\^ete). De plus, des ar\^etes multiples de $G$ doivent toutes \^etre orient\'ees de la m\^eme fa\c con pour que l'orientation devienne acyclique. Voil\`a pourquoi on peut supposer, sans restreindre la g\'en\'eralit\'e, que $G$ est simple, c'est-\`a-dire qu'il ne contient ni boucles ni ar\^etes multiples, lorsqu'on s'int\'eresse aux orientations acycliques. On appelle {\it puits} (resp.~{\it source}) d'une orientation de $G$ un sommet qui n'est l'extr\'emit\'e {\it initiale} (resp.~{\it terminale}) d'aucun arc. Apparemment, de quelque fa\c con que l'on choisisse une orientation de $G$, {\it chaque sommet isol\'e de $G$ est toujours \`a la fois un puits et une source}, un fait qui n\'ecessite une prise en charge particuli\`ere des sommets isol\'es lorsqu'il faut regarder des puits et des sources en m\^eme temps. \medskip Une coloration $c: V \to \{1,2,\dots,\lambda\}$ de $G$ avec $\lambda$ couleurs est dite {\it r\'eguli\`ere} si les deux extr\'emit\'es de chaque ar\^ete ont des couleurs diff\'erentes, c'est-\`a-dire $\{u,v\} \in E \; \Rightarrow \; c(u) \neq c(v)$. Soit $\chi_G(\lambda)$ le nombre de ces colorations. C'est un des faits les plus classiques de la th\'eorie des graphes (d\'ecoulant \`a plusieurs reprises de cet article) que $\chi_G(\lambda)$ est un polyn\^ome en $\lambda$ de degr\'e $\bf n := |V|$, appel\'e {\it polyn\^ome chromatique}. \'Evidemment, $\chi_G(\lambda) = 0$ si $G$ contient une boucle, et de nouveau on peut se cantonner aux graphes simples pour \'etudier le polyn\^ome chromatique. \medskip Les similarit\'es constat\'ees entre les orientations acycliques et le polyn\^ome chromatique ne sont pas une co\"\i ncidence. En fait, si $$ \chi_G(\lambda) \; = \; \lambda^n - c_{n-1} \cdot \lambda^{n-1} + c_{n-2} \cdot \lambda^{n-2} - \dots + (-1)^{n-1}c_1 \cdot \lambda, $$ alors il est classique que $c_1$, $c_2$, \dots, $c_{n-1}$ sont des entiers positifs; et gr\^ace \`a Stanley~[21], on sait que $c_1 + c_2 + \dots + c_{n-1} + 1$ d\'enombre effectivement les orientations acycliques de~$G$. \medskip Ceci soul\`eve imm\'ediatement la question de savoir s'il est possible de partitionner, de fa\c con canonique, l'ensemble des orientations acycliques en blocs de cardinalit\'es $c_1$, $c_2$, \dots, $c_{n-1}$, $1$. En effet, si les sommets de $G$ sont num\'erot\'es, c'est-\`a-dire $V = \{1,2,\dots,n\}$, alors une telle partition est possible en attachant, \`a chaque orientation acyclique, une partition de~$V$ constitu\'ee par $k$~blocs, appel\'es {\it composantes} de l'orientation acyclique. La m\^eme construction de ces composantes fut imagin\'ee par Greene et Zaslavsky~[12] (dans un contexte g\'eom\'etrique) et par Viennot~[27] (dans le cadre des empilements de pi\`eces). Un des buts de cet article est de populariser leur r\'esultat, qui est rest\'e plut\^ot inconnu sauf pour le cas d'une seule composante~: le fait que $c_1$ d\'enombre les orientations acycliques d'une seule composante (ce sont par d\'efinition les orientations acycliques dont le sommet $1$ est la seule source) se trouve dans~[4] et dans le livre r\'ecent de Bollob\'as~[1] (chapitre~X, th\'eor\`eme~8), par exemple. Suivons Sachs ([20], chapitre V.9.2) et appelons $\alpha_G := c_1$ {\it discriminant chromatique} du graphe~$G$. Les nombres $c_1$, $c_2$, \dots, $c_{n-1}$ sont d\'efinis ind\'ependamment de la num\'erotation choisie et du fait que l'on s'int\'eresse aux sources ou plut\^ot aux puits des orientations acycliques. Voil\`a pourquoi $\alpha_G$ compte les orientations acycliques de~$G$ dont un sommet fix\'e est la seule source (ou bien le seul puits). C'\'etait le leitmotif de l'article~[9] de Gebhard et Sagan de donner trois preuves nouvelles de ce th\'eor\`eme de Greene et Zaslavsky~[12], que ces derniers avaient d\'emontr\'e en s'appuyant sur les arrangements d'hyperplans. \medskip Supposons maintenant que $G$ est connexe de sorte que $\alpha_G$ est strictement positif. Il est classique (voir [26], chapitre IX.2) que le polyn\^ome chromatique admet alors le d\'eveloppe\-ment $$ \chi_G(\lambda) \; = \; \lambda \cdot \bigl[(\lambda-1)^{n-1} - b_{n-2} \cdot (\lambda-1)^{n-2} + \dots + (-1)^n b_1 \cdot (\lambda-1)\bigr], $$ o\`u $b_1$, $b_2$, \dots, $b_{n-2}$ sont des entiers positifs correspondant \`a certains coefficients du polyn\^ome de Tutte. Les nombres $b_1$, $b_2$, \dots, $b_{n-2}$ sont probablement les invariants les plus petits (i.~e.~les plus puissants) que l'on peut associer \`a tout graphe (connexe) \`a partir de son polyn\^ome chromatique. Leur positivit\'e implique en particulier une unimodalit\'e partielle des coefficients {\lfq ordinaires\rfq} de $\chi_G(\lambda)$, \`a savoir $1 \le c_{n-1} \le c_{n-2} \le \dots \le c_{\lceil n/2 \rceil}$ (voir~[1], chapitre~X, th\'eor\`eme~13). Num\'erotons les sommets du graphe~$G$. Il est \'evident que $$ b_1 + b_2 + \dots + b_{n-2} + 1 \; = \; \alpha_G $$ d\'enombre les orientations acycliques de~$G$ dont le sommet~$1$ est le seul puits; et la question se pose si l'on peut, de nouveau, trouver une partition canonique de l'ensemble de ces orientations en blocs de cardinalit\'es $b_1$, $b_2$, \dots, $b_{n-2}$, $1$. Une telle partition existe effectivement, et de surcro\^\i t, c'est la m\^eme que nous connaissons d\'ej\`a~: $b_k$ compte le nombre d'orientations acycliques de~$G$ de $k+1$~composantes, dont le puits unique est \'egal \`a $1$, si (et seulement si) la num\'erotation des sommets refl\`ete bien la connexit\'e du graphe. Ce r\'esultat risque d'\^etre absolument inconnu, puisque la positivit\'e des nombres $b_1$, $b_2$, \dots, $b_{n-2}$ constitue la premi\`ere moiti\'e du th\'eor\`eme principal de l'article tout r\'ecent~[10] de Gessel, mais pour la d\'emonstration, le lecteur est renvoy\'e \`a la litt\'erature (i.~e.~au polyn\^ome de Tutte), bien que le sujet dudit article soient des relations entre colorations et orientations acycliques~! Dans le cas particulier de l'{\it invariant $\beta_G := b_1$ de Crapo}~[6] cependant, on retrouve le th\'eor\`eme classique de Greene et Zaslavsky~[12] qui, gr\^ace aux arrangements d'hyperplans, ont indentifi\'e $\beta_G$ comme nombre d'orientations acycliques de $G$ n'ayant qu'une seule source et un seul puits, \`a savoir les deux sommets adjacents $2$ et $1$, respectivement. Gebhard et Sagan ont trouv\'e une preuve par induction de ce fait et ont pens\'e que le r\'esultat m\'eriterait d'autres d\'emonstrations (voir~[9]). Cet article se veut, entre autres, une r\'eponse \`a leur suggestion. Nous donnons, en effet, une s\'erie d'interpr\'etations apparemment nouvelles (incluant celle de Greene et Zaslavsky) de $\beta_G$, et nous les d\'emontrons avec l'aide de l'alg\`ebre des fonctions d'ensembles. \bigskip En fait, de notre point de vue, l'int\'er\^et principal de cet article consiste en l'exploration de la m\'ethode des fonctions g\'en\'eratrices dans le pr\'esent contexte, m\'ethode qui a d\'ej\`a fait ses preuves dans beaucoup de situations diff\'erentes (voir~[14]). Chacun de nos th\'eor\`emes s'obtient effectivement comme sp\'ecialisation d'une identit\'e dans l'alg\`ebre des fonctions d'ensembles et le passage entre ces diff\'erentes identit\'es se fait toujours en quelques lignes. Ceci permet notamment de trouver des nouvelles d\'emonstrations, tr\`es courtes et explicatives, des deux th\'eor\`emes de Greene et Zaslavsky mentionn\'es ci-dessus ainsi que de celui de Stanley sur $|\chi_G(-1)|$. Il nous semble particuli\`erement surprenant que chacune de nos identit\'es admettant une g\'en\'eralisation {\it non-commutative} appara\^\i t d\'ej\`a dans les travaux de Cartier-Foata~[5], Foata~[7] et Gessel~[10]. De plus, c'est Gessel (voir~[27], pages 343-344) qui a montr\'e (sur toute une page \`a l'\'epoque) comment on peut d\'eduire le r\'esultat de Stanley du th\'eor\`eme de Cartier et Foata (voir~[5]) sur l'inversion (de M\"obius) dans le mono\"\i de de commutation. En fait, de notre point de vue, ce th\'eor\`eme de Cartier et Foata devient une g\'en\'eralisation non-commutative directe du th\'eor\`eme de Stanley~[21] sans aucune d\'emonstration suppl\'ementaire. Ceci montre \`a quel point le livre de Cartier et Foata \'etait visionnaire~! Cependant, pour aller plus loin dans le sens des th\'eor\`emes de Greene et Zaslavsky qui font intervenir des interpr\'etations combinatoires du logarithme, il semble falloir se cantonner au cas {\it commutatif}. Cette n\'ecessit\'e fut d'abord r\'ev\'el\'ee par Viennot (voir~[27], proposition 5.10), qui a, de plus, \'etabli l'\'equivalence du mod\`ele de Cartier et Foata avec son mo\-d\`ele des empilements de pi\`eces ainsi que, notamment, avec notre mod\`ele pr\'ef\'er\'e, \`a savoir les orientations acycliques d'un graphe (voir [27], page 325, c)). Gr\^ace \`a cette \'equivalence, les th\'eor\`emes~3.2 et~5.1 de cet article deviennent effectivement des g\'en\'eralisations ou plut\^ot des raffinements de la proposition~5.10 de~[27]. \medskip Apr\`es avoir expliqu\'e notre m\'ethode alg\'ebrique dans le paragraphe~2, nous l'appliquons pour le traitement du polyn\^ome chromatique et des orientations acycliques dans les paragraphes 3, 4, 5 et 6. Trois appendices sont consacr\'es \`a la discussion, dans notre optique, des travaux de Cartier, Foata, Gessel, Viennot et Stanley mentionn\'es ci-dessus. En outre, nous consid\'erons bri\`evement les d\'eveloppements du polyn\^ome chromatique obtenus par Brenti, les graphes al\'eatoires \'etudi\'es par Welsh~[28] et la fonction (sym\'etrique) chromatique de Stanley (voir~[22]). \bigskip \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%% % % % Outils alg\'ebriques % % % %%%%%%%%%%%%%%%%%%%%%%%%%% \centerline{\bf 2. Outils alg\'ebriques} \bigskip \noindent Soit $V$ un ensemble fini et $$\openup2pt\eqalign{ f: 2^V & \to A \cr V' \subseteq V & \mapsto f(V') \in A \cr }$$ une fonction d'ensembles, o\`u $A$ est un anneau commutatif (avec $1$). \noindent Consid\'erons la fonction g\'en\'eratrice $$ F_f(\nu) \; := \; \sum_{V' \subseteq V} f(V') \cdot \nu^{V'}, \qquad \nu^{\emptyset} \; := \; 1, $$ \`a joindre aux r\`egles de calcul suivantes ($V',V'' \subseteq V$)~: $$ \nu^{V'} \cdot \nu^{V''} \; := \; \nu^{V'+V''}, \quad \hbox{o\`u} $$ $$ V'+V'' \; := \; \openup 2pt\left\{\eqalign{ V' \cup V'', \quad & \hbox{si} \quad V' \cap V'' = \emptyset, \cr \dag, \; \; \quad \quad & \hbox{si} \quad V' \cap V'' \ne \emptyset, \quad \hbox{o\`u} \cr }\right. $$ $$ \dag + V' \; := \; \dag, \quad \dag + \dag \; := \; \dag, \qquad \hbox{et} \qquad \nu^{\dag} \; := \; 0. $$ L'alg\`ebre $A[V]$ de ces fonctions g\'en\'eratrices n'est pas une inconnue. En effet, on a l'iso\-morphisme $$ A[V] \; \simeq \; A[v_1,\dots,v_n]/ \langle v_1^2,\dots,v_n^2 \rangle, $$ si $V$ contient $n$ \'el\'ements. \medskip \noindent {\sc Exemple 2.1.} Le produit $fg$ de deux fonctions d'ensembles $f,g$ est d\'efini, pour tout $V' \subseteq V$, par $$ (fg)(V') \; := \; \sum_{V' = V'' \uplus V'''} f(V'') \cdot g(V'''). $$ Il en r\'esulte $$ F_{fg} (\nu) \; = \; F_f (\nu) \cdot F_g (\nu). $$ \bigskip Pour $|V| = \infty$, soit $F(V)$ l'ensemble partiellement ordonn\'e des sous-ensembles finis de $V$. On a des projections canoniques $p_{V',V''}: A[V'] \to A[V'']$ ($V',V'' \in F(V), V' \supseteq V''$) et l'on pose $$ A[V] \; := \; \lim_{\longleftarrow} A[V'], \quad V' \in F(V) $$ pour travailler avec des fonctions g\'en\'eratrices de la forme $$ F_f (\nu) \; = \; \sum_{V' \in F(V)} f(V') \cdot \nu^{V'}. $$ \smallskip \noindent {\sc Remarque 2.1.} Dans~[14], les projections canoniques furent utilis\'ees pour d\'emontrer des propositions par analogie avec les propositions 3.2 et 4.1 de cet article. Deux de ces r\'esultats sont directement \'equivalents \`a la proposition~5.3 de~[27] et au lemme~1.2 de~[2]. Cependant, l'interaction des projections avec l'analyse est moins int\'eressante. C'est pourquoi elles ne sont plus employ\'ees ici. \bigskip \noindent Soit $$ V \; := \; \sum_{v \in V} \nu^{\{v\}} $$ la fonction indicatrice des sous-ensembles de $V$ de cardinalit\'e $1$ (l'usage double de $V$ pour l'ensemble et pour un \'el\'ement de $A[V]$ ne pourra pas \^etre \`a l'origine de confusions). En multipliant la fonction g\'en\'eratrice $V$ plusieurs fois par elle-m\^eme, on voit que $V^n/n!$ repr\'esente la fonction indicatrice des sous-ensembles de l'ensemble $V$ de cardinalit\'e $n$. L'identit\'e $$ \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, $$ fournit un plongement de l'anneau $A![[V]]$ des fonctions g\'en\'eratrices de type exponentiel dans l'anneau $A[V]$. Ce plongement est \`a l'origine de (presque?) toutes les applications de $A![[V]]$ en combinatoire, mais il n\'ecessite l'existence d'un mod\`ele combinatoire infini (qui ne fait intervenir que les cardinalit\'es). Par cons\'equent, $A[V]$ donne plus de flexibilit\'e et permet un traitement alg\'ebrique, qui refl\`ete parfaitement les op\'erations classiques de la combinatoire. Outre cela, $A[V]$ est appropri\'e, par excellence, aux calculs par ordinateur. \medskip \noindent {\sc Remarque 2.2.} L'anneau ${\bb Z}![[V]]$ n'est pas noeth\'erien, mais il contient des fonctions importantes comme $\exp(V)$ et $\log(1+V)$. \medskip \noindent {\sc Exemple 2.2.} Si $char \; A = 2$, on a $$\openup2pt\eqalign{ (1+V)^{-1} \; & = \; \sum_{n=0}^{\infty} (-1)^n n! \cdot V^n/n! \cr & \equiv \; 1+V \quad \hbox{et} \cr \log(1+V) \; & = \; \sum_{n=1}^{\infty} (-1)^{n-1} (n-1)! \cdot V^n/n! \cr & \equiv \; V+V^2/2 \cr }$$ dans l'anneau $A![[V]]$. Ces identit\'es sont \`a l'origine de maints r\'esultats de parit\'e en combinatoire. \bigskip \noindent Pour tout $t \in A$ posons $(t \cdot \nu)^{V'} \; := \; t^{|V'|} \cdot \nu^{V'}$, $\; V' \subseteq V$, et, par cons\'equent, $$ F_f(t\nu) \; = \; \sum_{\emptyset \subseteq V' \subseteq V} f(V') \; t^{|V'|} \; \nu^{V'}. $$ Il est \'evident que cette d\'efinition est compatible avec l'addition et la multiplication. Les cas particuliers les plus importants sont $t = -1$ et $t = 0$: $F_f(0) = F_f(0 \cdot \nu) = f(\emptyset)$. \medskip Si $F_f (0) = 0$, alors $F_f(\nu)^n/n!$ est d\'efini pour n'importe quel anneau $A$, parce qu'une partition en $n$ sous-ensembles non-vides peut \^etre ordonn\'ee de $n!$ mani\`eres diff\'erentes. Voil\`a pourquoi $A![[V]]$ op\`ere sur $A[V]$ par la substitution $G(F_f (\nu))$ d\'efinie pour tout $G \in A![[V]]$. \bigskip \noindent Finalement, on utilise les d\'eriv\'ees $\partial^v$ pour tout $v \in V$ d\'efinies par $$ \partial^v \nu^{V'} \; := \; \openup 2pt\left\{\eqalign{ \nu^{V'}, \quad & \hbox{si} \quad v \in V', \cr 0, \; \; \quad & \hbox{sinon.} \cr }\right. $$ La formule de d\'erivation d'un produit $$ \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)) $$ est l'analogue alg\'ebrique du fait ensembliste le plus fondamental~: $$ v \in V' \uplus V'' \qquad \Leftrightarrow \qquad v \in V' \quad \hbox{ou} \quad v \in V''. $$ La formule $$ \partial^v [G(F_f (\nu))] \; = \; G'(F_f (\nu)) \cdot \partial^v F_f (\nu), \quad G \in A![[V]], $$ en d\'ecoule imm\'ediatement. \medskip \noindent {\sc Remarque 2.3.} L'isomorphisme $A[V] \simeq A[v_1,\dots,v_n]/ \langle v_1^2,\dots,v_n^2 \rangle$ ne fait pas correspondre $\partial^v$ \`a $\partial / \partial v_i$, mais \`a $v_i \partial / \partial v_i$. La d\'eriv\'ee partielle $\partial / \partial v_i$ n'a point d'analogue dans $A[V]$. \bigskip \noindent Pour $\emptyset \subseteq V' \subseteq V$, posons $$ \partial^{V'} \; := \; \prod_{v \in V'} \partial^v, \;\; \hbox{i.~e.} \qquad \partial^{V'} \nu^{V''} \; = \; \openup 2pt\left\{\eqalign{ \nu^{V''}, \quad & \hbox{si} \quad V' \subseteq V'', \cr 0, \;\;\; \quad & \hbox{sinon;} \cr }\right. $$ en particulier, $\partial^{\emptyset}$ est l'identit\'e. Comme $(\partial^v)^2 = \partial^v$ pour tout $v \in V$, on a $$ \partial^{V'}\partial^{V''} \; = \; \partial^{V' \cup V''}, \quad V',V'' \subseteq V. $$ Les op\'erateurs diff\'erentiels n'\'etant pas des combinaisons lin\'eaires des d\'erivations d'\'el\'ements $\partial^v$, $v \in V$, ne satisfont pas aux formules de d\'erivation ordinaires. En s'appuyant sur la d\'efinition $\partial^{V'} := \prod_{v \in V'} \partial^v$, cependant, on peut calculer des r\`egles sp\'ecifiques pour eux : \bigskip \noindent {\sc Proposition 2.1.} \medskip \noindent a) {\it Soient $f,g: 2^V \to A$ des fonction d'ensembles, et soit $V' \subseteq V$ fix\'e. Alors} $$ \partial^{V'} [F_f (\nu) \cdot F_g (\nu) ] \; = \sum_{\emptyset \subseteq V'' \subseteq V'} \partial^{V''} F_f (\nu) \cdot \partial^{V' \backslash V''} F_g (\nu). $$ \smallskip \noindent b) {\it Soient $s,p \in V$, et soit $G \in A![[V]]$. Alors} $$ \partial^{\{s,p\}} [G(F_f (\nu))] \; = \;\; G''(F_f (\nu)) \cdot \partial^s F_f (\nu) \cdot \partial^p F_f (\nu) \; + \; G'(F_f (\nu)) \cdot \partial^{\{s,p\}} F_f (\nu). $$ \smallskip \noindent c) {\it Soit $t$ une variable (ou $t \in A$) et posons $\displaystyle D(t) \; := \; \sum_{\emptyset \subseteq V' \subseteq V} t^{|V'|}\partial^{V'}$. Alors} $$\openup2pt\eqalign{ D(t) [F_f (\nu) \cdot F_g (\nu) ] \; &= \; D(t) F_f (\nu) \; \cdot \; D(t) F_g (\nu); \quad puisque \cr D(t) F_f (\nu) \; &= \; F_f ((t+1)\nu).\qeda \cr }$$ \bigskip \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % Orientations acycliques et ensembles ind\'ependants % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \centerline{\bf 3. Orientations acycliques et ensembles ind\'ependants~:} \centerline{\bf sources ou puits} \bigskip Pour tout $\emptyset \subset V' \subseteq V$, soit $G[V']$ le sous-graphe de $G = (V,E)$ engendr\'e par~$V'$~: c'est le graphe dont les sommets sont les points de $V'$, et dont les ar\^etes sont les ar\^etes de $G$ ayant leurs deux extr\'emit\'es dans $V'$. Un sous-ensemble $I$ de sommets est dit {\it ind\'ependant}, si le sous-graphe engendr\'e par $I$ ne contient aucune ar\^ete. Une coloration $c: V \to \{1,2,\dots,\lambda\}$ de $G$ avec $\lambda$ couleurs est {\it r\'eguli\`ere} (voir l'introduction) si et seulement si, pour tout $i \in \{1,2,\dots,\lambda\}$, le sous-ensemble $c^{-1}(i)$ est un ensemble de sommets ind\'ependant (ou vide). {\it Voil\`a pourquoi une coloration r\'eguli\`ere avec $\lambda$ couleurs n'est rien d'autre qu'une partition de $V$ en $\lambda$ ensembles ind\'ependants, dont chacun peut \^etre vide.} \medskip Soit $I_G(\nu)$, $I_G(0) = 0$, la fonction indicatrice des sous-ensembles ind\'ependants de $G$ (la valeur de cette fonction indicatrice sur $V'$, $\emptyset \subset V' \subseteq V$, est \'egal \`a 1, si $G[V']$ ne contient aucune ar\^ete, et \'egal \`a 0 sinon)~: $$ {} \;\;\; I_G(\nu) \; := \sum_{\emptyset \subset I \subseteq V, \;\; I \; \hbox{\eightrm ind\'ependant}} \nu^I; $$ et posons $$ \chi_{G,\lambda}(\nu) \; := \sum_{\emptyset \subset V' \subseteq V} \chi_{G[V']}(\lambda) \cdot \nu^{V'}, $$ o\`u $\chi_{G[V']}(\lambda)$ d\'esigne le polyn\^ome chromatique (c'est-\`a-dire le nombre de colo\-rations r\'eguli\`e\-res avec $\lambda$ couleurs) de $G[V']$. \medskip Rappelons que le coefficient lin\'eaire de $\chi_G(\lambda)$ multipli\'e par $(-1)^{n-1}$, i.~e.~$(-1)^{n-1}\chi'_G(0)$, est appel\'e discriminant chromatique et not\'e $\alpha_G$; et g\'en\'eralisons la d\'efinition de l'invariant de Crapo donn\'ee dans l'introduction en posant $\beta_G := (-1)^{n+i}\chi'_G(1)$, o\`u $i$ d\'esigne le nombre de sommets isol\'es de $G$. Le lecteur familier avec $\beta_G$ verra facilement que cette d\'efinition est \'equivalente \`a la sienne, si $G$ contient au moins une ar\^ete. Si $G$ ne contient aucune ar\^ete, on obtient $\beta_G = n$, une d\'efinition artificielle qui sera modifi\'ee ci-dessous. \'Evidemment, nous utilisons les m\^emes d\'efinitions pour tous les sous-graphes engendr\'es, notant en particulier $i(G[V'])$ le nombre de sommets isol\'es de $G[V']$. \medskip Puisqu'une multiplication dans l'alg\`ebre $A[V]$ avec $\lambda$ facteurs compte des partitions en $\lambda$ ensembles, on a l'identit\'e fondamentale (un facteur 1 correspond au fait qu'on peut choisir l'ensemble vide pour la couleur correspondante, i.~e.~ne pas utiliser cette couleur pour la coloration), que nous reproduisons dans la proposition suivante. \bigskip \noindent {\sc Proposition 3.1.} {\it On a} $$\openup2pt\eqalign{ 1+\chi_{G,\lambda}(\nu) \; &= \; [1+I_G(\nu)]^{\lambda}, \cr \hbox{$\frac{d}{d\lambda}$}[1+\chi_{G,\lambda}(\nu)] \; &= \; [1+I_G(\nu)]^{\lambda} \cdot \log[1+I_G(\nu)]; \cr }$$ {\it et, en particulier, pour le discriminant chromatique $\alpha_G$ et l'invariant de Crapo $\beta_G$, on a~:} $$\openup2pt\eqalign{ -\log[1+I_G(-\nu)] \; &= \; \sum_{\emptyset \subset V' \subseteq V} \alpha_{G[V']} \cdot \nu^{V'}, \cr [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] \; &= \; \sum_{\emptyset \subset V' \subseteq V} (-1)^{i(G[V'])}\beta_{G[V']} \cdot \nu^{V'}.\qeda \cr }$$ \bigskip \noindent {\sc Exemple 3.1.} Selon l'exemple 2.2, $I_G(\nu) + I_G(\nu)^2/2$ compte les discriminants chromatiques modulo 2. Par cons\'equent, $\alpha_G$ est impair si et seulement si le graphe $G$ est connexe et biparti (voir [20], chapitre V.9.2). (Un graphe est biparti, si l'ensemble de ses sommets peut \^etre partitionn\'e en deux classes ind\'ependantes.) \bigskip \medskip Pour tout $\emptyset \subset V' \subseteq V$, soit $a(G[V'])$ le nombre d'orientations acycliques du graphe $G[V']$ (voir l'introduction), et soit $a_S(G[V'])$ le nombre d'orientations acycliques de $G[V']$, dont l'ensemble des sources est \'egal \`a $S$, $\emptyset \subseteq S \subseteq V$. \'Evidemment, $a_S(G[V']) = 0$, si $S$ n'est pas un sous-ensemble de $V'$. De plus, si $S = \emptyset$, alors on a toujours $a_S(G[V']) = 0$, puisque chaque orientation acyclique du graphe $G[V']$ ($|V'| > 0$) a au moins une source. Posons $$ A_G(\nu) \; := \sum_{\emptyset \subset V' \subseteq V} a(G[V']) \cdot \nu^{V'}, \qquad A_{G,S}(\nu) \; := \sum_{\emptyset \subset V' \subseteq V} a_S(G[V']) \cdot \nu^{V'}. $$ Le rapport fondamental entre les orientations acycliques et les sous-ensembles ind\'epen\-dants de $G$ repose uniquement sur le fait que {\it l'ensemble des sources d'une orientation acyclique est toujours ind\'ependant.} \medskip Or, si $S'$, $\emptyset \subseteq S' \subseteq V$, n'est pas ind\'ependant (l'ensemble vide est ind\'ependant), $S'$ ne peut pas \^etre un sous-ensemble de l'ensemble des sources. Si $S'$ est ind\'ependant, cependant, alors $[1+A_G(\nu)] \cdot \nu^{S'}$ compte le nombre d'orientations acycliques telles que $S'$ est un sous-ensemble de l'ensemble des sources; car ces orientations de $G[V']$, $S' \subseteq V' \subseteq V$, s'obtiennent en choisissant une orientation acyclique quelconque du graphe $G[V' \backslash S']$ et en orientant toutes les autres ar\^etes de $S'$ \`a $V' \backslash S'$. Par cons\'equent, le principe d'inclusion-exclusion fournit le r\'esultat suivant (voir~[7], th\'eor\`eme~3.1, pour une g\'en\'eralisation non-commutative ayant la m\^eme d\'emonstration)~: \eject \noindent {\sc Proposition 3.2.} (Foata) {\it Pour tout $\emptyset \subseteq S \subseteq V$ on a} $$ [1+A_G(\nu)] \cdot (-1)^{|S|}\partial^S [1+I_G(-\nu)] \; = \; \partial^S [1+A_{G,S}(\nu)], $$ {\it les cas particuliers les plus int\'eressants \'etant $S = \emptyset$ et $S = \{s\}$ ($s \in V$)~:} $$ [1+A_G(\nu)] \cdot [1+I_G(-\nu)] \; = \; 1, \qquad -[1+A_G(\nu)] \cdot \partial^s I_G(-\nu) \; = \; A_{G,s}(\nu).\qeda $$ \bigskip Alors il d\'ecoule des deux propositions pr\'ec\'edentes (voir [21] ou [17], 9.46, ainsi que [5], th\'eor\`eme 2.4, et [27], proposition 5.1)~: \bigskip \noindent {\sc Th\'eor\`eme 3.1.} (Stanley, Cartier-Foata, Gessel-Viennot) {\it Pour tout $\emptyset \subset V' \subseteq V$,} $$ [1+I_G(-\nu)]^{-1} \; = \; 1+A_G(\nu) \; = \; 1+\chi_{G,-1}(-\nu) $$ {\it d\'enombre les orientations acycliques de $G[V']$. En particulier, on a $a(G) = (-1)^n\chi_G(-1)$, et ce nombre est toujours strictement positif.\qeda} \bigskip \noindent Soit $s \in V$ fix\'e. Alors le th\'eor\`eme 3.1 et la proposition 3.2 impliquent $$ \partial^s -\log[1+I_G(-\nu)] \; = \; -[1+I_G(-\nu)]^{-1} \cdot \partial^s I_G(-\nu) \; = \; A_{G,s}(\nu). $$ Posons $A_G^*(\nu) \; := \; -\log[1+I_G(-\nu)]$. Il s'ensuit (voir [12] ou [9] ainsi que [27], proposition 5.10)~: \bigskip \noindent {\sc Th\'eor\`eme 3.2.} (Greene-Zaslavsky, Viennot) {\it Pour tout $\emptyset \subset V' \subseteq V$,} $$ -\log[1+I_G(-\nu)] \; = \; A_G^*(\nu) \; = \; -\hbox{$\frac{d}{d\lambda}$} \chi_{G,0}(-\nu) $$ {\it d\'enombre les orientations acycliques de $G[V']$ n'ayant qu'une seule source fix\'ee $s\in V'$. En particulier, on a $a_s(G) = (-1)^{n-1}\chi'_G(0) = \alpha_G$ pour tout $s\in V$, et ce nombre n'est jamais n\'egatif. Plus pr\'ecis\'ement, il est \'egal \`a 0 si $G$ n'est pas connexe, il est \'egal \`a 1 si $G$ est un arbre, et il est plus grand que 1 dans tous les autres cas.} \bigskip {\it D\'emonstration.} Seulement la toute derni\`ere affirmation n'est pas encore \'evidente. Elle se d\'emontre comme suit. Les plus courts chemins de $s \in V$ \`a n'importe quel autre sommet forment une arborescence avec $s$ comme source unique. Une ar\^ete suppl\'ementaire de $G$ doit {\lfq passer de travers\rfq} par rapport \`a cette arborescence et peut \^etre orient\'ee de deux mani\`eres diff\'erentes sans qu'il y ait un cycle orient\'e. Enfin, chacune de ces deux orientations acycliques peut \^etre prolong\'ee \`a tout $G$.\qeda \bigskip Finalement, soit $a_k(G)$ le nombre d'orientations acycliques de $G = (V,E)$ avec (pr\'ecis\'e\-ment) $k$ sources et posons $$ a_G(t) \; := \; \sum_{k=1}^{n} a_k(G)t^k, \qquad A_{G,t}(\nu) \; := \; \sum_{\emptyset \subset V' \subseteq V} a_{G[V']}(t) \cdot \nu^{V'}, $$ ($A_{G,1}(\nu) = A_G(\nu)$). Avec l'aide de la proposition 3.2 ainsi que de l'op\'erateur diff\'erentiel $D(t)$ de la proposition 2.1, c), on obtient~: \bigskip \noindent {\sc Th\'eor\`eme 3.3.} {\it On a} $$\openup2pt\eqalign{ 1+A_{G,t}(\nu) \; &= \; [1+A_G(\nu)] \cdot D(-t)[1+I_G(-\nu)] \cr &= \; \frac{1+I_G((t-1)\nu)}{1+I_G(-\nu)}.\qeda \cr }$$ \bigskip \'Evidemment, tout ce qui fut \'enonc\'e pour les sources vaut \'egalement pour les puits. En particulier, $a_S(G[V'])$ (pour les sources) ou encore $a_P(G[V'])$ (pour les puits), $\emptyset \subset V' \subseteq V$, est \'egal \`a z\'ero, si $V' \backslash S$ (ou bien $V' \backslash P$) contient un sommet isol\'e dans le graphe $G[V']$. \bigskip \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % Orientations acycliques et ensembles ind\'ependants % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \centerline{\bf 4. Orientations acycliques et ensembles ind\'ependants~:} \centerline{\bf sources et puits} \bigskip Les sommets isol\'es posent des probl\`emes lorsqu'on veut regarder les sources et les puits en m\^eme temps; car ces sommets sont toujours les deux \`a la fois. Dans cette optique, la d\'efinition suivante se r\'ev\`ele raisonnable. \medskip \noindent {\sc D\'efinition 4.1.} Pour tout $\emptyset \subset V' \subseteq V$, soit $I(G[V'])$ l'ensemble des sommets isol\'es de~$G[V'] \;$ ($|I(G[V'])| = i(G[V'])$). Si $\emptyset \subset S,P \subseteq V$ et $S \cap P = \emptyset$, notons $|a_{S,P}(G[V'])|$ le nombre d'orientations acycliques du graphe $G[V']$ telles que l'ensemble des sources est \'egal \`a $S \cup I(G[V'])$ et l'ensemble des puits est \'egal \`a $P \cup I(G[V'])$; et posons $a_{S,P}(G[V']) := (-1)^{I(G[V']) \backslash (S \cup P)} |a_{S,P}(G[V'])|$. Par d\'efinition, $a_{S,P}(G[V']) := 0$, si $S \cap P \ne \emptyset$. \medskip \noindent Posons $$ A_{G,S,P}(\nu) \; := \; \sum_{\emptyset \subset V' \subseteq V} a_{S,P}(G[V']) \cdot \nu^{V'}. $$ Alors la proposition 3.2, ainsi que le principe d'inclusion-exclusion, impliquent (voir Gessel~[10] pour une g\'en\'eralisation non-commutative et pond\'er\'ee)~: \bigskip \noindent {\sc Proposition 4.1.} (Gessel) {\it Pour $\emptyset \subset S,P \subseteq V$ on a~:} $$\openup2pt\eqalign{ &[1+A_G(\nu)] \cdot [(-1)^{|S|}\partial^S I_G(-\nu)] \cdot [(-1)^{|P|}\partial^P I_G(-\nu)] \cr &= \; A_{G,S}(\nu) \cdot [(-1)^{|P|}\partial^P I_G(-\nu)] \; = \; A_{G,P}(\nu) \cdot [(-1)^{|S|}\partial^S I_G(-\nu)] \cr &= \; A_{G,S,P}(\nu). }$$ \medskip {\it D\'emonstration.} Il ne s'agit que d'expliquer l'entr\'ee des nombres n\'egatifs due aux sommets isol\'es. Soit $i$ un sommet isol\'e de $G$ (pour les sous-graphes engendr\'es $G[V']$, $\emptyset \subset V' \subseteq V$, on a le m\^eme argument), alors $i \notin S$ implique $$ \partial^i A_{G,S}(\nu) \; = \; 0 \qquad \hbox{et} \qquad \partial^i (-1)^{|S|}\partial^S I_G(-\nu) \; = \; -\nu^i \cdot (-1)^{|S|}\partial^S I_G(-\nu), $$ o\`u $S$ peut \^etre remplac\'e par $P$. Par cons\'equent, $i \notin (S \cup P)$ implique $$ \partial^i A_{G,S,P}(\nu) \; = \; -\nu^i \cdot A_{G,S,P}(\nu).\qeda $$ \bigskip Maintenant, pour $s,p \in V$ fix\'es, il d\'ecoule de la proposition pr\'ec\'edente ainsi que du th\'eor\`eme 3.1 (voir aussi la proposition 2.1) que~: $$\openup2pt\eqalign{ &\partial^{\{s,p\}} \Bigl( [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] \Bigr) \cr &= \; [1+I_G(-\nu)]^{-1} \cdot \partial^s I_G(-\nu) \cdot \partial^p I_G(-\nu) \; + \; \Bigl( 1+\log[1+I_G(-\nu)] \Bigr) \cdot \partial^{\{s,p\}} I_G(-\nu) \cr &= \; A_{G,s,p}(\nu) \; + \; \Bigl( 1+\log[1+I_G(-\nu)] \Bigr) \cdot \partial^{\{s,p\}} I_G(-\nu). \cr }$$ Si $s$ et $p$ sont adjacents, alors $\partial^{\{s,p\}} I_G(-\nu) = 0$, et il s'ensuit $$ \partial^{\{s,p\}} \Bigl( [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] \Bigr) \; = \; A_{G,s,p}(\nu). $$ Cela implique le th\'eor\`eme suivant (voir [12] ou [9]), que nous repr\'esentons dans~$A[V]$~: \bigskip \noindent {\sc Th\'eor\`eme 4.1.} (Greene-Zaslavsky) {\it La fonction d'ensembles} $$ [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] \; = \; \hbox{$\frac{d}{d\lambda}$} \chi_{G,1}(-\nu) $$ {\it prend la valeur $(-1)^{|V'|}|V'|$ pour tout $\emptyset \subset V' \subseteq V$, lorsque $V'$ est ind\'ependant (car $\exp(-V') \cdot \log[\exp(-V')]$ $= -V' \cdot \exp(-V')$), et la valeur $$ a_{s,p}(G[V']) \; = \; (-1)^{|V'|}\chi'_{G[V']}(1) \; = \; (-1)^{|I|}\beta(G[V']) \; = \; $$ $$ (-1)^{|I|}a_{s,p}(G[V' \backslash I]) \; = \; (-1)^{|V'|}\chi'_{G[V' \backslash I]}(1) \; = \; (-1)^{|I|}\beta(G[V' \backslash I]), $$ lorsque $G[V']$ contient une ar\^ete $\{s,p\}$ et $I$ est l'ensemble des sommets isol\'es de $G[V']$. En particulier, si $G$ ne contient aucun sommet isol\'e et $\{s,p\}$ est une ar\^ete de $G$, alors $a_{s,p}(G) = (-1)^n\chi'_G(1) = \beta(G)$ d\'enombre les orientations acycliques de $G$ n'ayant qu'une seule source \`a $s$ et qu'un seul puits \`a $p$. Ce nombre n'est jamais n\'egatif et strictement positif si $G$ est un bloc, c'est-\`a-dire si $G$ est \hbox{2-connexe} ou la seule ar\^ete $\{s,p\}$.} \medskip {\it D\'emonstration.} Seulement la toute derni\`ere affirmation n'est pas encore \'evidente. Elle se d\'emontre comme suit. Selon [13], chapitre 3.2, tout graphe \hbox{2-connexe} admet une {\lfq d\'ecom\-po\-si\-tion en oreilles\rfq} donn\'ee par des chemins $C_1,\dots,C_k$ tels que $C_1 = \{s,p\}$, $|V(C_i) \cap [V(C_1) \cup \dots \cup V(C_{i-1})]| = 2$ pour tout $2 \le i \le k$ et $V = V(C_1) \cup \dots \cup V(C_k)$. Cette d\'ecomposition permet de munir $G$ d'une fonction injective $i: V \to [0,1]$, $i(s) = 0$, $i(p) = 1$, qui augmente (ou diminue) le long de tous les chemins $C_1,\dots,C_k$ de fa\c con strictement monotone. Alors il ne s'agit que d'orienter chaque ar\^ete de son extr\'emit\'e la plus petite (selon $i$) \`a son extr\'emit\'e la plus grande.\qeda \bigskip Nous avons d\'ej\`a interpr\'et\'e $[1+I_G(-\nu)]^{-1}$ (th\'eor\`eme 3.1), $-\log[1+I_G(-\nu)]$ en d\'erivant par rapport \`a un \'el\'ement (th\'eor\`eme 3.2) et $[1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)]$ en d\'erivant deux fois (th\'eor\`eme 4.1). En effet, $-\log[1-V]$ est l'int\'egrale de $[1-V]^{-1}$. Cependant, l'int\'egrale de $-\log[1-V]$ n'est pas $[1-V] \cdot \log[1-V]$, mais $[1-V] \cdot \log[1-V]-[-V]$. Voil\`a pourquoi le th\'eor\`eme principal de ce paragraphe est consacr\'e \`a l'interpr\'etation de $[1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu)$. Si l'on ajoute le terme $-I_G(-\nu)$ au membre de gauche de la derni\`ere identit\'e de la proposition 3.1, la valeur de $\beta_{G[V']}$ ne change que si $V'$ est ind\'ependant~: dans ce cas $\beta_{G[V']}$ n'est plus \'egal \`a $|V'|$ mais \`a $|V'|-1$ (toutes les deux d\'efinitions \'etant artificielles). On utilisera donc l'identit\'e $$ \sum_{\emptyset \subset V' \subseteq V} (-1)^{i(G[V'])}\beta_{G[V']} \cdot \nu^{V'} \; := \; [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu). $$ Avec cette modification (et la d\'efinition 4.1) on a alors~: \bigskip \noindent {\sc Th\'eor\`eme 4.2.} {\it Soit $V = \{1,\dots,n\}$ et soit $i$ le nombre de sommets isol\'es de $G$. Alors le coefficient de $\nu^V$ dans $ [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu), $ c'est-\`a-dire $(-1)^i \beta_G$, est \'egal \`a} $$ a_{\{1\},\{2\}}(G) - a_{\{1,2\},\{3\}}(G) + a_{\{1,2,3\},\{4\}}(G) - \dots + (-1)^na_{\{1,2,\dots,n-1\},\{n\}}(G), $$ {\it o\`u la somme pr\'ec\'edente s'arr\^ete d\`es que l'ensemble des sources $\{1,2,\dots,k\}$ n'est plus ind\'ependant.} \eject \noindent {\it D\'emonstration.} D\'erivons successivement par rapport \`a tous les \'el\'ements~: $$\openup2pt\eqalign{ &\partial^{\{1\}} \Bigl( [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu) \Bigr) \cr &= \; \log[1+I_G(-\nu)] \cdot \partial^{\{1\}} I_G(-\nu), \cr &\partial^{\{1,2\}} \Bigl( [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu) \Bigr) \cr &= \; A_{G,\{1\},\{2\}}(\nu) + \log[1+I_G(-\nu)] \cdot \partial^{\{1,2\}} I_G(-\nu), \cr &\partial^{\{1,2,3\}} \Bigl( [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu) \Bigr) \cr &= \; \partial^{\{3\}} A_{G,\{1\},\{2\}}(\nu) - A_{G,\{1,2\},\{3\}}(\nu) + \log[1+I_G(-\nu)] \cdot \partial^{\{1,2,3\}} I_G(-\nu), \cr & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \cdots \cr &\partial^{\{1,2,\dots,k\}} \Bigl( [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu) \Bigr) \cr &= \; \partial^{\{3,\dots,k\}} A_{G,\{1\},\{2\}}(\nu) - \partial^{\{4,\dots,k\}} A_{G,\{1,2\},\{3\}}(\nu) + \partial^{\{5,\dots,k\}} A_{G,\{1,2,3\},\{4\}}(\nu) \cr & \quad \;\; - \dots + (-1)^k A_{G,\{1,2,\dots,k-1\},\{k\}}(\nu) + \log[1+I_G(-\nu)] \cdot \partial^{\{1,2,\dots,k\}} I_G(-\nu), \cr & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \cdots \cr &\partial^V \Bigl( [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu) \Bigr) \cr &= \; \partial^V A_{G,\{1\},\{2\}}(\nu) - \partial^V A_{G,\{1,2\},\{3\}}(\nu) + \partial^V A_{G,\{1,2,3\},\{4\}}(\nu) \cr & \quad \;\; - \dots + (-1)^n \partial^V A_{G,\{1,2,\dots,n-1\},\{n\}}(\nu).\qeda \cr }$$ \bigskip \medskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % Le polyn\^ome chromatique % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \centerline{\bf 5. Le polyn\^ome chromatique~: bases canoniques} \bigskip \noindent Tout d'abord, il d\'ecoule de la proposition 3.1 et du th\'eor\`eme 3.1 que \bigskip \noindent {\sc Proposition 5.1.} (Stanley~[21], Gessel~[10]) $$ 1+\chi_{G,\lambda}(\nu) \; = \; [1+I_G(\nu)]^{\lambda}, \qquad 1+\chi_{G,-\lambda}(-\nu) \; = \; [1+A_G(\nu)]^{\lambda}.\qeda $$ \bigskip Soit $V = \{1,2,\dots,n\}$, et regardons une orientation acyclique des ar\^etes de $G = (V,E)$. Notons $V_1$ l'ensemble des sommets accessibles (par des chemins orient\'es) \`a partir de $v_1 := 1$. Soit $v_2$ le plus petit sommet de $V \backslash V_1$, et soit $V_2$ l'ensemble des sommets de $V \backslash V_1$ accessibles de $v_2$ \dots\ Finalement, soit $v_k$ le plus petit sommet de $V \backslash (V_1 \cup \dots \cup V_{k-1})$, et soit $V_k$ l'ensemble des sommets de $V \backslash (V_1 \cup \dots \cup V_{k-1})$ accessibles de $v_k$, $V = V_1 \uplus V_2 \uplus \dots \uplus V_k$. On appelle $k$ le nombre de {\it composantes} de l'orientation acyclique. Ainsi une orientation acyclique de $k$ composantes est constitu\'ee par une partition $V = V_1 \uplus \dots \uplus V_k$ en orientations acycliques avec des sources fix\'ees $v_1,\dots,v_k$ (le plus petit sommet $v_i$ de chaque composante $V_i$ est la source unique, et les ar\^etes entre deux composantes $V_i$ et $V_j$ avec $v_i < v_j$ sont toutes orient\'ees de $V_j$ \`a $V_i$). Or, puisque $A_G^*(\nu)$ compte des orientations acycliques avec une source unique fix\'ee (ou bien des orientations acycliques d'une seule composante), $A_G^*(0) = 0$, il s'ensuit que $A_G^*(\nu)^k/k!$ compte des orientations acycliques de $k$ composantes. En particulier, on a $$ \exp[A_G^*(\nu)] \; = \; 1+A_G(\nu), $$ ce qui est la d\'emonstration de Viennot (voir~[27], proposition 5.10) du th\'eor\`eme~3.2, \`a savoir de l'identit\'e $$ A_G^*(\nu) \; = \; -\log[1+I_G(-\nu)], $$ avec l'aide du th\'eor\`eme 3.1, i.~e.~de l'identit\'e $1+A_G(\nu) = [1+I_G(-\nu)]^{-1}$. \eject Notons $c(G)$ le nombre de {\it composantes connexes} de $G$, de sorte que chaque orientation acyclique de $G$ a au moins $c(G)$ composantes, ce nombre minimal pouvant \^etre atteint selon le th\'eor\`eme 3.2. On en d\'eduit le r\'esultat de Greene et Zaslavsky (voir [12] ou [26], chapitre IX.2), que nous reformulons dans l'alg\`ebre des fonctions d'ensembles. \bigskip \noindent {\sc Th\'eor\`eme 5.1.} (Greene-Zaslavsky, Viennot) {\it On a} $$\openup2pt\eqalign{ 1+\chi_{G,\lambda}(-\nu) \; &= \; \exp \Bigl( \lambda \cdot \log[1+I_G(-\nu)] \Bigr) \; = \; \exp \Bigl( -\lambda \cdot A_G^*(\nu) \Bigr) \cr &= \; \sum_{k=0}^\infty \Bigl( [-A_G^*(\nu)]^k/k! \Bigr) \cdot \lambda^k. }$$ {\it En particulier,} $$ \chi_G(\lambda) \; = \; \lambda^n - c_{n-1} \cdot \lambda^{n-1} + c_{n-2} \cdot \lambda^{n-2} - \dots + (-1)^{n-1}c_1 \cdot \lambda, $$ {\it o\`u $c_k$ d\'esigne le nombre d'orientations acycliques de $G$ de $k$ composantes, $c_{n-1} = |E|$, $c_1 = \alpha_G = a_{\{1\}}(G)$, $1+c_{n-1}+c_{n-2}+\dots+c_1 = a(G)$; $c_k = 0$, si $k < c(G)$, et $c_k > 0$, si $k \ge c(G)$.\qeda} \bigskip \noindent {\sc Remarque 5.1.} Le th\'eor\`eme pr\'ec\'edent montre que l'alternance des signes du polyn\^ome chromatique est une cons\'equence directe de la positivit\'e des discriminants chromatiques, c'est-\`a-dire de $A_G^*(\nu)$. \bigskip \medskip Un r\'esultat plus puissant que l'alternance des signes du polyn\^ome chromatique d\'evelopp\'e par rapport \`a la base des puissances $\lambda^k$ est celui de l'alternance des signes par rapport \`a la base des puissances $(\lambda - 1)^k$, ce qui correspond au polyn\^ome de Tutte. Pour la d\'emontrer avec l'aide des orientations acycliques, supposons que $G$ est connexe et que ses sommets sont num\'erot\'es avec les nombres $1,\dots,n$ de telle fa\c con que le plus petit voisin de chaque sommet (sauf $1$) porte un nombre plus petit que celui du sommet m\^eme. (De cette mani\`ere, la num\'erotation refl\`ete bien la connexit\'e.) Dans cette situation, les sommets $v_2,\dots,v_k$ d'une orientation acyclique de $k$ composantes $V = V_1 \uplus \dots \uplus V_k$ (de nouveau, pour chaque composante $V_i$, son plus petit sommet $v_i$ est sa source unique) ne peuvent pas \^etre des puits; car, pour chacun de ces sommets $v_i$, son plus petit voisin se trouve toujours dans une composante plus petite (la {\lfq grandeur\rfq} d'une composante \'etant m\'esur\'ee en fonction de son plus petit \'el\'ement) de sorte que l'ar\^ete corres\-pondante a $v_i$ comme extr\'emit\'e initiale et le plus petit voisin comme extr\'emit\'e terminale. Si $v_1 = 1$ est un puits (i.~e.~$v_2 = 2$), alors la suppression des puits r\'eduit le nombre de composantes de $1$ (\`a savoir de la composante $V_1 = \{1\}$). D'autre part, en ajoutant les puits distincts de $v_1 = 1$, on les affecte automatiquement \`a la composante la plus petite d'o\`u ils sont accessibles (c'est la composante du plus petit voisin ou une composante encore plus petite). Par cons\'equent, pour chaque ensemble de sommets ind\'ependant $I$ tel que $1 = v_1 \in I$, le coefficient de $\nu^V$ dans $[A_G^*(\nu)^k/k!] \cdot \nu^I$ compte le nombre d'orientations acycliques de $k+1$ composantes de $G$ telles que $I$ est un sous-ensemble des puits. Voil\`a pourquoi le principe d'inclusion-exclusion implique que le coefficient de $\nu^V$ dans $[A_G^*(\nu)^k/k!] \cdot [-\partial^{\{1\}} I_G(-\nu)]$ compte le nombre d'orientations acycliques de $k+1$ composantes de $G$, dont le puits unique est \'egal \`a $1$ (pour $k = 1$ il s'agit bien du nombre $a_{\{2\},\{1\}}(G)$). \medskip Notons $b(G)$ le nombre de {\it blocs} de $G$ (voir le th\'eor\`eme 4.1), de sorte que chaque orientation acyclique de $G$ telle que le sommet $1$ est son puits unique a au moins $b(G)+1$ composantes; pour une telle orientation il est n\'ecessaire et suffisant, que le plus petit sommet de tout bloc soit son puits unique. Selon le th\'eor\`eme 4.1 le nombre minimal de $b(G)+1$ composantes peut \^etre atteint. Nous avons d\'emontr\'e le th\'eor\`eme principal de ce paragraphe (voir [26], chapitre IX.2). \eject \noindent {\sc Th\'eor\`eme 5.2.} {\it On a} $$\openup2pt\eqalign{ -\partial^{\{1\}} \chi_{G,\lambda}(-\nu) \; &= \; \lambda \cdot [1+I_G(-\nu)]^{\lambda-1} \cdot [-\partial^{\{1\}} I_G(-\nu)] \cr &= \; \lambda \cdot \exp \Bigl( -(\lambda - 1) \cdot A_G^*(\nu) \Bigr) \cdot [-\partial^{\{1\}} I_G(-\nu)] \cr &= \; \lambda \cdot \sum_{k=0}^\infty \Bigl( [-A_G^*(\nu)]^k/k! \Bigr) \cdot [-\partial^{\{1\}} I_G(-\nu)] \cdot (\lambda-1)^k. }$$ \noindent {\it En particulier,} $$ \chi_G(\lambda) \; = \; \lambda \cdot [(\lambda-1)^{n-1} - b_{n-2} \cdot (\lambda-1)^{n-2} + \dots + (-1)^n b_1 \cdot (\lambda-1)], $$ {\it o\`u $b_k$ d\'esigne le nombre d'orientations acycliques de $G$ de $k+1$ composantes, dont le puits unique est \'egal \`a $1$, $b_{n-2} = |E| - (n-1)$, $b_1 = \beta_G = a_{\{2\},\{1\}}(G)$, $1+b_{n-2}+\dots+b_1 = \alpha_G = a_{\{1\}}(G)$; $b_k = 0$, si $k < b(G)$, et $b_k > 0$, si $k \ge b(G)$.\qeda} \bigskip \noindent {\sc Exemple 5.1.} Le graphe donn\'e dans les dessins suivants admet quatre orientations acycliques, dont le puits unique est $1$~: une de quatre composantes, deux de trois composantes et une de deux composantes. Voil\`a pourquoi son polyn\^ome chromatique s'\'ecrit~: $\lambda[(\lambda-1)^3 - 2(\lambda-1)^2 + (\lambda-1)] = \lambda(\lambda-1)(\lambda-2)^2$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 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 -------------------- \midinsert \newbox\boxquatre \newbox\boxcinq \newbox\boxsix \newbox\boxsept \def\fleche(#1,#2)\dir(#3,#4)\long#5{% {\leftput(#1,#2){\vector(#3,#4){#5}}}} \def\segment(#1,#2)\dir(#3,#4)\long#5{% \leftput(#1,#2){\lline(#3,#4){#5}}} \setbox\boxquatre=\vbox{\vskip 12mm\offinterlineskip \fleche(0,0)\dir(2,1)\long{6} \segment(0,0)\dir(2,1)\long{10} \segment(10,5)\dir(-2,1)\long{10} \fleche(0,10)\dir(2,-1)\long{6} \segment(0,10)\dir(0,-1)\long{10} \fleche(0,10)\dir(0,-1)\long{6} \segment(0,0)\dir(-2,1)\long{10} \fleche(-10,5)\dir(2,-1)\long{6} \fleche(-10,5)\dir(2,1)\long{6} \segment(-10,5)\dir(2,1)\long{10} % \centerput(12,4){1} \centerput(-12,4){4} \centerput(0,-3){2} \centerput(0,11){3} % \centerput(0,-7){composantes~:} \centerput(0,-11){\{1\},\{2\},\{3\},\{4\}} } \setbox\boxcinq=\vbox{\vskip 12mm\offinterlineskip \fleche(0,0)\dir(2,1)\long{6} \segment(0,0)\dir(2,1)\long{10} \segment(10,5)\dir(-2,1)\long{10} \fleche(0,10)\dir(2,-1)\long{6} \segment(0,10)\dir(0,-1)\long{10} \fleche(0,0)\dir(0,1)\long{6} \segment(0,0)\dir(-2,1)\long{10} \fleche(-10,5)\dir(2,-1)\long{6} \fleche(-10,5)\dir(2,1)\long{6} \segment(-10,5)\dir(2,1)\long{10} % \centerput(12,4){1} \centerput(-12,4){4} \centerput(0,-3){2} \centerput(0,11){3} % \centerput(0,-7){composantes~:} \centerput(0,-11){\{1\},\{2,3\},\{4\}} } \setbox\boxsix=\vbox{\vskip 12mm\offinterlineskip \fleche(0,0)\dir(2,1)\long{6} \segment(0,0)\dir(2,1)\long{10} \segment(10,5)\dir(-2,1)\long{10} \fleche(0,10)\dir(2,-1)\long{6} \segment(0,10)\dir(0,-1)\long{10} \fleche(0,10)\dir(0,-1)\long{6} \segment(0,0)\dir(-2,1)\long{10} \fleche(-10,5)\dir(2,-1)\long{6} \fleche(0,10)\dir(-2,-1)\long{6} \segment(-10,5)\dir(2,1)\long{10} % \centerput(12,4){1} \centerput(-12,4){4} \centerput(0,-3){2} \centerput(0,11){3} % \centerput(0,-7){composantes~:} \centerput(0,-11){\{1\},\{2\},\{3,4\}} } \setbox\boxsept=\vbox{\vskip 12mm\offinterlineskip \fleche(0,0)\dir(2,1)\long{6} \segment(0,0)\dir(2,1)\long{10} \segment(10,5)\dir(-2,1)\long{10} \fleche(0,10)\dir(2,-1)\long{6} \segment(0,10)\dir(0,-1)\long{10} \fleche(0,0)\dir(0,1)\long{6} \segment(0,0)\dir(-2,1)\long{10} \fleche(0,0)\dir(-2,1)\long{6} \fleche(-10,5)\dir(2,1)\long{6} \segment(-10,5)\dir(2,1)\long{10} % \centerput(12,4){1} \centerput(-12,4){4} \centerput(0,-3){2} \centerput(0,11){3} % \centerput(0,-7){composantes~:} \centerput(0,-11){\{1\},\{2,3,4\}} } $$ \box\boxquatre\hskip3cm\box\boxcinq \hskip3cm\box\boxsix \hskip3cm\box\boxsept $$ \endinsert %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bigskip \bigskip \bigskip \bigskip \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % Le polyn\^ome chromatique % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \centerline{\bf 6. Le polyn\^ome chromatique~: bases exotiques} \bigskip Notons $\chi(G)$ le nombre chromatique de $G$, i.~e.~le plus petit nombre de couleurs n\'ecessaire pour colorier les sommets de $G$ de fa\c con r\'eguli\`ere. Gr\^ace \`a la proposition~5.1 et \`a la formule du bin\^ome, on obtient le d\'eveloppe\-ment du polyn\^ome chromatique du graphe $G = (V,E)$ dans les deux bases $$ \lambda^{\underline{k}} \; := \; k! {\lambda \choose k}, \quad \lambda^{\overline{k}} \; := \; k! \biggl({\lambda \choose k}\biggr) \; = \; k! {\lambda+k-1 \choose k} \; = \; k! (-1)^k{-\lambda \choose k}. $$ \medskip \noindent {\sc Proposition 6.1.} (Brenti~[3]) $$\openup2pt\eqalign{ 1+\chi_{G,\lambda}(\nu) \; &= \; \sum_{k=0}^\infty I_G(\nu)^k {\lambda \choose k}, \quad 1+\chi_{G,-\lambda}(\nu) \; = \; \sum_{k=0}^\infty [-I_G(\nu)]^k \biggl({\lambda \choose k}\biggr), \cr 1+\chi_{G,-\lambda}(-\nu) \; &= \; \sum_{k=0}^\infty A_G(\nu)^k {\lambda \choose k}, \;\; 1+\chi_{G,\lambda}(-\nu) \; = \; \sum_{k=0}^\infty [-A_G(\nu)]^k \biggl({\lambda \choose k}\biggr). \cr }$$ {\it Alors, avec $|V| = n$, on a} $$\openup2pt\eqalign{ \chi_G(\lambda) \; &= \; \lambda^{\underline{n}} + i_{n-1} \cdot \lambda^{\underline{n-1}} + i_{n-2} \cdot \lambda^{\underline{n-2}} + \dots + i_1 \cdot \lambda \cr &= \; \lambda^{\overline{n}} - a_{n-1} \cdot \lambda^{\overline{n-1}} + a_{n-2} \cdot \lambda^{\overline{n-2}} - \dots + (-1)^{n-1} a_1 \cdot \lambda, \cr }$$ {\it o\`u les $i_k$ sont des entiers positifs (d\'enombrant des partitions en ensembles ind\'ependants non-vides) et les $a_k$ sont des entiers strictement positifs (d\'enombrant des partitions en orientations acycliques), $1 \le k \le n-1$. En particulier, $i_{n-1} = {n \choose 2} - |E|$, $a_{n-1} = {n \choose 2} + |E|$, $a_1 = a(G)$ et $i_1$ est \'egal \`a $1$ si $|E| = 0$ et \'egal \`a $0$ sinon. De plus, on a $i_k = 0$, si $k < \chi(G)$, et $i_k > 0$, si $k \ge \chi(G)$.\qeda} \eject Le r\'esultat sur les nombres $a_k$ constitue un des th\'eor\`emes principaux de~[3] (\`a savoir le th\'eor\`eme~5.5 qui est directement \'equivalent au th\'eor\`eme~5.3). Remarquons que la d\'emonstration de Brenti (par induction simultan\'ee sur le nombre des sommets et des ar\^etes du graphe) est la plus longue de tout l'article~[3], bien que Brenti remercie l'arbitre {\lfq for suggesting a simplification in the proof of theorem~5.3\rfq}. \bigskip \medskip \noindent Brenti~[3] a \'egalement regard\'e $$ \frac{p_G(x)}{(1-x)^{n+1}} \; := \; \sum_{\lambda = 0}^\infty \chi_G(\lambda) \cdot x^\lambda \quad \Rightarrow \quad -\frac{p_G(\frac{1}{x})}{(1-\frac{1}{x})^{n+1}} \; = \; \sum_{\lambda = 0}^\infty \chi_G(-\lambda) \cdot x^\lambda, $$ o\`u l'implication est une cons\'equence de [23], chapitre 4.2. Dans cet esprit, nous nous proposons de trouver plusieurs expressions pour $$ \overline{P}_{G,x}(\nu) \; := \; \sum_{\emptyset \subset V' \subseteq V} \frac{p_{G[V']}(x)}{(1-x)^{|V'|+1}} \cdot \nu^{V'}. $$ \medskip \noindent {\sc Proposition 6.2.} {\it On a} $$\openup2pt\eqalign{ {\textstyle{1 \over 1-x}} + \overline{P}_{G,x}(\nu) \; &= \; \sum_{\lambda = 0}^\infty [1+I_G(\nu)]^\lambda \cdot x^\lambda \; = \; \frac{1}{1-x[1+I_G(\nu)]} \cr &= \; \frac{1}{1-x} \cdot \Bigl[1 - \frac{x}{1-x} I_G(\nu)\Bigr]^{-1} \; = \; \frac{1}{1-x} \cdot \sum_{k=0}^\infty \Bigl(\frac{x \cdot I_G(\nu)}{1-x}\Bigr)^k, \cr {\textstyle{1 \over 1-x}} - \overline{P}_{G,\frac{1}{\scriptstyle x}}(-\nu) \; &= \; \sum_{\lambda = 0}^\infty [1+A_G(\nu)]^\lambda \cdot x^\lambda \; = \; \frac{1}{1-x[1+A_G(\nu)]} \cr &= \; \frac{1}{1-x} \cdot \Bigl[1 - \frac{x}{1-x} A_G(\nu)\Bigr]^{-1} \; = \; \frac{1}{1-x} \cdot \sum_{k=0}^\infty \Bigl(\frac{x \cdot A_G(\nu)}{1-x}\Bigr)^k, \cr {\textstyle{1 \over x-1} + \frac{1}{x}} \cdot \overline{P}_{G,\frac{1}{\scriptstyle x}}(\nu) \; &= \; \frac{1}{x-[1+I_G(\nu)]} \; = \; \frac{1}{x-1} \cdot \sum_{k=0}^\infty \Bigl(\frac{I_G(\nu)}{x-1}\Bigr)^k, \cr {\textstyle{1 \over x-1} - \frac{1}{x}} \cdot \overline{P}_{G,x}(-\nu) \; &= \; \frac{1}{x-[1+A_G(\nu)]} \; = \; \frac{1}{x-1} \cdot \sum_{k=0}^\infty \Bigl(\frac{A_G(\nu)}{x-1}\Bigr)^k.\qeda \cr }$$ \bigskip \noindent {\sc Remarque 6.1.} On n'a pas besoin de s'appuyer sur [23], chapitre 4.2, puisque l'identit\'e fondamentale $$\bf \frac{1}{1-y} \; = \; 1 - \frac{1}{1-\frac{1}{y}} $$ implique \'evidemment $$\openup2pt\eqalign{ &{\textstyle{1 \over 1-x}} + \overline{P}_{G,x}(\nu) \; = \; \frac{1}{1-x[1+I_G(\nu)]} \; = \; 1 - \frac{1}{1-\frac{1}{x}[1+A_G(-\nu)]} \quad \Rightarrow \cr &\frac{1}{1-x[1+A_G(\nu)]} \; = \; 1-{1 \over 1-{1 \over x}} - \overline{P}_{G,\frac{1}{\scriptstyle x}}(-\nu) \; = \; {\textstyle{1 \over 1-x}} - \overline{P}_{G,\frac{1}{\scriptstyle x}}(-\nu). \cr }$$ \bigskip \medskip \noindent Calculons aussi la fonction g\'en\'eratrice $$ P_{G,x}(\nu) \; := \; \sum_{\emptyset \subset V' \subseteq V} p_{G[V']}(x) \cdot \nu^{V'}. $$ \bigskip \noindent {\sc Proposition 6.3.} (Tomescu~[25], Gansner-Vo~[8], Brenti~[3]) {\it On a} $$\openup2pt\eqalign{ 1 + P_{G,x}(\nu) \; &= \; \Bigl(1 - \frac{x \cdot I_G[(1-x)\nu]}{1-x}\Bigr)^{-1} \; = \; \sum_{k=0}^\infty \Bigl(\frac{x \cdot I_G[(1-x)\nu]}{1-x}\Bigr)^k, \cr 1 + x \cdot P_{G,\frac{1}{\scriptstyle x}}(x\nu) \; &= \; \Bigl(1 - \frac{x \cdot A_G[(1-x)\nu]}{1-x}\Bigr)^{-1} \; = \; \sum_{k=0}^\infty \Bigl(\frac{x \cdot A_G[(1-x)\nu]}{1-x}\Bigr)^k, \cr 1 + P_{G,\frac{1}{\scriptstyle x}}(x\nu) \; &= \; \Bigl(1 - \frac{I_G[(x-1)\nu]}{x-1}\Bigr)^{-1} \; = \; \sum_{k=0}^\infty \Bigl(\frac{I_G[(x-1)\nu]}{x-1}\Bigr)^k, \cr 1 + {\textstyle{1 \over x}} \cdot P_{G,x}(\nu) \; &= \; \Bigl(1 - \frac{A_G[(x-1)\nu]}{x-1}\Bigr)^{-1} \; = \; \sum_{k=0}^\infty \Bigl(\frac{A_G[(x-1)\nu]}{x-1}\Bigr)^k. \cr }$$ {\it Alors, avec les nombres $i_k$ et $a_k$ de la proposition 6.1 on a notamment} $$\openup2pt\eqalign{ p_G(x) \; &= \; n! \cdot x^n + i_{n-1} \cdot (n-1)! \cdot x^{n-1}(1-x) + i_{n-2} \cdot (n-2)! \cdot x^{n-2}(1-x)^2 + \cr & \quad \;\; \dots + i_2 \cdot 2 \cdot x^2(1-x)^{n-2} + i_1 \cdot x(1-x)^{n-1} \cr \; &= \; n! \cdot x + a_{n-1} \cdot (n-1)! \cdot x(x-1) + a_{n-2} \cdot (n-2)! \cdot x(x-1)^2 + \cr & \quad \;\; \dots + a_2 \cdot 2 \cdot x(x-1)^{n-2} + a_1 \cdot x(x-1)^{n-1}.\qeda \cr }$$ \bigskip Supposons que $V = \{1,2,\dots,n\}$. Pour $\emptyset \subset V',V'' \subseteq V$ soit $V' < V''$ si et seulement si $v' < v''$ pour tout $v' \in V'$ et $v'' \in V''$. De plus, pour des ensembles de sommets non vides, deux \`a deux disjoints et ind\'ependants $I_1,\dots,I_k$, soit $G[\{I_1,\dots,I_k\}]$ le graphe dont les sommets sont les $k$ ensembles $I_1,\dots,I_k$ et tel que $\{I_{i_1},\dots,I_{i_j}\}$, $\emptyset \subset \{i_1,\dots,i_j\} \subseteq \{1,\dots,k\}$, est un ensemble de $j$ sommets ind\'ependants si et seulement si $I_{i_1} \cup \dots \cup I_{i_j}$ est ind\'ependant dans le graphe $G$ et (apr\`es une permutation appropri\'ee de $\{i_1,\dots,i_j\}$) $I_{i_1} < \dots < I_{i_j}$ (voir~[8]). Alors la proposition pr\'ec\'edente ainsi que le th\'eor\`eme 3.1 impliquent~: $$\openup2pt\eqalign{ &1 + P_{G,x}(\nu) \cr &= \; \Biggl( 1 - \sum_{\scriptstyle \emptyset \subset I \subseteq V \atop \scriptstyle I \; \hbox{\eightrm ind\'ependant}} x(1-x)^{|I|-1} \cdot \nu^I \Biggr)^{-1} \cr &= \; \Biggl( 1 + \sum_{\scriptstyle \emptyset \subset I \subseteq V \atop \scriptstyle I \; \hbox{\eightrm ind\'ependant}} \nu^I \cdot \sum_{j=1}^{|I|} {|I|-1 \choose j-1} \cdot (-x)^j \Biggr)^{-1} \cr &= \; \Biggl( 1 + \sum_{\scriptstyle \emptyset \subset I \subseteq V \atop \scriptstyle I \; \hbox{\eightrm ind\'ependant}} \sum_{\scriptstyle I_1 \uplus \dots \uplus I_j = I \atop \scriptstyle I_1 < \dots < I_j} (-x \nu^{I_1}) \cdot \dots \cdot (-x \nu^{I_j}) \Biggr)^{-1} \cr &= \; 1 + \sum_{\emptyset \subset V' \subseteq V} \sum_{\scriptstyle I_1 \uplus \dots \uplus I_k = V' \atop \scriptstyle I_1,\dots,I_k \; \hbox{\eightrm ind\'ependants}} a\Bigl(G[\{I_1,\dots,I_k\}]\Bigr) \cdot (x \nu^{I_1}) \cdot \dots \cdot (x \nu^{I_k}). \cr }$$ \bigskip \noindent {\sc Proposition 6.4.} (Linial~[15], Gansner-Vo~[8], Tomescu~[25]) {\it On a} $$ 1 + P_{G,x}(\nu) \; = \; 1 + \sum_{\emptyset \subset V' \subseteq V} \sum_{\scriptstyle I_1 \uplus \dots \uplus I_k = V' \atop \scriptstyle I_1,\dots,I_k \; \hbox{\eightrm ind\'ependants}} a\Bigl(G[\{I_1,\dots,I_k\}]\Bigr) \cdot (x \nu^{I_1}) \cdot \dots \cdot (x \nu^{I_k}). $$ {\it En particulier,} $$ p_G(x) \; = \; p_n x^n + p_{n-1} x^{n-1} + \dots + p_1 x $$ {\it o\`u les $p_k$, $1 \le k \le n$, sont des entiers positifs tels que $p_n + p_{n-1} + \dots + p_1 = p_G(1) = n!$. De plus, $p_n = a_1 = a(G)$ et $p_1$ est \'egal \`a $1$ si $|E| = 0$ et \'egal \`a $0$ sinon. Si $\chi(G)$ est le nombre chromatique de $G$, alors $p_k = 0$, si $k < \chi(G)$, et $p_k > 0$, si $k \ge \chi(G)$, $p_{\chi(G)} = i_{\chi(G)} \cdot \chi(G)!$.\qeda } \bigskip \medskip Brenti~[3] a aussi introduit et \'etudi\'e beaucoup de polyn\^omes qui ne furent jamais consid\'er\'es auparavant. \`A partir du polyn\^ome chromatique, leurs fonctions d'ensembles peuvent \^etre d\'efinies comme suit~: $$\openup0pt\eqalign{ 1+\chi_{G,\lambda}(\nu) \; &= \; [1+I_G(\nu)]^\lambda \; = \; \sum_{k=0}^\infty {\lambda \choose k} I_G(\nu)^k, \cr 1+\sigma_{G,\lambda}(\nu) \; &= \; \exp[\lambda I_G(\nu)] \; = \; \sum_{k=0}^\infty \lambda^k I_G(\nu)^k/k!, \cr 1+\overline{\sigma}_{G,\lambda}(\nu) \; &= \; [1-\lambda I_G(\nu)]^{-1} \; = \; \sum_{k=0}^\infty \lambda^k I_G(\nu)^k, \cr 1+\chi_{G,\lambda}(\nu) \; &= \; [1+A_G(-\nu)]^{-\lambda} \; = \; \sum_{k=0}^\infty \biggl({\lambda \choose k}\biggr) [-A_G(-\nu)]^k, \cr 1+\tau_{G,\lambda}(\nu) \; &= \; \exp[\lambda A_G(\nu)] \; = \; \sum_{k=0}^\infty \lambda^k A_G(\nu)^k/k!, \cr 1+\overline{\tau}_{G,\lambda}(\nu) \; &= \; [1-\lambda A_G(\nu)]^{-1} \; = \; \sum_{k=0}^\infty \lambda^k A_G(\nu)^k. \cr }$$ Finalement, une comparaison avec la proposition~6.2 fournit les identit\'es $$\openup2pt\eqalign{ 1 + (1-x) \cdot \overline{P}_{G,x}(\nu) \; &= \; 1 + \overline{\sigma}_{G,\textstyle{x \over 1-x}}(\nu) \quad \; \hbox{et} \cr 1 + ({\textstyle{ 1 \over x}}-1) \cdot \overline{P}_{G,x}(-\nu) \; &= \; 1 + \overline{\tau}_{G,\textstyle{1 \over x-1}}(\nu), \quad \hbox{d'o\`u} \cr }$$ \medskip \noindent {\sc Proposition 6.5.} (Brenti~[3]) $$\textstyle \overline{P}_{G,x}(\nu) \; = \; {1 \over 1-x} \cdot \overline{\sigma}_{G,\textstyle{x \over 1-x}}(\nu) \; = \; {x \over 1-x} \cdot \overline{\tau}_{G,\textstyle{1 \over x-1}}(-\nu).\qeda $$ \bigskip \bigskip %%%%%%%%%%%%%%%%%%% % % % Appendice I % % % %%%%%%%%%%%%%%%%%%% \centerline{\bf 7. Appendice~I~: Les travaux de Gessel et Stanley} \bigskip \noindent Une d\'erivation de notre polyn\^ome chromatique par rapport \`a plusieurs \'el\'ements fournit~: $$\openup2pt\eqalign{ 1+\chi_{G,\lambda}(\nu) \; &= \; [1+I_G(\nu)]^{\lambda}, \cr \partial^s \chi_{G,\lambda}(\nu)/\lambda \; &= \; [1+I_G(\nu)]^{\lambda-1} \cdot \partial^s I_G(\nu), \cr \partial^{\{s,p\}} \chi_{G,\lambda}(\nu)/\lambda(\lambda-1) \; &= \; [1+I_G(\nu)]^{\lambda-2} \cdot \partial^s I_G(\nu) \partial^p I_G(\nu), \cr \partial^{\{s,p,q\}} \chi_{G,\lambda}(\nu)/\lambda(\lambda-1)(\lambda-2) \; &= \; [1+I_G(\nu)]^{\lambda-3} \cdot \partial^s I_G(\nu) \partial^p I_G(\nu) \partial^q I_G(\nu), \cr }$$ si $\{s,p\}$ (resp.~$\{s,p,q\}$) est une ar\^ete (resp.~un triangle) de $G$, des conditions que l'on supposera toujours satisfaites dans la suite. \eject \noindent \`A l'aide du th\'eor\`eme~3.1 et de la proposition~3.2, on d\'eduit des expressions positives~: $$\openup2pt\eqalign{ 1+\chi_{G,-\lambda}(-\nu) \; &= \; [1+A_G(\nu)]^{\lambda}, \cr \partial^s \chi_{G,-\lambda}(-\nu)/\lambda \; &= \; [1+A_G(\nu)]^{\lambda} \cdot A_{G,s}(\nu), \cr \partial^{\{s,p\}} \chi_{G,-\lambda}(-\nu)/\lambda(\lambda+1) \; &= \; [1+A_G(\nu)]^{\lambda} \cdot A_{G,s}(\nu) A_{G,p}(\nu), \cr \partial^{\{s,p,q\}} \chi_{G,-\lambda}(-\nu)/\lambda(\lambda+1)(\lambda+2) \; &= \; [1+A_G(\nu)]^{\lambda} \cdot A_{G,s}(\nu) A_{G,p}(\nu) A_{G,q}(\nu), \cr }$$ o\`u les trois premi\`eres \'egalit\'es reprennent les th\'eor\`emes~3.2, 3.4 et 3.3 de Gessel~[10], res\-pectivement. Gr\^ace \`a la proposition~4.1, on peut r\'ecrire la troisi\`eme expression de la fa\c con suivante~: $$ \partial^{\{s,p\}} \chi_{G,-\lambda}(-\nu)/\lambda(\lambda+1) \; = \; [1+A_G(\nu)]^{\lambda+1} \cdot A_{G,s,p}(\nu). $$ Cependant, cette expression n'est particuli\`erement int\'eressante que si $\lambda = -1$, puisque, en g\'en\'eral, $A_{G,s,p}(\nu)$ n'est pas positif, au moins pour certains sous-graphes engendr\'es de $G$. Le cas $\lambda = -1$ fut utilis\'e par Gessel~[10] pour d\'emontrer son th\'eor\`eme~3.1 correspondant au th\'eor\`eme~4.1 de cet article. \bigskip \noindent Dans l'esprit du paragraphe~6, calculons $$\matrix{ \displaystyle \sum_{\lambda=0}^\infty [1+\chi_{G,\lambda}(\nu)] \cdot x^\lambda \qquad \hfill & \displaystyle \sum_{\lambda=1}^\infty {\partial^s \chi_{G,\lambda}(\nu) \over \lambda} \cdot x^{\lambda-1} \qquad \hfill & \displaystyle \sum_{\lambda=2}^\infty {\partial^{\{s,p\}} \chi_{G,\lambda}(\nu) \over \lambda(\lambda-1)} \cdot x^{\lambda-2} \hfill \cr \displaystyle = \; {1 \over 1 - x[1+I_G(\nu)]}, \qquad \hfill & \displaystyle = \; {\partial^s I_G(\nu) \over 1 - x[1+I_G(\nu)]}, \qquad \hfill & \displaystyle = \; {\partial^s I_G(\nu) \partial^p I_G(\nu) \over 1 - x[1+I_G(\nu)]}, \hfill \cr }$$ et posons $$\matrix{ \displaystyle \sum_{\lambda=0}^\infty \chi_G(\lambda) \cdot x^\lambda \qquad \quad \hfill & \displaystyle \sum_{\lambda=1}^\infty {\chi_G(\lambda) \over \lambda} \cdot x^{\lambda-1} \qquad \quad \hfill & \displaystyle \sum_{\lambda=2}^\infty {\chi_G(\lambda) \over \lambda(\lambda-1)} \cdot x^{\lambda-2} \hfill \cr \displaystyle =: \; {p_G(x) \over (1-x)^{n+1}}, \qquad \quad \hfill & \displaystyle =: \; {q_G(x) \over (1-x)^{n }}, \qquad \quad \hfill & \displaystyle =: \; {r_G(x) \over (1-x)^{n-1}}. \hfill \cr }$$ Pour les fonctions d'ensembles $P_{G,x}(\nu)$, $Q_{G,x}(\nu)$ et $R_{G,x}(\nu)$ d\'enombrant les poly\-n\^omes $p$, $q$ et $r$, respectivement, on obtient alors l'analogue de la proposition~6.3~: \bigskip \noindent {\sc Proposition 7.1.} {\it On a} $$\openup2pt\eqalign{ 1 + P_{G,x}(\nu) \; &= \; \Bigl(1 - {x \cdot I_G[(1-x)\nu] \over 1-x}\Bigr)^{-1}, \cr \partial^s Q_{G,x}(\nu) \; &= \; \Bigl(1 - {x \cdot I_G[(1-x)\nu] \over 1-x}\Bigr)^{-1} \cdot {\partial^s I_G[(1-x)\nu] \over 1-x}, \cr \partial^{\{s,p\}} R_{G,x}(\nu) \; &= \; \Bigl(1 - {x \cdot I_G[(1-x)\nu] \over 1-x}\Bigr)^{-1} \cdot {\partial^s I_G[(1-x)\nu] \over 1-x} {\partial^p I_G[(1-x)\nu] \over 1-x}. \cr }$$ {\it Alors avec les nombres $i_k$ des propositions~6.1 et~6.3 on a notamment ($i_1 = 0$ si $\{s,p\}$ est une ar\^ete de $G$)} $$\openup2pt\eqalign{ p_G(x) \; &= \; n! \cdot x^n + i_{n-1} \cdot (n-1)! \cdot x^{n-1}(1-x) + \cr & \quad \;\; \dots + i_2 \cdot 2 \cdot x^2(1-x)^{n-2} + i_1 \cdot x(1-x)^{n-1}, \cr q_G(x) \; &= \; (n-1)! \cdot x^{n-1} + i_{n-1} \cdot (n-2)! \cdot x^{n-2}(1-x) + \cr & \quad \;\; \dots + i_2 \cdot x(1-x)^{n-2} + i_1 \cdot (1-x)^{n-1}, \cr r_G(x) \; &= \; (n-2)! \cdot x^{n-2} + i_{n-1} \cdot (n-3)! \cdot x^{n-3}(1-x) + \cr & \quad \;\; \dots + i_2 \cdot (1-x)^{n-2}.\qeda \cr }$$ \bigskip Pour des ensembles de sommets non vides, deux \`a deux disjoints et ind\'ependants $I_1,\dots,I_k$, utilisons de nouveau le graphe $G[\{I_1,\dots,I_k\}]$ introduit dans le paragraphe~6. Si, pour le sommet $s \in V$, il existe un $i \in \{1,\dots,k\}$ tel que $s \in V_i$, notons $a_s \bigl( G[\{I_1,\dots,I_k\}] \bigr)$ le nombre d'orientations acycliques du graphe $G[\{I_1,\dots,I_k\}]$ dont le sommet correspondant \`a $V_i$ est la source unique. De m\^eme, si pour les deux extr\'emit\'es de l'ar\^ete $\{s,p\}$, il existe des $i,j \in \{1,\dots,k\}$ tels que $s \in V_i$ et $p \in V_j$, notons $a_{s,p} \bigl( G[\{I_1,\dots,I_k\}] \bigr)$ le nombre d'orientations acycliques du graphe $G[\{I_1,\dots,I_k\}]$ dont le sommet correspondant \`a $V_i$ est la source unique et dont le sommet correspondant \`a $V_j$ est le puits unique (nous supposons ici que $G$ ne contient aucun sommet isol\'e, voir la d\'efinition~4.1). On d\'emontre alors exactement comme dans le paragraphe~6 (en s'appuyant, de plus, sur les propositions~3.2 et 4.1)~: \bigskip \noindent {\sc Proposition 7.2.} (Gessel~[10]) {\it On a} $$\openup2pt\eqalign{ P_{G,x}(\nu) \; &= \; \sum_{\scriptstyle \emptyset \subset I_1 \uplus \dots \uplus I_k \subseteq V \atop \scriptstyle I_1,\dots,I_k \; \hbox{\eightrm ind\'ependants}} a\Bigl(G[\{I_1,\dots,I_k\}]\Bigr) \cdot (x \nu^{I_1}) \cdot \dots \cdot (x \nu^{I_k}), \cr \partial^s Q_{G,x}(\nu) \; &= \; \sum_{\scriptstyle s \in I_1 \uplus \dots \uplus I_k \subseteq V \atop \scriptstyle I_1,\dots,I_k \; \hbox{\eightrm ind\'ependants}} \!\!\!\!\!\!\!\!\!\!\!\!\!x^{-1} \cdot a_s\Bigl(G[\{I_1,\dots,I_k\}]\Bigr) \cdot (x \nu^{I_1}) \cdot \dots \cdot (x \nu^{I_k}), \cr \partial^{\{s,p\}} R_{G,x}(\nu) \; &= \; \sum_{\scriptstyle s,p \in I_1 \uplus \dots \uplus I_k \subseteq V \atop \scriptstyle I_1,\dots,I_k \; \hbox{\eightrm ind\'ependants}} \!\!\!\!\!\!\!\!\!\!\!\!\!x^{-2} \cdot a_{s,p}\Bigl(G[\{I_1,\dots,I_k\}]\Bigr) \cdot (x \nu^{I_1}) \cdot \dots \cdot (x \nu^{I_k}). \cr }$$ {\it En particulier,} $$\openup2pt\eqalign{ p_G(x) \; &= \; p_n x^n + p_{n-1} x^{n-1} + \dots + p_1 x, \cr q_G(x) \; &= \; q_{n-1} x^{n-1} + q_{n-2} x^{n-2} + \dots + q_1 x + q_0, \cr r_G(x) \; &= \; r_{n-2} x^{n-2} + r_{n-3} x^{n-3} + \dots + r_1 x + r_0, \cr }$$ {\it o\`u les $p_k$, $q_k$ et $r_k$ sont des entiers positifs (dans le cas des $r_k$ il faut supposer, de plus, que $G$ ne contient aucun sommet isol\'e) tels que $p_G(1) = n!$, $q_G(1) = (n-1)!$ et $r_G(1) = (n-2)!$ ainsi que $p_n = a(G)$, $q_{n-1} = a_s(G)$ et $r_{n-2} = a_{s,p}(G)$. Si $\chi(G)$ est le nombre chromatique de $G$ et $k < \chi(G)$, alors $p_k = 0$, $q_{k-1} = 0$ et $r_{k-2} = 0$ ainsi que $p_{\chi(G)} = i_{\chi(G)} \cdot \chi(G)!$, $q_{\chi(G)-1} = i_{\chi(G)} \cdot (\chi(G)-1)!$ et $r_{\chi(G)-2} = i_{\chi(G)} \cdot (\chi(G)-2)!$. Si $k \ge \chi(G)$, on a $p_k > 0$, et $q_{k-1} > 0$ si $G$ est connexe.\qeda } \bigskip \noindent \'Evidemment, on a aussi les expressions directes~: \bigskip \noindent {\sc Proposition 7.3.} \vskip-10pt $$\openup2pt\eqalign{ x \cdot Q_{G,x}(\nu) \; = \; &-\log \Bigl(1 - {x \cdot I_G[(1-x)\nu] \over 1-x}\Bigr), \cr x^2 \cdot R_{G,x}(\nu) \; = \; &\Bigl(1 - {x \cdot I_G[(1-x)\nu] \over 1-x}\Bigr) \cdot \log \Bigl(1 - {x \cdot I_G[(1-x)\nu] \over 1-x}\Bigr) \cr &+ {x \cdot I_G[(1-x)\nu] \over 1-x} \cdot \bigl[1-\log(1-x)\bigr].\qeda \cr }$$ \bigskip Notons que la positivit\'e des coefficients du polyn\^ome $r_G(x)$ est le r\'esultat principal de l'article~[10] de Gessel (d\'emontr\'e sur plus qu'une page \`a l'aide du th\'eor\`eme fondamental de Stanley sur les $P$-partitions) tandis que le polyn\^ome $q_G(x)$ n'y figure pas. \bigskip \medskip Remarquons finalement que Stanley~[22] a introduit et \'etudi\'e la fonction chromatique $X_G = X_G(x_1,x_2,x_3,\dots)$ que l'on peut, avec l'aide des fonctions d'ensembles, d\'efinir comme suit~: $$ 1 + \sum_{\emptyset \subset V' \subseteq V} X_{G[V']} \cdot \nu^{V'} \; := \; \prod_{i=1}^\infty \Bigl[ 1 + I_G(x_i \cdot \nu) \Bigr] \; = \; \exp \Bigl[ \sum_{i=1}^\infty -A_G^*(-x_i \cdot \nu) \Bigr]. $$ \bigskip \bigskip %%%%%%%%%%%%%%%%%%%% % % % Appendice II % % % %%%%%%%%%%%%%%%%%%%% \centerline{\bf 8. Appendice~II~: se passer des fonctions d'ensembles} \bigskip On pourrait \^etre f\^ach\'e de cette volont\'e syst\'ematique d'imposer les fonctions d'en\-sembles ou, qui pis est, leurs fonctions g\'en\'eratrices. C'est pourquoi il nous semble particuli\`erement important de bien expliciter plusieurs m\'ethodes permettant de s'en passer. Comme indiqu\'e dans le paragraphe~2, il s'agit de construire des mod\`eles combinatoires infinis qui ne font intervenir que les cardinalit\'es. \medskip Rempla\c cons donc chaque sommet $v \in V$ de notre graphe simple $G = (V,E)$ par une famille infinie $V_v$ de sommets, et relions (par une ar\^ete) deux sommets $u' \in V_u$ et $v' \in V_v$ avec $u,v \in V$ et $u \ne v$, si et seulement si $u$ et $v$ sont reli\'es dans le graphe~$G$. Ces d\'efinitions sont assez naturelles tandis qu'il n'est point clair s'il faut relier deux sommets diff\'erents d'un m\^eme ensemble $V_v$. En effet, pour tout $v \in V$, on a le choix de laisser $V_v$ comme ensemble ind\'ependant infini ou bien de le remplacer par un graphe complet infini. Si l'on se d\'ecide, pour tout $v \in V$, en faveur du graphe complet (resp.~de l'ensemble ind\'ependant), le graphe infini obtenu \`a partir de $G$ est not\'e $G_{\overline{\infty}}$ (resp.~$G_\infty$). Soit $V = \{1,2,\dots,n\}$. Alors les fonctions d'ensembles (ou bien leur fonctions g\'en\'eratrices) comme $I_{G_\infty}(\nu)$, $\chi_{G_\infty,\lambda}(\nu)$, $A_{G_\infty}(\nu)$, $A_{G_\infty}^*(\nu)$ et $A_{G_\infty,t}(\nu)$ (partout, $G_\infty$ peut \^etre remplac\'e par $G_{\overline{\infty}}$) sont, en effet, des fonctions g\'en\'era\-trices du type exponentiel en des variables (alg\'ebriquement) ind\'ependantes $v_1,v_2,\dots,v_n$, dont le coefficient de $(v_1^{i_1}/i_1!) \cdot \dots \cdot (v_n^{i_n}/i_n!)$ compte l'invariant respectif du graphe obtenu \`a partir de $G$ en rempla\c cant le sommet $1$ par $i_1$ exemplaires, le sommet $2$ par $i_2$ exemplaires, \dots, le sommet $n$ par $i_n$ exemplaires. \'Evidemment, tous ces invariants peuvent \^etre interpr\'et\'es avec l'aide du seul graphe $G$, et les th\'eor\`emes d\'emontr\'es dans les paragraphes pr\'ec\'edents fournissent des identit\'es pour eux. En particulier, l'identit\'e $1+A_{G_{\overline{\infty}}}(\nu) = [1+I_{G_{\overline{\infty}}}(-\nu)]^{-1}$ n'est rien d'autre que la proposition 5.1 de~[27] tandis que l'identit\'e $\log[1+A_{G_{\overline{\infty}}}(\nu)] = A^*_{G_{\overline{\infty}}}(\nu)$ n'est rien d'autre que la proposition 5.10 de~[27]. (Pour mettre les points sur les i, il faut ajouter que Viennot a remplac\'e les variables $v_1,v_2,\dots,v_n$ par des s\'eries sans terme constant et qu'il n'a pas mentionn\'e que, pour chaque ensemble de ses pi\`eces, le nombre de pyramides form\'ees de ces pi\`eces est divisible par le nombre de pi\`eces, puisque, pour chaque pi\`ece fix\'ee, le nombre de pyramides ayant cette pi\`ece en guise d'extr\'emit\'e est toujours le m\^eme.) En fait, m\^eme les inconditionnels des fonctions g\'en\'eratrices en une seule variable~$x$ peuvent s'y retrouver, puisque, dans toutes les identit\'es pour le graphe $G_\infty$ ou $G_{\overline{\infty}}$, on peut remplacer $(\nu)$ par $(x \cdot \nu)$ (m\^eme pour les fonctions d'ensembles). La substitution $\nu = 1$, i.~e.~$v_1 = v_2 = \dots = v_n = 1$, est alors bien d\'efinie (ceci est un v\'eritable avantage des fonctions g\'en\'eratrices du type exponentiel par rapport aux fonctions d'ensembles). Par exemple, le coefficient de $x^k$, $k > 0$, dans $I_{G_{\overline{\infty}}}(x)$ compte, pour notre graphe~$G$, le nombre d'ensembles ind\'ependants de cardinalit\'e~$k$; et la sp\'ecialisation $1+A_{G_{\overline{\infty}}}(x) = [1+I_{G_{\overline{\infty}}}(-x)]^{-1}$ du th\'eor\`eme~3.1 n'est rien d'autre que la relation de r\'eciprocit\'e du chapitre~2.1.2 de~[24]. \medskip Une m\'ethode tout \`a fait diff\'erente pour obtenir des fonctions g\'en\'eratrices (du type exponentiel) en la seule variable $V$ consiste \`a remplacer $G = (V,E)$ par le graphe al\'eatoire $G(p,q)$, $p+q = 1$, sur un ensemble infini $V$ de sommets, pour lequel la probabilit\'e d'avoir une ar\^ete entre deux sommets quelconques est \'egal \`a $p$, $0 \le p \le 1$ (et tous ces \'ev\'enements sont ind\'ependants). De cette mani\`ere, tous les coefficients de nos fonctions g\'en\'eratrices (pour les fonctions d'ensembles) deviennent des variables al\'eatoires, qui, dans les identit\'es, ne sont multipli\'ees que si elles sont ind\'ependantes. Alors, gr\^ace \`a la multiplicativit\'e de l'esp\'erance math\'ematique dans cette situation (et sa lin\'earit\'e sans restriction) on peut, dans toutes les identit\'es d\'ej\`a d\'emontr\'ees, remplacer chaque variable al\'eatoire par sa valeur moyenne. \medskip Notons, qu'un ensemble de $n$ sommets du graphe $G(p,q)$ est ind\'ependant avec la probabilit\'e $q^{n \choose 2}$. On en d\'eduit pour les esp\'erances math\'ematiques~: \bigskip \noindent {\sc Proposition 8.1.} $$ 1 + I_{G(p,q)} (V) \; = \; 1 + \sum_{n=1}^\infty q^{n \choose 2} \cdot V^n/n!.\qeda $$ \bigskip Alors, si $A_{G(p,q)} (V)$ compte le nombre moyen d'orientations acycliques, le th\'eor\`eme 3.1 implique (voir~[28], paragraphe 5)~: \bigskip \noindent {\sc Proposition 8.2.} (Welsh, Janson) $$ 1 + A_{G(p,q)} (V) \; = \; \Bigl[ 1 + \sum_{n=1}^\infty q^{n \choose 2} \cdot (-V)^n/n! \Bigr]^{-1}.\qeda $$ \bigskip Notons $a(n,m)$ le nombre de graphes orient\'es de fa\c con acyclique, qui ont $n$ sommets marqu\'es et $m$ ar\^etes. Il s'ensuit~: \bigskip \noindent {\sc Proposition 8.3.} (Liskovec~[16], Rodionov~[19]) {\it Soit $p+q = 1$. Alors on a} $$ 1 + \sum_{n=1}^\infty \Bigl[ \sum_{m=0}^{n \choose 2} a(n,m) \cdot p^m q^{{n \choose 2}-m} \Bigr] \cdot V^n/n! \; = \; \Bigl[ 1 + \sum_{n=1}^\infty q^{n \choose 2} \cdot (-V)^n/n! \Bigr]^{-1}.\qeda $$ \bigskip \noindent Regardons la sp\'ecialisation $p = q = 1/2$ et posons $a(n) \; := \; \sum_{m=0}^{n \choose 2} a(n,m)$. On obtient alors le r\'esultat de Stanley (voir~[21] ou~[23], chapitre~3.15)~: \bigskip \noindent {\sc Proposition 8.4.} (Stanley, Robinson~[18]) $$ 1 + \sum_{n=1}^\infty a(n) \cdot V^n/(2^{n \choose 2}n!) \; = \; \Bigl[ 1 + \sum_{n=1}^\infty (-V)^n/(2^{n \choose 2}n!) \Bigr]^{-1}.\qeda $$ \bigskip \'Evidemment, tous les autres r\'esultats de cet article peuvent \^etre sp\'ecialis\'es de la m\^eme fa\c con que le th\'eor\`eme~3.1. Cette sp\'ecialisation {\lfq probabiliste\rfq} du th\'eor\`eme~3.3 fournit notamment un des deux th\'eor\`emes principaux de l'article~[11], que Gessel a d\'emontr\'e en \'etablissant une relation de r\'ecurrence, dont il a imagin\'e la solution \`a l'aide des {\lfq bons d\'enominateurs\rfq}. \bigskip \bigskip %%%%%%%%%%%%%%%%%%%% % % % Appendice III % % % %%%%%%%%%%%%%%%%%%%% \centerline{\bf 9. Appendice~III~: se passer de la commutativit\'e} \bigskip Soit $G = (V,E)$, $V = \{1,2,\dots,n\}$, un graphe simple. Associons \`a ses $n$ sommets des variables $v_1,v_2,\dots,v_n$ et supposons que tout mon\^ome contenant une de ces variables au moins deux fois est nul. Ceci ne restreint pas la g\'en\'eralit\'e de nos consid\'erations parce que, selon l'appendice pr\'ec\'edent, on peut remplacer $G$ par $G_{\overline{\infty}}$ pour obtenir pr\'ecis\'ement les m\^emes r\'esultats que dans~[5] ou dans~[27]. \`A la diff\'erence de tous les autres paragraphes, cependant, nous ne supposons la loi commutative pour deux variables $v_i$ et $v_j$ que s'il n'y a pas d'ar\^ete entre les deux sommets $i,j \in V$. L'alg\`ebre associative ainsi obtenue est not\'ee $A[V]$ comme dans le cas commutatif. Il n'est pas difficile de d\'emontrer que chaque mon\^ome de $A[V]$ correspond, de fa\c con bijective, \`a une orientation acyclique du graphe engendr\'e par les sommets qui correspondent aux variables du mon\^ome. Pour \'ecrire le mon\^ome, commen\c cons par les variables des sources de l'orientation acyclique (ces variables commutent mutuellement puisque l'ensemble des sources est ind\'ependant). En appliquant la m\^eme proc\'edure au graphe engendr\'e par les sommets des autres variables du mon\^ome, on finit par obtenir une partition canonique des sommets du mon\^ome en ensembles ind\'ependants. Celle-ci est appel\'ee {\it V-d\'ecomposition} ou {\it forme normale de Foata} (voir~[24] ainsi que~[5], th\'eor\`eme~1.2). Notons $A_G(\nu)$, $A_G(0) = 0$, la somme de tous les mon\^omes diff\'erents de $A[V]$ de sorte qu'on recouvre la fonction $A_G(\nu)$ d\'ej\`a introduite en soumettant toutes les variables \`a la loi commutative. Si $I_G(\nu)$, $I_G(0) = 0$, d\'esigne la somme de tous les mon\^omes dont les variables commutent mutuellement (ce sont les mon\^omes correspondant aux ensembles ind\'ependants), alors la d\'emonstration m\^eme de la proposition~3.2, i.~e. le principe d'inclusion-exclusion, implique encore que le produit $[1+I_G(-\nu)] \cdot [1+A_G(\nu)]$ d\'enombre les orientations acycliques sans aucune source. Autrement dit, on a \'etabli le th\'eor\`eme de Cartier et Foata sur l'inversion (de M\"obius) dans le mono\"\i de de commutation, \`a savoir l'identit\'e (voir~[5], th\'eo\-r\`eme~2.4) $[1+I_G(-\nu)] \cdot [1+A_G(\nu)] = 1$. Cependant, les coefficients de $-\log[1+I_G(-\nu)]$ ne sont pas toujours des entiers dans le cas non-commutatif et la r\`egle $\partial^s -\log[1+I_G(-\nu)] = -[1+I_G(-\nu)]^{-1} \cdot \partial^s I_G(-\nu)$ n'est plus valable. Voil\`a pourquoi nous nous sommes impos\'es, dans cet article, la commutativit\'e pour toutes les variables. \bigskip \bigskip \bigskip {\it Remerciements.} En tout premier lieu, je voudrais remercier vivement D.~Foata de son accueil chaleureux \`a Strasbourg et de ses explications stimulantes en ce qui concerne le livre~[5]. Son aide et assistance sont au-del\`a de toute expression. Je remercie aussi E.~Triesch pour tout son appui dans mon projet de th\`ese v\'eritablement lotharingien. \bigskip \bigskip \bigskip %%%%%%%%%%%%%%%%%%%%%%% %% BIBLIOGRAPHIE %% %%%%%%%%%%%%%%%%%%%%%%% \centerline{\bf R\'ef\'erences bibliographiques} \medskip {\baselineskip=9pt\tenrm \item{[1]} B.~Bollob\'as, \lfq Modern Graph Theory\rfq, Springer-Verlag, Berlin, 1998. \smallskip \item{[2]} M.~Bousquet-M\'elou, q-\'Enum\'eration de polyominos convexes, {\it J.~Combin.~Theory, Ser.~A} {\bf 64} (1993), 265-288. \smallskip \item{[3]} F.~Brenti, Expansions of chromatic polynomials and log-concavity, {\it Trans.~Amer. Math. Soc.}~{\bf 332} (1992), 729-756. \smallskip \item{[4]} T.~H.~Brylawski et J.~G.~Oxley, \lfq The Tutte polynomial and its applications\rfq, in: {\it Matroid Applications}, (ed.~: N.~White) Cambridge University Press, Cambridge (1992), 123-225. \smallskip \item{[5]} P.~Cartier et D.~Foata, \lfq Probl\`emes combinatoires de commutation et r\'earrangements\rfq, Springer-Verlag, Berlin, 1969. \smallskip \item{[6]} H.~Crapo, A higher invariant for matroids, {\it J.~Combin.~Theory}~{\bf 2} (1967), 406-417. \smallskip \item{[7]} D.~Foata, A noncommutative version of the matrix inversion formula, {\it Adv. Math.}~{\bf 31} (1979), 330-349. \smallskip \item{[8]} E.~R.~Gansner, K.~P.~Vo, The chromatic generating function, {\it Linear and Multilinear Algebra}~{\bf 22} (1987), 87-93. \smallskip \item{[9]} D.~D.~Gebhard et B.~E.~Sagan, Sinks in acyclic orientations of graphs, {\it J.~Combin.~Theory, Ser.~B}~{\bf 80} (2000), 130-146. \smallskip \item{[10]} I.~M.~Gessel, Acyclic orientations and chromatic generating functions, {\it Discrete Math.}~{\bf 232} (2001), 119-130. \smallskip \item{[11]} I.~M.~Gessel, Counting acyclic digraphs by sources and sinks, {\it Discrete Math.}~{\bf 160} (1996), 253-258. \smallskip \item{[12]} C.~Greene et T.~Zaslavsky, On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-radon partitions, and orientations of graphs, {\it Trans. Amer.~Math.~Soc.}~{\bf 280} (1983), 97-126. \smallskip \item{[13]} A.~Huck, \lfq Fl\"usse und Wege in Graphen\rfq, Bonn, 1997. \smallskip \item{[14]} B.~Lass, \lfq Funktionen z\"ahlen\rfq, Diplomarbeit, 1997. \smallskip \item{[15]} N.~Linial, Graph colouring and monotone functions on posets, {\it Discrete Math.}~{\bf 58} (1986), 97-98. \smallskip \item{[16]} V.~A.~Liskovec, O chisle maksimalnyh vershin sluchajnogo aciklicheskogo orgrafa, {\it Teor. Verojatnost.~i Primenen.}~{\bf 20} (1975), 412-421. \smallskip \item{[17]} L.~Lov\'asz, \lfq Combinatorial Problems and Exercises\rfq, Akad\'emiai Kiad\'o, Budapest, 1993. \smallskip \item{[18]} R.~W.~Robinson, Counting labeled acyclic digraphs, in: {\it New Directions in the Theory of Graphs, Proc.~Third Ann Arbor Conference on Graph Theory}, (ed.~: F.~Harary) Academic Press, New York (1971), 239-273. \smallskip \item{[19]} V.~I.~Rodionov, Javnaja formula dlja chisla pomechennyh aciklicheskih orientirovannyh grafov, {\it Avtomorfnye funkcii i teorija chisel}, Sb.~nauch.~tr., Izhevsk (1987), 22-25. \smallskip \item{[20]} H.~Sachs, \lfq Einf\"uhrung in die Theorie der endlichen Graphen\rfq, Teil II, BSB B.~G.~Teubner Verlagsgesellschaft, 1972. \smallskip \item{[21]} R.~P.~Stanley, Acyclic orientations of graphs, {\it Discrete Math.}~{\bf 5} (1973), 171-178. \smallskip \item{[22]} R.~P.~Stanley, A symmetric function generalization of the chromatic polynomial of a graph, {\it Advances in Math.}~{\bf 111} (1995), 166-194. \smallskip \item{[23]} R.~P.~Stanley, \lfq Enumerative Combinatorics\rfq, Volume 1, Cambridge University Press, Cambridge, 1997. \smallskip \item{[24]} V.~Strehl, Counting domino tilings of rectangles via resultants, \`a para\^\i tre dans {\it Adv.~Appl. Math.}~(2001). \smallskip \item{[25]} I.~Tomescu, Graphical Eulerian numbers and chromatic generating functions, {\it Discrete Math.}~{\bf 66} (1987), 315-318. \smallskip \item{[26]} W.~T.~Tutte, \lfq Graph Theory\rfq, Addison-Wesley, 1984. \smallskip \item{[27]} G.~X.~Viennot, Heaps of pieces, I~: Basic definitions and combinatorial lemmas, {\it Combinatoire \'enum\'erative}, Proc.~Colloq., Montr\'eal/Can.~1985, {\it Lect.~Notes Math.}~{\bf 1234} (1986), 321-350. \smallskip \item{[28]} D.~J.~A.~Welsh, Counting colourings and flows in random graphs, {\it Combinatorics, Paul Erd\"os is Eighty}, Volume 2, Keszthely (Hungary), 1993, {\it Bolyai Society Mathematical Studies}~{\bf 2} (1996), 491-505. \smallskip } \bigskip \bigskip \bigskip \vskip 12pt \rightline{\sc Bodo Lass} \rightline{\it Lehrstuhl II f\"ur Mathematik,} \rightline{\it RWTH Aachen,} \rightline{\it Templergraben 55,} \rightline{\it D-52062 Aachen, Allemagne.} \rightline{Courriel: lass@math2.rwth-aachen.de} \vskip 6pt \rightline{et} \vskip 6pt \rightline{\it D\'epartement de math\'ematique,} \rightline{\it Universit\'e Louis-Pasteur,} \rightline{\it 7, rue Ren\'e-Descartes,} \rightline{\it F-67084 Strasbourg, France.} \rightline{Courriel: lass@math.u-strasbg.fr} \vskip 12pt \end