$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Théorème de Ramsey

Un exemple introductif

Avez-vous déjà remarqué le phénomène suivant : si l’on prend six personnes au hasard, alors ou bien (au moins) trois d’entre elles se connaissent toutes l’une l’autre,ou bien on peut en trouver trois parmi elles telles qu’aucune des trois n’en connaisse une autre (des trois). En effet, désignons par $P_1$ la première personne du groupe et distinguons deux cas :

  • $P_1$ connait au moins trois autres personnes du groupe et désignons par $P_2$, $P_3$ et $P_4$ ces personnes. Si deux d'entre elles se connaissent, mettons $P_2$ et $P_3$, alors $P_1$, $P_2$ et $P_3$ se connaissent toutes trois. Sinon $P_2$, $P_3$ et $P_4$ ne se connaissent pas du tout.
  • $P_1$ connait au plus deux autres personnes du groupe. Désignons par $P_2$, $P_3$ et $P_4$ trois personnes du groupe que $P_1$ ne connait pas. Si deux d'entre elles ne se connaissent pas, mettons $P_2$ et $P_3$, alors $P_1$, $P_2$ et $P_3$ ne se connaissent pas du tout. Sinon, $P_2$, $P_3$ et $P_4$ se connaissent toutes trois.

Pour rendre abstraite cette constatation, une bonne formulation du problème utilise la théorie des graphes. Le graphe associé est constitué des 6 personnes, que l'on relie chacune par des arêtes (c'est donc le graphe complet à 6 sommets). On colorie chaque arête d'une couleur si les deux personnes/sommets se connaissent, et d'une autre couleur si elles ne se connaissent pas. Alors, on vient de prouver qu'un tel graphe possède un sous-graphe complet à 3 sommets dont toutes les arêtes ont la même couleur. C'est une version du théorème de Ramsey, pour les colorations de graphes utilisant deux couleurs.

Énoncé du théorème
Théorème : Soit $r$ et $s$ deux entiers. Alors il existe un entier $N$ tel que, pour tout $n\geq N$, pour tout coloration des arêtes du graphe complet à $n$ sommets avec $s$ couleurs, il existe un sous-graphe complet à $r$ sommets dont toutes les arêtes ont la même couleur.