Get best of the week

La preuve arc-en-ciel démontre la disponibilité de composants standard dans les graphiques

Les mathématiciens ont prouvé que les grands graphiques peuvent toujours être idéalement recouverts de copies de petits graphiques.



Le 8 janvier, trois mathématiciens ont publié la preuve d'un théorème de la combinatoire formulé il y a près de 60 ans, connu sous le nom d'hypothèse de Ringel. En gros, elle prédit que les graphiques - constructions constituées de points et de lignes - peuvent idéalement être pliés à partir de pièces identiques de plus petite taille.

Les mathématiciens ont accepté avec enthousiasme la confirmation de cette hypothèse.

"La chance est que ce travail résout une très vieille hypothèse qui n'a pas pu être vérifiée par d'autres méthodes", a déclaré Gil Kalai , mathématicien à l'Université hébraïque de Jérusalem, sans rapport avec ce travail.

L'hypothèse de Ringel prédit que des types spéciaux de graphiques complexes - avec des milliards de sommets et d'arêtes - peuvent être «tuilés», c'est-à-dire couvrir complètement, avec des copies séparées de petits graphiques d'un certain type. D'un point de vue conceptuel, cette question est similaire à la suivante: puis-je carreler complètement le sol de la cuisine avec les mêmes copies de toutes les tuiles du magasin? Dans la vraie vie, la plupart des types de carreaux ne conviennent pas à votre cuisine - pour recouvrir complètement le sol, vous devez combiner leurs différentes formes. Mais dans le monde de la théorie des graphes, l'hypothèse prédit que vous pouvez toujours carreler un graphe.

Et dans la cuisine et dans les graphiques, il est important où vous placez exactement la première tuile. Le nouveau travail met en évidence ce problème crucial - et de telle manière qu'il est à la fois surprenant et étonnamment intuitif.

Forêt avec arbres


En combinatoire, les mathématiciens étudient comment les sommets (points) et les arêtes (lignes) se combinent pour former des objets plus complexes appelés graphiques. Vous pouvez poser beaucoup de questions sur les graphiques. L'un des principes de base: dans quels cas des graphiques plus petits et plus simples sont-ils idéalement intégrés dans des graphiques plus grands et plus complexes?

"Vous avez un ensemble de pièces de puzzle et vous ne savez pas si vous pouvez l'assembler à partir de ces pièces", a déclaré Jacob Fox de l'Université de Stanford.

En 1963, le mathématicien allemand Gerhard RingelIl a posé une question simple mais plus large de ce type. Commençons, dit-il, avec tout nombre impair de sommets supérieur à 3 (pour la plausibilité de l'hypothèse, le nombre de sommets doit être impair, comme nous le verrons plus loin). Connectez-les avec des arêtes afin que chaque sommet se connecte à tous les autres. Ensuite, nous obtenons un objet appelé un graphe complet .



Imaginez ensuite un graphique d'un type différent. Cela peut être un moyen simple - plusieurs bords connectés en une seule ligne. Ou un chemin avec des nervures ramifiées. Des branches peuvent être ajoutées à d'autres branches. Vous pouvez créer un graphique arbitrairement complexe, en évitant uniquement les boucles fermées. Ces graphiques sont appelés arbres.



La question de Ringel concerne la relation entre des graphiques et des arbres complets. Il a dit: d'abord, imaginez un graphe complet de 2n + 1 sommets (un nombre impair). Imaginez alors n'importe quel arbre composé de n + 1 sommets - et ces arbres peuvent être très différents.

Maintenant, prenez l'un de ces arbres et placez-le de sorte que chaque bord de l'arbre coïncide avec le bord du graphique complet. Ensuite, nous plaçons une autre copie du même arbre sur une autre partie du graphique complet.

Ringel a prédit qu'en agissant de cette manière et en partant du bon endroit, vous pourriez idéalement combler le graphique complet. Cela signifie que chaque bord du graphique complet sera couvert par le bord de l'arbre et que les copies des arbres ne se chevaucheront pas.



«Je peux prendre des copies de l'arbre. J'ai mis une copie sur le graphique complet. Elle couvre quelques côtes. Ensuite, je répète le processus. L'hypothèse suggère que cela peut tout couvrir », a déclaré Benny Sudakov de l'Institut fédéral suisse de technologie, co-auteur des nouvelles preuves, avec Richard Montgomery de l'Université de Birmingham et Alexei Pokrovsky du Birkbeck College de l'Université de Londres.

Enfin, Ringel a prédit que le graphique peut être pavé indépendamment des nombreuses options d'arborescence que vous utiliserez. Une telle déclaration peut sembler trop générale. La conjecture de Ringel s'applique à la fois aux graphiques complets avec 11 sommets et aux graphiques complets avec 11 billions + 1 sommets. Et plus le graphique complet est grand, plus le nombre d'arbres pouvant être dessinés pour n + 1 sommets augmentera. Comment chacun d'eux peut-il idéalement combler le graphique complet correspondant?

Cependant, il y avait des raisons de croire que l'hypothèse de Ringel pouvait être vraie. La toute première confirmation a été que l'arithmétique combinatoire la plus simple n'excluait pas une telle option: le nombre d'arêtes dans un graphique complet avec 2n + 1 sommets peut toujours être complètement divisé par le nombre d'arêtes dans un arbre avec n + 1 sommets.

"Le fait que le nombre de bords d'un graphique complet soit divisé par le nombre de bords d'un arbre est très important", a déclaré Montgomery.

Les mathématiciens ont rapidement trouvé d'autres preuves de la plausibilité de l'hypothèse, ce qui a déclenché une chaîne de découvertes qui a finalement conduit à la preuve.

Placer et tourner


L'un des arbres les plus simples est une étoile: un pic central dont les bords en émanent. Mais elle diffère de l'image typique d'une étoile, car les bords n'ont pas à être uniformément répartis autour du sommet. Ils doivent tous provenir d'un seul endroit et ne doivent se croiser nulle part sauf le pic central. Si vous voulez prouver l'exactitude de l'hypothèse de Ringel, alors un arbre en forme d'étoile sera un point de départ naturel.



Et, bien sûr, les mathématiciens ont rapidement découvert qu'une étoile de n + 1 sommets ouvre toujours parfaitement un graphe complet avec 2n + 1 sommets. Ce fait est intéressant en soi, mais sa preuve a fait réfléchir davantage les mathématiciens.

Prenons un exemple simple. Commençons par 11 pics. Nous les plaçons dans un cercle et connectons chaque sommet avec tous les autres, obtenant un graphique complet.



Considérons maintenant l'étoile qui lui correspond: le point central à cinq arêtes qui en émane.



Maintenant, nous plaçons l'étoile de sorte que le sommet central coïncide avec l'un des sommets du graphe complet. Nous couvrirons plusieurs bords, mais pas tous. Déplacez maintenant l'étoile d'un sommet, comme si vous tourniez le cadran de la boussole. Nous obtenons une nouvelle copie de l'étoile superposée à un ensemble complètement différent d'arêtes du graphique complet.

Nous allons faire tourner l'étoile plus loin. Au moment où nous reviendrons à notre point de départ, nous ouvrirons le graphique complet sans superposer les étoiles - exactement comme l'avait prédit Ringel.



"Nous savons qu'une hypothèse ne peut pas être écartée immédiatement, du moins si nous prenons un arbre sous la forme d'une étoile", a déclaré Sudakov. «De plus, nous pouvons même le démontrer très joliment: dessiner un graphique sur un cercle, déplacer une étoile, obtenir de nouvelles copies et remplacer tout le graphique.»

Peu de temps après que Ringel a avancé son hypothèse, le mathématicien slovaque-canadien Anton Kotzig a utilisé cet exemple pour une prédiction encore plus audacieuse que celle de Ringel. Ringel a déclaré que chaque graphique complet avec un sommet 2n + 1 peut être carrelé avec n'importe quel arbre avec un sommet n + 1, Kotsig a suggéré qu'il puisse être carrelé exactement de la même manière qu'avec une étoile: en plaçant l'arbre sur un graphique complet et en le tournant simplement.

L'idée semblait irréaliste. L'étoile est symétrique, donc peu importe comment la placer. La plupart des arbres sont tordus. Ils doivent être placés de manière très spécifique pour que la méthode de rotation fonctionne.

"L'étoile était une structure simple qui peut être placée manuellement, mais si vous avez un arbre étalé sur vos mains avec un tas de branches de différentes longueurs, il est difficile d'imaginer comment il peut être soigneusement placé", a déclaré Pokrovsky.

Pour résoudre l'hypothèse de Ringel en utilisant la méthode rotative de Kotsig, les mathématiciens devaient trouver comment placer la première copie de l'arbre afin que les fourrés infranchissables ne se révèlent pas. Heureusement, ils ont trouvé une solution colorée.

La coloration arc-en-ciel facilite souvent la vie. Il vous aide à organiser un calendrier ou à distinguer rapidement un récipient de nourriture d'un autre dans une grande famille. Il s'avère que cela peut également être un moyen efficace de comprendre comment placer correctement le premier arbre dans un graphique complet.

Imaginez à nouveau un graphique complet avec 11 sommets disposés en cercle. Marquez ses bords avec des codes de couleur selon une règle simple qui prend en compte la distance entre deux sommets.

Cette distance est déterminée par le nombre de pas à franchir pour passer d'un sommet à un autre dans un cercle (sans couper le chemin à l'intérieur du cercle). Bien sûr, dans un cercle, vous pouvez toujours aller dans deux directions, nous définirons donc la distance comme le chemin le plus court entre deux pics. Si ce sont des sommets voisins, alors la distance entre eux sera 1, pas 10. S'ils sont séparés par un sommet, alors la distance sera 2.



Maintenant, nous colorions les bords du graphique en fonction de la distance. Nous peignons tous les bords reliant les pics situés à une distance de 1 dans une couleur - par exemple, le bleu. Nous peignons tous les bords reliant les pics situés à une distance de deux unités dans l'autre - par exemple, le jaune.

Nous continuons de colorer le graphique afin que toutes les arêtes reliant les sommets à la même distance aient la même couleur. Différentes distances seront encodées dans différentes couleurs. Pour un graphique complet avec 2n + 1 sommets, vous avez besoin de n couleurs pour cela. Le résultat est une image magnifique et utile.



Peu de temps après que Ringel et Kotzig aient avancé leurs hypothèses, Kotzig s'est rendu compte que sa coloration du graphique complet pourrait être un guide pour placer un arbre dessus.

L'idée est de disposer l'arbre de manière à ce qu'il couvre un bord de chaque couleur et ne couvre aucune couleur deux fois. Les mathématiciens appellent cet arrangement une réplique arc-en-ciel d'un arbre. Étant donné que la coloration nécessite n couleurs et qu'un arbre de n + 1 sommets aura n bords, nous savons immédiatement qu'avec une forte probabilité, une copie arc-en-ciel peut être trouvée.



À la fin des années 1960, les mathématiciens ont compris qu'une copie arc-en-ciel d'un arbre avait une propriété spéciale: elle indique simplement la position à partir de laquelle vous pouvez combler le graphique entier en faisant tourner l'arbre.

"Si vous faites une copie arc-en-ciel, alors tout fonctionnera", a déclaré Pokrovsky.

Après cela, les mathématiciens savaient déjà qu'ils pouvaient prouver l'hypothèse de Ringel en prouvant que chaque graphique complet avec 2n + 1 sommets contenait une copie arc-en-ciel de tout arbre avec n + 1 sommets. Et si une copie arc-en-ciel existe toujours, vous pouvez toujours relier le graphique.

Cependant, prouver que quelque chose existe toujours est difficile. Pour cela, les mathématiciens devraient montrer que des graphiques complets ne peuvent tout simplement pas contenir des copies d'arc-en-ciel d'arbres. Cela a pris plus de 40 ans, mais c'est précisément ce que Sudakov et ses co-auteurs ont réalisé dans une nouvelle œuvre.

Emballage parfait


Supposons que l'on vous ait donné un graphique complet avec 11 sommets et un arbre avec six. Le graphique complet est peint en cinq couleurs différentes. L'arbre a cinq bords. Votre tâche consiste à trouver une copie arc-en-ciel de l'arbre à l'intérieur du graphique complet.

Vous pouvez simplement mettre les bords de l'arbre sur le graphique tour à tour. Le premier est facile à placer: vous pouvez choisir n'importe quel bord de n'importe quelle couleur. La seconde sera un peu plus difficile. Il peut se trouver presque n'importe où, sauf pour la nervure de la même couleur que celle qui vient d'être couverte. Et plus vous placez les bords de l'arbre, plus la tâche devient difficile. Après avoir atteint la dernière côte, vous perdrez complètement le choix de la couleur - il n'y en aura qu'une. Il reste à espérer que vous avez tout planifié bien à l'avance.

Cette idée que la tâche de trouver une copie arc-en-ciel d'un arbre devient plus compliquée à mesure que vous placez de plus en plus de bords de l'arbre sur le graphique était une partie nécessaire de la méthode que trois mathématiciens ont utilisée pour résoudre ce problème. Ils ont cherché des moyens de conserver autant de flexibilité que possible vers la fin du processus.

Dès le début, ils savaient qu'il serait facile de trouver des copies arc-en-ciel d'arbres très simples - des arbres qui ressemblaient à un long chemin, sans branches ou avec un petit nombre d'entre eux. La chose la plus difficile était de placer correctement les arbres avec de nombreux bords convergents en un point - comme des étoiles, mais avec une forme plus inégale et irrégulière. Les placer, c'est comme pousser une poussette dans le coffre à moitié rempli d'une voiture.

"La difficulté commence lorsque vous essayez de remplir un graphique complet avec des choses si maladroites qui ressemblent à des étoiles", a déclaré Pokrovsky.

Quiconque remplit le coffre sait que vous devez toujours commencer par les objets les plus complexes - les grandes valises et les gros objets rigides, comme les vélos. Les vestes peuvent alors toujours être poussées. Et les mathématiciens ont adopté cette philosophie.

Imaginez un arbre à 11 arêtes. Six d'entre eux convergent en un point central. Presque tous les autres forment une seule forme, éloignée de la principale.



La partie la plus difficile à placer est la partie de l'arbre qui se compose d'un pic à six bords. Par conséquent, les mathématiciens l'ont séparé du reste de l'arbre et l'ont placé en premier afin d'attacher cette partie plus tard - comme si vous décidiez de démonter le lit avant de le faire glisser au deuxième étage, puis de le remonter dans la pièce souhaitée. Ils n'ont même pas placé cette partie de l'étoile dans le graphique une fois - ils ont trouvé divers endroits appropriés pour placer ses copies à l'intérieur du graphique complet.

Et puis ils ont sélectionné au hasard une copie. Ce faisant, ils ont garanti que l'espace libre restant dans le graphique était également aléatoire - c'est-à-dire avec une distribution à peu près égale de bords de couleurs différentes. C'est à cet endroit qu'ils devaient placer le reste de l'arbre - le chemin qu'ils avaient d'abord mis de côté.

Ils ont fait face à des restrictions lors du choix des options pour son placement. Le chemin doit être connecté à l'étoile - la partie de l'arbre qu'ils ont déjà placée, et doit également couvrir des couleurs qui n'étaient pas précédemment couvertes par l'étoile avec laquelle elle se connecte.

Mais les mathématiciens se sont laissé des options. Ils pourraient connecter le chemin avec presque toutes les différentes copies de l'étoile. Ce qui est encore mieux, puisque l'espace autour de l'étoile était aléatoire, ils avaient la possibilité de choisir différentes couleurs à recouvrir avec le reste de l'arbre.

"Vers la fin de la construction des arbres, lorsque la situation se complique, je n'ai plus une couleur obligatoire, mais un petit choix", a déclaré Montgomery.

Trois mathématiciens complètent leur démonstration avec un argument de la théorie des probabilités. Ils ont montré qu'après avoir intégré les parties les plus complexes des arbres, à condition que l'espace restant dans la colonne complète soit essentiellement aléatoire, il serait toujours possible de trouver un moyen de construire dans le reste des arbres afin d'obtenir une copie arc-en-ciel.

"Maintenant, vous pouvez forcer ce que vous avez repoussé dès le début, comme pour absorber ce qui reste de l'arbre et obtenir une coloration arc-en-ciel complète", a déclaré Noga Alon de l'Université de Princeton.

Les mathématiciens n'ont pas décrit la manière exacte de trouver une copie arc-en-ciel pour chaque arbre avec n + 1 sommets dans chaque graphique complet avec 2n + 1 sommets. Cependant, ils ont prouvé qu'une copie arc-en-ciel devait s'y trouver.

Et si une copie arc-en-ciel existe toujours, vous pouvez toujours relier le graphique avec la méthode prédite par Ringel. Ainsi, son hypothèse est vraie.

La preuve fournit également de nouveaux outils pour résoudre des problèmes similaires non résolus en combinatoire - par exemple, le problème du «balisage gracieux», qui prédit qu'un graphique complet peut être carrelé même dans des conditions plus strictes, selon lesquelles les arbres doivent être placés encore plus précisément.

"Cela montre que les méthodes auxquelles les gens réfléchissent depuis longtemps ont vraiment un grand potentiel", a déclaré Fox. «Si vous les appliquez correctement, vous pouvez résoudre des problèmes qui semblaient auparavant imprenables.»

More articles:


All Articles