Méthode probabiliste

Supposons que nous ayons un graphe complet sur n sommets et que nous voulions démontrer (pour les valeurs assez petites de n) qu'il est possible de colorer les arêtes du graphe en deux couleurs (par exemple rouge et bleu), de sorte qu'il n'y ait pas de sous-graphe complet sur r sommets qui soit monochromatique (toutes les arêtes de même couleur).

Pour ce faire, colorions le graphe de façon aléatoire, c'est-à-dire colorions chaque arête de façon indépendante, avec probabilité ½ d'être rouge et ½ d'être bleu. Calculons le nombre de sous-graphes monochromatiques sur r sommets comme suit :

• Pour tout ensemble S de r sommets de notre graphe, affectons à la variable X(S) la valeur 1 si toutes les arêtes entre les r sommets sont de la même couleur et la valeur 0 autrement. Notons que le nombre de r-sous-graphes monochromatiques est la somme des X(S) quand S parcourt tous les sous-ensembles. Pour tout S, l'espérance de X(S) est la probabilité que toutes les ${\displaystyle {r \choose 2}}$ arêtes de S soient de même couleur,

${\displaystyle 2\cdot 2^{-{r \choose 2}}}$

(le facteur 2 provient de ce qu'il y a deux couleurs possibles), et ce, pour chacun des C(n, r) sous-ensembles que l'on peut choisir, si bien que la somme des E[X(S)] sur tous S est

${\displaystyle {n \choose r}2^{1-{r \choose 2}}.}$

La somme de l'espérance est l'espérance de la somme (même si les variables ne sont pas indépendantes), de sorte que l'espérance de la somme (le nombre moyen de r-sous-graphes monochromatiques) est

${\displaystyle {n \choose r}2^{1-{r \choose 2}}.}$

Pensez à ce qui se passe si cette valeur est inférieure à 1. Le nombre de r-sous-graphes monochromatiques dans notre coloration aléatoire sera toujours un entier, donc il doit être inférieur à l'espérance, pour au moins un des colorations. Mais le seul entier qui satisfait à ce critère est de 0. Ainsi, si

${\displaystyle C(n,r)<2^{{r \choose 2}-1}}$,

alors l'une des colorations répond au critère désiré, donc par définition, R(r, r; 2) doit être supérieur à n. En particulier, R(r, r; 2) doit augmenter au moins exponentiellement avec r.

Une particularité de cet argument est qu'il est entièrement non constructif. Même s'il démontre (par exemple) que presque toutes les colorations du graphe complet sur (1.1)^r sommets ne contiennent pas de r-sous-graphe monochromatique, il ne donne pas d'exemple explicite d'une telle coloration. Le problème de trouver une telle coloration est ouvert depuis plus de 50 ans.

Un article d'Erdős de 1959[3] a abordé le problème suivant de théorie des graphes : étant donnés deux entiers g et k, existe-t-il un graphe G ne contenant que des cycles de longueur au plus g, tel que le nombre chromatique de G soit au moins k ?

On peut démontrer que ce type de graphe existe pour tous g et k, et la démonstration est relativement simple. Soit n très grand et envisageons un graphe aléatoire G sur n sommets, où chaque arête dans G existe avec une probabilité n^(1-g)/g. On peut démontrer que, avec probabilité positive, les deux assertions suivantes sont vraies :

• G ne contient aucun stable de taille ${\displaystyle \lceil n/2k\rceil }$
• G contient au plus n/2 cycles de longueur au plus g.

Voici ensuite l'astuce : puisque G a ces deux propriétés, on peut supprimer au plus n/2 sommets de G pour obtenir un nouveau graphe G' sur n' sommets qui ne contient pas de cycles de longueur au plus g. On voit que ce nouveau graphe n'a pas un stable de taille ${\displaystyle \lceil n'/k\rceil }$, donc le nombre chromatique de G' vaut au moins k.

Ce résultat donne une indication sur les raisons pour lesquelles le calcul du nombre chromatique d'un graphe est si difficile : même quand un graphe n'a pas de raisons locales (telles que des petits cycles) pour nécessiter beaucoup de couleurs, son nombre chromatique peut être arbitrairement grand.

Preuves probabilistes de théorèmes non probabilistes (en)