Les nombres de Ramsey - Episode 2

Pourquoi les nombres sont-ils beaux ? Cela revient à se demander pourquoi la neuvième symphonie de Beethoven est belle. Si vous ne voyez pas pourquoi, personne ne pourra vous l’expliquer. Je sais que les nombres sont beaux. S’ils ne sont pas beaux, rien ne l’est.
Paul Erdös

Dans l’épisode précédent, nous avions vu ce qu’était un nombre de Ramsey à travers une énigme qui nous a fait calculer $R(3)$ . Essayons à présent de calculer $R(4)$ . Il s’agit de trouver le nombre minimal de sommets pour lequel on est sûr qu’un graphe contienne $4$ sommets tous reliés entre eux ou $4$ sommets isolés.

Interlude Vocabulaire

Introduisons un peu de vocabulaire pour que cela soit plus rapide à dire. Pour $n\in \mathbb{N}$ on appelle graphe complet à $n$ sommets et on note $K_n$ le graphe qui possède $n$ sommets tous reliés entre eux. Dire qu’un graphe contient $4$ sommets tous reliés entre eux signifie donc que le graphe contient un $K_4$ .

Pour $G$ un graphe, on appelle complémentaire de $G$ et on note $G^c$ le graphe avec les mêmes sommets que $G$ mais avec une arête entre deux sommets si et seulement si il n’y a pas d’arête entre ces deux sommets pour $G$ (voir l’image ci-dessous pour bien comprendre).

Dire qu’un graphe contient $4$ sommets isolés revient donc à dire qu’il contient un $K_4^c$ .

Plus généralement, on peut donc définir le nombre de Ramsey $R(k)$ (pour $k$ entier) comme le nombre minimal de sommets pour lequel on est sûr qu’un graphe contienne un $K_k$ ou un $K_k^c$ .

Étape 1 : Comprendre la question

Nous avons déjà compris ce qu’était un nombre de Ramsey grâce à l’épisode précédent. Mais faisons le point sur ce qu’il va falloir faire pour calculer $R(4)$ . Par définition de $R(4)$ , on doit pouvoir trouver un graphe avec $R(4)-1$ sommets tel qu’il n’ait pas de $K_4$ et pas de $K_4^c$ . Plus généralement, si on trouve un graphe avec $m$ sommets vérifiant cette dernière propriété, cela signifie que $R(4)>m$ . Pour minorer $R(4)$ nous allons donc devoir construire un tel graphe.

Pour ce qui est de la majoration, c’est différent. Pour montrer que $R(4)\leq M$ , il faut s’assurer que pour tous les graphes à $M$ sommets, on trouve forcément un $K_4$ ou un $K_4^c$ . Nous avons déjà vu que le nombre de graphe à $M$ sommets devient très vite immense donc c’est inenvisageable de vraiment tous les regarder un par un. Il va falloir faire un raisonnement général comme nous l’avions fait pour $R(3)$ . D’ailleurs, essayons de faire le même non ?

Étape 2 : Utilisation de notre expérience

Il y a un problème par rapport à l’épisode précédent, la valeur de $R(3)$ nous était donnée par l’énoncé. Il suffisait de vérifier que pour tout graphe à $6$ sommets, on trouve un $K_3$ ou un $K_3^c$ . Ici on ne sait pas à l’avance ce que sera la bonne valeur. Il va falloir découvrir cette valeur au cours de notre raisonnement. Fixons donc $M$ entier. On reprend le raisonnement de l’épisode précédent.

Supposons par l’absurde qu’il existe un graphe $G$ à $M$ sommets ne contenant pas de $K_4$ et pas de $K_4^c$ . Regardons l’un de ses sommets $u$ et voyons comment il est relié aux autres sommets.

Si on regarde bien le raisonnement qu’on avait effectué, ce qui nous permettait de trancher c’était soit que le nombre de sommets auxquels $u$ était relié était trop grand ou bien le nombre de sommets auxquels $u$ n’était pas relié était trop grand. Notons donc $V(u)$ l’ensemble des sommets reliés à $u$ et $W(u)$ l’ensemble des sommets non reliés à $u$ .

Que signifie ici $V(u)$ trop grand ? Dans la preuve pour $R(3)$ , cela signifiait simplement qu’on pouvait trouver une arête ou, autrement dit, un $K_2$ . De la même façon ici, cela signifie qu’on peut trouver un $K_3$ dans $V(u)$ . En effet si cela est le cas, alors ce $K_3$ avec le $u$ , auquel ils sont tous reliés par définition, ferait que nous pouvons trouver un $K_4$ ce qui serait absurde.

A partir de quelle taille on est sûr de trouver un $K_3$ ? La première réponse qui vient peut être c’est à partir d’un nombre $R(3)$ de sommets, mais ce n’est pas tout à fait correct. En fait, un nombre $R(3)$ de sommets assure l’existence d’un $K_3$ ou d’un $K_3^c$ , mais si seule l’option $K_3^c$ est cochée, cela ne nous aide pas. Mmm… Si on regarde bien à nouveau le raisonnement de l’épisode précédent, ce qu’on aimerait dans notre cas c’est un nombre de sommets qui assure l’existence d’un $K_3$ ou d’un $K_4^c$ . En effet, par notre hypothèse par l’absurde, on ne pourrait alors pas avoir de $K_4^c$ et on serait forcé d’avoir un $K_3$ . C’est vrai que jusque là on a toujours regardé les nombres de Ramsey avec le même entier $k$ pour $K_k$ et $K_k^c$ mais rien ne nous empêche de casser cette symétrie !

Étape 3 : Généraliser pour simplifier

Pour $k,l$ entiers, on définit le nombre de Ramsey $R(k,l)$ comme le nombre minimal de sommets d’un graphe nécessaire pour être sûr qu’il contienne un $K_k$ ou un $K_l^c$ . Muni de cette définition, si $V(u)$ comporte $R(3,4)$ sommets alors cela signifie, puisque notre hypothèse impose qu’il n’y ait pas de $K_4^c$ , qu’on a forcément un $K_3$ dans $V(u)$ et donc un $K_4$ dans $G$ . C’est absurde ! On doit donc forcément avoir $V(u)\leq R(3,4)-1$ .

Il faudra évidemment pouvoir calculer ce $R(3,4)$ mais continuons pour l’instant notre raisonnement qui a l’air de fonctionner de façon assez générale.

Que signifie $W(u)$ trop grand ? Si vous avez bien suivi, cela arrive quand $W(u)$ comporte $R(4,3)$ sommets. En effet, notre hypothèse impose de ne pas avoir de $K_4$ donc on a forcément un $K_3^c$ dans $W(u)$ . Mais par définition de $W(u)$ , on sait aussi que $u$ est isolé de ce $K_3^c$ et il forme donc avec celui-ci un $K_4^c$ . C’est absurde ! On doit donc forcément avoir $W(u)\leq R(4,3)-1$ .

Finalement on a réussi à majorer le nombre de sommets de notre graphe, notons ce nombre $|G|$ . On a

$|G| \leq R(3,4)-1+R(4,3)-1+1=R(3,4)+R(4,3)-1.$

Dès qu’on dépasse ce nombre de sommets, on est sûr de trouver un $K_4$ ou un $K_4^c$ . Cela signifie donc qu’on a montré que

$R(4,4)\leq R(3,4)+R(4,3)$

En fait, ce raisonnement peut se faire pour le cas général exactement de la même façon. On a la propriété suivante, dont la preuve est laissée au lecteur comme exercice de compréhension :

$\forall k,l\geq 1 \quad R(k+1,l+1)\leq R(k,l+1)+R(k+1,l)$

Étape 4 : Calcul de R(3,4)

Je vous laisse encore un exercice de compréhension (eh ouais au boulot un peu !) : Montrer que $R(k,l)=R(l,k)$ en se servant du graphe complémentaire.

Il nous faut donc seulement calculer $R(3,4)$ .

Majoration de R(3,4)

En se servant du résultat général précédent on a

$R(3,4)\leq R(2,4)+R(3,3).$

On connaît la valeur de $R(3,3)$ grâce à l’épisode précédent, elle est de $6$ .

Pour $R(2,4)$ il s’agit de s’avoir à partir de quel nombre de sommets on est sûr qu’un graphe contienne une arête ou $4$ sommets isolés. On peut avoir un graphe constitué de $3$ sommets isolés qui ne contient donc ni arête ni $4$ sommets isolés mais dès qu’un graphe a $4$ sommets c’est impossible d’éviter cela. Il est donc clair que $R(2,4)=4$ .

Finalement on a donc

$R(3,4) \leq 4+6=10.$

Minoration de R(3,4)

Idéalement on aimerait bien que ce soit la majoration optimale, c’est-à-dire qu’on ait en fait $R(3,4)=10$ . Mais pour s’assurer de cela, il faut construire un graphe à $9$ sommets ne contenant pas de $K_3$ et pas de $K_4^c$ .

Faisons cela étape par étape en commençant par un peu moins de sommets. Disons $6$ sommets étant donné qu’on sait déjà que $R(3,4)\geq 6$ .

Une façon qui me vient de faire un graphe sans triangle c’est de simplement relier les sommets entre eux en cercle.

Pour $6$ sommets, cela fonctionne. Il n’y a pas de triangles et il n’y a pas $4$ sommets isolés. Pour $7$ sommets cela fonctionne aussi.

Par contre en faisant pareil à $8$ sommets, on peut trouver $4$ sommets isolés.

On va donc ajouter des arêtes, sans créer de triangle, pour rompre ces isolements. Si on relie deux sommets séparés de $1$ , cela crée immédiatement un triangle. On peut par contre relier les sommets rouges opposés qui ne sont alors plus isolés, par contre les sommets bleus sont toujours isolés.

On répète donc l’opération avec eux et on obtient le graphe suivant :

On voit que ce graphe n’a pas de triangle et n’a pas non plus $4$ sommets isolés. On a donc $R(4)>8$ .

Plus qu’à traiter le graphe à neuf sommets et c’est gagné. En faisant la même stratégie, on se rend compte que le sommet supplémentaire pose vraiment problème.

Bon on est un peu embêtés… On continue à faire des dessins et à essayer de tracer des arêtes sans créer de triangles et sans avoir quatre sommets isolés mais rien à faire, on n’y arrive pas… Est-ce vraiment possible ? Peut être que finalement la majoration $R(3,4)\leq 10$ de tout à l’heure n’est pas optimale ?

Retour sur la majoration de R(3,4)

Supposons que $R(3,4)=10$ et regardons plus précisément ce que cela implique. Par définition de $R(3,4)$ , il existe alors un graphe $G$ avec $9$ sommets et qui n’a ni $K_3$ ni $K_4^c$ . Prenons comme précédemment un sommet $u$ de $G$ . En reprenant notre raisonnement sur la majoration, on voit qu’on doit alors forcément avoir $|V(u)|=R(2,4)-1=3$ et $|W(u)|=R(3,3)-1=5$ .

Que peut-on tirer de plus que tout à l’heure …? En y réfléchissant, c’est assez fort ce que l’on dit car on a précisément ces égalités pour tout sommet $u$ de notre graphe $G$ . Les $9$ sommets de notre graphe sont tous reliés à exactement $3$ sommets, ces $3$ sommets étant en plus isolés. Qu’est-ce cela nous donne comme information sur notre graphe …? Mmm… Peut-on connaître le nombre d’arêtes de notre graphe par exemple ? Oui on peut ! On vient de dire que chaque sommet est relié à exactement $3$ autres sommets, autrement dit il y a précisément $3$ arêtes reliées à chaque sommet. Il faut faire attention à ne pas les compter $2$ fois car chaque arête est reliée à exactement $2$ sommets.

Puisqu’il y a $9$ sommets, le nombre d’arêtes de notre graphe est donc censé être

$\frac{3\times 9}{2}=13,5$

mais ce n’est pas un nombre entier ça ! C’est absurde ! En vérifiant à nouveau notre décompte d’arêtes, on se convainc bien qu’on aboutit à une contradiction en supposant que $R(3,4)=10$ . Finalement on a donc $R(3,4)\leq 9$ . Et en combinant avec notre minoration, on déduit finalement le résultat

$R(3,4)=9.$

Étape 5 : Calcul de R(4)

Majoration de R(4)

On a toujours la majoration du résultat général précédent :

$R(4)=R(4,4)\leq R(3,4)+R(4,3)=9+9=18$

On espère que cette majoration sera suffisante vu que ce n’était pas si simple à améliorer pour $R(3,4)$ .

Minoration de R(4)

Idéalement, on aimerait réussir à construire un graphe à 17 sommets sans $K_4$ et sans $K_4^c$ . On commence comme avant à faire une structure en cercle.

Essayons de rajouter le plus possible d’arêtes sans créer de $K_4$ . On n’a plus de problème en créant des $K_3$ et on peut donc mettre une arête tous les deux sommets.

On ne peut pas mettre une arête tous les 3 sommets par contre. Par exemple en mettant une arête entre le sommet 1 et le sommet 4, on crée un $K_4$ avec les sommets 1,2,3 et 4. On continue donc en mettant une arête tous les quatre sommets.

On voit qu’il nous reste toujours beaucoup de sommets isolés, il y en a 5 en rouge par exemple. Essayons de casser l’isolement de ces sommets rouge. On ne peut pas tracer une arête entre 1 et 4 sinon ça crée un $K_4$ avec les sommets 1,3,5 et 7. On va donc tracer une arête entre 1 et 10 puis tous les neuf sommets.

On obtient un magnifique graphe et on peut vérifier que celui-ci ne contient pas de $K_4$ et ne contient pas non plus de $K_4^c$ . On a donc $R(4)>17$ et donc finalement $R(4)=18$ !

Conclusion

Eh ben dis donc c’était pas de tout repos mais on y est parvenu ! On sent que ça se complique mais on ne sent pas encore vraiment pourquoi $R(5)$ serait si compliqué à calculer. On n’est plus si loin finalement, il faudrait $R(4,5)$ et puis juste après vient $R(5)$ . On verra dans le prochain épisode que ce n’est hélas pas si simple…

En tout cas j’espère que ce tout premier article piste rouge du blog vous a plu et je vous dis à très bientôt pour la suite =)

Les nombres de Ramsey – Episode 2

Interlude Vocabulaire

Étape 1 : Comprendre la question

Étape 2 : Utilisation de notre expérience

Étape 3 : Généraliser pour simplifier