Un très grand petit bond en avant dans la théorie des graphes

Le 15 mars, des annonces de séminaire intrigantes ont envoyé des rumeurs dans le domaine de la combinatoire, l'étude mathématique du comptage. Trois collaborateurs prévoyaient de donner des conférences coordonnées le lendemain. Julien Sahasrabudhe s'adressait aux mathématiciens de Cambridge, en Angleterre, tandis que Simon Griffiths partagerait la nouvelle à Rio de Janeiro et Marcelo Campos à São Paulo. Les trois conférences arboraient des titres identiques et des résumés énigmatiques de deux phrases faisant référence aux "progrès récents sur un vieux problème d'Erdős". Tandis que Paul Erdős, un mathématicien hongrois décédé en 1996, posait des centaines de problèmes au cours de sa carrière, les combinatoristes ont rapidement deviné le problème précis dont le trio envisageait de parler. Des rumeurs ont circulé à propos de quelque chose appelé le nombre de Ramsey, l'une des quantités les plus difficiles à calculer dans toutes les mathématiques.

Les nombres de Ramsey ont donné naissance à toute une discipline appelée théorie de Ramsey, qui recherche des modèles incontournables dans une vaste gamme de systèmes.

Par exemple, supposons que vous essayez de répartir tous les nombres entiers dans un certain nombre de compartiments et que vous souhaitiez éviter de placer des séquences de nombres régulièrement espacés dans l'un des compartiments. La théorie de Ramsey montre que vous échouerez (sauf si vous avez une infinité de seaux). La théorie peut être appliquée à presque tout ce que vous pouvez compter. Sa leçon centrale est que "vous ne pouvez pas créer un système complètement chaotique", a déclaré Benny Sudakov, mathématicien à l'Ecole polytechnique fédérale de Zurich.

Le nombre de Ramsey quantifie la taille d'un exemple paradigmatique avant que des modèles particuliers n'apparaissent inévitablement. Mais malgré sa centralité, personne n'a été en mesure de calculer le nombre de Ramsey pour tous sauf le exemples les plus simples. Le mieux qu'ils aient pu faire est de trouver des limites (ou des limites) à ce que cela pourrait être. Même alors, la limite supérieure établie pour la première fois par Erdős et un collaborateur il y a près d'un siècle avait à peine bougé.

Puis, lors des séminaires du 15 mars et dans un article publié plus tard dans la soirée, les chercheurs ont annoncé qu'ils avaient amélioré la limite supérieure du nombre de Ramsey d'une quantité exponentielle.

"J'étais terrassé", a déclaré Yuval Wigderson, mathématicien à l'Université de Tel-Aviv, en entendant parler du nouveau résultat. "J'ai littéralement tremblé pendant une demi-heure à une heure."

Les lignes du parti

La théorie de Ramsey pose le plus souvent des questions sur les nombres entiers ou sur les graphiques. Un graphe, dans ce contexte, fait référence à des collections de points appelés nœuds, reliés par des lignes appelées arêtes, qui peuvent avoir des propriétés comme la longueur ou - comme dans le cas des nombres de Ramsey - la couleur.

Un graphe complet est à la fois compliqué et simple - chaque nœud est connecté à tous les autres nœuds. Le nombre de Ramsey décrit le nombre de nœuds qu'un graphe complet doit contenir pour être forcé d'avoir une structure particulière. Supposons que les arêtes d'un graphique complet se voient attribuer l'une des deux couleurs suivantes : rouge ou bleu. Et disons que vous essayez de colorer les bords d'une manière qui évite de connecter un groupe de nœuds avec des bords de la même couleur. En 1930, Frank Ramsey a prouvé que si un graphe est suffisamment grand, il devient impossible d'éviter de créer ce que les mathématiciens appellent une clique monochromatique - un groupe de nœuds dont les arêtes communes sont soit toutes rouges, soit toutes bleues.

Quelle doit être exactement la taille d'un graphe avant qu'une clique monochromatique ne soit forcée d'émerger ? La réponse dépend de la taille de la clique. Ramsey a montré qu'il existe un nombre, maintenant appelé nombre de Ramsey, représentant le nombre minimum de nœuds pour lesquels une clique monochromatique d'une taille donnée doit exister, quelle que soit la couleur des arêtes.

Mais la taille du nombre de Ramsey est difficile à cerner. En 1935, cinq ans après que Ramsey ait montré son existence, Erdős et George Szekeres ont fourni une nouvelle limite supérieure plus stricte sur la taille du nombre de Ramsey pour une clique d'une taille donnée. Mais depuis lors, les mathématiciens ont à peine pu améliorer le calcul d'Erdős et Szekeres.

Pour avoir une meilleure intuition de ce que cela signifie, considérons un exemple classique, dans lequel les nœuds représentent les invités à une fête. Colorez le bord entre deux invités en rouge s'ils se sont déjà rencontrés et en bleu s'ils ne l'ont pas encore fait. Vous pouvez choisir n'importe quelle taille de clique - inviter suffisamment de personnes à la fête, et vous ne pouvez pas éviter d'inviter un groupe de personnes qui se connaissent toutes (une clique dans plusieurs sens du terme) ou d'inviter un groupe de personnes qui ne se sont jamais rencontrés auparavant.

"La chose la plus simple que vous puissiez avoir dans un graphique est une clique monochromatique", a déclaré Maria Chudnovski, mathématicien à l'université de Princeton. "C'est assez incroyable que dans chaque énorme graphique, vous puissiez en trouver un gros. Ce n'est absolument pas clair. »

Les premiers nombres de Ramsey sont relativement simples à calculer. Disons que vous voulez connaître la taille du plus petit graphe qui doit inévitablement contenir une clique de taille deux, ou R(2) pour les mathématiciens. Puisqu'un graphe complet avec deux nœuds n'est que deux nœuds reliés par une arête, et que cette arête doit être rouge ou bleue, R(2) vaut 2. Plus généralement, R(k), ou le nombre de Ramsey de k, est le nombre minimum de nœuds au-delà duquel un graphe ne peut éviter de contenir une clique de taille k.

Il n'est pas si difficile de montrer que le nombre de Ramsey pour une clique de taille 3, ou R(3), est 6 (voir graphique). Mais ce n'est qu'en 1955 que R(4) a été fixé à 18. R(5) reste inconnu - c'est au moins 43 et pas plus grand que 48. Bien que ces nombres soient petits, il est impossible de passer au crible toutes les colorations possibles. de la question, a déclaré David Conlon du California Institute of Technology. Considérons le nombre de coloriages sur un graphe complet à 43 nœuds. « Vous avez 903 arêtes ; chacun de ceux-ci peut être coloré de deux manières », a-t-il expliqué. "Donc, vous obtenez 2⁹⁰³, qui est juste astronomiquement grand.

À mesure que la taille de la clique augmente, la tâche de déterminer le nombre de Ramsey devient de plus en plus difficile. Erdős a plaisanté en disant qu'une guerre totale avec des extraterrestres mathématiquement exigeants serait plus facile que d'essayer de comprendre R(6), qui se situe quelque part entre 102 et 165. La plage d'incertitude augmente rapidement : selon estimations compilées par Stanisław Radziszowski, R(10) pourrait être aussi petit que 798 et aussi grand que 23,556 10. Mais les objectifs des mathématiciens vont bien au-delà du nombre de Ramsey de XNUMX. Ils veulent une formule qui donne une bonne estimation de R(k), même — ou surtout — lorsque k est extrêmement grand.

"Je ne connais personne en combinatoire qui n'ait pas pensé à ce problème au moins un peu", a déclaré Wigderson. "Ce problème est, je pense, vraiment spécial."

Ordonnance au tribunal

Frank Ramsey était une figure éclectique et brillante qui est décédée à l'âge de 26 ans. Quelques semaines seulement avant sa mort, le Actes de la London Mathematical Society publié le papier dans lequel il a introduit les nombres de Ramsey. Ce travail ne portait même pas sur les graphiques, mais sur un problème de logique mathématique. Ramsey a prouvé qu'une déclaration qui satisfait à certaines conditions doit être vraie au moins une partie du temps. L'une de ces conditions était qu'il y ait un grand « univers » de scénarios pour tester l'énoncé. Comme tremplin vers ce résultat, Ramsey a montré que le nombre de Ramsey est fini.

Cinq ans plus tard, Erdős et Szekeres ont montré que le nombre de Ramsey de k est inférieur à 4^k. Et 12 ans plus tard, Erdős a montré qu'il est plus grand qu'environ $latex sqrt{2}^k$. Pour ce faire, il a calculé les chances qu'un graphe avec des arêtes colorées au hasard contienne une clique monochromatique. Cette technique «probabiliste» est devenue massivement influente dans la théorie des graphes. Il a également piégé R(k) entre deux objectifs à croissance exponentielle : $latex sqrt{2}^k$ et $latex 4^k$.

Au fil des décennies, de nombreux mathématiciens ont tenté de réduire l'écart entre les valeurs possibles du nombre de Ramsey. Certains ont réussi : En 1975, Joel Spencer doublé la limite inférieure. Et une série d'articles de Conlon, Andrew Thomasson et de Ashvin Sah poussé vers le bas la limite supérieure par un facteur d'environ $latex 4^{log(k)^2}$ d'ici 2020. Mais par rapport à la taille des limites du nombre de Ramsey, ces ajustements étaient faibles. En revanche, toute réduction au 4 dans la formule d'Erdős et Szekeres R(k) < 4^k serait une amélioration exponentielle, augmentant rapidement à mesure que k Devient plus grand.

"Cela semble être juste une petite question mignonne", a déclaré Robert Morris, mathématicien à l'IMPA, l'Institut brésilien de mathématiques pures et appliquées, à Rio de Janeiro, qui a co-écrit le nouveau résultat avec Campos, Griffiths et Sahasrabudhe. « C'est un peu subtil à apprécier. Mais les gens s'en soucient vraiment. C'est peut-être un euphémisme. "S'ils l'avaient prouvé en 1936, les gens auraient dit, OK, alors quel est le problème?" a déclaré Béla Bollobás, qui était le directeur de doctorat de Morris et Sahasrabudhe à l'Université de Memphis. "Depuis lors, il a été prouvé que c'est un très gros problème, car au fil des ans, plusieurs milliers d'articles ont été écrits sur diverses variantes du problème de Ramsey." Comme Liane Yepremyan, mathématicien à l'Université Emory, a déclaré: "Les nombres de Ramsey créent ce pont entre la combinatoire, la probabilité et la géométrie."

La théorie des jeux

 En août 2018, Sahasrabudhe était stagiaire postdoctoral sous Morris à l'IMPA. Les deux espéraient démarrer un nouveau projet avec Griffiths, qui enseigne à l'Université catholique pontificale voisine, quand un article de Conlon attiré leur attention. Le document décrivait une stratégie possible pour obtenir une amélioration exponentielle du nombre de Ramsey. Griffiths, Morris et Sahasrabudhe ont commencé à jouer avec l'idée.

"C'était vraiment excitant au début", se souvient Sahasrabudhe. Il ne leur a fallu qu'environ un mois, a-t-il dit, pour présenter une esquisse de leur argumentation.

Leur plan était de s'appuyer sur les idées utilisées dans la preuve originale d'Erdős et Szekeres que $latex R(k) < 4^k$. Pour prouver que le nombre de Ramsey est au plus $latex 4^k$, imaginez jouer à un jeu sur un graphe complet avec des nœuds $latex 4^k$. Le jeu a deux joueurs. Tout d'abord, votre adversaire colore chaque bord en rouge ou en bleu, dans l'espoir de colorer les bords d'une manière qui évite de créer une clique monochromatique de k nœuds.

Une fois que votre adversaire a fini de colorier, c'est à vous de rechercher une clique monochrome. Si vous en trouvez un, vous gagnez.

Pour gagner ce jeu, vous pouvez suivre une stratégie simple. Il est utile de penser (métaphoriquement) à trier vos nœuds en deux seaux. Les nœuds d'un seau formeront une clique bleue et les nœuds de l'autre formeront une clique rouge. Certains nœuds seront supprimés, pour ne plus jamais être entendus. Au début, les deux compartiments sont vides et chaque nœud est candidat pour entrer dans l'un ou l'autre.

Commencez par n'importe quel nœud qui vous plaît. Ensuite, regardez les bords de connexion. Si la moitié ou plus des arêtes sont rouges, supprimez toutes les arêtes bleues et les nœuds auxquels elles sont connectées. Ensuite, mettez votre choix initial dans le seau "rouge". Tous les bords rouges de ce nœud sont toujours bien vivants, accrochés au reste du graphique depuis l'intérieur du seau. Si plus de la moitié des arêtes sont bleues, vous supprimez de la même manière les arêtes et les nœuds rouges et les placez dans le seau bleu.

Répétez jusqu'à ce que vous n'ayez plus de nœuds. (Puisque le graphique est terminé, chaque nœud restant à tout moment est connecté aux deux compartiments jusqu'à ce qu'il soit placé dans l'un d'eux.)

Lorsque vous avez terminé, regardez à l'intérieur des seaux. Parce qu'un nœud n'est entré dans le seau rouge qu'après l'élimination de ses voisins bleus, tous les nœuds du seau rouge sont reliés par des bords rouges - ils forment une clique rouge. De même, le seau bleu forme une clique bleue. Si votre graphe d'origine a au moins $latex 4^k$ nœuds, il est possible de prouver que l'un de ces compartiments doit contenir au moins k nœuds, garantissant une clique monochromatique dans le graphe d'origine.

Cet argument est intelligent et élégant, mais il vous fait construire deux cliques - une bleue et une rouge - même si vous n'en avez vraiment besoin que d'une. Il serait plus efficace de toujours passer au rouge, a expliqué Conlon. Dans le cadre de cette stratégie, vous choisiriez un nœud à chaque étape, effaceriez ses bords bleus et le jetteriez dans le seau rouge. Le seau rouge se remplirait alors rapidement, et vous amasseriez une clique rouge de k nœuds en deux fois moins de temps.

Mais votre stratégie doit fonctionner pour n'importe quelle coloration rouge-bleu, et il est difficile de savoir si vous pouvez toujours trouver un nœud avec beaucoup de bords rouges. Donc, suivre la suggestion de Conlon risque de tomber sur un nœud qui n'a presque pas de bords rouges attachés. Cela vous obligerait à supprimer une grande partie du graphique à la fois, vous obligeant à vous débrouiller pour construire votre clique avant de manquer de nœuds. Pour mettre en œuvre la suggestion de Conlon, Griffiths, Morris et Sahasrabudhe devaient prouver que ce risque était évitable.

Un examen à livre ouvert

En mettant à jour leur gameplay, Griffiths, Morris et Sahasrabudhe ont suivi une route légèrement plus détournée. Plutôt que de construire une clique monochromatique directement en lançant des nœuds dans leurs seaux rouges et bleus, ils se sont d'abord concentrés sur la construction d'une structure appelée livre rouge.

Un livre, en théorie des graphes, est composé de deux parties : il y a une clique monochromatique, appelée la « colonne vertébrale », et un deuxième groupe distinct de nœuds appelés les « pages ». Dans un livre rouge, tous les bords reliant les nœuds à l'intérieur du dos sont rouges, de même que les bords reliant le dos aux pages. Les bords reliant les nœuds dans les pages, cependant, peuvent être n'importe quelle combinaison de couleurs. Conlon avait noté dans son article de 2018 que si vous pouviez trouver une clique rouge dans les pages d'un livre, vous pouviez la combiner avec le dos pour obtenir une clique rouge plus grande. Cela vous permet de décomposer une recherche d'une grande clique rouge en deux recherches plus faciles. Cherchez d'abord un livre rouge. Cherchez ensuite une clique dans les pages du livre.

Griffiths, Morris et Sahasrabudhe voulaient ajuster l'algorithme gagnant du jeu afin qu'il construise un livre rouge au lieu d'une clique rouge. Bien qu'ils se soient mis d'accord sur ce plan quelques semaines seulement après le début de leur projet, il faudrait des années pour le faire fonctionner. Ils devaient encore conjurer la menace de perdre tous leurs bords rouges.

"Nous sommes restés bloqués pendant très longtemps", a déclaré Campos, qui a rejoint le projet en 2021.

En janvier dernier, les quatre mathématiciens ont convenu de passer à une autre version du problème. Cette version semble plus compliquée, mais elle s'est avérée plus facile.

Tout au long, l'équipe s'était concentrée sur le nombre Ramsey R(k), également connu sous le nom de nombre de Ramsey "diagonal". Un graphe de taille R(k) doit contenir k nœuds, tous reliés par des bords de la même couleur, mais peu importe si cette couleur est rouge ou bleue. D'autre part, le nombre de Ramsey "hors diagonale" R(k, l) mesure la taille d'un graphique avant qu'il ne contienne soit une clique rouge avec k nœuds, ou une clique bleue avec l nœuds. Au lieu de continuer à s'attaquer au problème de la diagonale, le groupe a décidé d'essayer la version hors diagonale. Cela s'est avéré révélateur.

"Pendant longtemps, j'ai eu l'impression que chaque porte sur laquelle vous poussiez était soit verrouillée, soit du moins assez difficile à franchir", a déclaré Griffiths. "Et après ce changement, vous aviez l'impression que toutes les portes étaient ouvertes. D'une manière ou d'une autre, tout semblait fonctionner. Dans la version hors diagonale, ils ont trouvé un moyen de supprimer un tas de bords bleus à la fois en suivant un protocole particulier, ce qui a augmenté la densité des bords rouges et a conduit à une meilleure limite sur le nombre de Ramsey hors diagonale. Cette méthode, appelée argument « incrément de densité », avait auparavant été utilisée pour résoudre autres problèmes importants en combinatoire, mais il n'avait pas été utilisé sur le problème du nombre de Ramsey.

Les quatre mathématiciens ont ensuite utilisé la nouvelle borne sur le nombre de Ramsey hors diagonale pour ouvrir la voie au résultat diagonal. Début février, ils avaient finalement abaissé la limite du nombre de Ramsey d'un facteur exponentiel, une réalisation que les mathématiciens recherchaient depuis près d'un siècle. Et ils l'ont fait en modernisant le même argumentaire qu'Erdős et Szekeres avaient avancé en 1935.

Epsilon, Epsilon

Après les pourparlers du 16 mars, les participants ont commencé à confirmer les rumeurs. Des photos du discours de Sahasrabudhe ont circulé par le biais d'appels téléphoniques et de messages privés - même dans un message vague mais suggestif sur le blog du mathématicien Gil Kalai. Campos, Griffiths, Sahasrabudhe et Morris ont prétendu avoir montré que $latex R(k) < 3.993^k$. Cette nuit-là, les quatre auteurs ont posté leur article en ligne, permettant aux mathématiciens de voir la nouvelle preuve par eux-mêmes.

"Je pense que beaucoup d'entre nous ne s'attendaient pas à voir une telle amélioration dans notre vie, essentiellement", a déclaré Matija Bucić, mathématicien à l'Université de Princeton et à l'Institute for Advanced Study. "Je pense que c'est un résultat absolument incroyable."

De nombreux experts espèrent qu'une fois la barrière exponentielle abattue, d'autres progrès suivront rapidement. Les auteurs du nouvel article n'ont intentionnellement pas poussé leur méthode à ses limites, pour éviter d'embrouiller leur argumentation avec des détails inutiles. "Je suis très intéressé de savoir jusqu'où la méthode peut réellement aller, car je n'en ai aucune idée", a déclaré Campos.

« C'est une preuve tout à fait ingénieuse, absolument merveilleuse, et une véritable percée. Alors maintenant, je m'attends à ce que les vannes soient ouvertes », a déclaré Bollobás. « Je suis convaincu que dans trois ans, le débat portera sur les améliorations possibles. Pouvons-nous améliorer 3.993 à 3.9 ? Peut-être à 3.4 ? Et qu'en est-il du 3 ? »

La nouvelle preuve arrive sur 56 pages, et il faudra des semaines pour que chaque détail soit entièrement vérifié par la communauté combinatoire. Mais les collègues sont optimistes. « Ce groupe d'auteurs, ce sont des gens très sérieux. Et ce sont des gens qui sont vraiment, vraiment doués pour des choses très techniques », a déclaré Wigderson.

En ce qui concerne ses collaborateurs, Griffiths est d'accord. « C'est un privilège de travailler avec des gens brillants, n'est-ce pas ? Et je pense que c'est ce dont je suis très reconnaissant », a-t-il déclaré. "S'ils m'avaient laissé le soin de m'en charger, j'aurais peut-être mis encore cinq ans à régler les détails."