Du Théorème de Ramsey à la Conjecture d’Erdős-Hajnal (2)
Le pouvoir de l’interdit
Piste noire Le 21 décembre 2017 Voir les commentaires (2)
Dans une première partie, nous avons vu qu’une certaine dose d’ordre est inévitable et qu’en particulier, tout graphe contient un grand ensemble stable ou une grande clique.
La taille minimale de cet ensemble stable ou clique inévitable est obtenue pour les graphes aléatoires. Que se passe-t-il si, à l’opposé, nous imposons une contrainte locale forte ? C’est le propos de la conjecture d’Erdős-Hajnal...
Au moment de continuer notre cheminement du théorème de Ramsey à la conjecture d’Erdős-Hajnal, et avant de nous plonger plus profondément encore dans les « technicalités » mathématiques, prenons le temps de contempler le paysage. Le point de vue, en ce moment charnière, est une invitation à la rêverie mathématique sur les notions d’ordre et de hasard, une invitation à nourrir notre intuition de ce monde toujours surprenant.
La faculté qui nous apprend à voir, c’est l’intuition. Sans elle, le géomètre serait comme un écrivain qui serait ferré sur la grammaire, mais qui n’aurait pas d’idée.
Henri Poincaré [1]
Un peu de philosophie au hasard
Nous avons vu, dans la première partie, que tout graphe suffisamment grand contient un ensemble stable ou une clique de taille non négligeable. Rappelons qu’un ensemble stable est un ensemble de sommets deux à deux non-adjacents, et qu’à l’inverse une clique est un ensemble de sommets deux à deux adjacents.
Cet ordre inévitable nous met en garde contre toutes sortes de conclusions hâtives.
« Où l’homme aperçoit un tout petit peu d’ordre, il en suppose immédiatement beaucoup trop. »
Francis Bacon [2]
Néanmoins, pour être sûrs de trouver un ensemble stable ou une clique de taille $t$, nous devons considérer un graphe de taille au moins $2^t$. En particulier, un graphe aléatoire [3] de taille $2^t$ ne contient très probablement [4] ni stable ni clique de taille plus grande que $2t$.
Bien que cette propriété soit vraie pour un grand graphe pris au hasard, il est très difficile de construire explicitement des graphes ayant cette propriété, c’est-à-dire contenant beaucoup de sommets ($2^t$) et ne contenant ni clique ni ensemble stable significativement plus grand que le minimum inévitable ($t$).
Quel est le rôle du hasard ? Comment caractériser le chaos et la folie combinatoire qui naît du hasard ? Permettons-nous, à nouveau, de détourner une citation philosophique afin d’illustrer notre propos.
« Ce qui caractérise le chaos, en effet, c’est moins l’absence de déterminations que la vitesse infinie à laquelle elles s’ébauchent et s’évanouissent : ce n’est pas un mouvement de l’une à l’autre, mais au contraire l’impossibilité d’un rapport entre deux déterminations, puisque l’une n’apparaît pas sans que l’autre ait déjà disparu, et que l’une disparaît comme évanouissante quand l’autre disparaît comme ébauche. »
Gilles Deleuze, Félix Guattari [5]
Autrement dit, lorsqu’on construit aléatoirement un graphe, les stables et les cliques apparaissent en se détruisant, et aucun des deux ne parvient à grossir de manière significative.
Que se passe-t-il si nous nous éloignons du hasard ? Si, par la contrainte, nous imposons une forme de structure ? C’est l’idée de la conjecture d’Erdős-Hajnal :
De la contrainte naît la structure, et de la structure naît l’ordre.
En interdisant la présence d’une sous-structure, nous forçons une structure globale, et cette structure globale implique l’apparition de stables ou de cliques significativement plus grands que ce qu’on trouverait dans un graphe aléatoire. Précisément, Paul Erdős et András Hajnal ont proposé en 1989 la conjecture suivante.
Tout graphe $G$ suffisamment grand qui ne contient pas de copies induites de $F$ et qui a plus de $t^{c(F)}$ sommets contient un ensemble stable ou une clique de taille $t$.
Dans cet énoncé, un graphe $G$ contient une copie induite d’un graphe $F$ si on peut trouver dans $G$ autant de sommets qu’il y a dans $F$, avec exactement les mêmes paires de sommets adjacents (cf première partie).
Nous dirons qu’un graphe $F$ possède la propriété d’Erdős-Hajnal s’il existe un entier $c(F)$ tel que tout graphe $G$ suffisamment grand qui ne contient pas de copies induites de $F$ et qui a plus de $t^{c(F)}$ sommets contient un ensemble stable ou une clique de taille $t$. Nous définissons alors la valeur $c(F)$ comme étant le plus petit entier avec cette propriété.
Nous avons démontré dans la première partie que les cliques possèdent la propriété d’Erdős-Hajnal. En fait, si $F$ est une clique de taille $k$, nous avons $c(F)\leq k-1$.
Un cas d’école : les chemins de longueur $3$ et les cographes
Un petit chemin pour se mettre en jambes...
Qu’en est-il du chemin $P_3$ de longueur $2$ (le $3$ de $P_3$ compte le nombre de sommets du chemin, et non la longueur) ?
Un graphe contient une copie induite du chemin $P_3$ de longueur $2$ s’il contient trois sommets $a,b,c$ tels que $a$ est voisin de $b$ et $b$ de $c$, mais $a$ n’est pas voisin de $c$.
- une copie de $P_3$ induite par les sommets $a,b,c$.
Les graphes sans copies induites de $P_3$ ont une structure très simple : ce sont des unions de cliques !
- Un graphe (non connexe) sans copies induites d’un chemin de longueur 2
- Dans ce graphe, chaque composante connexe est une clique.
Si $G$ ne contient pas cliques de taille $t$, alors il contient au moins $t$ cliques. En prenant un sommet dans chaque clique nous formons alors un ensemble stable de taille au moins $t$.
∎
Entrons dans la danse : du pas de deux au pas de trois.
Un exemple, bien moins simple — mais fort instructif — est le chemin de longueur $3$.
Un graphe contient une copie induite du chemin $P_4$ de longueur $3$ s’il contient quatre sommets $a,b,c,d$ tels que $a$ est voisin de $b$, $b$ de $c$, $c$ de $d$, mais $a$ n’est voisin ni de $c$ ni de $d$, et $b$ n’est pas voisin de $d$, c’est-à-dire si on peut trouver dans le graphe la configuration suivante :
- une copie de $P_4$ induite par les sommets $a,b,c,d$.
Cet exemple va nous révéler comment une contrainte locale peut engendrer une structure globale, et comment cette structure globale implique la présence d’une grande clique ou d’un grand stable.
De la contrainte naît la structure
- Un exemple de cographe
Les cographes ont une structure globale bien particulière, qui
lie en particulier les ensembles stables maximaux (c’est-à-dire les ensembles stables qui ne sont pas strictement contenus dans des ensembles stables plus grands) et les cliques maximales (c’est-à-dire les cliques qui ne sont pas strictement contenues dans des cliques plus grandes) :
Supposons qu’il existe un ensemble stable
maximal $S$ et une clique maximale $K$ qui ne s’intersectent pas.
- Il existe au moins un sommet de $S$ qui a un voisin dans $K$.
Sinon, nous pourrions ajouter l’un des sommets de $K$ à $S$ et former un ensemble stable plus grand (puisqu’aucun sommet de $S$ ne l’a pour voisin).
Soit donc $a$ un sommet de $S$ avec un nombre maximum de voisins dans $K$.
- La clique $K$ contient un sommet $c$ qui n’est pas voisin de $a$.
Sinon, le sommet $a$ serait voisin de tous les sommets de $K$ et donc en ajoutant $a$ à $K$ nous pourrions obtenir une clique plus grande.
- L’ensemble $S$ contient un sommet $d$ voisin de $c$.
Sinon $c$ pourrait être ajouté à $S$ pour former un ensemble stable plus grand.
Le sommet $d$ est distinct de $a$ (car $c$ est voisin de $d$ mais pas de $a$) et n’est pas voisin de $a$ (car $a$ et $d$ appartiennent tous deux à l’ensemble stable $S$).
- Le sommet $a$ possède au moins un voisin $b$ dans $K$ qui n’est pas un voisin de $d$. Sinon, le sommet $d$ serait voisin de tous les voisins de $a$ dans $K$, ce qui contrarierait le choix de $a$ comme sommet de $S$ ayant le plus de voisins dans $K$.
Donc le sommet $b$ est distinct de $c$ (avec lequel il est voisin).
Les sommets $a,b,c,d$ forment donc une copie induite du chemin de longueur $3$, ce qui est contraire à notre hypothèse de départ !
Par l’absurde, nous avons donc démontré que, dans un cographe — c’est-à-dire dans un graphe qui ne contient pas de copies induites de $P_4$ — tout ensemble stable maximal intersecte toute clique maximale.
∎
Cette propriété globale a une conséquence directe sur la structure des ensembles stables et des cliques d’un cographe :
Soit $G'$ le graphe obtenu à partir de $G$ en supprimant tous les sommets de $S$ (ainsi que les arêtes qui y sont incidentes), et soit $K'$ la clique de $G''$ obtenue en enlevant de $K$ l’unique sommet à la fois dans $K$ et dans $S$.
Alors $K'$ est une clique de taille maximale du cographe $G'$.
- Suppression d’un ensemble stable maximal d’un cographe
Supposons pour contradiction que $K'$ ne soit pas une clique de taille maximale de $G'$. Soit $K''$ une clique de $G'$ de taille maximale, donc de taille au moins $c$.
Mais $K''$ est également une clique de $G$, et même une clique maximale de $G$ puisqu’elle est de taille $c$. Donc $K''$ intersecte $S$, ce qui contredit l’hypothèse que $K''$ est une clique de $G'$.
∎
Et de la structure naît l’ordre
Nous allons voir que cette propriété va nous permettre de démontrer que $P_4$ possède la propriété d’Erdős-Hajnal. Précisément :
En effet, supposons que notre graphe $G$ ne contient aucune clique de taille $t$, et soit $K$ une clique de taille maximale (qui contient $k\leq t-1$ sommets). Choisissons un ensemble stable maximal $S$ (qui contient donc un sommet $v$ de $K$) et supprimons-le. Nous obtenons un nouveau graphe $G'$, qui est toujours un cographe.
Comme toute clique maximale de $G$ intersecte $S$, les cliques de $G'$ sont de taille au plus $k-1$. Nous en déduisons que $K-v$ est une clique de taille maximale de $G'$.
Répétons cette même opération, jusqu’à ce que le graphe soit vide (i.e. ne contienne plus aucun sommet). Comme à chaque étape nous supprimons un sommet de $K$ exactement, nous avons donc supprimé $k$ ensembles stables. Si $n>(t-1)^2$ (donc $n>k(t-1)$) alors un des ensembles stables que nous avons supprimés contenait au moins $t$ sommets. Comme le fait de supprimer des sommets n’a pas changé les liens à l’intérieur de cet ensemble, le graphe de départ contenait donc un ensemble stable de taille $t$.
∎
Retour au problème général, ou comment faire du neuf avec du vieux.
Nous avons réussi à élucider un cas de la conjecture d’Erdős-Hajnal. Étudier les cas un par un serait un travail de titan. C’est pourquoi, au lieu de considérer tous les graphes $F$ un par un, nous allons rechercher quelles constructions permettent d’obtenir de nouveaux graphes ayant la propriété d’Erdős-Hajnal à partir d’exemples connus.
Compléments d’exemples
La première construction consiste en la complémentation d’un graphe.
Le graphe complémentaire d’un graphe $G$ est le graphe, noté $\overline{G}$, qui a le même ensemble de sommets que $G$, et dans lequel on a échangé les arêtes et les non-arêtes.
En d’autres termes, deux sommets $x$ et $y$ sont adjacents dans $\overline{G}$ si, et seulement si, il ne le sont pas dans $G$ :
- Le graphe complémentaire
À noter que le graphe complémentaire du graphe complémentaire d’un graphe est le graphe lui-même ($\overline{\overline{G}}=G$).
Nous allons maintenant démontrer que la propriété d’Erdős-Hajnal est conservée quand on prend le graphe complémentaire, formellement, sous la forme d’une proposition.
De plus, nous avons alors
\[c(\overline{F})=c(F).\]
On vérifie immédiatement que $G$ ne contient pas de copies induites de $\overline{F}$ si, et seulement si, le graphe $\overline{G}$ ne contient pas de copies induites de $F$.
Soit donc un graphe $G$ suffisamment grand ne contenant pas de copies induites de $\overline{F}$. Alors $\overline{G}$ (qui est aussi grand que $G$) ne contient pas de copies induites de $F$, et donc (puisque nous supposons que $F$ à la propriété d’Erdős-Hajnal) si la taille de $\overline{G}$ (i.e. la taille de $G$) est au moins $t^{c(F)}$ alors $\overline{G}$ contient une clique ou un ensemble stable de taille $t$. Or, une clique de $\overline{G}$ est un ensemble stable de $G$, et un ensemble stable de $\overline{G}$ est une clique de $G$.
Donc $G$ contient une clique ou un ensemble stable de taille $t$, ce qui signifie que $\overline{F}$ à la propriété d’Erdős-Hajnal et que $c(\overline{F})\leq c(F)$.
En appliquant une deuxième complémentation, nous obtenons \[c(F)=c(\overline{\overline{F}})\leq c(\overline{F})\leq c(F)\text{ donc }c(\overline{F})=c(F).\]
∎
Les cliques ayant la propriété d’Erdős-Hajnal, il en est de même des graphes sans arêtes. Précisément, nous déduisons que tout graphe à $n\geq t^{k-1}$ sommets sans ensembles stables de taille $k$ contient une clique de taille $t$.
Quelque chose d’universel
Ajouter un sommet universel à un graphe $F$ consiste a créer un nouveau graphe $F'$, obtenu à partir de $F$ en ajoutant un nouveau sommet et à le relier par des arêtes à tous les sommets de $F$ :
- Ajout d’un sommet universel
De plus, nous avons alors
\[c(F')\leq c(F)+1.\]
- Si $G$ possède un sommet $v$ ayant au moins $t^{c(F)}$ voisins, alors le graphe $G'$ formé par les voisins de $v$ (et les arêtes les reliant) ne contient pas de copies induites de $F$, car toute copie induite de $F$ dans le voisinage de $F$ formerait, avec $v$, une copie induite de $F'$ dans $G$.
Le graphe $G'$ ne contient aucune copie induite de $F$ et possède au moins $t^{c(F)}$ sommets (puisque $v$ a au moins $t^{c(F)}$ voisins). Comme $F$ a la propriété d’Erdős-Hajnal nous en déduisons que $G'$ contient une clique ou un ensemble stable de taille $t$, et il en est naturellement de même pour $G$. - Sinon, tout sommet de $G$ a au plus $t^{c(F)}-1$ voisins. Ainsi que nous l’avons vu dans la Partie $1$, nous pouvons alors colorier les sommets de $G$ en $n/t^{c(F)}$ couleurs, de manière à ce que deux sommets de même couleur ne soient jamais voisins. En considérant la couleur majoritaire, nous obtenons alors un ensemble stable de taille au moins $n/t^{c(F)}$. Si $n\geq t^{c(F)+1}$, le graphe $G$ contient donc un ensemble stable de taille $t$.
∎
Remarquons que cette proposition nous permet de retrouver le fait que la clique $K_k$ de taille $k$ possède la propriété d’Erdős-Hajnal avec $c(K_k)\leq k-1$ :
la clique $K_2$ de taille $2$ (formée de deux sommets joints par une arête) possède évidemment la propriété d’Erdős-Hajnal avec $c(K_2)=1$, car tout graphe sans arête de taille $t^1$ contient un ensemble stable de taille $t$. La clique $K_k$ de taille $k$ étant obtenue par ajout d’un sommet universel à la clique $K_{k-1}$ de taille $k-1$, nous obtenons donc, par récurrence sur $k$, l’inégalité $c(K_k)\leq k-1$.
Un exemple moins immédiat est celui de l’étoile $S_k$, qui est le graphe obtenu en ajoutant un sommet universel à un graphe de taille $k$ sans arêtes.
- L’étoile $S_7$
Nous déduisons donc de la proposition précédente que l’étoile $S_k$ possède, pour tout entier $k$, la propriété d’Erdős-Hajnal, et que de plus nous avons $c(S_k)\leq k$.
Dérivé de substitution
Au début des années 2000, Alon, Pach et Solymosi ont démontré que la propriété d’Erdős-Hajnal est préservée par une opération appelée « substitution ».
Soient $F_1$ et $F_2$ deux graphes, et soit $v$ un sommet de $F_1$. La substitution dans $F_1$ du sommet $v$ par le graphe $F_2$ consiste à prendre l’union disjointe des graphes $F_1$ et $F_2$, à supprimer le sommet $v$ dans $F_1$ et à relier tous les sommets qui étaient voisins de $v$ dans $F_1$ à tous les sommets de $F_2$ :
- La substitution dans $F_1$ de $v$ par $F_2$
Esquisse de preuve.
Soit $F$ le graphe obtenu en substituant dans $F_1$ le sommet $v$ par le graphe $F_2$.
Soit $t$ un entier, et soit $k$ un entier suffisamment grand. Soit $n=t^{\max(c(F_1),c(F_2))}$.
Considérons un graphe $G$ contenant au moins $N=n^k$ sommets
ne contenant aucune copie induite du graphe $F$. Supposons (pour contradiction) que le graphe $G$ ne contienne pas de cliques ou d’ensembles stables de taille $t$. Comme $F_1$ et $F_2$ possèdent la propriété d’Erdős-Hajnal, si nous prenons n’importe quel sous-ensemble de sommets $A$ de taille $n$, alors le graphe $G[A]$ formé par les sommets dans $A$ et les arêtes les joignant contient à la fois une copie induite de $F_1$ et une copie induite de $F_2$.
Un argument de comptage montre alors (en supposant $k$ suffisamment grand) qu’il existe dans $G$ une copie induite $F_1'$ de $F_1$ avec la propriété suivante : si on note $v'$ le sommet correspondant à $v$ dans $F_1'$, alors il existe au moins $n$ sommets de $G$ qui permettent d’étendre $F_1'-v'$ (i.e. la copie induite $F_1'$ de $F_1$ moins le sommet $v'$ correspondant à $v$) en une copie induite de $F_1$ :
L’ensemble $A$ des sommets permettant d’étendre $F_1'-v'$ en une copie induite de $F_1$ induit alors un graphe $G[A]$ qui possède plus de $n$ sommets et ni ensemble stable ni clique de taille $t$. Comme $F_2$ a la propriété d’Erdős-Hajnal, nous en déduisons que $G[A]$ contient une copie induite de $F_2$ qui, avec $F_1'-v'$ forme une copie induite de $F$. Le graphe $G$ contient
donc une copie induite de $F$, ce qui contredit notre hypothèse de départ. Nous avons donc démontré (ou plutôt esquissé la preuve) que le graphe $F$ possède la propriété d’Erdős-Hajnal.
∎
Et maintenant ?
Quelques autres exemples de graphes ayant la propriété d’Erdős-Hajnal sont connus, tels que tous les graphes d’au plus $4$ sommets.
Pour les graphes à $5$ sommets, deux graphes résistent : le chemin de longueur $4$ (ou, de manière équivalente, son graphe complémentaire) et le cycle de longueur $5$ :
- Cas difficiles pour la conjecture d’Erdős-Hajnal
Et pour les autres, me direz-vous ? Même si la conjecture n’est pas résolue dans le cas général, elle l’est approximativement :
Presque tous [6] les graphes $G$ suffisamment grands qui ne contiennent pas de copies induites de $F$ et qui ont plus de $t^{c(F)}$ sommets contiennent un ensemble stable ou une clique de taille $t$.
En d’autres termes, les exemples de graphes $G$ « difficiles » ne sont plus, dans ce cas, les graphes aléatoires sans copies induites de $F$.
Comme quoi...
« On se fait une idée précise de l’ordre, mais non pas du désordre. »
Jacques-Henri Bernardin de Saint-Pierre [7]
Je tiens à exprimer à nouveau ma reconnaissance à Shalom Eliahou pour ses commentaires inestimables lors de la rédaction de cette deuxième partie. Je tiens à remercier Bedaride Nicolas, Marielle Simon et Cidrolin pour leur relecture attentive et leurs commentaires bienveillants. Enfin, un grand merci à Carole Gaboriau et Maï Sauvageot, inlassables chasseuses de coquilles, pour leur soutien précieux.
Notes
[2] Francis Bacon, Aphorismes, p. 233-234 de la traduction française
[3] Ici, aléatoire peut signifier que chaque arête existe, indépendamment des autres, avec une probabilité de 1/2, ou que le graphe est tiré au hasard uniformément parmi tous les graphes de taille $2^t$ (modèles d’Erdős-Rényi)
[4] Avec une probabilité tendant vers $1$ lorsque $t$ tend vers l’infini
[5] Gilles Deleuze, Félix Guattari, Qu’est-ce que la philosophie ?, p.44
[6] « Presque tous les graphes $G$ » signifie que la proportion de graphes $G$ de taille $n$ possédant cette propriété tend vers $1$ lorsque $n$ tend vers l’infini.
[7] Jacques-Henri Bernardin de Saint-Pierre, Paul et Virginie.
Partager cet article
Pour citer cet article :
Patrice Ossona de Mendez — «Du Théorème de Ramsey à la Conjecture d’Erdős-Hajnal (2)» — Images des Mathématiques, CNRS, 2017
Laisser un commentaire
Articles suggérés
Si vous avez aimé cet article, voici quelques suggestions automatiques qui pourraient vous intéresser :
-
le Septembre 2017Ordnung muss sein ! (L’ordre est inévitable). Cet adage, attribué à Théodore Motzkin, résume bien la théorie de Ramsey, qui tente de résoudre des problèmes du type « À...lire l'article -
le 19 juilletFormule d’Euler pour les graphes planaires à travers un déroulé de petits problèmes. Amusez-vous !lire l'article -
le Juin 2015Notion d’arbre en théorie des graphes à travers un déroulé de petits problèmes. Amusez-vous !lire l'article
L'auteur
Actualités des maths
-
15 octobre 2019“Gathering for Gardner” (Paris, 21/10)
-
11 octobre 2019Appel à candidature aux prix d’Alembert et Jacqueline Ferrand
-
9 octobre 2019Les mathématiques de l’origami (Villeurbanne, 15/10)
-
8 octobre 2019Labyrinthes aléatoires et transition de phase (Lyon, 14/10)
-
6 octobre 2019Pi tout rond (Paris, 12/10)
-
30 septembre 2019La science taille XX Elles
Commentaire sur l'article
Du Théorème de Ramsey à la Conjecture d’Erdős-Hajnal (2)
le 3 janvier 2018 à 11:28, par Kamakor
Du Théorème de Ramsey à la Conjecture d’Erdős-Hajnal (2)
le 3 janvier 2018 à 11:43, par Patrice Ossona de Mendez