Le Théorème De Ramsey

Le nombre de Ramsey {$R(m,n)$}

La théorie de Ramsey s'attache à établir certaines régularités dans des coloriages à grandes échelles. Dans cet exposé, on s'intéresse à des coloriages des arêtes d'un graphe. Le graphe complet {$K_n$} est le graphe consitué de {$n$} sommets {$\{1,2,\ldots,n\}$} qui sont tous reliés entre eux. {$K_n$} contient {$\frac{n\ (n-1)}{2}$} arêtes.

Le nombre de Ramsey {$R(m,n)$} est le plus petit entier {$r$} tel que pour tout coloriage des arêtes de {$K_r$} en rouge et bleu, on puisse trouve soit un {$K_m$} rouge, soit un {$K_n$} bleu.

Une définition équivalente du nombre {$R(m,n)$} est le plus petit entier {$r$} tel que tout graphe à {$r$} sommets possède soit une clique à {$m$} sommets soit {$n$} sommets indépendants (il suffit de considérer les arêtes rouges d'un graphe complet comme un graphe).

Le théorème de Ramsey

Le théorème de Ramsey est l'inégalité {$R(m,n) \leq R(m-1,n) + R(m,n-1)$} qui montre en particulier que ces nombres sont bien définis. Les premiers termes sont plutôt facile à calculer, cependant la plupart d'entre eux restent encore inconnus! Le plus petit de ces nombres et qui restent inconnus à l'heure actuelle est {$R(5,5)$}. Les autres sont donnés dans le tableau suivant

Les nombres de ce tableaux sont relativement simples à calculer, mis à part {$R(4,5) = 25$} qui fait l'objet de l'article B. D. McKay et S. P. Radziszowski, R(4,5)=25. Ce calcul a nécessité de nombreux calculs sur ordinateurs.

Petit point biographique

Frank Plumpton Ramsey (22 Février 1903 – 19 Janvier 1930) était un mathématicient anglais. En plus des mathématiques, il fit des contributions en philosophie et économie avant de mourrir à l'age de 26 ans.

Bibliographie

• wikipédia