L’ordre se cache dans le chaos. C’est le travail principal de la théorie de Ramsey.
Pendant quatre-vingt-dix ans, les mathématiciens ont tenté de le trouver. Les progrès ont été glaciaires.
Ils voulaient savoir quand le hasard cesse de fonctionner. Quand la structure devient obligatoire.
Les sujets ? Graphiques.
Pas de graphiques à barres. Réseaux. Points reliés par des lignes.
Pensez aux itinéraires aériens. Pensez aux amitiés. Pensez aux molécules.
Tout graphique suffisamment grand contient deux choses.
Une clique. Un groupe où tout le monde connaît tout le monde.
Ou un ensemble indépendant. Un groupe de gens qui ne connaissent personne.
R(3,10). C’est la question. Quelle doit être la taille d’un réseau social pour garantir trois amis communs ou dix inconnus ?
Nous ne connaissons pas la réponse.
Il existe exactement moins de trente numéros de Ramsey. Le reste est un mystère.
Les mathématiciens utilisent donc des limites. Un piège.
Imaginez un compacteur de déchets Star Wars. 🤖
La limite inférieure est un mur. La limite supérieure est l’autre.
Pendant des décennies, l’écart a été énorme.
Puis Domagoj Bradaä est apparu.
Il travaille à l’Ecole Polytechnique Fédérale Suisse. Le mois dernier, il a posté une preuve. Cela a brisé une barrière.
Les murs ont emménagé. Fermez. Délicieusement proche.
Voici comment il a procédé.
“La géométrie est quelque chose que nous comprenons bien mieux que la théorie des graphes.” — Marcelo Campos
Bradaä n’a pas commencé dans le chaos. Il a commencé par la géométrie.
Il a d’abord construit un graphique géant. Rigide. Algébrique. Structuré.
Pourquoi?
Parce que la géométrie vous donne des propriétés gratuitement.
Puis il a ajouté le chaos.
Il a découpé au hasard son grand graphique géométrique. J’en ai pris un morceau. Suppression de certains nœuds défectueux.
Le résultat ?
Des graphiques devenus massifs. Mais j’ai évité les modèles.
Pas de cliques. Pas de grands ensembles indépendants.
Je m’accroche à peine.
La meilleure limite supérieure ? Coincé depuis les années 193. Bradaä l’a presque touché.
“Dans un monde idéal, je dirais simplement : voici le graphique. Ce serait fini.” — Domagoj Bradaâ
Dommage que le monde ne soit pas idéal.
Il a prouvé qu’ils pouvaient exister. Il ne leur en a pas donné. C’est la méthode probabiliste. Inventé par Paul Erdäs. Prouver l’existence par hasard.
La preuve de Bradaâ était bonne. Mais ce n’était pas la fin.
Entrez dans l’IA.
OpenAI a vu le journal. Alimenté leur modèle de raisonnement.
L’IA a trouvé un ajustement.
Pas un remplacement. Un affûtage.
Cela a éliminé le peu d’incertitude qui restait dans les limites de Bradaâ.
Désormais, les limites inférieure et supérieure correspondent aux écarts polylogarithmiques.
En gros rien.
Le jeu est-il terminé ?
Pas tout à fait.
“Nous n’essayons pas systématiquement de réparer les papiers arXiv. Nous avons juste eu de la chance.” — Mehtaab Sawhney (OpenAI)
L’IA n’a pas tout résolu. Cela a resserré les vis sur le travail de Bradaâ.
Marcelo Campos aime nous rappeler qui a fait le gros du travail. Le concept est venu de l’humain. L’IA vient de nettoyer les bords.
Toujours.
Une IA a amélioré un problème mathématique vieux d’un siècle. En quelques semaines.
Qui savait ?
Nous sommes juste à côté de la vérité des chiffres de Ramsey.
L’écart est mince. Comme la glace en avril.
Montez dessus et voyez ce qui casse.
