Europ. J. Combinatorics 22, 1101–1123, 2001

Orientations acycliques et le polynôme chromatique

BODO LASS

On attache à tout graphe G son polynôme chromatique χ_{G}(λ), qui dénombre ses colorations régulières avec λ couleurs. D’après Stanley, on sait que |χ_{G}(−1)| est égal au nombre d’orientations acycliques du graphe, un résultat qui fut raffiné par Greene et Zaslavsky. Nous nous proposons de l’affiner davantage en interprétant, avec l’aide de certaines orientations acycliques, les coefficients de χ_{G}(λ) développé en puissances de λ et surtout en puissances de (λ−1). L’utilisation systématique des fonctions génératrices des fonctions d’ensembles permet d’avoir des démonstrations très courtes et explicatives. Elles se veulent une réponse à la suggestion faite par Gebhard et Sagan, qui ont déjà trouvé des démonstrations combinatoires de deux résultats de Greene et Zaslavsky. Les fonctions d’ensembles permettent aussi d’établir une série d’interprétations nouvelles de l’invariant β_{G} de Crapo. Cet article donne également un nouvel éclat aux résultats classiques de Cartier, Foata, Viennot, Brenti, Gessel et Stanley.

The chromatic polynomial χ_{G}(λ), which is associated with each graph G, enumerates its regular colorations with λ colors. Stanley showed that |χ_{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 χ_{G}(λ), when the polynomial is developed with respect to powers of λ and (λ−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 β_{G} invariant. This paper also brings a new light to the classical results due to Cartier, Foata, Viennot, Brenti, Gessel and Stanley.

1. Introduction

Soit G = (V, E) un graphe fini non-orienté. Une orientation de G est un graphe orienté obtenu à partir de G en remplaçant chaque arête e ∈ E par un des deux arcs (i. e. arêtes orientées) possibles. L’orientation est acyclique si elle ne contient pas de cycles orientés. Évidemment, le nombre d’orientations acycliques est égal à zéro si G contient une boucle (et égal à 1 si G ne contient aucune arête). De plus, des arêtes multiples de G doivent toutes être orientées de la même façon pour que l’orientation devienne acyclique. Voilà pourquoi on peut supposer, sans restreindre la généralité, que G est simple, c’est-à-dire qu’il ne contient ni boucles ni arêtes multiples, lorsqu’on s’intéresse aux orientations acycliques.

On appelle puits (resp. source) d’une orientation de G un sommet qui n’est l’extrémité initiale (resp. terminale) d’aucun arc. Apparemment, de quelque façon que l’on choisisse une orientation de G, chaque sommet isolé de G est toujours à la fois un puits et une source, un fait qui nécessite une prise en charge particulière des sommets isolés lorsqu’il faut regarder des puits et des sources en même temps.

Une coloration c : V → {1, 2, …, λ} de G avec λ couleurs est dite régulière si les deux extrémités de chaque arête ont des couleurs différentes, c’est-à-dire {u, v} ∈ E ⇒ c(u) ≠ c(v). Soit χ_{G}(λ) le nombre de ces colorations. C’est un des faits les plus classiques de la théorie des graphes (découlant à plusieurs reprises de cet article) que χ_{G}(λ) est un polynôme en λ de degré n := |V|, appelé polynôme chromatique. Évidemment, χ_{G}(λ) = 0 si G contient

Bodo Lass

Mots clés: graphe, polynôme chromatique, orientation acyclique, source, puits, invariant de Crapo une boucle, et de nouveau on peut se cantonner aux graphes simples pour étudier le polynôme chromatique.

Les similarités constatées entre les orientations acycliques et le polynôme chromatique ne sont pas une coïncidence. En fait, si

χ_{G}(λ) = λ^{n} − c_{n−1} · λ^{n−1} + c_{n−2} · λ^{n−2} − … + (−1)^{n−1}c_{1} · λ,

alors il est classique que c_{1}, c_{2}, …, c_{n−1} sont des entiers positifs; et grâce à Stanley [21], on sait que c_{1} + c_{2} + … + c_{n−1} + 1 dénombre effectivement les orientations acycliques de G.

Ceci soulève immédiatement la question de savoir s’il est possible de partitionner, de façon canonique, l’ensemble des orientations acycliques en blocs de cardinalités c_{1}, c_{2}, …, c_{n−1},

1. En effet, si les sommets de G sont numérotés, c’est-à-dire V = {1, 2, …, n}, alors une telle partition est possible en attachant, à chaque orientation acyclique, une partition de V constituée par k blocs, appelés composantes de l’orientation acyclique. La même construction de ces composantes fut imaginée par Greene et Zaslavsky [12] (dans un contexte géométrique) et par Viennot [27] (dans le cadre des empilements de pièces). Un des buts de cet article est de populariser leur résultat, qui est resté plutôt inconnu sauf pour le cas d’une seule composante : le fait que c_{1} dénombre les orientations acycliques d’une seule composante (ce sont par définition les orientations acycliques dont le sommet 1 est la seule source) se trouve dans [4] et dans le livre récent de Bollobás [1] (chapitre X, théorème 8), par exemple.

Suivons Sachs ([20], chapitre V.9.2) et appelons α_{G} := c_{1} discriminant chromatique du graphe G. Les nombres c_{1}, c_{2}, …, c_{n−1} sont définis indépendamment de la numérotation choisie et du fait que l’on s’intéresse aux sources ou plutôt aux puits des orientations acycliques. Voilà pourquoi α_{G} compte les orientations acycliques de G dont un sommet fixé est la seule source (ou bien le seul puits). C’était le leitmotif de l’article [9] de Gebhard et Sagan de donner trois preuves nouvelles de ce théorème de Greene et Zaslavsky [12], que ces derniers avaient démontré en s’appuyant sur les arrangements d’hyperplans.

Supposons maintenant que G est connexe de sorte que α_{G} est strictement positif. Il est classique (voir [26], chapitre IX.2) que le polynôme chromatique admet alors le développement

χ_{G}(λ) = λ · [(λ − 1)^{n−1} − b_{n−2} · (λ − 1)^{n−2} + … + (−1)^{n}b_{1} · (λ − 1)],

où b_{1}, b_{2}, …, b_{n−2} sont des entiers positifs correspondant à certains coefficients du polynôme de Tutte. Les nombres b_{1}, b_{2}, …, b_{n−2} sont probablement les invariants les plus petits (i. e. les plus puissants) que l’on peut associer à tout graphe (connexe) à partir de son polynôme chromatique. Leur positivité implique en particulier une unimodalité partielle des coefficients ^{⟨⟨} ordinaires^{⟩⟩} de χ_{G}(λ), à savoir 1 ≤ c_{n−1} ≤ c_{n−2} ≤ … ≤ c_{⌈n/2⌉} (voir [1], chapitre X, théorème 13). Numérotons les sommets du graphe G. Il est évident que

b_{1} + b_{2} + … + b_{n−2} + 1 = α_{G}

dénombre 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és b_{1}, b_{2}, …, b_{n−2}, 1. Une telle partition existe effectivement, et de surcroît, c’est la même que nous connaissons déjà : b_{k} compte le nombre d’orientations acycliques de G de k + 1 composantes, dont le puits unique est égal à 1, si (et seulement si) la numérotation des sommets reflète bien la connexité du graphe. Ce résultat risque d’être absolument inconnu, puisque la positivité des nombres b_{1}, b_{2}, …, b_{n−2} constitue la première moitié du théorème principal de l’article tout récent [10] de Gessel, mais pour la démonstration, le lecteur est renvoyé à la littérature (i. e. au polynôme de Tutte), bien que le sujet dudit article soient des relations entre colorations et orientations acycliques !

Orientations acycliques

Dans le cas particulier de l’invariant β_{G} := b_{1} de Crapo [6] cependant, on retrouve le théorème classique de Greene et Zaslavsky [12] qui, grâce aux arrangements d’hyperplans, ont indentifié β_{G} comme nombre d’orientations acycliques de G n’ayant qu’une seule source et un seul puits, à savoir les deux sommets adjacents 2 et 1, respectivement. Gebhard et Sagan ont trouvé une preuve par induction de ce fait et ont pensé que le résultat mériterait d’autres démonstrations (voir [9]). Cet article se veut, entre autres, une réponse à leur suggestion. Nous donnons, en effet, une série d’interprétations apparemment nouvelles (incluant celle de Greene et Zaslavsky) de β_{G}, et nous les démontrons avec l’aide de l’algèbre des fonctions d’ensembles.

En fait, de notre point de vue, l’intérêt principal de cet article consiste en l’exploration de la méthode des fonctions génératrices dans le présent contexte, méthode qui a déjà fait ses preuves dans beaucoup de situations différentes (voir [14]). Chacun de nos théorèmes s’obtient effectivement comme spécialisation d’une identité dans l’algèbre des fonctions d’ensembles et le passage entre ces différentes identités se fait toujours en quelques lignes. Ceci permet notamment de trouver des nouvelles démonstrations, très courtes et explicatives, des deux théorèmes de Greene et Zaslavsky mentionnés ci-dessus ainsi que de celui de Stanley sur |χ_{G}(−1)|.

Il nous semble particulièrement surprenant que chacune de nos identités admettant une généralisation non-commutative apparaît déjà 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é (sur toute une page à l’époque) comment on peut déduire le résultat de Stanley du théorème de Cartier et Foata (voir [5]) sur l’inversion (de Möbius) dans le monoïde de commutation. En fait, de notre point de vue, ce théorème de Cartier et Foata devient une généralisation noncommutative directe du théorème de Stanley [21] sans aucune démonstration supplémentaire. Ceci montre à quel point le livre de Cartier et Foata était visionnaire !

Cependant, pour aller plus loin dans le sens des théorèmes de Greene et Zaslavsky qui font intervenir des interprétations combinatoires du logarithme, il semble falloir se cantonner au cas commutatif. Cette nécessité fut d’abord révélée par Viennot (voir [27], proposition 5.10), qui a, de plus, établi l’équivalence du modèle de Cartier et Foata avec son modèle des empilements de pièces ainsi que, notamment, avec notre modèle préféré, à savoir les orientations acycliques d’un graphe (voir [27], page 325, c)). Grâce à cette équivalence, les théorèmes 3.2 et 5.1 de cet article deviennent effectivement des généralisations ou plutôt des raffinements de la proposition 5.10 de [27].

Après avoir expliqué notre méthode algébrique dans le paragraphe 2, nous l’appliquons pour le traitement du polynôme chromatique et des orientations acycliques dans les paragraphes 3, 4, 5 et 6. Trois appendices sont consacrés à la discussion, dans notre optique, des travaux de Cartier, Foata, Gessel, Viennot et Stanley mentionnés ci-dessus. En outre, nous considérons brièvement les développements du polynôme chromatique obtenus par Brenti, les graphes aléatoires étudiés par Welsh [28] et la fonction (symétrique) chromatique de Stanley (voir [22]).

2. Outils algébriques

Soit V un ensemble fini et

\begin{matrix}f : 2^{V} & → A \\ V′ ⊆ V & ↦ f(V′) ∈ A \end{matrix}

une fonction d’ensembles, où A est un anneau commutatif (avec 1). Considérons la fonction génératrice

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

à joindre aux règles de calcul suivantes (V′, V′′ ⊆ V) :

ν^{V′} · ν^{V′′} := ν^{V′+V′′}, où

V′ + V′′ := \{ \begin{matrix}V′ ∪ V′′, & si V′ ∩ V′′ = ∅, \\ †, & si V′ ∩ V′′ ≠ ∅, où \end{matrix}

† + V′ := †, † + † := †,  et  ν† := 0.

L’algèbre A[V] de ces fonctions génératrices n’est pas une inconnue. En effet, on a l’isomorphisme

A[V] ≃ A[v_{1}, …, v_{n}]/⟨v_{1}^{2}, …, v_{n}^{2}⟩,

si V contient n éléments.

Exemple 2.1. Le produit fg de deux fonctions d’ensembles f, g est défini, pour tout V′ ⊆ V, par

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

Il en résulte

F_{fg}(ν) = F_{f}(ν) · F_{g}(ν).

Pour |V | = ∞, soit F (V) l’ensemble partiellement ordonné des sous-ensembles finis de V. On a des projections canoniques p_{V′,V′′} : A[V′] → A[V′′] (V′, V′′ ∈ F (V), V′ ⊇ V′′) et l’on pose

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

pour travailler avec des fonctions génératrices de la forme

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

Remarque 2.1. Dans [14], les projections canoniques furent utilisées pour démontrer des propositions par analogie avec les propositions 3.2 et 4.1 de cet article. Deux de ces résultats sont directement équivalents à la proposition 5.3 de [27] et au lemme 1.2 de [2]. Cependant, l’interaction des projections avec l’analyse est moins intéressante. C’est pourquoi elles ne sont plus employées ici.

Soit

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

la fonction indicatrice des sous-ensembles de V de cardinalité 1 (l’usage double de V pour l’ensemble et pour un élément de A[V] ne pourra pas être à l’origine de confusions). En multipliant la fonction génératrice V plusieurs fois par elle-même, on voit que V^{n}/n! représente la fonction indicatrice des sous-ensembles de l’ensemble V de cardinalité n. L’identité

∑_{n=0}^{∞} f(n) · V^{n}/n! = ∑_{V′∈F (V)} f(|V′|) · ν^{V′}, f : ℕ → A,

fournit un plongement de l’anneau A![[V]] des fonctions génératrices de type exponentiel dans l’anneau A[V]. Ce plongement est à l’origine de (presque?) toutes les applications de A![[V]] en combinatoire, mais il nécessite l’existence d’un modèle combinatoire infini (qui ne fait intervenir que les cardinalités). Par conséquent, A[V] donne plus de flexibilité et permet un traitement algébrique, qui reflète parfaitement les opérations classiques de la combinatoire. Outre cela, A[V] est approprié, par excellence, aux calculs par ordinateur.

Remarque 2.2. L’anneau ℤ![[V]] n’est pas noethérien, mais il contient des fonctions importantes comme exp(V) et log(1 + V).

Exemple 2.2. Si char A = 2, on a

(1 + V)^{−1} = ∑_{n=0}^{∞}(−1)^{n}n! · V^{n}/n!
≡ 1 + V et
log(1 + V) = ∑_{n=1}^{∞}(−1)^{n−1}(n − 1)! · V^{n}/n!
≡ V + V^{2}/2

dans l’anneau A![[V]]. Ces identités sont à l’origine de maints résultats de parité en combinatoire.

Pour tout t ∈ A posons (t · ν)^{V′} := t^{|V′|} · ν^{V′}, V′ ⊆ V, et, par conséquent,

F_{f}(tν) = ∑_{∅⊆V′⊆V} f(V′) t^{|V′|} ν^{V′}.

Il est évident que cette définition 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 · ν) = f(∅).

Si F_{f}(0) = 0, alors F_{f}(ν)^{n}/n! est défini pour n’importe quel anneau A, parce qu’une partition en n sous-ensembles non-vides peut être ordonnée de n! manières différentes. Voilà pourquoi A![[V]] opère sur A[V] par la substitution G(F_{f}(ν)) définie pour tout G ∈ A![[V]].

Finalement, on utilise les dérivées ∂^{v} pour tout v ∈ V définies par

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

La formule de dérivation d’un produit

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

est l’analogue algébrique du fait ensembliste le plus fondamental :

v ∈ V′ ⊎ V′′  ⇔  v ∈ V′ ou v ∈ V′′.

La formule

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

en découle immédiatement.

Remarque 2.3. L’isomorphisme A[V] ≃ A[v_{1}, …, v_{n}]/⟨v_{1}^{2}, …, v_{n}^{2}⟩ ne fait pas correspondre ∂^{v} à ∂/∂v_{i}, mais à v_{i}∂/∂v_{i}. La dérivée partielle ∂/∂v_{i} n’a point d’analogue dans A[V].

Pour ∅ ⊆ V′ ⊆ V, posons

∂^{V′} := ∏_{v∈V′} ∂^{v}, i. e. ∂^{V′}ν^{V′′} = \{ \begin{matrix}ν^{V′′}, & si V′ ⊆ V′′, \\ 0, & sinon; \end{matrix}

en particulier, ∂^{∅} est l’identité. Comme (∂^{v})^{2} = ∂^{v} pour tout v ∈ V, on a

∂^{V′}∂^{V′′} = ∂^{V′∪V′′}, V′, V′′ ⊆ V.

Les opérateurs différentiels n’étant pas des combinaisons linéaires des dérivations d’éléments ∂^{v}, v ∈ V, ne satisfont pas aux formules de dérivation ordinaires. En s’appuyant sur la définition ∂^{V′} := ∏_{v∈V′} ∂^{v}, cependant, on peut calculer des règles spécifiques pour eux :

Proposition 2.1.

a) Soient f, g : 2^{V} → A des fonction d’ensembles, et soit V′ ⊆ V fixé. Alors

∂^{V′}[F_{f}(ν) · F_{g}(ν)] = ∑_{∅⊆V′′⊆V′} ∂^{V′′}F_{f}(ν) · ∂^{V′\V′′}F_{g}(ν).

b) Soient s, p ∈ V, et soit G ∈ A![[V]]. Alors

∂^{{s,p}}[G(F_{f}(ν))] = G′′(F_{f}(ν)) · ∂^{s}F_{f}(ν) · ∂^{p}F_{f}(ν) + G′(F_{f}(ν)) · ∂^{{s,p}}F_{f}(ν).

c) Soit t une variable (ou t ∈ A) et posons D(t) := ∑_{∅⊆V′⊆V} t^{|V′|}∂^{V′}. Alors

\begin{aligned}D(t)[F_{f}(ν) · F_{g}(ν)] & = D(t)F_{f}(ν) · D(t)F_{g}(ν); puisque \\ D(t)F_{f}(ν) & = F_{f}((t + 1)ν). \end{aligned}

3. Orientations acycliques et ensembles indépendants : sources ou puits

Pour tout ∅ ⊂ V′ ⊆ V, soit G[V′] le sous-graphe de G = (V, E) engendré par V′ : c’est le graphe dont les sommets sont les points de V′, et dont les arêtes sont les arêtes de G ayant leurs deux extrémités dans V′. Un sous-ensemble I de sommets est dit indépendant, si le sous-graphe engendré par I ne contient aucune arête.

Une coloration c : V → {1, 2, …, λ} de G avec λ couleurs est régulière (voir l’introduction) si et seulement si, pour tout i ∈ {1, 2, …, λ}, le sous-ensemble c^{−1}(i) est un ensemble de sommets indépendant (ou vide). Voilà pourquoi une coloration régulière avec λ couleurs n’est rien d’autre qu’une partition de V en λ ensembles indépendants, dont chacun peut être vide.

Soit I_{G}(ν), I_{G}(0) = 0, la fonction indicatrice des sous-ensembles indépendants de G (la valeur de cette fonction indicatrice sur V′, ∅ ⊂ V′ ⊆ V, est égal à 1, si G[V′] ne contient aucune arête, et égal à 0 sinon) :

I_{G}(ν) := ∑_{∅⊂I⊆V, I indépendant} ν^{I};

et posons

χ_{G,λ}(ν) := ∑_{∅⊂V′⊆V} χ_{G[V′]}(λ) · ν^{V′},

où χ_{G[V′]}(λ) désigne le polynôme chromatique (c’est-à-dire le nombre de colorations régulières avec λ couleurs) de G[V′].

Rappelons que le coefficient linéaire de χ_{G}(λ) multiplié par (−1)^{n−1}, i. e. (−1)^{n−1}χ′_{G}(0), est appelé discriminant chromatique et noté α_{G}; et généralisons la définition de l’invariant de Crapo donnée dans l’introduction en posant β_{G} := (−1)^{n+i}χ′_{G}(1), où i désigne le nombre de sommets isolés de G. Le lecteur familier avec β_{G} verra facilement que cette définition est équivalente à la sienne, si G contient au moins une arête. Si G ne contient aucune arête, on obtient β_{G} = n, une définition artificielle qui sera modifiée ci-dessous.

Évidemment, nous utilisons les mêmes définitions pour tous les sous-graphes engendrés, notant en particulier i(G[V′]) le nombre de sommets isolés de G[V′].

Puisqu’une multiplication dans l’algèbre A[V] avec λ facteurs compte des partitions en λ ensembles, on a l’identité 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.

Proposition 3.1. On a

\begin{aligned}1 + χ_{G,λ}(ν) & = [1 + I_{G}(ν)]^{λ}, \\ \frac{d}{dλ}[1 + χ_{G,λ}(ν)] & = [1 + I_{G}(ν)]^{λ} · log[1 + I_{G}(ν)]; \end{aligned}

et, en particulier, pour le discriminant chromatique α_{G} et l’invariant de Crapo β_{G}, on a :

\begin{aligned}− log[1 + I_{G}(−ν)] & = ∑_{∅⊂V′⊆V} α_{G[V′]} · ν^{V′}, \\ [1 + I_{G}(−ν)] · log[1 + I_{G}(−ν)] & = ∑_{∅⊂V′⊆V} (−1)^{i(G[V′])}β_{G[V′]} · ν^{V′}. \end{aligned}

Exemple 3.1. Selon l’exemple 2.2, I_{G}(ν)+I_{G}(ν)^{2}/2 compte les discriminants chromatiques modulo 2. Par conséquent, α_{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 être partitionné en deux classes indépendantes.)

Pour tout ∅ ⊂ V′ ⊆ 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 égal à S, ∅ ⊆ S ⊆ V. Évidemment, a_{S}(G[V′]) = 0, si S n’est pas un sous-ensemble de V′. De plus, si S = ∅, 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}(ν) := ∑_{∅⊂V′⊆V} a(G[V′]) · ν^{V′}, A_{G,S}(ν) := ∑_{∅⊂V′⊆V} a_{S}(G[V′]) · ν^{V′}.

Le rapport fondamental entre les orientations acycliques et les sous-ensembles indépendants de G repose uniquement sur le fait que l’ensemble des sources d’une orientation acyclique est toujours indépendant.

Or, si S′, ∅ ⊆ S′ ⊆ V, n’est pas indépendant (l’ensemble vide est indépendant), S′ ne peut pas être un sous-ensemble de l’ensemble des sources. Si S′ est indépendant, cependant, alors [1 + A_{G}(ν)] · ν^{S′} compte le nombre d’orientations acycliques telles que S′ est un sousensemble de l’ensemble des sources; car ces orientations de G[V′], S′ ⊆ V′ ⊆ V, s’obtiennent en choisissant une orientation acyclique quelconque du graphe G[V′\S′] et en orientant toutes les autres arêtes de S′ à V′\S′. Par conséquent, le principe d’inclusion-exclusion fournit le résultat suivant (voir [7], théorème 3.1, pour une généralisation non-commutative ayant la même démonstration) :

Proposition 3.2. (Foata) Pour tout ∅ ⊆ S ⊆ V on a

[1 + A_{G}(ν)] · (−1)^{|S|}∂^{S}[1 + I_{G}(−ν)] = ∂^{S}[1 + A_{G,S}(ν)],

les cas particuliers les plus intéressants étant S = ∅ et S = {s} (s ∈ V) :

[1 + A_{G}(ν)] · [1 + I_{G}(−ν)] = 1, −[1 + A_{G}(ν)] · ∂^{s}I_{G}(−ν) = A_{G,s}(ν).

Alors il découle des deux propositions précédentes (voir [21] ou [17], 9.46, ainsi que [5], théorème 2.4, et [27], proposition 5.1) :

Théorème 3.1. (Stanley, Cartier-Foata, Gessel-Viennot) Pour tout ∅ ⊂ V′ ⊆ V,

[1 + I_{G}(−ν)]^{−1} = 1 + A_{G}(ν) = 1 + χ_{G,−1}(−ν)

dénombre les orientations acycliques de G[V′]. En particulier, on a a(G) = (−1)^{n}χ_{G}(−1), et ce nombre est toujours strictement positif.

Soit s ∈ V fixé. Alors le théorème 3.1 et la proposition 3.2 impliquent

∂^{s} − log[1 + I_{G}(−ν)] = −[1 + I_{G}(−ν)]^{−1} · ∂^{s}I_{G}(−ν) = A_{G,s}(ν).

Posons A_{G}^{∗}(ν) := − log[1 + I_{G}(−ν)]. Il s’ensuit (voir [12] ou [9] ainsi que [27], proposition 5.10) :

Théorème 3.2. (Greene-Zaslavsky, Viennot) Pour tout ∅ ⊂ V′ ⊆ V,

− log[1 + I_{G}(−ν)] = A_{G}^{∗}(ν) = −\frac{d}{dλ}χ_{G,0}(−ν)

dénombre les orientations acycliques de G[V′] n’ayant qu’une seule source fixée s ∈ V′. En particulier, on a a_{s}(G) = (−1)^{n−1}χ′_{G}(0) = α_{G} pour tout s ∈ V, et ce nombre n’est jamais négatif. Plus précisément, il est égal à 0 si G n’est pas connexe, il est égal à 1 si G est un arbre, et il est plus grand que 1 dans tous les autres cas.

Démonstration. Seulement la toute dernière affirmation n’est pas encore évidente. Elle se démontre comme suit. Les plus courts chemins de s ∈ V à n’importe quel autre sommet forment une arborescence avec s comme source unique. Une arête supplémentaire de G doit ⟨⟨ passer de travers^{⟩⟩} par rapport à cette arborescence et peut être orientée de deux manières différentes sans qu’il y ait un cycle orienté. Enfin, chacune de ces deux orientations acycliques peut être prolongée à tout G.

Finalement, soit a_{k}(G) le nombre d’orientations acycliques de G = (V, E) avec (précisément) k sources et posons

a_{G}(t) := ∑_{k=1}^{n} a_{k}(G)t^{k}, A_{G,t}(ν) := ∑_{∅⊂V′⊆V} a_{G[V′]}(t) · ν^{V′},

(A_{G,1}(ν) = A_{G}(ν)). Avec l’aide de la proposition 3.2 ainsi que de l’opérateur différentiel D(t) de la proposition 2.1, c), on obtient :

Théorème 3.3. On a

\begin{aligned}1 + A_{G,t}(ν) & = [1 + A_{G}(ν)] · D(−t)[1 + I_{G}(−ν)] \\ & = \frac{1 + I_{G}((t − 1)ν)}{1 + I_{G}(−ν)}. \end{aligned}

Évidemment, tout ce qui fut énoncé pour les sources vaut également pour les puits. En particulier, a_{S}(G[V′]) (pour les sources) ou encore a_{P} (G[V′]) (pour les puits), ∅ ⊂ V′ ⊆ V, est égal à zéro, si V′\S (ou bien V′\P) contient un sommet isolé dans le graphe G[V′].

4. Orientations acycliques et ensembles indépendants : sources et puits

Les sommets isolés posent des problèmes lorsqu’on veut regarder les sources et les puits en même temps; car ces sommets sont toujours les deux à la fois. Dans cette optique, la définition suivante se révèle raisonnable.

Définition 4.1. Pour tout ∅ ⊂ V′ ⊆ V, soit I(G[V′]) l’ensemble des sommets isolés de G[V′] (|I(G[V′])| = i(G[V′])). Si ∅ ⊂ S, P ⊆ V et S ∩ P = ∅, notons |a_{S,P} (G[V′])| le nombre d’orientations acycliques du graphe G[V′] telles que l’ensemble des sources est égal à S ∪ I(G[V′]) et l’ensemble des puits est égal à P ∪ I(G[V′]); et posons a_{S,P} (G[V′]) := (−1)^{I(G[V′])\(S∪P)}|a_{S,P} (G[V′])|. Par définition, a_{S,P} (G[V′]) := 0, si S ∩ P ≠ ∅.

Posons

A_{G,S,P} (ν) := ∑_{∅⊂V′⊆V} a_{S,P} (G[V′]) · ν^{V′}.

Alors la proposition 3.2, ainsi que le principe d’inclusion-exclusion, impliquent (voir Gessel [10] pour une généralisation non-commutative et pondérée) :

Proposition 4.1. (Gessel) Pour ∅ ⊂ S, P ⊆ V on a :

[1 + A_{G}(ν)] · [(−1)^{|S|}∂^{S}I_{G}(−ν)] · [(−1)^{|P |}∂^{P} I_{G}(−ν)]
= A_{G,S}(ν) · [(−1)^{|P |}∂^{P} I_{G}(−ν)] = A_{G,P} (ν) · [(−1)^{|S|}∂^{S}I_{G}(−ν)]
= A_{G,S,P} (ν).

Démonstration. Il ne s’agit que d’expliquer l’entrée des nombres négatifs due aux sommets isolés. Soit i un sommet isolé de G (pour les sous-graphes engendrés G[V′], ∅ ⊂ V′ ⊆ V, on a le même argument), alors i ∉ S implique

∂^{i}A_{G,S}(ν) = 0  et  ∂^{i}(−1)^{|S|}∂^{S}I_{G}(−ν) = −ν^{i} · (−1)^{|S|}∂^{S}I_{G}(−ν),

où S peut être remplacé par P. Par conséquent, i ∉ (S ∪ P) implique

∂^{i}A_{G,S,P} (ν) = −ν^{i} · A_{G,S,P} (ν).

Maintenant, pour s, p ∈ V fixés, il découle de la proposition précédente ainsi que du théorème 3.1 (voir aussi la proposition 2.1) que :

∂^{{s,p}}([1 + I_{G}(−ν)] · log[1 + I_{G}(−ν)])
= [1 + I_{G}(−ν)]^{−1} · ∂^{s}I_{G}(−ν) · ∂^{p}I_{G}(−ν) + (1 + log[1 + I_{G}(−ν)]) · ∂^{{s,p}}I_{G}(−ν)
= A_{G,s,p}(ν) + (1 + log[1 + I_{G}(−ν)]) · ∂^{{s,p}}I_{G}(−ν).

Si s et p sont adjacents, alors ∂^{{s,p}}I_{G}(−ν) = 0, et il s’ensuit

∂^{{s,p}}([1 + I_{G}(−ν)] · log[1 + I_{G}(−ν)]) = A_{G,s,p}(ν).

Cela implique le théorème suivant (voir [12] ou [9]), que nous représentons dans A[V] :

Théorème 4.1. (Greene-Zaslavsky) La fonction d’ensembles

[1 + I_{G}(−ν)] · log[1 + I_{G}(−ν)] = \frac{d}{dλ}χ_{G,1}(−ν)

prend la valeur (−1)^{|V′|}|V′| pour tout ∅ ⊂ V′ ⊆ V, lorsque V′ est indépendant (car exp(−V′)· log[exp(−V′)] = −V′ · exp(−V′)), et la valeur

a_{s,p}(G[V′]) = (−1)^{|V′|}χ′_{G[V′]}(1) = (−1)^{|I|}β(G[V′]) =

(−1)^{|I|}a_{s,p}(G[V′\I]) = (−1)^{|V′|}χ′_{G[V′\I]}(1) = (−1)^{|I|}β(G[V′\I]),

lorsque G[V′] contient une arête {s, p} et I est l’ensemble des sommets isolés de G[V′]. En particulier, si G ne contient aucun sommet isolé et {s, p} est une arête de G, alors a_{s,p}(G) = (−1)^{n}χ′_{G}(1) = β(G) dénombre les orientations acycliques de G n’ayant qu’une seule source à s et qu’un seul puits à p. Ce nombre n’est jamais négatif et strictement positif si G est un bloc, c’est-à-dire si G est 2-connexe ou la seule arête {s, p}.

Démonstration. Seulement la toute dernière affirmation n’est pas encore évidente. Elle se démontre comme suit. Selon [13], chapitre 3.2, tout graphe 2-connexe admet une ^{⟨⟨} décomposition en oreilles^{⟩⟩} donnée par des chemins C_{1}, …, C_{k} tels que C_{1} = {s, p}, |V (C_{i})∩[V (C_{1})∪ … ∪ V (C_{i−1})]| = 2 pour tout 2 ≤ i ≤ k et V = V (C_{1}) ∪ … ∪ V (C_{k}). Cette décomposition permet de munir G d’une fonction injective i : V → [0, 1], i(s) = 0, i(p) = 1, qui augmente (ou diminue) le long de tous les chemins C_{1}, …, C_{k} de façon strictement monotone. Alors il ne s’agit que d’orienter chaque arête de son extrémité la plus petite (selon i) à son extrémité la plus grande.

Nous avons déjà interprété [1 + I_{G}(−ν)]^{−1} (théorème 3.1), − log[1 + I_{G}(−ν)] en dérivant par rapport à un élément (théorème 3.2) et [1 + I_{G}(−ν)] · log[1 + I_{G}(−ν)] en dérivant deux fois (théorème 4.1). En effet, − log[1 − V] est l’intégrale de [1 − V]^{−1}. Cependant, l’intégrale de − log[1 − V] n’est pas [1 − V] · log[1 − V], mais [1 − V] · log[1 − V] − [−V]. Voilà pourquoi le théorème principal de ce paragraphe est consacré à l’interprétation de [1 + I_{G}(−ν)] · log[1 + I_{G}(−ν)] − I_{G}(−ν). Si l’on ajoute le terme −I_{G}(−ν) au membre de gauche de la dernière identité de la proposition 3.1, la valeur de β_{G[V′]} ne change que si V′ est indépendant : dans ce cas β_{G[V′]} n’est plus égal à |V′| mais à |V′| − 1 (toutes les deux définitions étant artificielles). On utilisera donc l’identité

∑_{∅⊂V′⊆V} (−1)^{i(G[V′])}β_{G[V′]} · ν^{V′} := [1 + I_{G}(−ν)] · log[1 + I_{G}(−ν)] − I_{G}(−ν).

Avec cette modification (et la définition 4.1) on a alors :

Théorème 4.2. Soit V = {1, …, n} et soit i le nombre de sommets isolés de G. Alors le coefficient de ν^{V} dans [1 + I_{G}(−ν)] · log[1 + I_{G}(−ν)] − I_{G}(−ν), c’est-à-dire (−1)^{i}β_{G}, est égal à

a_{{1},{2}}(G) − a_{{1,2},{3}}(G) + a_{{1,2,3},{4}}(G) − … + (−1)^{n}a_{{1,2,...,n−1},{n}}(G),

où la somme précédente s’arrête dès que l’ensemble des sources {1, 2, …, k} n’est plus indépendant.

Démonstration. Dérivons successivement par rapport à tous les éléments :

∂^{{1}}([1 + I_{G}(−ν)] · log[1 + I_{G}(−ν)] − I_{G}(−ν))
= log[1 + I_{G}(−ν)] · ∂^{{1}}I_{G}(−ν),
∂^{{1,2}}([1 + I_{G}(−ν)] · log[1 + I_{G}(−ν)] − I_{G}(−ν))
= A_{G,{1},{2}}(ν) + log[1 + I_{G}(−ν)] · ∂^{{1,2}}I_{G}(−ν),
∂^{{1,2,3}}([1 + I_{G}(−ν)] · log[1 + I_{G}(−ν)] − I_{G}(−ν))
= ∂^{{3}}A_{G,{1},{2}}(ν) − A_{G,{1,2},{3}}(ν) + log[1 + I_{G}(−ν)] · ∂^{{1,2,3}}I_{G}(−ν),
⋯
∂^{{1,2,...,k}}([1 + I_{G}(−ν)] · log[1 + I_{G}(−ν)] − I_{G}(−ν))
= ∂^{{3,...,k}}A_{G,{1},{2}}(ν) − ∂^{{4,...,k}}A_{G,{1,2},{3}}(ν) + ∂^{{5,...,k}}A_{G,{1,2,3},{4}}(ν)
− … + (−1)^{k}A_{G,{1,2,...,k−1},{k}}(ν) + log[1 + I_{G}(−ν)] · ∂^{{1,2,...,k}}I_{G}(−ν),
⋯
∂^{V} ([1 + I_{G}(−ν)] · log[1 + I_{G}(−ν)] − I_{G}(−ν))
= ∂^{V} A_{G,{1},{2}}(ν) − ∂^{V} A_{G,{1,2},{3}}(ν) + ∂^{V} A_{G,{1,2,3},{4}}(ν)
− … + (−1)^{n}∂^{V} A_{G,{1,2,...,n−1},{n}}(ν).

5. Le polynôme chromatique : bases canoniques

Tout d’abord, il découle de la proposition 3.1 et du théorème 3.1 que

Proposition 5.1. (Stanley [21], Gessel [10])

1 + χ_{G,λ}(ν) = [1 + I_{G}(ν)]^{λ}, 1 + χ_{G,−λ}(−ν) = [1 + A_{G}(ν)]^{λ}.

Soit V = {1, 2, …, n}, et regardons une orientation acyclique des arêtes de G = (V, E). Notons V_{1} l’ensemble des sommets accessibles (par des chemins orientés) à partir de v_{1} := 1. Soit v_{2} le plus petit sommet de V \V_{1}, et soit V_{2} l’ensemble des sommets de V \V_{1} accessibles de v_{2} … Finalement, soit v_{k} le plus petit sommet de V \(V_{1}∪…∪V_{k−1}), et soit V_{k} l’ensemble des sommets de V \(V_{1} ∪ … ∪ V_{k−1}) accessibles de v_{k}, V = V_{1} ⊎ V_{2} ⊎ … ⊎ V_{k}. On appelle k le nombre de composantes de l’orientation acyclique. Ainsi une orientation acyclique de k composantes est constituée par une partition V = V_{1}⊎…⊎V_{k} en orientations acycliques avec des sources fixées v_{1}, …, v_{k} (le plus petit sommet v_{i} de chaque composante V_{i} est la source unique, et les arêtes entre deux composantes V_{i} et V_{j} avec v_{i} < v_{j} sont toutes orientées de V_{j} à V_{i}). Or, puisque A_{G}^{∗}(ν) compte des orientations acycliques avec une source unique fixée (ou bien des orientations acycliques d’une seule composante), A_{G}^{∗}(0) = 0, il s’ensuit que A_{G}^{∗}(ν)^{k}/k! compte des orientations acycliques de k composantes. En particulier, on a

exp[A_{G}^{∗}(ν)] = 1 + A_{G}(ν),

ce qui est la démonstration de Viennot (voir [27], proposition 5.10) du théorème 3.2, à savoir de l’identité

A_{G}^{∗}(ν) = − log[1 + I_{G}(−ν)],

avec l’aide du théorème 3.1, i. e. de l’identité 1 + A_{G}(ν) = [1 + I_{G}(−ν)]^{−1}.

Notons c(G) le nombre de composantes connexes de G, de sorte que chaque orientation acyclique de G a au moins c(G) composantes, ce nombre minimal pouvant être atteint selon le théorème 3.2. On en déduit le résultat de Greene et Zaslavsky (voir [12] ou [26], chapitre IX.2), que nous reformulons dans l’algèbre des fonctions d’ensembles.

Théorème 5.1. (Greene-Zaslavsky, Viennot) On a

1 + χ_{G,λ}(−ν) = exp(λ · log[1 + I_{G}(−ν)]) = exp(−λ · A_{G}^{∗}(ν))

= ∑_{k=0}^{∞}([−A_{G}^{∗}(ν)]^{k}/k!) · λ^{k}.

En particulier,

χ_{G}(λ) = λ^{n} − c_{n−1} · λ^{n−1} + c_{n−2} · λ^{n−2} − … + (−1)^{n−1}c_{1} · λ,

où c_{k} désigne le nombre d’orientations acycliques de G de k composantes, c_{n−1} = |E|, c_{1} = α_{G} = a_{{1}}(G), 1 + c_{n−1} + c_{n−2} + … + c_{1} = a(G); c_{k} = 0, si k < c(G), et c_{k} > 0, si k ≥ c(G).

Remarque 5.1. Le théorème précédent montre que l’alternance des signes du polynôme chromatique est une conséquence directe de la positivité des discriminants chromatiques, c’est-à-dire de A_{G}^{∗}(ν).

Un résultat plus puissant que l’alternance des signes du polynôme chromatique développé par rapport à la base des puissances λ^{k} est celui de l’alternance des signes par rapport à la base des puissances (λ − 1)^{k}, ce qui correspond au polynôme de Tutte. Pour la démontrer avec l’aide des orientations acycliques, supposons que G est connexe et que ses sommets sont numérotés avec les nombres 1, …, n de telle façon que le plus petit voisin de chaque sommet (sauf 1) porte un nombre plus petit que celui du sommet même. (De cette manière, la numérotation reflète bien la connexité.)

Dans cette situation, les sommets v_{2}, …, v_{k} d’une orientation acyclique de k composantes V = V_{1} ⊎ … ⊎ V_{k} (de nouveau, pour chaque composante V_{i}, son plus petit sommet v_{i} est sa source unique) ne peuvent pas être des puits; car, pour chacun de ces sommets v_{i}, son plus petit voisin se trouve toujours dans une composante plus petite (la ^{⟨⟨} grandeur^{⟩⟩} d’une composante étant mésurée en fonction de son plus petit élément) de sorte que l’arête correspondante a v_{i} comme extrémité initiale et le plus petit voisin comme extrémité terminale.

Si v_{1} = 1 est un puits (i. e. v_{2} = 2), alors la suppression des puits réduit le nombre de composantes de 1 (à savoir de la composante V_{1} = {1}). D’autre part, en ajoutant les puits distincts de v_{1} = 1, on les affecte automatiquement à la composante la plus petite d’où ils sont accessibles (c’est la composante du plus petit voisin ou une composante encore plus petite).

Par conséquent, pour chaque ensemble de sommets indépendant I tel que 1 = v_{1} ∈ I, le coefficient de ν^{V} dans [A_{G}^{∗}(ν)^{k}/k!] · ν^{I} compte le nombre d’orientations acycliques de k + 1 composantes de G telles que I est un sous-ensemble des puits. Voilà pourquoi le principe d’inclusion-exclusion implique que le coefficient de ν^{V} dans [A_{G}^{∗}(ν)^{k}/k!] · [−∂^{{1}}I_{G}(−ν)] compte le nombre d’orientations acycliques de k + 1 composantes de G, dont le puits unique est égal à 1 (pour k = 1 il s’agit bien du nombre a_{{2},{1}}(G)).

Notons b(G) le nombre de blocs de G (voir le théorème 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écessaire et suffisant, que le plus petit sommet de tout bloc soit son puits unique. Selon le théorème 4.1 le nombre minimal de b(G) + 1 composantes peut être atteint. Nous avons démontré le théorème principal de ce paragraphe (voir [26], chapitre IX.2).

Théorème 5.2. On a

−∂^{{1}}χ_{G,λ}(−ν) = λ · [1 + I_{G}(−ν)]^{λ−1} · [−∂^{{1}}I_{G}(−ν)]

= λ · exp(−(λ − 1) · A_{G}^{∗}(ν)) · [−∂^{{1}}I_{G}(−ν)]

= λ · ∑_{k=0}^{∞}([−A_{G}^{∗}(ν)]^{k}/k!) · [−∂^{{1}}I_{G}(−ν)] · (λ − 1)^{k}.

En particulier,

χ_{G}(λ) = λ · [(λ − 1)^{n−1} − b_{n−2} · (λ − 1)^{n−2} + … + (−1)^{n}b_{1} · (λ − 1)],

où b_{k} désigne le nombre d’orientations acycliques de G de k + 1 composantes, dont le puits unique est égal à 1, b_{n−2} = |E| − (n − 1), b_{1} = β_{G} = a_{{2},{1}}(G), 1 + b_{n−2} + … + b_{1} = α_{G} = a_{{1}}(G); b_{k} = 0, si k < b(G), et b_{k} > 0, si k ≥ b(G).

Exemple 5.1. Le graphe donné 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à pourquoi son polynôme chromatique s’écrit : λ[(λ − 1)^{3} − 2(λ − 1)^{2} + (λ − 1)] = λ(λ − 1)(λ − 2)^{2}.

[figure: 1; 4; 2; 3; composantes :; {1},{2},{3},{4}; 1; 4; 2; 3; composantes :; {1},{2,3},{4}; 1; 4; 2; 3; composantes :; {1},{2},{3,4}; 1; 4; 2; 3; composantes :; {1},{2,3,4}]

6. Le polynôme chromatique : bases exotiques

Notons χ(G) le nombre chromatique de G, i. e. le plus petit nombre de couleurs nécessaire pour colorier les sommets de G de façon régulière.

Grâce à la proposition 5.1 et à la formule du binôme, on obtient le développement du polynôme chromatique du graphe G = (V, E) dans les deux bases

λ\underline{k} := k!\binom{λ}{k}, λ\overline{k} := k!(\binom{λ}{k}) = k!\binom{λ + k − 1}{k} = k!(−1)^{k}\binom{−λ}{k}.

Proposition 6.1. (Brenti [3])

\begin{aligned}1 + χ_{G,λ}(ν) & = ∑_{k=0}^{∞} I_{G}(ν)^{k}\binom{λ}{k}, 1 + χ_{G,−λ}(ν) = ∑_{k=0}^{∞}[−I_{G}(ν)]^{k}(\binom{λ}{k}), \\ 1 + χ_{G,−λ}(−ν) & = ∑_{k=0}^{∞} A_{G}(ν)^{k}\binom{λ}{k}, 1 + χ_{G,λ}(−ν) = ∑_{k=0}^{∞}[−A_{G}(ν)]^{k}(\binom{λ}{k}). \end{aligned}

Alors, avec |V | = n, on a

\begin{aligned}χ_{G}(λ) & = λ\underline{n} + i_{n−1} · λ\underline{n−1} + i_{n−2} · λ\underline{n−2} + … + i_{1} · λ \\ & = λ\overline{n} − a_{n−1} · λ\overline{n−1} + a_{n−2} · λ\overline{n−2} − … + (−1)^{n−1}a_{1} · λ, \end{aligned}

où les i_{k} sont des entiers positifs (dénombrant des partitions en ensembles indépendants non-vides) et les a_{k} sont des entiers strictement positifs (dénombrant des partitions en orientations acycliques), 1 ≤ k ≤ n − 1. En particulier, i_{n−1} = \binom{n}{2} − |E|, a_{n−1} = \binom{n}{2} + |E|, a_{1} = a(G) et i_{1} est égal à 1 si |E| = 0 et égal à 0 sinon. De plus, on a i_{k} = 0, si k < χ(G), et i_{k} > 0, si k ≥ χ(G).

Le résultat sur les nombres a_{k} constitue un des théorèmes principaux de [3] (à savoir le théorème 5.5 qui est directement équivalent au théorème 5.3). Remarquons que la démonstration de Brenti (par induction simultanée sur le nombre des sommets et des arêtes du graphe) est la plus longue de tout l’article [3], bien que Brenti remercie l’arbitre ^{⟨⟨} for suggesting a simplification in the proof of theorem 5.3^{⟩⟩}.

Brenti [3] a également regardé

\frac{p_{G}(x)}{(1 − x)^{n+1}} := ∑_{λ=0}^{∞} χ_{G}(λ) · x^{λ} ⇒ −\frac{p_{G}(\frac{1}{x})}{(1 − \frac{1}{x})^{n+1}} = ∑_{λ=0}^{∞} χ_{G}(−λ) · x^{λ},

où l’implication est une conséquence de [23], chapitre 4.2. Dans cet esprit, nous nous proposons de trouver plusieurs expressions pour

\overline{P}_{G,x}(ν) := ∑_{∅⊂V′⊆V} \frac{p_{G[V′]}(x)}{(1 − x)^{|V′|+1}} · ν^{V′}.

Proposition 6.2. On a

\frac{1}{1−x} + \overline{P}_{G,x}(ν) = ∑_{λ=0}^{∞}[1 + I_{G}(ν)]^{λ} · x^{λ} = \frac{1}{1 − x[1 + I_{G}(ν)]}

= \frac{1}{1 − x} · [1 − \frac{x}{1 − x}I_{G}(ν)]^{−1} = \frac{1}{1 − x} · ∑_{k=0}^{∞}(\frac{x · I_{G}(ν)}{1 − x})^{k},

\frac{1}{1−x} − \overline{P}_{G, \frac{1}{x}} (−ν) = ∑_{λ=0}^{∞}[1 + A_{G}(ν)]^{λ} · x^{λ} = \frac{1}{1 − x[1 + A_{G}(ν)]}

= \frac{1}{1 − x} · [1 − \frac{x}{1 − x}A_{G}(ν)]^{−1} = \frac{1}{1 − x} · ∑_{k=0}^{∞}(\frac{x · A_{G}(ν)}{1 − x})^{k},

\frac{1}{x−1} + \frac{1}{x} · \overline{P}_{G, \frac{1}{x}} (ν) = \frac{1}{x − [1 + I_{G}(ν)]} = \frac{1}{x − 1} · ∑_{k=0}^{∞}(\frac{I_{G}(ν)}{x − 1})^{k},

\frac{1}{x−1} − \frac{1}{x} · \overline{P}_{G,x}(−ν) = \frac{1}{x − [1 + A_{G}(ν)]} = \frac{1}{x − 1} · ∑_{k=0}^{∞}(\frac{A_{G}(ν)}{x − 1})^{k}.

Remarque 6.1. On n’a pas besoin de s’appuyer sur [23], chapitre 4.2, puisque l’identité fondamentale

\frac{1}{1 − y} = 1 − \frac{1}{1 − \frac{1}{y}}

implique évidemment

\begin{matrix}\frac{1}{1−x} + \overline{P}_{G,x}(ν) = \frac{1}{1 − x[1 + I_{G}(ν)]} = 1 − \frac{1}{1 − \frac{1}{x}[1 + A_{G}(−ν)]} ⇒ \\ \frac{1}{1 − x[1 + A_{G}(ν)]} = 1 − \frac{1}{1 − \frac{1}{x}} − \overline{P}_{G, \frac{1}{x}} (−ν) = \frac{1}{1−x} − \overline{P}_{G, \frac{1}{x}} (−ν). \end{matrix}

Calculons aussi la fonction génératrice

P_{G,x}(ν) := ∑_{∅⊂V′⊆V} p_{G[V′]}(x) · ν^{V′}.

Proposition 6.3. (Tomescu [25], Gansner-Vo [8], Brenti [3]) On a

\begin{aligned}1 + P_{G,x}(ν) & = (1 − \frac{x · I_{G}[(1 − x)ν]}{1 − x})^{−1} = ∑_{k=0}^{∞}(\frac{x · I_{G}[(1 − x)ν]}{1 − x})^{k}, \\ 1 + x · P_{G, \frac{1}{x}} (xν) & = (1 − \frac{x · A_{G}[(1 − x)ν]}{1 − x})^{−1} = ∑_{k=0}^{∞}(\frac{x · A_{G}[(1 − x)ν]}{1 − x})^{k}, \\ 1 + P_{G, \frac{1}{x}} (xν) & = (1 − \frac{I_{G}[(x − 1)ν]}{x − 1})^{−1} = ∑_{k=0}^{∞}(\frac{I_{G}[(x − 1)ν]}{x − 1})^{k}, \\ 1 + \frac{1}{x} · P_{G,x}(ν) & = (1 − \frac{A_{G}[(x − 1)ν]}{x − 1})^{−1} = ∑_{k=0}^{∞}(\frac{A_{G}[(x − 1)ν]}{x − 1})^{k}. \end{aligned}

Alors, avec les nombres i_{k} et a_{k} de la proposition 6.1 on a notamment

p_{G}(x) = n! · x^{n} + i_{n−1} · (n − 1)! · x^{n−1}(1 − x) + i_{n−2} · (n − 2)! · x^{n−2}(1 − x)^{2}+
… + i_{2} · 2 · x^{2}(1 − x)^{n−2} + i_{1} · x(1 − x)^{n−1}
= n! · x + a_{n−1} · (n − 1)! · x(x − 1) + a_{n−2} · (n − 2)! · x(x − 1)^{2}+
… + a_{2} · 2 · x(x − 1)^{n−2} + a_{1} · x(x − 1)^{n−1}.

Supposons que V = {1, 2, …, n}. Pour ∅ ⊂ V′, V′′ ⊆ V soit V′ < V′′ si et seulement si v′ < v′′ pour tout v′ ∈ V′ et v′′ ∈ V′′. De plus, pour des ensembles de sommets non vides, deux à deux disjoints et indépendants I_{1}, …, I_{k}, soit G[{I_{1}, …, I_{k}}] le graphe dont les sommets sont les k ensembles I_{1}, …, I_{k} et tel que {I_{i_{1}}, …, I_{i_{j}}}, ∅ ⊂ {i_{1}, …, i_{j}} ⊆ {1, …, k}, est un ensemble de j sommets indépendants si et seulement si I_{i_{1}} ∪ … ∪ I_{i_{j}} est indépendant dans le graphe G et (après une permutation appropriée de {i_{1}, …, i_{j}}) I_{i_{1}} < … < I_{i_{j}} (voir [8]). Alors la proposition précédente ainsi que le théorème 3.1 impliquent :

1 + P_{G,x}(ν)

= (1 − ∑_{∅⊂I⊆V I indépendant} x(1 − x)^{|I|−1} · ν^{I})^{−1}

= (1 + ∑_{∅⊂I⊆V I indépendant} ν^{I} · ∑_{j=1}^{|I|} \binom{|I| − 1}{j − 1} · (−x)^{j})^{−1}

= (1 + ∑_{∅⊂I⊆V I indépendant} ∑_{{I_{1}⊎...⊎I_{j}=I \atop I_{1}<...<I_{j}}} (−xν^{I_{1}}) · . . . · (−xν^{I_{j}}))^{−1}

= 1 + ∑_{∅⊂V′⊆V} ∑_{I_{1}⊎...⊎I_{k}=V′ I_{1},...,I_{k} indépendants} a(G[{I_{1}, …, I_{k}}]) · (xν^{I_{1}}) · . . . · (xν^{I_{k}}).

Proposition 6.4. (Linial [15], Gansner-Vo [8], Tomescu [25]) On a

1 + P_{G,x}(ν) = 1 + ∑_{∅⊂V′⊆V} ∑_{I_{1}⊎...⊎I_{k}=V′ I_{1},...,I_{k} indépendants} a(G[{I_{1}, …, I_{k}}]) · (xν^{I_{1}}) · . . . · (xν^{I_{k}}).

En particulier,

p_{G}(x) = p_{n}x^{n} + p_{n−1}x^{n−1} + … + p_{1}x

où les p_{k}, 1 ≤ k ≤ n, sont des entiers positifs tels que p_{n} + p_{n−1} + … + p_{1} = p_{G}(1) = n!. De plus, p_{n} = a_{1} = a(G) et p_{1} est égal à 1 si |E| = 0 et égal à 0 sinon. Si χ(G) est le nombre chromatique de G, alors p_{k} = 0, si k < χ(G), et p_{k} > 0, si k ≥ χ(G), p_{χ(G)} = i_{χ(G)} · χ(G)!.

Brenti [3] a aussi introduit et étudié beaucoup de polynômes qui ne furent jamais considérés auparavant. À partir du polynôme chromatique, leurs fonctions d’ensembles peuvent être définies comme suit :

\begin{aligned}1 + χ_{G,λ}(ν) & = [1 + I_{G}(ν)]^{λ} = ∑_{k=0}^{∞} \binom{λ}{k}I_{G}(ν)^{k}, \\ 1 + σ_{G,λ}(ν) & = exp[λI_{G}(ν)] = ∑_{k=0}^{∞} λ^{k}I_{G}(ν)^{k}/k!, \\ 1 + \overline{σ}_{G,λ}(ν) & = [1 − λI_{G}(ν)]^{−1} = ∑_{k=0}^{∞} λ^{k}I_{G}(ν)^{k}, \\ 1 + χ_{G,λ}(ν) & = [1 + A_{G}(−ν)]^{−λ} = ∑_{k=0}^{∞}(\binom{λ}{k})[−A_{G}(−ν)]^{k}, \\ 1 + τ_{G,λ}(ν) & = exp[λA_{G}(ν)] = ∑_{k=0}^{∞} λ^{k}A_{G}(ν)^{k}/k!, \\ 1 + \overline{τ}_{G,λ}(ν) & = [1 − λA_{G}(ν)]^{−1} = ∑_{k=0}^{∞} λ^{k}A_{G}(ν)^{k}. \end{aligned}

Finalement, une comparaison avec la proposition 6.2 fournit les identités

\begin{aligned}1 + (1 − x) · \overline{P}_{G,x}(ν) & = 1 + \overline{σ}_{G, \frac{x}{1−x}} (ν) et \\ 1 + (\frac{1}{x} − 1) · \overline{P}_{G,x}(−ν) & = 1 + \overline{τ}_{G, \frac{1}{x−1}} (ν), d’où \end{aligned}

Proposition 6.5. (Brenti [3])

\overline{P}_{G,x}(ν) = \frac{1}{1−x} · \overline{σ}_{G, \frac{x}{1−x}} (ν) = \frac{x}{1−x} · \overline{τ}_{G, \frac{1}{x−1}} (−ν).

7. Appendice I : Les travaux de Gessel et Stanley

Une dérivation de notre polynôme chromatique par rapport à plusieurs éléments fournit :

\begin{aligned}1 + χ_{G,λ}(ν) & = [1 + I_{G}(ν)]^{λ}, \\ ∂^{s}χ_{G,λ}(ν)/λ & = [1 + I_{G}(ν)]^{λ−1} · ∂^{s}I_{G}(ν), \\ ∂^{\{s,p\}}χ_{G,λ}(ν)/λ(λ − 1) & = [1 + I_{G}(ν)]^{λ−2} · ∂^{s}I_{G}(ν)∂^{p}I_{G}(ν), \\ ∂^{\{s,p,q\}}χ_{G,λ}(ν)/λ(λ − 1)(λ − 2) & = [1 + I_{G}(ν)]^{λ−3} · ∂^{s}I_{G}(ν)∂^{p}I_{G}(ν)∂^{q}I_{G}(ν), \end{aligned}

si {s, p} (resp. {s, p, q}) est une arête (resp. un triangle) de G, des conditions que l’on supposera toujours satisfaites dans la suite.

À l’aide du théorème 3.1 et de la proposition 3.2, on déduit des expressions positives :

\begin{aligned}1 + χ_{G,−λ}(−ν) & = [1 + A_{G}(ν)]^{λ}, \\ ∂^{s}χ_{G,−λ}(−ν)/λ & = [1 + A_{G}(ν)]^{λ} · A_{G,s}(ν), \\ ∂^{\{s,p\}}χ_{G,−λ}(−ν)/λ(λ + 1) & = [1 + A_{G}(ν)]^{λ} · A_{G,s}(ν)A_{G,p}(ν), \\ ∂^{\{s,p,q\}}χ_{G,−λ}(−ν)/λ(λ + 1)(λ + 2) & = [1 + A_{G}(ν)]^{λ} · A_{G,s}(ν)A_{G,p}(ν)A_{G,q}(ν), \end{aligned}

où les trois premières égalités reprennent les théorèmes 3.2, 3.4 et 3.3 de Gessel [10], respectivement. Grâce à la proposition 4.1, on peut récrire la troisième expression de la façon suivante :

∂^{{s,p}}χ_{G,−λ}(−ν)/λ(λ + 1) = [1 + A_{G}(ν)]^{λ+1} · A_{G,s,p}(ν).

Cependant, cette expression n’est particulièrement intéressante que si λ = −1, puisque, en général, A_{G,s,p}(ν) n’est pas positif, au moins pour certains sous-graphes engendrés de G. Le cas λ = −1 fut utilisé par Gessel [10] pour démontrer son théorème 3.1 correspondant au théorème 4.1 de cet article.

Dans l’esprit du paragraphe 6, calculons

\begin{matrix}∑_{λ=0}^{∞}[1 + χ_{G,λ}(ν)] · x^{λ} & ∑_{λ=1}^{∞} \frac{∂^{s}χ_{G,λ}(ν)}{λ} · x^{λ−1} & ∑_{λ=2}^{∞} \frac{∂^{\{s,p\}}χ_{G,λ}(ν)}{λ(λ − 1)} · x^{λ−2} \\ = \frac{1}{1 − x[1 + I_{G}(ν)]}, & = \frac{∂^{s}I_{G}(ν)}{1 − x[1 + I_{G}(ν)]}, & = \frac{∂^{s}I_{G}(ν)∂^{p}I_{G}(ν)}{1 − x[1 + I_{G}(ν)]}, \end{matrix}

et posons

\begin{matrix}∑_{λ=0}^{∞} χ_{G}(λ) · x^{λ} & ∑_{λ=1}^{∞} \frac{χ_{G}(λ)}{λ} · x^{λ−1} & ∑_{λ=2}^{∞} \frac{χ_{G}(λ)}{λ(λ − 1)} · x^{λ−2} \\ =: \frac{p_{G}(x)}{(1 − x)^{n+1}} , & =: \frac{q_{G}(x)}{(1 − x)^{n}} , & =: \frac{r_{G}(x)}{(1 − x)^{n−1}} . \end{matrix}

Pour les fonctions d’ensembles P_{G,x}(ν), Q_{G,x}(ν) et R_{G,x}(ν) dénombrant les polynômes p, q et r, respectivement, on obtient alors l’analogue de la proposition 6.3 :

Proposition 7.1. On a

\begin{aligned}1 + P_{G,x}(ν) & = (1 − \frac{x · I_{G}[(1 − x)ν]}{1 − x})^{−1}, \\ ∂^{s}Q_{G,x}(ν) & = (1 − \frac{x · I_{G}[(1 − x)ν]}{1 − x})^{−1} · \frac{∂^{s}I_{G}[(1 − x)ν]}{1 − x}, \\ ∂^{\{s,p\}}R_{G,x}(ν) & = (1 − \frac{x · I_{G}[(1 − x)ν]}{1 − x})^{−1} · \frac{∂^{s}I_{G}[(1 − x)ν]}{1 − x} \frac{∂^{p}I_{G}[(1 − x)ν]}{1 − x}. \end{aligned}

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ête de G)

p_{G}(x) = n! · x^{n} + i_{n−1} · (n − 1)! · x^{n−1}(1 − x)+
… + i_{2} · 2 · x^{2}(1 − x)^{n−2} + i_{1} · x(1 − x)^{n−1},
q_{G}(x) = (n − 1)! · x^{n−1} + i_{n−1} · (n − 2)! · x^{n−2}(1 − x)+
… + i_{2} · x(1 − x)^{n−2} + i_{1} · (1 − x)^{n−1},
r_{G}(x) = (n − 2)! · x^{n−2} + i_{n−1} · (n − 3)! · x^{n−3}(1 − x)+
… + i_{2} · (1 − x)^{n−2}.

Pour des ensembles de sommets non vides, deux à deux disjoints et indépendants I_{1}, …, I_{k}, utilisons de nouveau le graphe G[{I_{1}, …, I_{k}}] introduit dans le paragraphe 6. Si, pour le sommet s ∈ V, il existe un i ∈ {1, …, k} tel que s ∈ V_{i}, notons a_{s}(G[{I_{1}, …, I_{k}}]) le nombre d’orientations acycliques du graphe G[{I_{1}, …, I_{k}}] dont le sommet correspondant à V_{i} est la source unique. De même, si pour les deux extrémités de l’arête {s, p}, il existe des i, j ∈ {1, …, k} tels que s ∈ V_{i} et p ∈ V_{j}, notons a_{s,p}(G[{I_{1}, …, I_{k}}]) le nombre d’orientations acycliques du graphe G[{I_{1}, …, I_{k}}] dont le sommet correspondant à V_{i} est la source unique et dont le sommet correspondant à V_{j} est le puits unique (nous supposons ici que G ne contient aucun sommet isolé, voir la définition 4.1).

On démontre alors exactement comme dans le paragraphe 6 (en s’appuyant, de plus, sur les propositions 3.2 et 4.1) :

Proposition 7.2. (Gessel [10]) On a

P_{G,x}(ν) = ∑_{∅⊂I_{1}⊎...⊎I_{k}⊆V I_{1},...,I_{k} indépendants} a(G[{I_{1}, …, I_{k}}]) · (xν^{I_{1}}) · . . . · (xν^{I_{k}}),

∂^{s}Q_{G,x}(ν) = ∑_{s∈I_{1}⊎...⊎I_{k}⊆V I_{1},...,I_{k} indépendants} x^{−1} · a_{s}(G[{I_{1}, …, I_{k}}]) · (xν^{I_{1}}) · . . . · (xν^{I_{k}}),

∂^{{s,p}}R_{G,x}(ν) = ∑_{s,p∈I_{1}⊎...⊎I_{k}⊆V I_{1},...,I_{k} indépendants} x^{−2} · a_{s,p}(G[{I_{1}, …, I_{k}}]) · (xν^{I_{1}}) · . . . · (xν^{I_{k}}).

En particulier,

\begin{aligned}p_{G}(x) & = p_{n}x^{n} + p_{n−1}x^{n−1} + … + p_{1}x, \\ q_{G}(x) & = q_{n−1}x^{n−1} + q_{n−2}x^{n−2} + … + q_{1}x + q_{0}, \\ r_{G}(x) & = r_{n−2}x^{n−2} + r_{n−3}x^{n−3} + … + r_{1}x + r_{0}, \end{aligned}

où 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é) 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 χ(G) est le nombre chromatique de G et k < χ(G), alors p_{k} = 0, q_{k−1} = 0 et r_{k−2} = 0 ainsi que p_{χ(G)} = i_{χ(G)} · χ(G)!, q_{χ(G)−1} = i_{χ(G)} · (χ(G) − 1)! et r_{χ(G)−2} = i_{χ(G)} · (χ(G) − 2)!. Si k ≥ χ(G), on a p_{k} > 0, et q_{k−1} > 0 si G est connexe.

Évidemment, on a aussi les expressions directes :

Proposition 7.3.

x · Q_{G,x}(ν) = − log(1 − \frac{x · I_{G}[(1 − x)ν]}{1 − x}),
x^{2} · R_{G,x}(ν) = (1 − \frac{x · I_{G}[(1 − x)ν]}{1 − x}) · log(1 − \frac{x · I_{G}[(1 − x)ν]}{1 − x})

+ \frac{x · I_{G}[(1 − x)ν]}{1 − x} · [1 − log(1 − x)].

Notons que la positivité des coefficients du polynôme r_{G}(x) est le résultat principal de l’article [10] de Gessel (démontré sur plus qu’une page à l’aide du théorème fondamental de Stanley sur les P -partitions) tandis que le polynôme q_{G}(x) n’y figure pas.

Remarquons finalement que Stanley [22] a introduit et étudié la fonction chromatique X_{G} = X_{G}(x_{1}, x_{2}, x_{3}, …) que l’on peut, avec l’aide des fonctions d’ensembles, définir comme suit :

1 + ∑_{∅⊂V′⊆V} X_{G[V′]} · ν^{V′} := ∏_{i=1}^{∞}[1 + I_{G}(x_{i} · ν)] = exp[∑_{i=1}^{∞} −A_{G}^{∗}(−x_{i} · ν)].

8. Appendice II : se passer des fonctions d’ensembles

On pourrait être fâché de cette volonté systématique d’imposer les fonctions d’ensembles ou, qui pis est, leurs fonctions génératrices. C’est pourquoi il nous semble particulièrement important de bien expliciter plusieurs méthodes permettant de s’en passer. Comme indiqué dans le paragraphe 2, il s’agit de construire des modèles combinatoires infinis qui ne font intervenir que les cardinalités.

Remplaçons donc chaque sommet v ∈ V de notre graphe simple G = (V, E) par une famille infinie V_{v} de sommets, et relions (par une arête) deux sommets u′ ∈ V_{u} et v′ ∈ V_{v} avec u, v ∈ V et u ≠ v, si et seulement si u et v sont reliés dans le graphe G. Ces définitions sont assez naturelles tandis qu’il n’est point clair s’il faut relier deux sommets différents d’un même ensemble V_{v}. En effet, pour tout v ∈ V, on a le choix de laisser V_{v} comme ensemble indépendant infini ou bien de le remplacer par un graphe complet infini. Si l’on se décide, pour tout v ∈ V, en faveur du graphe complet (resp. de l’ensemble indépendant), le graphe infini obtenu à partir de G est noté G\overline{∞} (resp. G_{∞}).

Soit V = {1, 2, …, n}. Alors les fonctions d’ensembles (ou bien leur fonctions génératrices) comme I_{G_{∞}}(ν), χ_{G_{∞},λ}(ν), A_{G_{∞}}(ν), A_{G_{∞}}^{∗}(ν) et A_{G_{∞},t}(ν) (partout, G_{∞} peut être remplacé par G\overline{∞}) sont, en effet, des fonctions génératrices du type exponentiel en des variables (algébriquement) indépendantes v_{1}, v_{2}, …, v_{n}, dont le coefficient de (v_{1}^{i_{1}}/i_{1}!) · . . . · (v_{n}^{i_{n}}/i_{n}!) compte l’invariant respectif du graphe obtenu à partir de G en remplaçant le sommet 1 par i_{1} exemplaires, le sommet 2 par i_{2} exemplaires, …, le sommet n par i_{n} exemplaires. Évidemment, tous ces invariants peuvent être interprétés avec l’aide du seul graphe G, et les théorèmes démontrés dans les paragraphes précédents fournissent des identités pour eux. En particulier, l’identité 1+A_{G\overline{∞}}(ν) = [1+I_{G\overline{∞}}(−ν)]^{−1} n’est rien d’autre que la proposition 5.1 de [27] tandis que l’identité log[1 + A_{G\overline{∞}}(ν)] = A_{G\overline{∞}}^{∗}(ν) 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é les variables v_{1}, v_{2}, …, v_{n} par des séries sans terme constant et qu’il n’a pas mentionné que, pour chaque ensemble de ses pièces, le nombre de pyramides formées de ces pièces est divisible par le nombre de pièces, puisque, pour chaque pièce fixée, le nombre de pyramides ayant cette pièce en guise d’extrémité est toujours le même.)

En fait, même les inconditionnels des fonctions génératrices en une seule variable x peuvent s’y retrouver, puisque, dans toutes les identités pour le graphe G_{∞} ou G\overline{∞}, on peut remplacer (ν) par (x · ν) (même pour les fonctions d’ensembles). La substitution ν = 1, i. e. v_{1} = v_{2} = … = v_{n} = 1, est alors bien définie (ceci est un véritable avantage des fonctions génératrices du type exponentiel par rapport aux fonctions d’ensembles). Par exemple, le coefficient de x^{k}, k > 0, dans I_{G\overline{∞}}(x) compte, pour notre graphe G, le nombre d’ensembles indépendants de cardinalité k; et la spécialisation 1 + A_{G\overline{∞}}(x) = [1 + I_{G\overline{∞}}(−x)]^{−1} du théorème 3.1 n’est rien d’autre que la relation de réciprocité du chapitre 2.1.2 de [24].

Une méthode tout à fait différente pour obtenir des fonctions génératrices (du type exponentiel) en la seule variable V consiste à remplacer G = (V, E) par le graphe aléatoire G(p, q), p+q = 1, sur un ensemble infini V de sommets, pour lequel la probabilité d’avoir une arête entre deux sommets quelconques est égal à p, 0 ≤ p ≤ 1 (et tous ces événements sont indépendants). De cette manière, tous les coefficients de nos fonctions génératrices (pour les fonctions d’ensembles) deviennent des variables aléatoires, qui, dans les identités, ne sont multipliées que si elles sont indépendantes. Alors, grâce à la multiplicativité de l’espérance mathématique dans cette situation (et sa linéarité sans restriction) on peut, dans toutes les identités déjà démontrées, remplacer chaque variable aléatoire par sa valeur moyenne.

Notons, qu’un ensemble de n sommets du graphe G(p, q) est indépendant avec la probabilité q^{\binom{n}{2}}. On en déduit pour les espérances mathématiques :

Proposition 8.1.

1 + I_{G(p,q)}(V) = 1 + ∑_{n=1}^{∞} q^{\binom{n}{2}} · V^{n}/n!.

Alors, si A_{G(p,q)}(V) compte le nombre moyen d’orientations acycliques, le théorème 3.1 implique (voir [28], paragraphe 5) :

Proposition 8.2. (Welsh, Janson)

1 + A_{G(p,q)}(V) = [1 + ∑_{n=1}^{∞} q^{\binom{n}{2}} · (−V)^{n}/n!]^{−1}.

Notons a(n, m) le nombre de graphes orientés de façon acyclique, qui ont n sommets marqués et m arêtes. Il s’ensuit :

Proposition 8.3. (Liskovec [16], Rodionov [19]) Soit p + q = 1. Alors on a

1 + ∑_{n=1}^{∞}[\begin{matrix}( & {n \atop 2} & ) \\ ∑ \\ m=0 \end{matrix} a(n, m) · p^{m}q^{\binom{n}{2}−m}] · V^{n}/n! = [1 + ∑_{n=1}^{∞} q^{\binom{n}{2}} · (−V)^{n}/n!]^{−1}.

Regardons la spécialisation p = q = 1/2 et posons a(n) := ∑\binom{n}{2}_{m=0} a(n, m). On obtient alors le résultat de Stanley (voir [21] ou [23], chapitre 3.15) :

Proposition 8.4. (Stanley, Robinson [18])

1 + ∑_{n=1}^{∞} a(n) · V^{n}/(2^{\binom{n}{2}}n!) = [1 + ∑_{n=1}^{∞}(−V)^{n}/(2^{\binom{n}{2}}n!)]^{−1}.

Évidemment, tous les autres résultats de cet article peuvent être spécialisés de la même façon que le théorème 3.1. Cette spécialisation ^{⟨⟨} probabiliste^{⟩⟩} du théorème 3.3 fournit notamment un des deux théorèmes principaux de l’article [11], que Gessel a démontré en établissant une relation de récurrence, dont il a imaginé la solution à l’aide des ^{⟨⟨} bons dénominateurs^{⟩⟩}.

9. Appendice III : se passer de la commutativité

Soit G = (V, E), V = {1, 2, …, n}, un graphe simple. Associons à ses n sommets des variables v_{1}, v_{2}, …, v_{n} et supposons que tout monôme contenant une de ces variables au moins deux fois est nul. Ceci ne restreint pas la généralité de nos considérations parce que, selon l’appendice précédent, on peut remplacer G par G\overline{∞} pour obtenir précisément les mêmes résultats que dans [5] ou dans [27]. À la différence 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ête entre les deux sommets i, j ∈ V. L’algèbre associative ainsi obtenue est notée A[V] comme dans le cas commutatif. Il n’est pas difficile de démontrer que chaque monôme de A[V] correspond, de façon bijective, à une orientation acyclique du graphe engendré par les sommets qui correspondent aux variables du monôme. Pour écrire le monôme, commençons par les variables des sources de l’orientation acyclique (ces variables commutent mutuellement puisque l’ensemble des sources est indépendant). En appliquant la même procédure au graphe engendré par les sommets des autres variables du monôme, on finit par obtenir une partition canonique des sommets du monôme en ensembles indépendants. Celle-ci est appelée V-décomposition ou forme normale de Foata (voir [24] ainsi que [5], théorème 1.2).

Notons A_{G}(ν), A_{G}(0) = 0, la somme de tous les monômes différents de A[V] de sorte qu’on recouvre la fonction A_{G}(ν) déjà introduite en soumettant toutes les variables à la loi commutative. Si I_{G}(ν), I_{G}(0) = 0, désigne la somme de tous les monômes dont les variables commutent mutuellement (ce sont les monômes correspondant aux ensembles indépendants), alors la démonstration même de la proposition 3.2, i. e. le principe d’inclusion-exclusion, implique encore que le produit [1+I_{G}(−ν)]·[1+A_{G}(ν)] dénombre les orientations acycliques sans aucune source. Autrement dit, on a établi le théorème de Cartier et Foata sur l’inversion (de Möbius) dans le monoïde de commutation, à savoir l’identité (voir [5], théorème 2.4) [1 + I_{G}(−ν)] · [1 + A_{G}(ν)] = 1.

Cependant, les coefficients de − log[1 + I_{G}(−ν)] ne sont pas toujours des entiers dans le cas non-commutatif et la règle ∂^{s} − log[1 + I_{G}(−ν)] = −[1 + I_{G}(−ν)]^{−1} · ∂^{s}I_{G}(−ν) n’est plus valable. Voilà pourquoi nous nous sommes imposés, dans cet article, la commutativité pour toutes les variables.

Remerciements. En tout premier lieu, je voudrais remercier vivement D. Foata de son accueil chaleureux à Strasbourg et de ses explications stimulantes en ce qui concerne le livre [5]. Son aide et assistance sont au-delà de toute expression. Je remercie aussi E. Triesch pour tout son appui dans mon projet de thèse véritablement lotharingien.

Références bibliographiques

[1] B. Bollobás, ^{⟨⟨} Modern Graph Theory^{⟩⟩}, Springer-Verlag, Berlin, 1998.

[2] M. Bousquet-Mélou, q-Énumération de polyominos convexes, J. Combin. Theory, Ser. A 64 (1993), 265-288.

[3] F. Brenti, Expansions of chromatic polynomials and log-concavity, Trans. Amer. Math. Soc. 332 (1992), 729-756.

[4] T. H. Brylawski et J. G. Oxley, ^{⟨⟨} The Tutte polynomial and its applications^{⟩⟩}, in: Matroid Applications, (ed. : N. White) Cambridge University Press, Cambridge (1992), 123-225.

[5] P. Cartier et D. Foata, ^{⟨⟨} Problèmes combinatoires de commutation et réarrangements^{⟩⟩}, Springer-Verlag, Berlin, 1969.

[6] H. Crapo, A higher invariant for matroids, J. Combin. Theory 2 (1967), 406-417.

[7] D. Foata, A noncommutative version of the matrix inversion formula, Adv. Math. 31 (1979), 330-349.

[8] E. R. Gansner, K. P. Vo, The chromatic generating function, Linear and Multilinear Algebra 22 (1987), 87-93.

[9] D. D. Gebhard et B. E. Sagan, Sinks in acyclic orientations of graphs, J. Combin. Theory, Ser. B 80 (2000), 130-146.

[10] I. M. Gessel, Acyclic orientations and chromatic generating functions, Discrete Math. 232 (2001), 119-130.

[11] I. M. Gessel, Counting acyclic digraphs by sources and sinks, Discrete Math. 160 (1996), 253-258.

[12] C. Greene et T. Zaslavsky, On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-radon partitions, and orientations of graphs, Trans. Amer. Math. Soc. 280 (1983), 97-126.

[13] A. Huck, ^{⟨⟨} Flüsse und Wege in Graphen^{⟩⟩}, Bonn, 1997.

[14] B. Lass, ^{⟨⟨} Funktionen zählen^{⟩⟩}, Diplomarbeit, 1997.

[15] N. Linial, Graph colouring and monotone functions on posets, Discrete Math. 58 (1986), 97-98.

[16] V. A. Liskovec, O chisle maksimalnyh vershin sluchajnogo aciklicheskogo orgrafa, Teor. Verojatnost. i Primenen. 20 (1975), 412-421.

[17] L. Lovász, ^{⟨⟨} Combinatorial Problems and Exercises^{⟩⟩}, Akadémiai Kiadó, Budapest, 1993.

[18] R. W. Robinson, Counting labeled acyclic digraphs, in: 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.

[19] V. I. Rodionov, Javnaja formula dlja chisla pomechennyh aciklicheskih orientirovannyh grafov, Avtomorfnye funkcii i teorija chisel, Sb. nauch. tr., Izhevsk (1987), 22-25.

[20] H. Sachs, ^{⟨⟨} Einführung in die Theorie der endlichen Graphen^{⟩⟩}, Teil II, BSB B. G. Teubner Verlagsgesellschaft, 1972.

[21] R. P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973), 171-178.

[22] R. P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.

[23] R. P. Stanley, ^{⟨⟨} Enumerative Combinatorics^{⟩⟩}, Volume 1, Cambridge University Press, Cambridge, 1997.

[24] V. Strehl, Counting domino tilings of rectangles via resultants, à paraître dans Adv. Appl. Math. (2001).

[25] I. Tomescu, Graphical Eulerian numbers and chromatic generating functions, Discrete Math. 66 (1987), 315-318.

[26] W. T. Tutte, ^{⟨⟨} Graph Theory^{⟩⟩}, Addison-Wesley, 1984.

[27] G. X. Viennot, Heaps of pieces, I : Basic definitions and combinatorial lemmas, Combinatoire énumérative, Proc. Colloq., Montréal/Can. 1985, Lect. Notes Math. 1234 (1986), 321-350.

[28] D. J. A. Welsh, Counting colourings and flows in random graphs, Combinatorics, Paul Erdös is Eighty, Volume 2, Keszthely (Hungary), 1993, Bolyai Society Mathematical Studies 2 (1996), 491-505.

Bodo Lass

Lehrstuhl II für Mathematik,

RWTH Aachen, Templergraben 55,

D-52062 Aachen, Allemagne. Courriel: lass@math2.rwth-aachen.de

et

Département de mathématique,

Université Louis-Pasteur, 7, rue René-Descartes, F-67084 Strasbourg, France. Courriel: lass@math.u-strasbg.fr