Ramsey Franck

En 1924, à Cambridge, Frank Ramsey obtient un poste au King's College à seulement 21 ans. Sa carrière s'achève avec sa mort en 1930, mais elle laisse des travaux en logique, en mathématiques et en économie.

Son nom reste notamment attaché à une idée frappante : dans un ensemble assez grand, le désordre ne peut pas être total. Certaines relations finissent forcément par former une configuration régulière. La taille nécessaire dépend toutefois de la configuration recherchée.

Frank Plumpton Ramsey est un mathématicien et logicien britannique né en 1903 et mort en 1930. Formé au Winchester College puis au Trinity College de Cambridge, il obtient en 1924, à 21 ans, un poste au King's College de Cambridge. Il travaille en logique, en mathématiques et en économie. Sa maîtrise de l'allemand, acquise en une semaine selon la légende rapportée par la source, lui permet de lire le Tractatus logico-philosophicus de Ludwig Wittgenstein. Il se rend ensuite en Autriche pour discuter de l'ouvrage avec son auteur.

La théorie qui porte son nom appartient à la combinatoire et à la théorie des graphes. Elle recherche des seuils à partir desquels une configuration donnée devient inévitable, quelle que soit la manière dont on répartit un nombre fini de relations. Dans le cas classique de deux couleurs, pour des entiers positifs r et s, le nombre de Ramsey noté $R(r,s)R(r,s)$ est le plus petit entier positif n tel que toute coloration en rouge et noir des arêtes du graphe complet $K_{n}K\_n$ contienne soit un sous-graphe complet à r sommets dont toutes les arêtes sont rouges, soit un sous-graphe complet à s sommets dont toutes les arêtes sont noires. Cette formulation précise un type de configuration ; elle ne réduit pas toute la théorie de Ramsey à ce seul cas.

Considérons six sommets reliés deux à deux. Chaque arête est rouge ou noire. Les données sont donc six sommets, quinze arêtes et deux couleurs. On cherche un triangle dont les trois arêtes ont la même couleur.

1. Choisissons un sommet A. Cinq arêtes partent de A.
2. Parmi ces cinq arêtes, au moins trois ont la même couleur. Supposons que AB, AC et AD soient rouges.
3. Si l'une des arêtes BC, BD ou CD est rouge, elle forme avec A un triangle rouge.
4. Si aucune n'est rouge, BC, BD et CD sont toutes noires : BCD est alors un triangle noir.

Dans tous les cas, un triangle monochrome existe. Le contrôle consiste à examiner les deux branches : une arête rouge parmi BC, BD et CD suffit ; sinon leurs trois couleurs noires donnent immédiatement l'autre triangle. La figure présente une coloration particulière, tandis que le raisonnement couvre toutes les colorations possibles.

Dans un réseau fini, on traduit des relations de deux types par deux couleurs d'arêtes. La théorie de Ramsey est pertinente lorsque la question porte sur l'existence forcée d'un motif, indépendamment de la répartition observée. Pour localiser tous les motifs dans un graphe déjà connu, une recherche exhaustive répond à une autre question.

Pour établir un seuil, on combine deux gestes. Une démonstration montre qu'au-delà d'une taille, le motif est inévitable ; une construction sans ce motif montre que le seuil ne peut pas être abaissé. Si seule une borne suffit, il n'est pas nécessaire de déterminer le seuil exact.

Face à un énoncé informel sur l'ordre caché dans le désordre, il faut préciser les objets, les relations, le nombre de couleurs et la configuration attendue. Sans ces données, l'intuition ramseyenne ne constitue pas encore un résultat applicable.

Frank Ramsey et la théorie de Ramsey. Frank Ramsey est la personne, née en 1903 et morte en 1930. La théorie de Ramsey est la branche mathématique attachée à son nom. Une date biographique concerne l'homme ; un seuil combinatoire concerne la théorie.

Théorie de Ramsey et théorie des graphes. La première utilise notamment des graphes pour étudier l'apparition inévitable de configurations. La seconde couvre beaucoup d'autres questions. Un problème de chemins dans un graphe n'est donc pas automatiquement un problème de Ramsey.

Structure ordonnée et suite triée. Ici, « ordonnée » signifie qu'un motif régulier imposé émerge parmi les relations. Il ne s'agit pas nécessairement de ranger des nombres du plus petit au plus grand ; le triangle monochrome de l'exemple suffit à trancher.

« Assez grand » n'est pas un seuil universel. Le seuil dépend du motif recherché et du nombre de couleurs. Le symptôme d'un énoncé incomplet est l'absence de ces paramètres ; il faut les fixer avant de chercher une valeur.

Existence ne signifie ni unicité ni abondance. Une garantie ramseyenne assure qu'au moins une configuration apparaît. Elle ne dit pas, à elle seule, combien il en existe ni où la trouver. Il faut un argument supplémentaire pour compter ou localiser les configurations.

Le cas à six sommets est un exemple précis. Il suppose un graphe complet : chaque paire de sommets est reliée, et chaque arête reçoit exactement l'une des deux couleurs. Si des arêtes manquent ou restent sans couleur, la démonstration donnée ne s'applique plus telle quelle ; il faut reformuler le modèle.

Une figure particulière ne prouve pas le résultat général. Repérer un triangle monochrome sur un dessin confirme seulement cette coloration. La preuve doit couvrir les deux branches possibles après le choix des trois arêtes de même couleur issues de A.

L’ordre selon Ramsey — Prolonge l'idée d'une régularité inévitable au sein de configurations suffisamment grandes.

analyse combinatoire — Replace la recherche de configurations et de seuils dans le cadre plus large du dénombrement fini.