ArithmétiqueNotion · Glossaire
nombre de Ramsey
Pour des entiers n et k au moins égaux à 1, le nombre de Ramsey R(n, k) est le plus petit entier N tel que tout graphe simple à N sommets contient soit une clique de n sommets, soit un ensemble indépendant de k sommets. Autrement dit, dans tout groupe assez grand où se connaître est une relation réciproque, on garantit soit n personnes se connaissant toutes, soit k personnes qui ne se connaissent pas deux à deux.
Sommaire
Ce que vous allez apprendre
- Traduire la définition entre groupes de personnes et graphes simples.
- Distinguer clique, ensemble indépendant et nombre de Ramsey.
- Refaire les deux bornes qui prouvent R(3,3)=6.
- Reconnaître les hypothèses du modèle et les cas où seules des bornes sont connues.
En clair
Réunissez six personnes et regardez chaque paire : soit les deux personnes se connaissent, soit elles ne se connaissent pas. Quelles que soient les relations du groupe, on trouvera toujours trois personnes qui se connaissent toutes, ou trois personnes qui sont deux à deux inconnues.
Le nombre de Ramsey cherche le plus petit effectif qui rend inévitable une telle configuration. Il ne prédit pas laquelle apparaîtra ni où la trouver ; il affirme qu'à partir d'un certain seuil, l'une des deux possibilités ne peut plus être évitée.
Définition
On représente une relation binaire symétrique par un graphe simple non orienté : chaque sommet représente une personne, et une arête relie deux sommets lorsque les deux personnes se connaissent. Une clique de taille n est un groupe de n sommets tous reliés deux à deux. Un ensemble indépendant de taille k est un groupe de k sommets sans aucune arête entre eux.
Pour deux entiers n et k au moins égaux à 1, le nombre de Ramsey R(n, k) est le plus petit entier N tel que tout graphe simple ayant N sommets contient une clique de taille n ou un ensemble indépendant de taille k. Il suffit de considérer exactement N sommets : si la propriété est vraie à N, elle reste vraie au-delà en choisissant N sommets.
Échanger arêtes et non-arêtes transforme les cliques en ensembles indépendants. Cette complémentarité donne la symétrie . La valeur R(3, 3) = 6 signifie donc que six sommets suffisent toujours, tandis qu'un graphe à cinq sommets peut encore éviter simultanément une clique et un ensemble indépendant de taille 3.
Un exemple, pas à pas
Prenons six personnes. Les données sont les 6 sommets du graphe et, pour chacune des 15 paires, l'une des deux situations : connaissance ou non-connaissance. Nous allons établir que R(3, 3) = 6.
1. Choisissons une personne A. Parmi ses cinq relations, au moins trois sont du même type : A connaît au moins trois personnes, ou A ne connaît pas au moins trois personnes.
2. Supposons que A connaisse B, C et D. Si une paire parmi B, C et D se connaît, cette paire forme avec A trois connaissances mutuelles. Sinon, B, C et D sont trois inconnus deux à deux. Le raisonnement symétrique traite le cas où A ne connaît pas B, C et D. Six personnes suffisent donc.
3. Pour vérifier que cinq ne suffisent pas, plaçons cinq sommets en pentagone. Les côtés représentent les connaissances et les diagonales les non-connaissances. Chaque couleur forme un cycle de longueur 5, sans triangle monochrome : aucun trio n'est entièrement fait de connaissances ou de non-connaissances.
Le contrôle combine les deux sens : l'étape 2 garantit la propriété pour tout groupe de six, et l'étape 3 fournit un contre-exemple à cinq. On obtient donc exactement .
En pratique
Pour traduire un problème de relations, on crée un sommet par objet et l'on décide précisément ce que signifie une arête. Si la relation n'est pas symétrique, le modèle de graphe simple utilisé par R(n, k) ne convient pas directement ; un graphe orienté est alors plus fidèle.
Pour établir une valeur exacte, on cherche deux résultats complémentaires. Une preuve que tout graphe d'une certaine taille contient la configuration voulue donne une borne supérieure ; un graphe plus petit qui l'évite donne une borne inférieure. Quand les deux bornes coïncident, la valeur est déterminée.
Pour de petites tailles, on peut examiner des graphes ou des colorations d'arêtes. Dès que le nombre de sommets augmente, l'énumération naïve devient vite impraticable ; on préfère alors des arguments combinatoires, des constructions de contre-exemples ou des recherches informatiques contrôlées.
À ne pas confondre
Le nombre de Ramsey n'est pas le théorème de Ramsey dans toute sa généralité. Le premier est un seuil minimal fini associé ici à deux tailles ; le second désigne une famille de résultats d'inévitabilité dans des structures colorées. La question « quel est le plus petit N ? » appelle un nombre de Ramsey.
Une clique et un ensemble indépendant ne sont pas deux noms pour le même sous-graphe. Dans une clique, chaque paire porte une arête ; dans un ensemble indépendant, aucune paire n'en porte. Un trio ayant exactement une ou deux arêtes n'est ni l'un ni l'autre.
Le nombre de Ramsey ne compte pas le nombre de cliques présentes. Il fixe un effectif qui garantit l'existence d'au moins une clique de taille n ou d'au moins un ensemble indépendant de taille k, sans indiquer combien de telles configurations existent.
Limites et pièges
Le seuil est une garantie universelle, pas une description de tous les graphes plus petits. À cinq sommets, certains graphes possèdent déjà un triangle ; le pentagone de l'exemple montre seulement que ce n'est pas inévitable. Il faut donc produire un contre-exemple pour réfuter une garantie, et non un graphe qui satisfait déjà la conclusion.
Le modèle suppose un graphe simple non orienté : pas de boucle, pas d'arêtes multiples, et une relation symétrique. Si « A connaît B » n'implique pas « B connaît A », le symptôme est une relation à sens unique ; il faut reformuler la relation ou employer une notion adaptée aux graphes orientés.
Les cas avec un paramètre égal à 1 sont dégénérés mais bien définis : . Dès qu'un sommet est présent, une clique ou un ensemble indépendant de taille 1 existe. Il ne faut pas extrapoler à ces cas les raisonnements conçus pour n et k au moins égaux à 2.
L'existence de R(n, k) ne fournit pas automatiquement sa valeur exacte. Pour des paramètres plus grands, une preuve peut seulement encadrer le nombre entre une construction qui évite les configurations et une garantie universelle. Il faut alors annoncer des bornes, pas une égalité.
Pour aller plus loin
L'article L’ordre selon Ramsey replace ce phénomène d'inévitabilité dans un récit plus large.
Le glossaire Graphe complet précise la structure dont une clique est un exemplaire à l'intérieur d'un graphe.
L'entrée clique - graphe - approfondit directement la configuration complète recherchée par le nombre de Ramsey.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres