Du Théorème de Ramsey à la Conjecture d’Erdős-Hajnal (1)

L’ordre inévitable

Piste rouge Le 22 septembre 2017  - Ecrit par  Patrice Ossona de Mendez Voir les commentaires (2)

Ordnung 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 « À partir de quelle taille une structure ne peut-elle éviter de posséder une certaine propriété ? ».

Un premier exemple

Un problème récréatif classique est le problème des amis :

Quand six personnes se rencontrent, on est sûr que trois d’entre elles se connaissent ou que trois d’entre elles ne se connaissent pas.

La démonstration de ce fait est un peu fastidieuse, car il faut considérer différents cas de figure. Néanmoins, cette complication ennuyeuse nous ouvrira la voie vers un point de vue plus général et plus intéressant. Regardons cela de plus près :

Nous avons donc six personnes. Appelons Dominique [1] l’une des personnes du groupe.

Si Dominique connaît au moins trois personnes du groupe, deux cas peuvent se produire :

  • soit deux d’entre elles se connaissent (et avec Dominique, cela fait au moins trois personnes qui se connaissent) ;
  • soit elles ne se connaissent pas entre elles (et cela fait trois personnes qui ne se connaissent pas).

Nous voyons que dans les deux cas nous arrivons à la conclusion souhaitée. Il ne nous reste donc qu’à considérer le cas où Dominique connaît au plus deux personnes du groupe. Là encore, deux cas peuvent se produire pour les personnes que Dominique ne connaît pas :

  • soit deux d’entre elles ne se connaissent pas (et avec Dominique, cela fait trois personnes qui se ne connaissent pas) ;
  • soit elles se connaissent toutes entre elles (et cela fait au moins trois personnes qui se connaissent).

Dans ce cas encore nous arrivons à la conclusion souhaitée.

C’est graphe, docteur ?

Regardons maintenant comment nous pouvons traduire ce résultat dans le langage de la théorie des graphes. Un graphe est une collection de sommets reliés (ou non) entre eux par des arêtes. Chaque arête, ayant deux incidences (c’est-à-dire reliant deux sommets) permet de représenter une relation entre deux entités, les entités étant les sommets. Par exemple, les sommets peuvent être des personnes, et les arêtes peuvent indiquer qui connaît qui. Deux sommets reliés par une arête sont dit adjacents.
Nous utiliserons également les deux éléments de vocabulaire suivants :

  • Un ensemble de sommets est un ensemble stable s’il ne contient pas deux sommets adjacents. Dans notre exemple, un ensemble de personnes qui ne se connaissent pas entre elles est un ensemble stable.
  • Un ensemble de sommets est une clique si tous les sommets de l’ensemble sont deux à deux adjacents (c’est-à-dire si l’ensemble ne contient pas deux sommets non-adjacents). Dans notre exemple, un ensemble de personnes qui se connaissent toutes forme une clique.

Reprenons notre exemple. Nous avons six personnes (donc six sommets) et les arêtes relient les sommets correspondant à des gens qui se connaissent : une arête relie le sommet Dominique et le sommet Claude si Dominique et Claude se connaissent [2].

Dans ce langage, le résultat que nous avons démontré plus haut s’exprime ainsi :

Dans tout graphe à six sommets, il existe trois sommets formant un ensemble stable ou trois sommets formant une clique.

En rouge et bleu, Ramsey et sa clique

Nous aurions pu, également, construire un graphe différemment, en reliant entre elles deux personnes par une arête rouge si elles se connaissent, et par une arête bleue, si elles ne se connaissent pas. Ainsi, deux sommets sont toujours reliés entre eux par une arête, soit rouge, soit bleue.
Notre résultat peut alors s’énoncer ainsi :

Dans toute clique à six sommets dont les arêtes sont coloriées en rouge ou bleu, il existe une clique de trois sommets dont toutes les arêtes sont de la même couleur (toutes rouges ou toutes bleues).

Cette dernière forme est un cas particulier du Théorème de Ramsey.

Théorème de Ramsey Pour tout ensemble fini de couleurs rouge, vert, bleu, violet, ... et toute suite d’entiers nrouge, nvert, nbleu, nviolet, ... il existe un entier $ N $ ayant la propriété suivante :

Pour toute clique à $ N $ sommets dont les arêtes sont coloriées par les couleurs rouge, vert, bleu, violet, ... il existe une clique de taille nrouge dont toutes les arêtes sont rouges, ou une clique de taille nvert dont toutes les arêtes sont vertes, ou une clique de taille nbleu dont toutes les arêtes sont bleues, ou une clique de taille nviolet dont toutes les arêtes sont violettes, etc.

Notre exemple plus haut correspond au fait que $N=6$ a la propriété exprimée par le théorème, dans le cas où $k=2$, pour les couleurs rouge et bleu et pour les valeurs
nrouge=3 et nbleu=3. Par contre, $N=5$ n’a pas cette propriété :
PNG

Ce groupe de cinq personnes est tel que dans tout sous-groupe de trois personnes on peut trouver deux personnes qui se connaissent et deux personnes qui ne se connaissent pas. Dit autrement, dans un cycle de longueur 5 (correspondant aux arêtes rouges), on ne trouve ni clique de taille 3, ni ensemble stable de taille 3.

Plus grand, plus coloré

Regardons un exemple un peu plus gros et voyons comment, dans une clique de taille 17 dont les arêtes sont coloriées en rouge, vert et bleu, nous pouvons trouver un triangle monochromatique, c’est-à-dire un triangle dont toutes les arêtes sont de la même couleur. Voici la clique :

PNG

Choisissons arbitrairement un sommet $v_1$. Considérons la couleur majoritaire sur les arêtes incidentes à ce sommet (ici la couleur rouge présente sur 6 arêtes), et concentrons-nous sur la clique dont les sommets sont $v_1$ et ses voisins reliés par des arêtes rouges :

PNGPNG

Si deux voisins sélectionnés de $v_1$ étaient liés par une arête rouge, nous aurions trouvé un triangle monochromatique (rouge). Ici, ce n’est pas le cas.

Nous choisissons alors, arbitrairement, l’un des voisins sélectionnés de $v_1$, et nous l’appelons $v_2$. À ce sommet, nous considérons à nouveau la couleur majoritaire (ici le bleu, présent sur trois arêtes), et nous sélectionnons maintenant les sommets qui sont non seulement adjacents à $v_1$ par une arête de couleur rouge, mais aussi adjacents à $v_2$ par une arête de couleur bleue.

PNG

Si deux voisins sélectionnés étaient liés par une arête de couleur bleue, nous aurions trouvé un triangle monochromatique (bleu). Comme ce n’est pas le cas, cela signifie que les trois voisins de $v_2$ sont tous reliés par des arêtes vertes, donc nous avons finalement trouvé un triangle monochromatique (vert). Pour trouver ce triangle, il fallait que $v_2$ ait trois voisins dans la couleur majoritaire, donc au moins 5 voisins (après sélection des voisins de $v_1$). Il fallait donc que $v_1$ ait au moins 6 voisins dans la couleur majoritaire, donc soit de degré au moins 16, c’est-à-dire que la clique de départ soit de taille au moins 17.

Par contre, les arêtes d’une clique de taille 16 peuvent être coloriées en rouge, vert, bleu, sans qu’un triangle monochromatique ne soit créé :

PNG

Deux couleurs, c’est déjà pas simple

Revenons au problème à deux couleurs :

Pour un entier $t$, quel est le plus petit entier $n$ tel que dans toute clique de taille $n$ dont les arêtes sont coloriées en rouge et bleu on est sûr de trouver une clique monochromatique de taille $t$ ?

Par exemple, nous avons montré que toute clique de taille 6 dont les arêtes sont coloriées en deux couleurs contient un triangle monochromatique. En d’autres termes, pour $t=3$ il est suffisant de choisir $n\geq 6$.

Dans le cas général, nous pouvons appliquer la même méthode de démonstration que celle que nous avons suivie plus haut.

Considérons une clique de taille $n$ dont les arêtes sont coloriées bleu et rouge. Soit $v_1$ un sommet quelconque et soit $c_1$ la couleur majoritaire des arêtes incidentes à $v_1$. Sélectionnons les voisins de $v_1$ liés à $v_1$ par une arête de couleur $c_1$ et parmi ces sommets choisissons arbitrairement $v_2$. Soit $c_2$ la couleur majoritaire des arêtes incidentes à $v_2$ liant $v_2$ à des sommets liés à $v_1$ par une arête de couleur $v_1$. Sélectionnons les sommets à la fois liés à $v_1$ par une arête de couleur $c_1$ et liés à $v_2$ par une arête de couleur $c_2$. Parmi ces sommets nous choisissons arbitrairement $v_3$, etc.

Dans ce processus, nous sélectionnons une suite $v_1,v_2,v_3,\dots, v_k$ de sommets, jusqu’à ce que $v_k$ n’ait plus de voisin. De plus nous colorions le sommet $v_i$ avec la couleur $c_i$.

En comptant à rebours, nous voyons que $v_{k-1}$ a au moins 1 voisin ($v_k$), $v_{k-2}$ a au moins 3 voisins, $v_{k-3}$ a au moins 7 voisins, etc.

Une autre manière de compter, est que la clique formée par $v_{k-1}$ et l’ensemble des sommets liés à $v_1$ par une arête de couleur $c_1$, à $v_2$ par une arête de couleur $c_2$,..., à $v_{k-1}$ par une arête de couleur $c_{k-1}$ est de taille $2$ (elle ne contient que $v_{k-1}$ et $v_k$) ; la clique formée par $v_{k-2}$ et l’ensemble des sommets liés à $v_1$ par une arête de couleur $c_1$, à $v_2$ par une arête de couleur $c_2$,..., à $v_{k-2}$ par une arête de couleur $c_{k-2}$ est deux fois plus grande, de taille 4, et ainsi de suite. Pour être sûrs de trouver une clique monochromatique de taille $t$, il suffit que $k$ soit au moins égal à $2t-1$, car les sommets parmi $v_1,\dots,v_{2t-1}$ de la couleur majoritaire (qui apparaît au moins $t$ fois) forment alors une clique monochromatique. Il suffit donc que la taille $n$ de la clique initiale dont les arêtes sont coloriées en bleu et rouge soit au moins

\[ n\geq \overbrace{2\times 2\times\dots\times 2}^{2t-1}=2^{2t-1}. \]

Il est assez étonnant que ce résultat soit, à peu de chose près, optimal. En effet, si on colorie au hasard [3] les arêtes d’une clique de taille $2^t$ en rouge et bleu, il y a de très fortes chances [4] pour que la taille de la plus grande clique monochromatique soit du même ordre de grandeur que $t$ [5].

En résumé, le théorème de Ramsey exprime qu’une certaine dose d’ordre est inévitable, et les structures où cet ordre est « minimal » sont, assez intuitivement [6], les structures aléatoires.

Au lieu d’examiner une coloration des arêtes d’une clique en deux couleurs, on peut étudier un graphe arbitraire $G$ sur un ensemble de $n$ sommets. En effet, considérant que les arêtes présentes dans $G$ sont bleues et que les arêtes non présentes dans $G$ sont rouges, le théorème de Ramsey peut s’interpréter sous la forme suivante :

Théorème Soit $t$ un entier naturel, et soit $n$ un entier naturel excédant $2^{2t-1}$.

Soit $G$ un graphe à $n$ sommets. Alors $G$ contient nécessairement une clique de taille $t$ ou un ensemble stable de taille $t$ (ou les deux).

Nous voyons que le nombre $n$ augmente très rapidement avec $t$. Par exemple, pour être sûr de trouver une clique ou un ensemble stable de taille $t=100$, nous avons besoin de considérer un graphe de taille

\[ n\geq 2^{199}=803469022129495137770981046170581301261101496891396417650688! \]

Une question se pose alors naturellement : à quelle condition pouvons-nous réduire ce nombre astronomique ?

La conjecture d’Erdős-Hajnal

Nous avons vu que si le nombre $n$ des sommets d’un graphe est suffisamment grand, alors le graphe contient une grande clique ou un grand ensemble stable.

Que se passe-t-il si l’une des possibilités est « fortement » interdite ? Par exemple, que se passe-t-il si nous considérons un graphe qui ne contient aucun triangle, c’est-à-dire aucune clique de taille 3 ? Est-ce que le nombre $n$ de sommets de $G$ a toujours besoin d’augmenter aussi rapidement que $2^{2t-1}$ pour assurer l’existence d’un ensemble stable de taille $t$ ? Nous allons voir qu’en fait, au lieu de $n\geq 2^{2t-1}$, il suffit d’avoir $n\geq t ^2$ (i.e. $n\geq t\times t$). Par exemple, pour $t=100$, la taille nécessaire est réduite à $n\geq 10000$.

Pourquoi est-ce le cas ?

Considérons un graphe $G$ sans triangles, ayant $n\geq t^2$ sommets.

  • Supposons que le graphe $G$ contient un sommet $v$ ayant au moins $t$ voisins.
    Alors, l’ensemble des voisins de $v$ forme un ensemble stable de taille $t$ : il ne peut en effet exister d’arête joignant deux voisins de $v$, car sinon ces deux sommets et $v$ formeraient un triangle.
  • Sinon, tous les sommets de $G$ ont au plus $t-1$ voisins.
    Nous allons les colorier en utilisant les couleurs entre 1 et $t$ comme suit : nous prenons les sommets un par un. Chaque sommet reçoit la plus petite couleur qui n’est pas déjà utilisée par un de ses voisins. Comme chaque sommet a au plus $t-1$ voisins, il existe toujours une couleur disponible. À la fin, nous avons colorié les sommets du graphe et, par construction, deux sommets voisins n’ont jamais la même couleur.
    Choisissons maintenant la couleur la plus utilisée. Comme le graphe contient $n$ sommets, au moins $n/t$ sommets ont la couleur majoritaire. Ces sommets forment un ensemble stable. En effet, deux sommets de même couleur ne sont jamais voisins. Comme $n\geq t^2$, cet ensemble est de taille au moins $t$.

Nous avons donc démontré la proposition suivante :

Proposition Si un graphe sans triangles possède au moins $t^2$ sommets, alors il contient un ensemble stable de taille $t$.

Nous avons vu que lorsque nous interdisons la présence d’un triangle (c’est-à-dire une clique de taille $3$), nous pouvons trouver un grand ensemble stable.
Que se passe-t-il si on interdit une plus grande clique ? A priori, nous nous attendons à ce que la taille du graphe nécessaire à la présence d’un ensemble stable de taille $t$ grandisse progressivement de $t^2$ à $2^{2t-1}$.

Nous allons voir que la taille du graphe nécessaire à la présence d’un ensemble stable de taille $t$ grandit comme $\overbrace{t\times t\times\dots\times t}^{k-1}=t^{k-1}$ :

Proposition Si un graphe sans clique de taille $k\geq 3$ possède au moins $t^{k-1}$ sommets, alors il contient un ensemble stable de taille $t$.
Esquisse de démonstration par induction sur $k$ : Nous avons déjà démontré que si nous interdisons tout triangle (c’est-à-dire toute clique de taille $3$) tout graphe à $t^2$ sommets contient un ensemble stable de taille $t$.

Voyons comment nous pouvons passer de la démonstration pour $k=3$ à $k=4$ : Considérons donc un graphe sans cliques de taille $4$ ayant $n\geq t^3$ sommets.

  • Supposons que le graphe $G$ contient un sommet $v$ ayant au moins $t^2$ voisins.
    Alors, le graphe formé par les voisins de $G$ ne contient aucun triangle, car tout triangle dans le voisinage de $v$ formerait, avec $v$, une clique de taille $4$. De plus le graphe formé par les voisins de $v$ contient au moins $t^2$ sommets (puisque $v$ a au moins $t^2$ voisins). Par le résultat précédent, nous pouvons conclure que le voisinage de $v$ contient un ensemble stable de taille $t$.
  • Sinon , tous les sommets de $G$ ont au plus $t^2-1$ voisins.
    Dans ce cas, ainsi que nous l’avons vu plus haut, les sommets de $G$ peuvent être coloriés en utilisant $t^2$ couleurs sans que des voisins reçoivent la même couleur.
    La couleur majoritaire forme alors un ensemble stable de taille $n/t^2$. Le graphe $G$ contient donc un ensemble stable de taille au moins $t$, puisque $n\geq t^3$.

Le même procédé permet de déduire, à partir du résultat pour les graphes sans clique de taille $4$, que tout graphe avec au moins $t^4$ sommets et sans cliques de taille $5$ contient un ensemble stable de taille $t$ et, de proche en proche, que tout graphe avec au moins $t^{k-1}$ sommets et sans cliques de taille $k$ contient un ensemble stable de taille $t$.
 

Ces résultats montrent que le fait d’interdire une clique de taille fixée permet d’assurer que le nombre de sommets nécessaire pour assurer la présence d’un ensemble stable de taille $t$ est borné par une puissance de $t$ dont l’exposant dépend de la clique interdite.

En considérant le graphe complémentaire (obtenu en échangeant arêtes et non-arêtes) nous obtenons de même que le nombre de sommets nécessaire pour assurer la présence d’une clique de taille $t$ dans un graphe sans ensemble stable de taille $k$ est au plus $t^{k-1}$, donc bornée par une puissance de $t$ dont l’exposant ne dépend que de la taille de l’ensemble stable interdit.

Il est naturel de se demander si un tel phénomène peut être généralisé. C’est le sens de la conjecture qu’Erdős et Hajnal ont posée en 1989. Avant d’énoncer cette conjecture, prenons le temps pour quelques définitions.

Soient $G$ et $H$ deux graphes. Soient $a_1,\dots,a_h$ les sommets de $H$. Une copie de $H$ dans $G$ est un ensemble $v_1,\dots,v_h$ de sommets distincts de $G$ tels que $v_i$ est voisin de $v_j$ dans $G$ si, et seulement si, $a_i$ est voisin de $a_j$ dans $H$ :

En particulier, si $H$ est un graphe avec $t$ sommets et aucune arête, alors une copie de $H$ dans $G$ est un ensemble stable de $G$ de taille $t$. De même, si $H$ est un graphe avec $t$ sommets et toutes les arêtes entre ces sommets (i.e. un graphe complet de taille $t$), alors une copie de $H$ dans $G$ est une clique de $G$ de taille $t$.

La conjecture, proposée par Paul Erdős et András Hajnal, est la suivante :

Conjecture d’Erdős-Hajnal Pour tout graphe $F$, il existe un entier $c(F)$ avec la propriété suivante :

Tout graphe $G$ suffisamment grand [7] qui ne contient pas de copies de $F$ et qui a plus de $t^{c(F)}$ sommets (avec $t$ entier) contient un ensemble stable ou une clique de taille $t$.

Nous pouvons reformuler la conjecture d’Erdős-Hajnal de manière duale, mettant en évidence la raison pour laquelle nous pouvons affirmer que cette conjecture concerne une notion d’« ordre inévitable » :

Conjecture d’Erdős-Hajnal (deuxième formulation) Pour tout entier $h$, il existe un entier $K(h)$ avec la propriété suivante :

Si un graphe $G$ ne contient ni ensemble stable ni clique de taille $t$ et qu’il possède au moins $t^{K(h)}$ sommets, alors $G$ contient une copie de chacun des graphes à $h$ sommets.

Dans une seconde partie, nous examinerons quelques cas particuliers où l’on peut démontrer la validité de la conjecture, et ferons le point sur tout le chemin qui reste à parcourir pour la démontrer dans toute sa généralité.

Post-scriptum :

Cet article est né d’une conversation, à Prague, autour d’un verre de vin, avec Shalom Eliahou. Je lui suis reconnaissant pour son impulsion, ses suggestions éclairées et ses commentaires précieux lors du premier jet de cet article. Je tiens à remercier Marielle Simon et Pierre Lescanne pour leurs commentaires bienveillants, leurs conseils avisés et leur relecture attentive. Enfin, je tiens à exprimer ma gratitude à Carole Gaboriau et Maï Sauvageot, indispensables secrétaires de rédaction, pour leur aide constante.

Article édité par Shalom Eliahou

Notes

[1Notez que c’est un épicène, le genre n’ayant aucun intérêt ici.

[2Remarquez que nous considérons ici des relations symétriques, ce qui n’aurait pas été le cas si nous avions considéré la propriété « Dominique connaît Claude » qui n’implique pas forcément que, symétriquement, Claude connaisse Dominique.

[3Indépendamment, avec une probabilité 1/2 pour chaque couleur.

[4Précisément, avec une probabilité qui tend vers $1$ lorsque $t$ tends vers l’infini, c’est-à-dire « asymptotiquement presque sûrement ».

[5Ce résultat peut être dérivé de l’inégalité de Markov. Matula a démontré dans les années 70 que les valeurs probables de la taille de la plus grande clique se concentrent essentiellement sur deux valeurs proches de $2t$. Par exemple, si $t=10$ (c’est-à-dire si on considère une clique de taille $2^{10}=1024$) il y a environ $80\%$ de chances pour que la plus grande clique monochromatique soit de taille $15$ exactement.

[6Dans le sens où « au hasard » et « sans ordre » sont deux notions souvent considérées, pragmatiquement, comme équivalentes.

[7« Suffisamment grand » signifie « plus grand qu’une certaine taille $N(F)$ ne dépendant que de $F$ ».

Partager cet article

Pour citer cet article :

Patrice Ossona de Mendez — «Du Théorème de Ramsey à la Conjecture d’Erdős-Hajnal (1)» — Images des Mathématiques, CNRS, 2017

Crédits image :

Image à la une - Le logo a été obtenu à partir d’une photographie issue des archives J. M. Keynes Papers (JMK B/4, p. 283) du King’s College, Cambridge.
Le photographe et copyright de la photographie d’origine sont inconnus, cf Alexander Soifer, The Mathematical Colouring Book, Springer, 2008, 283.

Commentaire sur l'article

Voir tous les messages - Retourner à l'article

  • Du Théorème de Ramsey à la Conjecture d’Erdős-Hajnal (1)

    le 23 septembre à 21:51, par Carole Gaboriau

    Coquilles corrigées ! Merci de votre lecture attentive.

    Carole Gaboriau
    Secrétaire de rédaction

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM