Un mathématicien russe réfute l'hypothèse de 53 ans sur la coloration des réseaux

Seulement trois pages étaient nécessaires pour que le mathématicien russe décrive une méthode de coloration des réseaux d'un certain type qui dépassait les attentes des experts

Une hypothèse de 53 ans concernant la meilleure façon d'attribuer des couleurs aux nœuds du réseau est réfutée dans un article en ligne. Le travail sur seulement trois pages montre l'existence de méthodes de coloration de certaines couleurs qui ont dépassé toutes les attentes des experts.

Tâches de coloration des filets [ voir numéro chromatique / env. perev. ], inspiré par la question de la coloration des cartes, dans laquelle les pays voisins ont des couleurs différentes, fait l'objet de recherches de mathématiciens depuis près de 200 ans. La tâche consiste à comprendre comment colorer les nœuds d'un certain réseau (ou graphe , ce que leurs mathématiciens les appellent) afin que deux nœuds connectés aient des couleurs différentes. Selon le contexte, cette coloration peut fournir un moyen efficace de faire asseoir des invités lors d'un mariage, d'organiser des tâches de production pour des intervalles de temps libres, ou même de résoudre des sudoku .

Les tâches de coloration des graphiques sont souvent faciles à formuler, mais incroyablement difficiles à résoudre. Même à la recherche d'une réponse à la question par laquelle tout ce domaine de recherche a commencé, quatre couleurs suffisent-elles pour colorier une carte ? - Cela a pris plus de cent ans (si cela vous intéresse, la réponse est oui).

La tâche envisagée dans les nouveaux travaux, jusqu'à présent, n'était pas considérée comme une exception. Il n'a pas pu être résolu pendant plus de 50 ans, et il concerne les produits tensoriels - des graphiques constitués d'une combinaison spéciale de deux graphiques différents (appelons-les G et H). Le produit tensoriel des graphes G et H est un nouveau graphe plus grand, dont chaque sommet dénote une paire de sommets des graphes originaux - un de G et un de H - tandis que les deux sommets du produit tensoriel sont connectés si les deux sommets correspondants dans G et leurs sommets correspondants en H.

Supposons que vous soyez professeur de musique et que vous ayez besoin de trouver de bons couples en duo pour un concert de cinquième année. Vous pouvez faire un graphique, dont les sommets seront des étudiants, et les liens entre les paires indiqueront la présence de bonnes relations entre elles. Ensuite, vous pouvez faire un deuxième graphique dans lequel chaque nœud indiquera différents instruments de musique, et la connexion entre eux est la présence de feuilles de musique pour un duo de ces deux instruments. Dans le produit tensoriel de ces deux graphiques, il y aura un sommet pour chaque combinaison possible de l'étudiant et de l'instrument (disons, Alice et trombone), et les deux sommets seront connectés si deux étudiants fonctionnent bien ensemble, et les deux instruments sont compatibles.

En 1966, Stephen Hedetniemi , maintenant professeur à l'Université Clemson en Caroline du Sud, a suggéré dans sa thèse de doctorat que le nombre minimum de couleurs nécessaires pour colorer un produit tensoriel est la plus petite des deux couleurs nécessaires pour colorier l'un ou l'autre des deux graphiques. . «C'est l'une des principales hypothèses de la théorie des graphes», a déclaré Gil Kalai de l'Université hébraïque de Jérusalem. «Beaucoup de gens ont essayé de la méditer.»

Au cours des dernières décennies, les mathématiciens ont rassemblé une montagne de preuves, dont certaines ont parlé de la vérité de l'hypothèse, et d'autres - de sa fausseté. Différents mathématiciens avaient des hypothèses différentes quant à l'option qui gagnerait finalement. Mais tout le monde était d'accord qu'au moins c'était une tâche difficile.

«Personnellement, je pensais que cette hypothèse était vraie, car un grand nombre de personnes intelligentes l'ont étudiée et devraient trouver un contre-exemple», si cela existait, a déclaré Anthony Bonato de l'Université Ryerson à Toronto.

Et donc le mathématicien russe Yaroslav Nikolaevich Shitov a trouvé un moyen simple de créer des contre-exemples, des travaux de tenseur qui nécessitent moins de couleurs que l'un des deux graphiques qui les composent. Les preuves sont «élémentaires mais brillantes», a déclaré Pavol Hell de l'Université Simon Fraser à Burnaby, au Canada.

Les graphiques de tenseurs sont étroitement liés aux questions sur les correspondances de différents graphiques les uns avec les autres, et dans ce domaine des mathématiques, l'hypothèse de Hedetniemi était probablement le plus grand problème ouvert, a déclaré Hell. "Il s'agit d'une percée majeure."

Hangouts colorés

Pour imaginer quelles informations peuvent être extraites de la coloration du graphique tensoriel, imaginez que vous allez inviter vos amis dans votre domaine de banlieue chaque week-end. Et, en tant que bon hôte, vous voulez rassembler des gens qui apprécieront la compagnie de chacun.

Vous savez que certains de vos amis pourront se faire rapidement des amis sur la base du travail, d'autres non. Vous savez également que vos amis ont un passe-temps - une autre façon par laquelle les invités peuvent trouver des intérêts communs. Vous spéculez qu'un professeur de danse du violon peut s'amuser à parler avec un professeur de yoga en jouant au tennis ou à discuter de musique avec un fermier qui produit du sirop d'érable et joue du piano, mais probablement pas à son sujet qu'il parlera avec un politologue collectionnant des timbres. Vous voulez que chaque couple d'invités puisse trouver des intérêts communs à n'importe quel week-end, que ce soit un travail ou un passe-temps, et vous vous demandez combien de rassemblements vous devez organiser pour trier tous les invités de la liste.


Yaroslav Shitov a découvert un contre-exemple de l'hypothèse de Hedetniemi, 53 ans, issue de la théorie des graphes

Vous pourriez imaginer la relation de différents types de travaux sous la forme d'un graphique, dont les nœuds seront le travail, et deux travaux seront connectés par des bords, entre lesquels, très probablement, il ne sera pas possible de trouver des sujets de conversation communs (cette approche peut cependant sembler inversée dans le contexte de la coloration graphiques une telle connexion de sommets est logique, car nous allons utiliser des couleurs pour séparer ces paires problématiques). Vous pouvez également créer un graphique dont les sommets sont différents passe-temps et interconnecter tous ceux qui sont incompatibles.

Le produit tensoriel de ces deux graphiques aura des nœuds pour chaque paire travail-loisir, et les deux sommets seront combinés si le travail et les deux loisirs sont incompatibles - c'est exactement la situation que vous voulez éviter le week-end. Si vous pouvez colorer les sommets du produit tensoriel afin que les sommets reliés par les nervures aient des couleurs différentes, cela vous donnera un moyen de créer des listes d'invités pour différents week-ends: vous pouvez inviter des personnes correspondant aux sommets verts au week-end «vert», les sommets rouges au «rouge» ", Et ainsi de suite, et assurez-vous que des invités incompatibles figureront sur les listes les différents week-ends. Le nombre de couleurs que vous utilisez vous dira combien de jours de congé vous devrez prendre sur le calendrier.

De cet exemple, il s'ensuit que toute coloration valide du graphique de travail peut être transférée vers le produit tensoriel - vous pouvez simplement colorer chaque combinaison travail-passe-temps dans la même couleur que celle que vous avez utilisée pour le travail. Une telle coloration conduira au fait que lors des rassemblements, chaque couple d'invités sera compatible exclusivement en fonction de ses intérêts professionnels, quel que soit son passe-temps.

Et vice versa, toute coloration admissible du graphique de passe-temps est reportée sur le produit tensoriel. Hedetniemi a suggéré que la meilleure façon de colorer un graphique tensoriel serait d'avoir l'un des graphiques originaux avec un nombre minimal de couleurs.

À première vue, l'hypothèse de Hedetniemi semble peu probable. Après tout, si vous basez la coloration du tenseur sur la coloration du graphique de travail, vous ignorez tout ce que vous savez sur les passe-temps compatibles de vos amis et partagez potentiellement des invités qui s'entendent bien. Si vous combinez toutes les informations sur le travail et les loisirs, vous pourrez peut-être utiliser moins de fleurs et profiter d'un week-end bien mérité sans invités.

Et pourtant, pendant plus de 50 ans, les mathématiciens n'ont pas pu trouver un seul produit tensoriel, pour une coloration qui nécessiterait moins de couleurs que pour n'importe lequel de ses graphes constitutifs. Ils ont pu prouver que l'hypothèse était vraie s'il ne fallait pas plus de quatre couleurs pour colorer l'un des deux graphiques. Cela est également vrai dans le cas plus général des colorations «fractionnelles», lorsque chaque sommet peut se voir attribuer une combinaison de couleurs - par exemple, 2/3 jaune et 1/3 vert. (En termes de rassemblements de week-end, cela peut correspondre à une situation où il y a trois journalistes sur votre liste d'amis, dont l'un joue au tennis, et vous en avez invité deux au week-end «jaune» et le troisième au «vert»).

Ces résultats suggèrent que l'hypothèse pourrait être vraie, mais d'autres ont dit le contraire. Par exemple, les mathématiciens ont montré que l'hypothèse de Hedetniemi s'effondre pour les graphiques qui nécessitent un nombre infini de couleurs pour la coloration, ou pour les graphiques dirigés dont les bords ont des directions préférées. Mais, malgré le fait que les mathématiciens aient prouvé l'hypothèse de Hedetniemi dans certains cas, et l'ont réfutée pour d'autres, ils n'ont pas pu résoudre le problème dans le domaine que Hedetniemi lui-même considérait à l'origine: les graphes finis non orientés avec une coloration entière.

"Tout le monde pensait généralement que c'était vrai, mais il était difficile de le prouver ou de le réfuter", a déclaré Noga Elon de l'Université de Princeton.

Coloriages

Shitov a brisé toutes ces incertitudes avec une démonstration claire et simple de la fausseté de l'hypothèse Hedetniemi. Dans l'œuvre, dont la principale preuve tient sur une seule page, remplie de mathématiques, il montre comment créer un type spécial de produit tensoriel, qui nécessite moins de couleur à peindre que n'importe lequel de ses composants.

Shitov commence son travail en observant ce qui se passera si nous combinons le graphe G avec l'un de ses graphes exponentiels et obtenons leur produit tensoriel. Le graphe exponentiel a un nœud pour chacune des colorations possibles G avec un certain nombre fixe de couleurs (toutes les colorations possibles sont autorisées, pas seulement celles dont les sommets connectés ont des couleurs différentes). Si le graphique G, par exemple, a 7 sommets, et qu'il y a 5 couleurs dans notre palette, alors le graphique exponentiel aura 5 ⁷ sommets - c'est pourquoi il est appelé exponentiel.


L'hypothèse de Stephen Hedetniemi du nombre minimum de couleurs pour colorer le produit tensoriel des graphiques est restée non confirmée pendant plus de 50 ans

Si nous revenons à l'option de coloration, dans laquelle les sommets connectés doivent être de couleurs différentes, nous ne pouvons pas garantir que les cinq couleurs de notre palette seront suffisantes pour colorer le graphique G, et de la même manière, elles peuvent ne pas être suffisantes pour colorer le graphique exponentiel avec 5 ⁷ sommets . Cependant, les mathématiciens savent depuis longtemps qu'il existe un graphique pour lequel cinq couleurs suffisent: il s'agit d'un produit tensoriel constitué de G et de son graphique exponentiel.

En fait, tous les graphiques exponentiels ont cette propriété: un produit tensoriel qui combine un graphique exponentiel avec le graphique à partir duquel il a été créé peut être coloré avec exactement le même nombre de couleurs que le graphique d'origine. Shitov a réfuté l'hypothèse de Hedetniemi, montrant comment il est possible de créer un tel graphique G que plus de couleurs sont nécessaires pour le colorier à la fois lui et son graphique exponentiel.

Hedetniemi a déclaré qu'il était «complètement ravi» de la résolution de la situation avec son hypothèse après tant de décennies. Les preuves de Shitov "ont une certaine élégance, simplicité et pure qualité", écrit-il dans un e-mail.

Le nouveau contre-exemple s'est avéré rusé et inventif, disent les mathématiciens, et il n'a pas besoin d'outils mathématiques avancés complexes. "Pour un spécialiste de la théorie des graphes, cette conception peut être expliquée en deux phrases", a déclaré Kalai.

Pourquoi personne n'a remarqué cet argument depuis plus de 50 ans est un mystère pour les mathématiciens. "Parfois, un petit bijou se cache sous un tas de feuillage", a déclaré Hell. "Shitov a simplement réussi à comprendre cette question plus profondément que tout le monde."

Les graphiques de Shitov sont gigantesques: il n'a pas calculé leur taille exacte, mais estime que le graphique G aura probablement environ ^{4 100} sommets, et les graphiques exponentiels auront au moins ^{4 000} sommets, ce qui est beaucoup plus que le nombre approximatif de particules élémentaires dans univers observable [ environ 10 ⁸⁰ / env. perev. ].

Mais, bien sûr, tout dépend de l'observateur. Shitov estime que son contre-exemple «n'est pas si énorme. En mathématiques, vous pouvez trouver des contre-exemples, par rapport auxquels ce sera très petit. "

Et bien qu'il soit peu probable que vous puissiez inviter ^{4000 personnes} dans votre maison de campagne, le travail de Shitov ne rejette pas l'existence de contre-exemples d'une taille beaucoup plus petite. Mais maintenant que les mathématiciens savent que l'hypothèse de Hedetniemi est fausse, la question naturelle sera de savoir exactement comment elle est fausse: combien moins de couleurs peuvent être nécessaires pour colorer un produit tensoriel par rapport à ses graphiques constitutifs, et quel est le nombre minimum de nœuds et d'arêtes que peuvent avoir ces contre-exemples?

Pendant ce temps, Elon a déclaré que le nouveau travail contient une leçon importante pour tous les mathématiciens: "Parfois, la raison pour laquelle une hypothèse est si difficile à prouver est qu'elle est fausse."