Nombre de Ramsey

Rappel : qu’est-ce qu’une clique dans un graphe ?

Un graphe est constitué de sommets reliés par des arêtes.
Une clique dans un graphe est un sous-ensemble de sommets où chaque sommet est relié à tous les autres sommets du sous-ensemble. Autrement dit, tous les sommets de la clique sont connectés entre eux.

Exemple : dans un graphe, si les sommets A,B,CA, B, CA,B,C sont connectés entre eux par des arêtes, alors {A,B,C}\{A, B, C\}{A,B,C} forme une clique.

Coloration des arêtes

Imaginons un graphe complet KnK_nKn avec nnn sommets. Cela signifie qu’il y a une arête entre chaque paire de sommets.
On colore chaque arête du graphe avec 2 couleurs (par exemple, rouge et bleu). L’objectif est d’étudier les sous-graphes colorés ainsi.

Nombres de Ramsey : que cherche-t-on ?

Un nombre de Ramsey R(k,l)R(k, l)R(k,l) est le plus petit nombre de sommets nnn nécessaire pour garantir qu’après avoir coloré les arêtes d’un graphe complet KnK_nKn avec deux couleurs :

soit il existe une clique rouge de taille kkk,
soit il existe une clique bleue de taille lll.

En d’autres termes, R(k,l)R(k, l)R(k,l) est le seuil où l’on ne peut pas éviter de créer une grande clique monochrome, peu importe comment on choisit de colorer les arêtes.

Exemple concret : R(3, 3)

Prenons R(3,3)R(3, 3)R(3,3). Cela signifie que nous cherchons le plus petit nnn tel que, dans un graphe complet KnK_nKn, chaque coloration en rouge et bleu contient forcément :

une clique rouge de taille 3, ou
une clique bleue de taille 3.

Pour n=5n = 5n=5, il est possible de colorer les arêtes de K5K_5K5 de façon à éviter une clique monochrome de taille 3. Mais pour n=6n = 6n=6, c’est impossible ! Ainsi, R(3,3)=6R(3, 3) = 6R(3,3)=6.

Encadrement des nombres de Ramsey

Les nombres de Ramsey sont difficiles à calculer. On connaît quelques valeurs précises, mais souvent on ne dispose que d’encadrements.

R(3,3)=6R(3, 3) = 6R(3,3)=6 est une des rares valeurs connues précisément.
R(4,4)R(4, 4)R(4,4) est compris entre 18 et 25 (valeur exacte inconnue).
R(5,5)R(5, 5)R(5,5) est compris entre 43 et 49.

À quoi ça sert ?

Les nombres de Ramsey sont importants en mathématiques, en informatique et en théorie des graphes car ils permettent d’étudier :

La structure inévitable : ils montrent qu’au-delà d’un certain seuil, des configurations « ordonnées » (comme des cliques monochromes) sont garanties.
Applications pratiques : ils interviennent en réseaux (télécommunications, planification), en théorie des jeux et en bioinformatique.

Exemple pour expérimenter

Prenons un graphe K6K_6K6 avec 6 sommets nommés A,B,C,D,E,FA, B, C, D, E, FA,B,C,D,E,F. Colorons les arêtes au hasard en rouge et bleu. Montrez qu’il y aura toujours une clique monochrome de 3 sommets.

Essayez de choisir une coloration. Puis, examinez les sous-ensembles de 3 sommets et vérifiez ! C’est un bon exercice pour visualiser ce concept.

Timothy Gowers (Médaille Fields 1998)

Timothy Gowers a reçu la Médaille Fields en 1998 pour ses travaux en analyse fonctionnelle et en combinatoire additive. Une partie de ses recherches est liée aux idées de la théorie de Ramsey, en particulier dans le cadre de la combinatoire et des structures dans des ensembles infinis.

Endre Szemerédi (Prix Abel 2012, pas Médaille Fields)

Endre Szemerédi, bien que n’ayant pas reçu la Médaille Fields, a été récompensé par le Prix Abel en 2012 pour ses contributions fondamentales à la combinatoire et à la théorie des graphes.
Le théorème de Szemerédi, qui dit que tout ensemble suffisamment grand de nombres entiers contient des progressions arithmétiques de longueur arbitraire, peut être vu comme une extension des idées de la théorie de Ramsey dans un contexte arithmétique.

Paul Erdős

Paul Erdős n’ait pas reçu la Médaille Fields, il a été un pionnier des nombres de Ramsey et de la combinatoire. Il a contribué à poser les bases de la recherche moderne dans ce domaine, notamment avec ses conjectures sur les bornes asymptotiques des nombres de Ramsey.

Analyse des réseaux biologiques

Les réseaux biologiques, comme les réseaux de protéines (PPI : Protein-Protein Interaction Networks) ou les réseaux de gènes (Gene Regulatory Networks), sont souvent modélisés sous forme de graphes où :

Les nœuds représentent des molécules (protéines, gènes, métabolites, etc.).
Les arêtes représentent des interactions biologiques.

Application des concepts de Ramsey :

On peut étudier si un réseau contient des motifs structuraux inévitables comme des sous-graphes spécifiques (cliques ou structures monochromes) qui pourraient correspondre à des modules fonctionnels ou des complexes de protéines.
Par exemple, dans un réseau d’interactions protéiques, une clique de taille kkk peut représenter un complexe protéique où chaque protéine interagit directement avec toutes les autres.

Coloration des interactions

Dans certains contextes, on peut « colorer » les interactions biologiques pour représenter des propriétés différentes, par exemple :

Une interaction rouge pourrait indiquer une interaction activatrice (stimulation entre deux gènes/protéines).
Une interaction bleue pourrait représenter une interaction inhibitrice.

Problème de Ramsey en bioinformatique :

Si on examine un graphe coloré de ce type, les concepts de Ramsey permettent de répondre à des questions comme :
- Existe-t-il une sous-région monochrome ? Cela peut correspondre à un module activé ou inhibé dans son ensemble.
- Quelle est la taille minimale d’un réseau dans lequel ces propriétés sont inévitables ? Cela peut guider les chercheurs à détecter des motifs critiques dans des réseaux complexes.

Analyse des co-expressions géniques

Les profils d’expression génique mesurés dans des expériences comme la RNA-seq produisent de vastes ensembles de données où les gènes co-exprimés peuvent être modélisés comme des graphes.

Les cliques monochromes dans ces graphes indiquent souvent des modules de co-expression, c’est-à-dire des ensembles de gènes qui sont activés ou réprimés ensemble sous certaines conditions biologiques.
Les concepts de Ramsey aident à formaliser ces analyses en garantissant qu’un certain type de régularité (comme une clique monochrome) est inévitable dans des ensembles suffisamment grands.

Modélisation de l’évolution

En biologie évolutive, les concepts de Ramsey peuvent être appliqués pour modéliser des phénomènes liés à l’évolution :

Convergence évolutive : Des motifs similaires apparaissent inévitablement dans différentes branches de l’arbre évolutif (analogie aux structures monochromes dans un graphe coloré).
Résistance aux mutations : On peut utiliser des graphes colorés pour modéliser les relations entre différents génotypes et phénotypes. Une clique monochrome pourrait indiquer un ensemble de génotypes robustes qui produisent des phénotypes similaires.

Pour aller plus loin, conférence de Timothy au collège de France et à l’IHP