Une vue rapprochée révèle le point de « fusion » d’un graphique infini | Magazine Quanta

En 2008, le mathématicien Oded Schramm est décédé dans un accident de randonnée dans les montagnes des Cascades, à environ 50 km à l'est de Seattle. Même s’il n’avait que 46 ans, il avait construit des domaines mathématiques entièrement nouveaux.

"C'était un mathématicien fantastique", a déclaré Itaï Benjamini, mathématicien à l’Institut des sciences Weizmann et ami et collaborateur de Schramm. « Extrêmement créatif, extrêmement élégant, extrêmement original. »

Les questions qu’il a posées repoussent encore les frontières de la théorie des probabilités et de la physique statistique. Beaucoup de ces questions concernent des structures mathématiques qui présentent une transition de phase – un changement macroscopique soudain, comme la fonte de la glace et l’eau. Tout comme différents matériaux ont des points de fusion différents, les transitions de phase des structures mathématiques varient également.

Schramm a supposé que la transition de phase dans un processus appelé percolation pouvait être estimée en utilisant uniquement une vue rapprochée du système – appelée perspective locale – pour de nombreuses structures mathématiques importantes. Zoomer complètement et regarder l’ensemble ne changera pas de manière significative le calcul. Au cours des 15 dernières années, les mathématiciens ont réduit à néant cette conjecture, mais jusqu’à présent, ils n’ont pas réussi à la résoudre complètement.

Dans un prépublication publiée en octobre, Tom Hutchcroft du California Institute of Technology et son doctorant Philippe Easo a prouvé la conjecture de localité de Schramm. Leur preuve s’appuie sur des idées majeures de la théorie des probabilités et d’autres domaines des mathématiques, qu’ils ont combinées de manière intelligente.

« C’est un article remarquable. C’est l’accumulation d’un long travail », a déclaré Benjamini.

Clusters infinis

Le mot « percolation » faisait à l’origine référence au mouvement d’un fluide à travers un milieu poreux, tel que l’eau s’écoulant à travers le marc de café ou l’huile s’infiltrant à travers les fissures d’une roche.

En 1957, les mathématiciens Simon Ralph Broadbent et John Michael Hammersley développèrent un modèle mathématique de ce processus physique. Au cours des décennies qui ont suivi, ce modèle est devenu un objet d’étude à part entière. Les mathématiciens étudient la percolation parce qu'elle établit un équilibre important : la configuration est simple, mais elle présente des caractéristiques complexes et déroutantes.

"C'est une sorte de modèle canonique pour les mathématiciens", a déclaré Hutchcroft. « Vous pouvez penser aux choses visuellement. C’est vraiment agréable de travailler avec eux.

La percolation commence par un graphique, qui est une collection de sommets (points) pouvant être reliés par des arêtes (lignes). L’un des exemples les plus simples est une grille carrée, dont les sommets sont alignés pour former les coins des carrés et les arêtes reliant certains d’entre eux.

Peu avant sa mort, Schramm conjectura que le théorème de Grimmett et Marstrand pouvait être généralisé. Il pensait que le seuil de percolation était entièrement déterminé par la perspective rapprochée, ou « microscopique », d’une grande classe de graphiques appelés graphiques transitifs.

En 2009, Benjamini, Asaf Nachmias et les Yuval Peres prouvé La conjecture de localité de Schramm, comme on l'appelle maintenant, pour un type spécifique de graphe transitif qui ressemble à un arbre. Schramm, cependant, avait postulé que cela serait valable pour tous les graphes transitifs (à l'exception des graphes unidimensionnels).

Dans un graphe transitif, tous les sommets se ressemblent. Une grille bidimensionnelle en est un exemple. Si vous choisissez deux sommets, vous pouvez toujours trouver une symétrie qui déplace un sommet vers l’autre.

Cette relation est valable pour tout graphe transitif. En raison de ces symétries, si vous effectuez un zoom avant et regardez deux patchs de taille égale d'un graphe transitif, ils se ressembleront. Pour cette raison, Schramm pensait que la perspective rapprochée était suffisante pour permettre aux mathématiciens de calculer le seuil de percolation pour tous les graphes transitifs.

Les graphiques transitifs peuvent prendre de nombreuses formes. Il peut s’agir d’une simple grille composée de carrés, de triangles, d’hexagones ou d’une autre forme. Ou ils peuvent former un objet plus complexe, comme un « arbre 3-régulier », où un point central se connecte à trois sommets, et chaque sommet se ramifie ensuite pour en créer deux nouveaux à l'infini, dont les premières étapes sont vues ici :

La variété des graphes transitifs a contribué à la difficulté de prouver la conjecture de localité de Schramm. Au cours des 15 années qui se sont écoulées entre la conjecture de Schramm et la preuve d’Easo et Hutchcroft, divers groupes de mathématiciens ont prouvé la conjecture pour des types spécifiques de graphes, mais leurs idées ne se sont jamais étendues au cas général.

"L'espace de toutes les géométries possibles est tellement vaste et il y a toujours des choses étranges qui se cachent", a déclaré Hutchcroft.

Élargir l'objectif

Easo et Hutchcroft ne cherchaient pas initialement une solution à la conjecture de localité de Schramm, qui s’applique aux graphes infinis. Ils étudiaient plutôt la percolation sur des graphes finis. Mais ils ont eu une idée qui a soudainement attiré leur attention sur la conjecture.

"Nous avons mis au point ce nouvel outil et nous avons pensé, oh, cela semble être le genre de chose qui pourrait être utile pour attaquer une localité", a déclaré Easo.

Pour prouver cette hypothèse, ils devaient montrer que la perspective microscopique donne un aperçu précis du seuil de percolation. Lorsque vous affichez seulement une partie d’un graphique et observez un grand cluster connecté, vous pouvez supposer que le graphique possède un cluster infini et se trouve donc au-dessus du seuil de percolation. Easo et Hutchcroft ont décidé de le prouver.

Ils se sont appuyés sur une technique qui peut être considérée comme « un élargissement de la lentille ». Commencez à un seul sommet. Effectuez ensuite un zoom arrière pour afficher tous les sommets situés à seulement un bord du graphique d'origine. Sur la grille carrée, vous pourrez désormais voir cinq sommets au total. Élargissez à nouveau l'objectif pour voir tous les sommets situés à une distance de deux arêtes, puis à une distance de trois arêtes, quatre arêtes, et ainsi de suite.

Easo et Hutchcroft règlent le cadran qui détermine le nombre de liens proches de l'endroit où ils ont vu un grand cluster. Ils ont ensuite élargi la lentille, observant de plus en plus de bords se rassembler dans leur grand amas. Ce faisant, ils ont dû augmenter la probabilité que des liens soient présents, ce qui permet de montrer plus facilement que le graphique comporte une composante connexe importante. Il s’agit d’un exercice d’équilibre délicat. Ils devaient élargir le champ de vision assez rapidement et ajouter des liens assez lentement pour révéler le graphique infini complet sans changer radicalement la position du cadran.

Ils ont pu montrer que les grands clusters se développent plus rapidement que les plus petits, de sorte que, comme le dit Easo, "votre cluster se développe de plus en plus vite à mesure qu'il devient de plus en plus gros, tout comme lorsque vous faites rouler une boule de neige".

Pour la grille carrée, le nombre de sommets augmente relativement lentement. C'est à peu près la largeur de votre objectif au carré. Après 10 étapes, vous trouverez environ 100 sommets. Mais un arbre 3 régulier pousse exponentiellement plus vite – environ 2 élevés à la puissance de la largeur de votre lentille. Après 10 étapes, vous verrez environ 1,024 3 sommets. L'illustration ci-dessous montre comment l'arbre XNUMX-régulier est beaucoup plus grand après seulement sept étapes, même si la grille carrée a plus de sommets au début. En général, les graphiques peuvent avoir des taux de croissance différents à différentes échelles : ils peuvent démarrer rapidement, puis ralentir.

En 2018, Hutchcroft utilisé une idée similaire pour prouver la conjecture de localité pour les graphes à croissance rapide comme l'arbre 3-régulier. Mais cela n’a pas fonctionné pour les graphiques à croissance lente comme la grille carrée, ni pour les graphiques qui croissent à une vitesse intermédiaire, ne répondant ni aux critères mathématiques d’une croissance rapide ni à ceux d’une croissance lente.

"C'est là que les choses deviennent vraiment frustrantes pendant environ trois ans", a déclaré Hutchcroft.

Structure contre expansion

Pour les graphiques mélangeant des taux de croissance à différentes échelles, vous devez utiliser diverses techniques.

Un fait très utile est que, comme l’explique Easo, « si un graphique semble avoir une croissance lente à une certaine échelle, alors il reste bloqué ». Il continuera à croître lentement à plus grande échelle. Étant donné que les graphiques à croissance lente ont une structure supplémentaire déterminée par une branche des mathématiques appelée théorie des groupes, on savait également que si vous effectuez un zoom arrière suffisamment important, les graphiques à croissance lente affichent une géométrie mathématiquement apprivoisée.

En 2021, Sébastien Martineau de la Sorbonne Université à Paris, en collaboration avec Daniel Contreras et Vincent Tasion de l'ETH Zurich, a pu utiliser cette propriété pour prouver la conjecture de localité de Schramm pour les graphiques qui finissent par croître lentement.

À ce stade, les deux groupes de mathématiciens avaient abordé avec succès la conjecture sous des angles différents : croissance rapide et croissance lente. Mais cela a laissé des lacunes considérables. D’une part, il existe une catégorie de croissance intermédiaire qui n’était pas couverte par la technique d’Easo et Hutchcroft ni par la preuve de Contreras, Martineau et Tassion. Un autre problème était que les arguments ne s’appliquaient toujours pas aux graphiques présentant des taux de croissance variables – uniquement à ceux qui restaient rapides ou lents. Pour que les arguments de Contreras, Martineau et Tassion soient appliqués à des graphiques arbitraires, il ne suffisait pas que la géométrie finisse par paraître docile lorsque vous effectuez un zoom arrière, a expliqué Easo : « Nous avons besoin qu'elle paraisse docile maintenant, proche de l'échelle actuelle. »

Au milieu de nulle part

Les graphiques transitifs de croissance intermédiaire sont très mystérieux. Les mathématiciens n'ont jamais trouvé d'exemple de graphe transitif dont la croissance se situe dans cette fourchette. Il est possible qu’ils n’existent même pas. Mais les mathématiciens n’ont pas prouvé qu’ils n’existaient pas, donc toute preuve complète de la conjecture de localité de Schramm doit les aborder. Pour ajouter au défi, Easo et Hutchcroft devaient traiter des graphiques qui pourraient n'avoir que brièvement une croissance intermédiaire à une échelle de longueur particulière, même s'ils croissent plus rapidement ou plus lentement lorsque vous effectuez un zoom avant ou arrière.

Easo et Hutchcroft ont passé une grande partie de l’année dernière à travailler pour étendre leurs résultats afin de les appliquer à des graphiques qui n’étaient couverts par aucune des méthodes précédentes.

Premièrement, ils ont modifié la technique de 2018 que Hutchcroft avait appliquée aux graphiques à croissance rapide pour travailler sur des graphiques qui modifient les niveaux de croissance à différentes échelles. Ils ont ensuite abordé le cas de la croissance lente, en un papier de 27 pages ils ont partagé en août le développement du travail sur Contreras, Martineau et Tassion. Enfin, dans leur prépublication d'octobre, ils ont conçu un autre argument utilisant la théorie des marches aléatoires (des lignes qui se tortillent de manière aléatoire dans l'espace) pour traiter le cas de croissance intermédiaire. Une fois la trichotomie terminée, ils avaient prouvé la conjecture de localité de Schramm.

"Nous avons dû mettre tout ce que nous connaissions sur le problème", a déclaré Hutchcroft.

La solution donne aux mathématiciens un meilleur aperçu de ce qui se passe au-dessus du seuil de percolation, où la probabilité d'un amas infini est de 100 %, et en dessous, où la chance est de 0 %. Mais les mathématiciens sont encore perplexes quant à ce qui se passe exactement au seuil de la plupart des graphiques, y compris la grille tridimensionnelle. "C'est probablement la question ouverte la plus célèbre et la plus fondamentale de la théorie de la percolation", a déclaré Russell Lyons de l'Université de l'Indiana.

La grille bidimensionnelle est l'un des rares cas où les mathématiciens ont prouvé ce qui se passe exactement au seuil : des clusters infinis ne se forment pas. Et après que Grimmett et Marstrand aient prouvé une version de la conjecture de localité pour les grandes dalles, Grimmett et ses collaborateurs ont montré que si vous coupez une grille 3D en deux horizontalement, créant un sol, et réglez le cadran exactement sur le seuil de percolation, aucun cluster infini n'apparaît. Leurs résultats suggèrent que la grille tridimensionnelle complète, comme sa contrepartie bidimensionnelle, pourrait ne pas avoir d'amas infini au seuil de percolation.

En 1996, Benjamini et Schramm conjecturé que la chance de trouver un cluster infini juste au seuil est nulle pour tous les graphes transitifs — tout comme c'est le cas pour la grille 2D ou pour la grille 3D coupée en deux. Maintenant que la conjecture de la localité a été réglée, la compréhension de ce qui se passe juste au point de transition pourrait être un peu plus précise.

Correction: 18 décembre 2023
Le nombre de nœuds dans n liens d'un nœud de départ sur un graphe 3-régulier augmente d'environ 2ⁿ, pas 3ⁿ comme cet article l’indiquait à l’origine. L'article a été corrigé.

Quanta mène une série d’enquêtes pour mieux servir notre public. Prenez notre enquête auprès des lecteurs de mathématiques et vous serez inscrit pour gagner gratuitement Quanta marchandise.