Le problème mathématique qu’il a fallu près d’un siècle pour résoudre

Nous sommes tous passés par là : regarder un examen de mathématiques avec un problème qui semble impossible à résoudre. Et si trouver la solution à un problème prenait près d’un siècle ? Pour les mathématiciens qui s’intéressent à la théorie de Ramsey, c’est tout à fait le cas. En fait, peu de progrès ont été réalisés dans la résolution des problèmes de Ramsey depuis les années 1930.

Aujourd’hui, les chercheurs Jacques Verstraete et Sam Mattheus de l’Université de Californie à San Diego ont trouvé la réponse à r(4,t), un problème de Ramsey de longue date qui laisse le monde mathématique perplexe depuis des décennies.

De toute façon, quel était le problème de Ramsey ?

En langage mathématique, un graphique est une série de points et les lignes entre ces points. La théorie de Ramsey suggère que si le graphique est suffisamment grand, vous êtes assuré d’y trouver une sorte d’ordre : soit un ensemble de points sans lignes entre eux, soit un ensemble de points avec toutes les lignes possibles entre eux (ces ensembles sont appelés « cliques »). Ceci s’écrit r(s,t) où s sont les points avec des lignes et t sont les points sans lignes.

Pour ceux d’entre nous qui ne s’intéressent pas à la théorie des graphes, le problème de Ramsey le plus connu, r(3,3), est parfois appelé « le théorème des amis et des étrangers » et s’explique sous forme de partie : dans un Dans un groupe de six personnes, vous trouverez au moins trois personnes qui se connaissent toutes ou trois personnes qui ne se connaissent pas toutes. La réponse à r(3,3) est six.

“C’est un fait naturel, une vérité absolue”, déclare Verstraete. « Peu importe la situation ou les six personnes que vous choisissez : vous trouverez trois personnes qui se connaissent toutes ou trois personnes qui ne se connaissent pas toutes. Vous pourrez peut-être en trouver davantage, mais vous êtes il est garanti qu’il y en aura au moins trois dans une clique ou dans l’autre.”

Que s’est-il passé après que les mathématiciens ont découvert que r(3,3) = 6 ? Naturellement, ils voulaient connaître r(4,4), r(5,5) et r(4,t) où le nombre de points non connectés est variable. La solution de r(4,4) est 18 et est prouvée à l’aide d’un théorème créé par Paul Erdös et George Szekeres dans les années 1930.

Actuellement, r(5,5) est encore inconnu.

Un bon problème se défend

Pourquoi quelque chose de si simple à énoncer est-il si difficile à résoudre ? Cela s’avère plus compliqué qu’il n’y paraît. Disons que vous saviez que la solution de r(5,5) se situe entre 40 et 50. Si vous commenciez avec 45 points, il y en aurait plus de 10²³⁴ graphiques à considérer.

“Comme ces chiffres sont notoirement difficiles à trouver, les mathématiciens recherchent des estimations”, a expliqué Verstraete. “C’est ce que Sam et moi avons réalisé dans nos récents travaux. Comment pouvons-nous trouver non pas la réponse exacte, mais les meilleures estimations de ce que pourraient être ces chiffres de Ramsey ?”

Les étudiants en mathématiques découvrent très tôt les problèmes de Ramsey, c’est pourquoi r(4,t) a été sur le radar de Verstraete pendant la majeure partie de sa carrière professionnelle. En fait, il a vu le problème pour la première fois sous forme imprimée dans Erdös on Graphs: His Legacy of Unsolved Problems, écrit par deux professeurs de l’UC San Diego, Fan Chung et feu Ron Graham. Le problème est une conjecture d’Erdös, qui a offert 250 dollars à la première personne capable de le résoudre.

“Beaucoup de gens ont pensé à r(4,t) : c’est un problème ouvert depuis plus de 90 ans”, a déclaré Verstraete. “Mais ce n’était pas quelque chose qui était au premier plan de mes recherches. Tout le monde sait que c’est difficile et tout le monde a essayé de le comprendre, donc à moins d’avoir une nouvelle idée, vous n’irez probablement nulle part.”

Puis, il y a environ quatre ans, Verstraete travaillait sur un autre problème de Ramsey avec un mathématicien de l’Université de l’Illinois à Chicago, Dhruv Mubayi. Ensemble, ils ont découvert que les graphes pseudo-aléatoires pouvaient faire progresser les connaissances actuelles sur ces vieux problèmes.

En 1937, Erdös découvrit que l’utilisation de graphes aléatoires pouvait donner de bonnes limites inférieures aux problèmes de Ramsey. Ce que Verstraete et Mubayi ont découvert, c’est que l’échantillonnage à partir de graphiques pseudo-aléatoires donne souvent de meilleures limites sur les nombres de Ramsey que les graphiques aléatoires. Ces limites – limites supérieure et inférieure de la réponse possible – ont resserré la gamme d’estimations qu’ils pouvaient faire. En d’autres termes, ils se rapprochaient de la vérité.

En 2019, pour le plus grand plaisir du monde mathématique, Verstraete et Mubayi ont utilisé des graphes pseudo-aléatoires pour résoudre r(3,t). Cependant, Verstraete a eu du mal à construire un graphe pseudo-aléatoire qui pourrait aider à résoudre r(4,t).

Il a commencé à s’intéresser à différents domaines mathématiques en dehors de la combinatoire, notamment la géométrie finie, l’algèbre et les probabilités. Finalement, il s’est associé à Mattheus, un chercheur postdoctoral de son groupe dont la formation était en géométrie finie.

“Il s’est avéré que le graphe pseudo-aléatoire dont nous avions besoin pouvait être trouvé en géométrie finie”, a déclaré Verstraete. “Sam était la personne idéale pour nous aider à construire ce dont nous avions besoin.”

Une fois le graphique pseudo-aléatoire mis en place, ils devaient encore résoudre plusieurs éléments mathématiques. Cela a pris près d’un an, mais ils ont finalement réalisé qu’ils avaient une solution : r(4,t) est proche d’une fonction cubique de t. Si vous souhaitez une soirée où il y aura toujours quatre personnes qui se connaissent toutes ou des personnes qui ne se connaissent pas toutes, vous aurez besoin d’environ trois personnes présentes. Il y a un petit astérisque (en fait un o) car, rappelez-vous, il s’agit d’une estimation et non d’une réponse exacte. Mais t3 est très proche de la réponse exacte.

Les résultats sont actuellement en cours d’examen avec le Annales de mathématiques. Une prépublication peut être consultée sur arXiv.

“Il nous a vraiment fallu des années pour résoudre le problème”, a déclaré Verstraete. “Et il y a eu de nombreuses fois où nous étions coincés et nous nous demandions si nous serions capables de résoudre le problème. Mais il ne faut jamais abandonner, peu importe le temps que cela prend.”

Verstraete souligne l’importance de la persévérance, quelque chose qu’il rappelle souvent à ses étudiants. “Si vous trouvez que le problème est difficile et que vous êtes coincé, cela signifie que c’est un bon problème. Fan Chung a dit qu’un bon problème se défend. Vous ne pouvez pas vous attendre à ce qu’il se révèle.”

Verstraete sait qu’une telle détermination est bien récompensée : “J’ai reçu un appel de Fan me disant qu’elle me devait 250 dollars.”