Factorisation du numérateur

 Factorisation par chaîne

Sachant que N(G) est nul pour les graphes non connexes, nous supposons par la suite que tous les graphes sont connexes. De même, sachant que le numérateur de la fraction réduite ΨG est égal à N(H(G)), l’étude de N(G) sur les graphes est équivalente à celle de N(G) sur les graphes sans circuits et sans relations transitives (une arête ayant même origine et même fin qu’une autre chaîne). Soit G un graphe, c une chaîne de G, Vc l’ensemble des sommets de c (incluant l’origine et la fin de la chaîne) et G1, . . . , Gk tous les graphes connexes de G \ Vc. Le sous-graphe 67 Factorisation du numérateur 5.1. Factorisation par chaîne 68 Gi induit sur VGi ∪ Vc (pour 1 ≤ i ≤ k) sera appelé région de G. Considérons, par exemple le graphe de la figure 5.2 et la chaîne c = (1, 2, 13, 3, 4, 5, 6, 14). Sous cette forme, le graphe G \ Vc possède quatre composantes connexes. Fig. 5.2 – Un graphe G avec une chaîne c, les composantes Gi de G \ c et les régions correspondantes Gi Le théorème de factorisation par chaîne s’énonce de la façon suivante : Théorème 5.1.1. Soit G un graphe, c une chaîne de G et G1, G2,… , Gk les régions correspondant à G. Alors nous avons N(G) = Y k j=1 N(Gj ). Par exemple, le numérateur de la fraction rationnelle associée au graphe de la figure 5.2 peut être exprimé comme un produit de quatre facteurs non triviaux. Preuve. L’idée centrale est d’appliquer le théorème 3.5.1 sur les cycles C contenus dans une seule région et telle que HE(C) ∩ c = ∅. Cela signifie que les arêtes de c peuvent apparaître dans C, mais uniquement avec la mauvaise orientation. Ainsi, quand nous appliquons la proposition 4.5.2, nous ne modifions pas la chaîne c. Une illustration de la preuve est disponible dans la figure 5.3. La première étape, réalisée par le lemme 5.1.2 et illustrée par la figure 5.4, consiste à prouver l’existence de tels cycles. Lemme 5.1.2. Soit G un graphe et c une chaîne de G. On note par G1,… , Gk les régions correspondantes. Si G1 n’est pas un arbre, il existe un cycle C de G1 tel que HE(C)∩c = ∅. Démonstration. Choisissons un cycle C0 de G1. Deux cas doivent être examinés : 1) Le cycle C0 n’a pas de sommet en commun avec c. Rien ne doit être fait. 

Factorisations complètes des posets planaires

Dans l’article [23], C. Greene a proposé une formule close pour la somme Ψ(G) où G est le graphe minimal (diagramme de Hasse) d’un poset planaire (voir la section 4.3 et le théorème 4.3.1). Dans ce cas, le numérateur N(G) peut être écrit comme un produit de termes de degré 1 (théorème 4.3.1). Nous verrons que la propriété de factorisation est une conséquence du théorème 5.1.1. Mieux encore, ce dernier permet d’étendre le théorème de Greene (théorème 4.3.1) qui peut s’appliquer sur un ensemble plus important de graphes. Il est à noter que le graphe induit d’un graphe fortement planaire est fortement planaire (la définition des graphes fortement planaires a été donnée à la section 4.3). Même si on supprime quelques arêtes, on ne peut pas obtenir un graphe non planaire. En particulier, les régions d’un graphe planaire sont, elles aussi, des graphes planaires. De plus, un graphe avec un seul cycle et sans sommet de valence 1 est fortement planaire si et seulement s’il possède une unique source et un unique puits. Dans ce cas, nous appellerons ce graphe un diamant. Un exemple de diamant est reproduit dans la figure 5.5. Fig. 5.5 – Un diamant Quand le graphe est fortement planaire, nous allons montrer qu’il est toujours possible de trouver une chaîne qui déconnecte le graphe. Ce qui explique le fait que la fonction N(G) peut être factorisée en facteur de degré 1. Proposition 5.2.1. Soit G un graphe orienté, fortement planaire, possédant un nombre de cycles plus grand que 1, alors il existe une chaîne de G, séparant G en deux régions non triviales (chaque région contient au moins un cycle). Démonstration. En appliquant un émondage sur le graphe G, on peut supposer le fait que G n’a pas de sommet de valence 1. Dans ce contexte, comme G possède au moins 2 cycles, il possède au moins un sommet c2 de valence 3 ou plus. Ainsi, à une symétrie verticale près, nous avons l’un des deux cas suivants (dans le second cas, on supposera que c2 constitue la fin d’exactement 2 arêtes) : c2 c2 5.2. Factorisations complètes des posets planaires 72 Dans le premier cas, choisissons les étiquettes des sommets selon ce schéma : b c1 a c2 Dans le second cas, nous définissons par induction ci pour i ≥ 3. Nous choisissons pour ci n’importe quel sommet tel qu’il existe une arête d’origine ci−1 et de fin ci . Pour k ≥ 3, on ne peut pas définir ck+1 si ck n’est l’origine d’aucune arête. Alors, comme ck n’est pas un sommet de valence 1, il est nécessairement la fin d’une arête dont l’origine est le sommet b 6= ck−1. En dernier lieu, on appelle c1 et a les origines des deux arêtes dont la fin est c2. Pour distinguer le sommet c1 du sommet a, il faut savoir si b est au-dessus ou en dessous de ck−1 (voir la figure ci-après). c1 a c2 ck b a c1 c2 ck b Dans tout les cas, les ci sont des sommets d’une chaîne c de G. Cette chaîne c peut être prolongée en une chaîne maximale cmax. Nous rappelons qu’avec la définition de C. Greene concernant les graphes planaires, le graphe G0,∞, peut toujours être plongé dans le plan sans arêtes qui se croisent. Il existe alors une chaîne de G0,∞ contenant v0, cmax et v∞. Cette chaîne coupe G0,∞ en au moins deux régions. La première région contient a et l’autre contient b. Cette propriété reste vraie pour la chaîne cmax de G. Comme G n’a pas de sommet de valence 1, les régions correspondantes possèdent un cycle ou plus. Corollaire 5.2.2. Soit G un poset planaire fortement connexe. En itérant la factorisation par chaîne, on peut écrire N(G) comme un produit de numérateurs de fonctions rationnelles associées aux diamants. Démonstration. La proposition 5.2.1 et le théorème 5.1.1 impliquent que N(G) peut être factorisé en un produit de numérateurs de sous-graphes avec un seul cycle. Comme les sousgraphes sont fortement planaires, l’opération d’émondage transforme les sous-graphes en diamants, ce qui finit la preuve. Il est à noter que pour un diamant, la fonction N possède une formule explicite (proposition 4.7.1) : N(D) = xmin(D) − xmax(D) , soit de manière équivalente, Ψ(D) = Y y,z∈P (xy − xz) µD(y,z) où µD est la fonction de Möbius du poset associé au diamant D.