Le but ici est de tracer des triangles au-dessus de ces lignes de sorte que les triangles satisfassent à deux exigences : premièrement, aucun triangle ne partage une arête. (Les systèmes qui remplissent cette exigence sont appelés systèmes triples de Steiner.) Et deuxièmement, assurez-vous que chaque petit sous-ensemble de triangles utilise un nombre suffisamment grand de nœuds.
La façon dont les chercheurs ont procédé est peut-être mieux comprise par une analogie.
Dites qu’au lieu de faire des triangles avec des bords, vous construisez des maisons en briques Lego. Les premiers bâtiments que vous construisez sont extravagants, avec des renforts structurels et une ornementation élaborée. Une fois que vous en avez terminé, mettez-les de côté. Ils serviront d’« absorbeur », une sorte de réserve structurée.
Commencez maintenant à construire des bâtiments avec vos briques restantes, en procédant sans trop de planification. Lorsque votre stock de Legos diminue, vous pouvez vous retrouver avec des briques errantes ou des maisons structurellement fragiles. Mais puisque les bâtiments absorbants sont tellement surfaits et renforcés, vous pouvez arracher quelques briques ici et là et les utiliser sans courtiser la catastrophe.
Dans le cas du système triple de Steiner, vous essayez de créer des triangles. Votre absorbeur, dans ce cas, est une collection de bords soigneusement choisis. Si vous ne parvenez pas à trier le reste du système en triangles, vous pouvez utiliser certains des bords qui mènent à l’absorbeur. Ensuite, lorsque vous avez terminé, vous décomposez l’absorbeur lui-même en triangles.
L’absorption ne fonctionne pas toujours. Mais les mathématiciens ont bricolé le processus, trouvant de nouvelles façons de contourner les obstacles. Par exemple, une variante puissante appelée absorption itérative divise les arêtes en une séquence imbriquée d’ensembles, de sorte que chacun agit comme un absorbeur pour le plus grand suivant.
“Au cours de la dernière décennie, il y a eu des améliorations massives”, a déclaré Conlon. “C’est une forme d’art, mais ils l’ont vraiment portée au niveau de l’art supérieur à ce stade.”
Le problème d’Erdős était délicat même avec une absorption itérative. “Il est devenu assez clair assez rapidement pourquoi ce problème n’avait pas été résolu”, a déclaré Mehtaab Sawhney, l’un des quatre chercheurs qui l’ont résolu, avec Ashwin Sah, qui, comme Sawhney, est étudiant diplômé au Massachusetts Institute of Technology; Michael Simkin, boursier postdoctoral au Center of Mathematical Sciences and Applications de l’Université de Harvard; et Matthew Kwan, mathématicien à l’Institut des sciences et technologies d’Autriche. “Il y avait des tâches techniques assez intéressantes et assez difficiles.”
Par exemple, dans d’autres applications d’absorption itérative, une fois que vous avez fini de couvrir un ensemble – soit avec des triangles pour les systèmes triples de Steiner, soit avec d’autres structures pour d’autres problèmes – vous pouvez le considérer comme traité et l’oublier. Les conditions d’Erdős, cependant, ont empêché les quatre mathématiciens de le faire. Un groupe problématique de triangles pourrait facilement impliquer des nœuds de plusieurs ensembles d’absorbeurs.
“Un triangle que vous avez choisi il y a 500 pas, vous devez en quelque sorte vous rappeler comment y penser”, a déclaré Sawhney.
Ce que les quatre ont finalement compris, c’est que s’ils choisissaient soigneusement leurs triangles, ils pourraient contourner le besoin de garder une trace de chaque petite chose. “Ce qu’il vaut mieux faire, c’est de penser à n’importe quel petit ensemble de 100 triangles et de garantir que cet ensemble de triangles est choisi avec la bonne probabilité”, a déclaré Sawhney.
Les auteurs du nouvel article sont optimistes quant à la possibilité d’étendre leur technique au-delà de ce seul problème. Ils ont déjà appliqué leur stratégie à un problème sur les carrés latins, qui sont comme une simplification d’un puzzle sudoku.
Au-delà de cela, plusieurs questions pourraient éventuellement céder le pas aux méthodes d’absorption, a déclaré Kwan. “Il y a tellement de problèmes en combinatoire, en particulier en théorie de la conception, où les processus aléatoires sont un outil vraiment puissant.” L’un de ces problèmes, la conjecture de Ryser-Brualdi-Stein, concerne également les carrés latins et attend une solution depuis les années 1960.
Bien que l’absorption puisse nécessiter un développement supplémentaire avant de résoudre ce problème, elle a parcouru un long chemin depuis sa création, a déclaré Maya Stein, directrice adjointe du Centre de modélisation mathématique de l’Université du Chili. “C’est quelque chose de vraiment formidable à voir, comment ces méthodes évoluent.”
Histoire originale reproduit avec la permission de Quanta Magazine, une publication éditorialement indépendante de la Fondation Simons dont la mission est d’améliorer la compréhension publique de la science en couvrant les développements et les tendances de la recherche en mathématiques et en sciences physiques et de la vie.
Laissez un commentaire