Les chercheurs de l'Université de Californie de San Diego ont trouvé la réponse à r(4,t), un problème de Ramsey de longue date qui perplexe le monde des mathématiques depuis des décennies.
Quel était le problème de Ramsey, de toute façon ?
En langage mathématique, un graphique est une série de points et de lignes entre ces points. La théorie de Ramsey suggère que si le graphique est assez grand, vous êtes garanti de trouver un ordre à l'intérieur - soit un ensemble de points sans ligne entre eux, soit un ensemble de point avec toutes les lignes possibles entre eux (ces ensembles sont appelés « cliques »). Ceci est écrit en 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 traitent pas de la théorie des graphes, le problème Ramsey le plus connu, r(3,3), est parfois appelé "le théorème sur les amis et les étrangers" et s'explique par une fête : dans un groupe de six personnes, vous trouverez au moins trois personnes qui connaissent toutes chacun autres ou trois personnes qui ne se connaissent pas tous. La réponse à r(3,3) est six.
Que s'est-il passé après que les mathématiciens aient trouvé que r(3,3) = 6 ? Naturellement, ils voulaient savoir r(4,4), r(5,5) et r(4,t) où le nombre de points qui ne sont pas connectés est variable. La solution à r(4,4) est 18 et est prouvée en utilisant un théorème créé par Paul Erdös et George Szekeres dans les années 1930.
Actuellement, r(5,5) est toujours inconnu.
Un bon problème riposte
Pourquoi quelque chose de si simple à affirmer est-il si difficile à résoudre ? Il s'avère être plus compliqué qu'il n'y paraît. Disons que vous saviez que la solution à r(5,5) se situait entre 40 et 50. Si vous commenciez avec 45 points, il y aurait plus de 10234 graphiques à prendre en compte.
En 1937, Erdös découvrit que l'utilisation de graphiques 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 pseudorandoms donne fréquemment de meilleures limites sur les nombres de Ramsey que les graphiques Ces limites - limites supérieures et inférieures de la réponse possible - ont resserré la gamme d'estimations qu'ils pouvaient faire. Autrement dit, ils se rapprochaient de la vérité.
En 2019, pour le plaisir du monde des mathématiques, Verstraete et Mubayi ont utilisé des graphiques pseudorandom pour résoudre r(3,t). Cependant, Verstraete a eu du mal à construire un graphique pseudorandom qui pourrait aider à résoudre r(4,t).
Il a commencé à tirer dans différents domaines des mathématiques en dehors de la combinatoire, y compris la géométrie finie, l'algèbre et la probabilité. Finalement, il s'est joint à Mattheus, un boursier postdoctoral de son groupe dont les origines étaient en géométrie finie.
Une fois qu'ils ont eu le graphique pseudorandom en place, ils ont quand même dû décrocher plusieurs morceaux de mathématiques. Cela a pris presque un an, mais finalement ils ont réalisé qu'ils avaient une solution : r(4,t) est proche d'une fonction cubique de t. Si vous voulez une fête où il y aura toujours quatre personnes qui se connaissent tous ou des gens qui ne se connaissent pas tous, vous aurez besoin d'environ t3 personnes présentes. Il y a un petit astérisque (en fait un o) parce que, rappelez-vous, c'est une estimation, pas une réponse exacte. Mais t3 est très proche de la réponse exacte.
https://phys.org/news/2023-10-....math-problem-century