Get best of the week

Les coloriages arc-en-ciel sont les meilleurs amis des mathématiciens

Récemment, les couleurs arc-en-ciel ont permis de réaliser une nouvelle épreuve. Et ils ne sont pas la première fois à être utiles.



Le codage couleur du carré latin et de son graphe peut en dire beaucoup

, récemment, nous avons parlé d'une nouvelle preuve de l'hypothèse de Ringel . Une partie de la preuve était liée à l'utilisation des colorations arc-en-ciel, un moyen spécial de codage couleur pour visualiser les informations. Cependant, de tels livres à colorier sont utilisés depuis longtemps par les mathématiciens pour faciliter la résolution d'énigmes, et maintenant ils essaient d'appliquer cette technique au problème associé au précédent.

L'hypothèse de Ringel est un problème du domaine de la combinatoire lié à la construction de graphes - points (sommets) reliés par des lignes (arêtes). Il prédit une relation spéciale entre les grands graphes d'un certain type avec 2n + 1 sommets et les graphes proportionnellement plus petits avec n + 1 sommets.

Commençons, par exemple, avec 11 pics. Connectez chaque sommet avec tous les autres pour obtenir le soi-disant graphique complet. Ensuite, prenez six des sommets disponibles et connectez-les, à notre guise, uniquement pour ne pas obtenir de boucles fermées. Ainsi, nous obtenons le soi-disant "bois".


Exemples de graphiques et d'arbres complets

L'hypothèse de Ringel indique que des copies de n'importe quel arbre peuvent idéalement couvrir, ou carreler, tous les bords du graphique complet correspondant - tout comme vous pouvez carreler le sol de la cuisine avec les mêmes carreaux.



Comme pour le sol de la cuisine, pour réussir, il est nécessaire de choisir l'emplacement correct de la première tuile. Les trois mathématiciens qui ont proposé la couleur d'épreuve ont codé les bords du graphique complet en fonction de la distance entre les sommets pour trouver cet emplacement.



Ensuite, ils ont essayé d'arranger l'arbre à l'intérieur du graphique complet afin qu'il couvre un bord de chaque couleur. Ayant montré qu'un tel arrangement «arc-en-ciel» est en tout cas possible, ils ont prouvé que le carrelage idéal prédit par Ringel fonctionne toujours.

Cependant, cette technique de coloration arc-en-ciel n'est pas venue à la rescousse pour la première fois.

Au 18ème siècle, Leonard Euler s'est intéressé à quelque chose comme le Sudoku pour les enfants. Prenez un carré de 3x3 cellules. Euler l'a rempli de sorte que dans chaque ligne et chaque colonne, il y avait des nombres de 1 à 3, sans jamais se répéter. Ce puzzle est appelé le carré latin . Les modèles et les techniques découverts par Euler et d'autres mathématiciens dans l'étude des carrés latins ont un lien avec de nombreux domaines différents des mathématiques.



Puis Euler s'est demandé: est-il possible de choisir trois cellules, une dans chaque colonne et chaque ligne, pour que les nombres qu'elles contiennent ne se répètent pas? Supposons que vous pouvez sélectionner une cellule de la première colonne de la première ligne contenant 1, une cellule de la deuxième ligne de la deuxième colonne contenant 3 et de la troisième ligne de la troisième colonne contenant 2. Donc, nous avons sélectionné trois cellules, chacune appartenant à différentes lignes et colonnes, et contient son nombre - 1, 3, 2. Cet ensemble de cellules est appelé transversal.



Euler a voulu savoir s'il était possible de diviser entièrement la grille 3x3 (ou une grille carrée de n'importe quelle taille) en ensembles transversaux, de sorte que chaque ensemble ait un numéro de chaque ligne et de chaque colonne. C'est-à-dire que dans le cas d'un carré 3x3, j'espère que nous pourrons trouver trois ensembles transversaux différents couvrant ensemble toutes les cellules du carré.

En conséquence, les mathématiciens ont découvert qu'une façon d'explorer cette question est de transformer un carré en graphique. Pour ce faire, dessinez trois sommets sur la gauche, désignant trois colonnes. Ensuite, nous dessinons trois sommets à droite, représentant les lignes. Tracez les bords reliant chaque sommet à droite à chaque sommet à gauche. Chaque bord, étant une combinaison d'une ligne et d'une colonne particulières, représente l'une des neuf cellules. Par exemple, le bord entre le sommet supérieur droit et le sommet supérieur gauche correspond à la cellule de la première ligne de la première colonne (cellule supérieure gauche du carré latin).



Maintenant, nous sortons les crayons de couleur et encodons les couleurs des nervures en fonction du nombre de carrés qu'elles désignent. Supposons que nous colorions les lignes indiquant 1 avec du bleu, rouge avec 2, jaune avec 3. Si 1 est dans la cellule supérieure gauche, alors le bord entre les sommets supérieurs sera bleu.



Regardons les couleurs des bords. Est-il possible de choisir trois bords de chacune des trois couleurs pour qu'elles commencent et se terminent à des sommets différents? Cet ensemble est appelé correspondance arc-en-ciel. Si vous le trouvez, il devient clair que dans le carré latin correspondant il y a un transversal. De plus, si vous trouvez trois correspondances arc-en-ciel différentes, il devient clair que tout le carré latin est constitué de transversales.



La coloration arc-en-ciel a aidé les chercheurs à étudier les problèmes du passé et est également devenue un élément clé de la nouvelle preuve de l'hypothèse de Ringel. Ils jouent également un rôle dans une tâche encore plus complexe, l'hypothèse du balisage gracieux .

Pour comprendre l'essence du problème, dessinez d'abord six sommets, puis connectez-les pour former un arbre. Attribuez à chaque sommet un numéro de quelque façon que ce soit. Marquez ensuite chaque arête avec la différence entre les nombres des sommets qu'elle relie. C'est-à-dire, par exemple, si une arête relie les sommets 6 et 2, alors nous marquons cette arête avec le numéro 4.

Votre objectif est de faire en sorte que les étiquettes d'arête se succèdent et que leur nombre ne se répète pas. Dans ce cas, 1, 2, 3, 4, 5. Si vous pouvez le faire, un balisage gracieux existera pour votre arborescence.



Dans les années 1960, Gerhard Ringel - celui qui a avancé l'hypothèse - et Anton Kotsig, ensemble, ont suggéré que tout arbre, quel que soit le nombre d'arêtes ou de forme, puisse être marqué gracieusement.

L'hypothèse de balisage gracieux implique l'hypothèse de Ringel - c'est-à-dire que si la première hypothèse est vraie, alors l'hypothèse de Ringel est également vraie. Pour comprendre cela, revenons à un arbre gracieusement marqué de six sommets et à un graphe complet de 11 sommets. Nous distribuons ces 11 sommets autour de la circonférence et les numérotons de 1 à 11. Maintenant, nous plaçons une copie de l'arbre sur le graphique complet afin que les étiquettes des sommets coïncident: les 5 premiers de l'arbre chevauchent les 5 premiers du graphique complet, et ainsi de suite. Ce placement est une copie arc-en-ciel d'un arbre gracieusement marqué.



Donc, si vous savez que les arbres avec le nombre de sommets n + 1 peuvent toujours être gracieusement marqués, alors vous savez qu'ils peuvent toujours être placés à l'intérieur du graphique complet correspondant avec 2n + 1 sommets afin d'obtenir une copie arc-en-ciel de l'arbre. Et un tel placement sera exactement la position avec laquelle commencer le processus de carrelage de Ringel.

"Si vous trouvez un balisage gracieux, je peux vous dire comment trouver votre copie arc-en-ciel", a déclaré Benny Sudakov de l'Institut fédéral suisse de technologie, l'un des trois auteurs de la preuve de l'hypothèse Ringel.

Bien sûr, les mathématiciens ont finalement pu prouver la vérité de l'hypothèse de Ringel sans avoir à prouver l'hypothèse d'un balisage gracieux, laissant cette question sans réponse.

"Le balisage gracieux est une belle et attrayante question en soi, et reste toujours ouvert", a déclaré Sudakov.

Cependant, les méthodes qui ont conduit à la preuve de l'hypothèse de Ringel peuvent probablement être appliquées à un balisage gracieux - et les mathématiciens sont impatients de savoir jusqu'où ces méthodes peuvent les mener.

More articles:


All Articles