Der russische Mathematiker widerlegt die 53 Jahre alte Hypothese über die Färbung von Netzwerken

Der russische Mathematiker benötigte nur drei Seiten, um eine Methode zum Färben von Netzwerken eines bestimmten Typs zu beschreiben, die die Erwartungen von Experten übertraf

Eine 53 Jahre alte Hypothese, wie Netzwerkknoten am besten Farben zugewiesen werden können, wird in einem Online- Artikel widerlegt. Die Arbeit auf nur drei Seiten zeigt die Existenz von Methoden zum Färben bestimmter Farben, die alle Erwartungen von Experten übertroffen haben.

Aufgaben zum Färben von Netzen [ siehe chromatische Zahl / ca. perev. ], inspiriert von der Frage einer solchen Färbung von Karten, in denen Nachbarländer unterschiedliche Farben haben, stehen seit fast 200 Jahren im Fokus der Forschung von Mathematikern. Die Aufgabe besteht darin, zu verstehen, wie die Knoten eines bestimmten Netzwerks (oder eines Diagramms , wie ihre Mathematiker sie nennen) so gefärbt werden, dass zwei verbundene Knoten unterschiedliche Farben haben. Je nach Kontext bietet diese Farbgebung eine effektive Möglichkeit, Gäste bei einer Hochzeit unterzubringen, Produktionsaufgaben für freie Zeitintervalle zu arrangieren oder sogar Sudoku zu lösen.

Aufgaben zum Färben von Grafiken sind oft einfach zu formulieren, aber unglaublich schwer zu lösen. Sind auf der Suche nach einer Antwort auf die Frage, mit der dieses gesamte Forschungsfeld begann, vier Farben genug, um eine Karte einzufärben ? - Es hat mehr als hundert Jahre gedauert (wenn Sie interessiert sind, lautet die Antwort ja).

Die bisher in der neuen Arbeit berücksichtigte Aufgabe wurde nicht als Ausnahme angesehen. Es konnte seit mehr als 50 Jahren nicht mehr gelöst werden und betrifft Tensorprodukte - Graphen, die aus einer speziellen Kombination zweier verschiedener Graphen bestehen (nennen wir sie G und H). Das Tensorprodukt der Graphen G und H ist ein neuer, größerer Graph, von dem jeder Scheitelpunkt ein Paar von Scheitelpunkten der ursprünglichen Graphen bezeichnet - einen von G und einen von H -, während zwei Scheitelpunkte des Tensorprodukts verbunden sind, wenn beide die entsprechenden Scheitelpunkte in G und ihre entsprechenden Eckpunkte in H.

Angenommen, Sie sind Musiklehrer und müssen gute Duettpaare für ein Konzert im fünften Jahr finden. Sie können ein Diagramm erstellen, dessen Eckpunkte Schüler sind, und die Bindungen zwischen den Paaren zeigen das Vorhandensein guter Beziehungen zwischen ihnen an. Dann können Sie ein zweites Diagramm erstellen, in dem jeder Knoten unterschiedliche Musikinstrumente anzeigt, und die Verbindung zwischen ihnen ist das Vorhandensein von Notenblättern für ein Duett dieser beiden Instrumente. Im Tensorprodukt dieser beiden Graphen gibt es einen Scheitelpunkt für jede mögliche Vereinigung von Schüler und Instrument (z. B. Alice und Posaune), und die beiden Scheitelpunkte werden verbunden, wenn zwei Schüler gut zusammenarbeiten und die beiden Instrumente kompatibel sind.

Im Jahr 1966 schlug Stephen Hedetniemi , heute Professor an der Clemson University in South Carolina, in seiner Dissertation vor, dass die Mindestanzahl von Farben, die zum Färben eines Tensorprodukts erforderlich ist, die kleinste der beiden Farben ist, die zum Färben eines der beiden Diagramme benötigt werden . "Dies ist eine der wichtigsten Hypothesen in der Graphentheorie", sagte Gil Kalai von der Hebrew University in Jerusalem. "Viele Leute haben versucht, über sie nachzudenken."

In den letzten Jahrzehnten haben Mathematiker einen Berg von Beweisen gesammelt, von denen einige über die Wahrheit der Hypothese und andere über ihre Falschheit sprachen. Verschiedene Mathematiker hatten unterschiedliche Annahmen darüber, welche Option letztendlich gewinnen würde. Aber alle waren sich einig, dass es zumindest eine schwierige Aufgabe war.

"Ich persönlich dachte, diese Hypothese sei wahr, da eine große Anzahl kluger Leute sie studierte und ein Gegenbeispiel entwickeln müsste", sagte Anthony Bonato von der Ryerson University in Toronto.

Und so entwickelte der russische Mathematiker Jaroslaw Nikolajewitsch Schitow eine einfache Möglichkeit, Gegenbeispiele zu erstellen, Tensorarbeiten, die weniger Farben erfordern als alle beiden Graphen, aus denen sie bestehen. Die Beweise kamen "elementar, aber brillant" heraus, sagte Pavol Hell von der Simon Fraser University in Burnaby, Kanada.

Tensordiagramme stehen in engem Zusammenhang mit Fragen zur Abbildung verschiedener Diagramme aufeinander, und in diesem Bereich der Mathematik war die Hedetniemi-Hypothese wahrscheinlich das größte offene Problem, sagte Hell. "Dies ist ein großer Durchbruch."

Bunte Treffpunkte

Um sich vorzustellen, welche Informationen aus dem Färben des Tensordiagramms extrahiert werden können, stellen Sie sich vor, Sie werden Ihre Freunde jedes Wochenende in Ihr Vorort-Anwesen einladen. Und als guter Gastgeber möchten Sie Menschen zusammenbringen, die sich gegenseitig amüsieren.

Sie wissen, dass einige Ihrer Freunde aufgrund ihrer Arbeit schnell Freunde finden können, andere nicht. Sie wissen auch, dass Ihre Freunde ein Hobby haben - ein weiterer Weg, auf dem Gäste gemeinsame Interessen finden können. Sie spekulieren, dass ein Geigen-Tanzlehrer eine gute Zeit haben kann, mit einem Yogalehrer zu sprechen, der Tennis spielt oder Musik mit einem Bauern bespricht, der Ahornsirup herstellt und Klavier spielt, aber wahrscheinlich nicht über ihn dann wird er mit einem Politikwissenschaftler sprechen, der Briefmarken sammelt. Sie möchten, dass jedes Paar von Gästen an jedem Wochenende gemeinsame Interessen findet, sei es ein Job oder ein Hobby, und Sie fragen sich, wie viele Versammlungen Sie arrangieren müssen, um alle Gäste aus der Liste herauszusuchen.


Yaroslav Shitov entdeckte ein Gegenbeispiel der 53 Jahre alten Hedetniemi-Hypothese aus der Graphentheorie

Sie können sich die Beziehung verschiedener Arten von Arbeiten in Form eines Diagramms vorstellen, dessen Knoten die Arbeit sein werden, und zwei beliebige Arbeiten werden durch Kanten verbunden, zwischen denen es höchstwahrscheinlich nicht möglich sein wird, gemeinsame Gesprächsthemen zu finden (dieser Ansatz scheint jedoch im Zusammenhang mit der Färbung auf den Kopf gestellt zu sein Graphen Eine solche Verbindung von Eckpunkten ist sinnvoll, da wir Farben verwenden werden, um diese problematischen Paare zu trennen. Sie können auch ein Diagramm erstellen, dessen Eckpunkte unterschiedliche Hobbys sind, und alle inkompatiblen miteinander verbinden.

Das Tensorprodukt dieser beiden Diagramme hat Knoten für jedes Work-Hobby-Paar, und die beiden Eckpunkte werden kombiniert, wenn sowohl Arbeit als auch beide Hobbys nicht kompatibel sind - genau diese Situation möchten Sie am Wochenende vermeiden. Wenn Sie die Scheitelpunkte des Tensorprodukts so färben können, dass die durch die Rippen verbundenen Scheitelpunkte unterschiedliche Farben haben, können Sie auf diese Weise Gästelisten für verschiedene Wochenenden erstellen: Sie können Personen, die grünen Scheitelpunkten entsprechen, zum „grünen“ Wochenende, rote Scheitelpunkte zum „roten“ einladen. ", Und so weiter, und stellen Sie sicher, dass inkompatible Gäste an verschiedenen Wochenenden auf den Listen stehen. Die Anzahl der verwendeten Farben gibt an, wie viele freie Tage Sie für den Kalender benötigen.

Aus diesem Beispiel folgt, dass jede gültige Färbung des Arbeitsgraphen auf das Tensorprodukt übertragen werden kann. Sie können einfach jede Arbeit-Hobby-Kombination in derselben Farbe färben, die Sie für die Arbeit verwendet haben. Eine solche Färbung führt dazu, dass bei den Versammlungen jedes Gästepaar unabhängig von seinem Hobby ausschließlich nach seinen beruflichen Interessen kompatibel ist.

Und umgekehrt wird jede zulässige Färbung des Hobbygraphen auf das Tensorprodukt übertragen. Hedetniemi schlug vor, dass der beste Weg zum Färben eines Tensordiagramms darin besteht, dass eines der Originaldiagramme eine minimale Anzahl von Farben aufweist.

Auf den ersten Blick erscheint die Hedetniemi-Hypothese unwahrscheinlich. Wenn Sie die Tensorfarbe auf die Farbe des Arbeitsdiagramms stützen, ignorieren Sie schließlich alles, was Sie über die kompatiblen Hobbys Ihrer Freunde wissen, und teilen möglicherweise Gäste, die miteinander auskommen. Wenn Sie alle Informationen über Arbeit und Hobbys kombinieren, können Sie möglicherweise weniger Blumen verwenden und ein wohlverdientes Wochenende ohne Gäste genießen.

Und doch konnten Mathematiker seit mehr als 50 Jahren kein einziges Tensorprodukt zum Färben finden, für das weniger Farben erforderlich wären als für einen seiner Bestandteile. Sie konnten beweisen, dass die Hypothese wahr ist, wenn nicht mehr als vier Farben erforderlich sind, um einen der beiden Graphen zu färben. Dies gilt auch für den allgemeineren Fall von „gebrochenen“ Färbungen, bei denen jedem Scheitelpunkt eine Kombination von Farben zugewiesen werden kann - beispielsweise 2/3 Gelb und 1/3 Grün. (In Bezug auf Wochenendversammlungen kann dies einer Situation entsprechen, in der drei Journalisten auf Ihrer Freundesliste stehen, von denen einer Tennis spielt und Sie zwei von ihnen zum „gelben“ Wochenende und den dritten zum „grünen“ eingeladen haben.)

Diese Ergebnisse legen nahe, dass die Hypothese wahr sein könnte, aber andere sagten das Gegenteil. Zum Beispiel haben Mathematiker gezeigt, dass die Hedetniemi-Hypothese für Graphen, die eine unendliche Anzahl von Farben zum Färben erfordern, oder für gerichtete Graphen, deren Kanten Vorzugsrichtungen haben, auseinanderfällt. Trotz der Tatsache, dass Mathematiker die Hedetniemi-Hypothese in einigen Fällen bewiesen und in anderen widerlegt hatten, konnten sie das Problem auf dem Gebiet, das Hedetniemi ursprünglich selbst in Betracht gezogen hatte, nicht lösen: endliche ungerichtete Graphen mit ganzzahliger Färbung.

"Alle dachten im Allgemeinen, es sei wahr, aber es war schwierig, es zu beweisen oder zu widerlegen", sagte Noga Elon von der Princeton University.

Malvorlagen

Shitov zerschmetterte all diese Unsicherheiten mit einer klaren und einfachen Demonstration der Falschheit der Hedetniemi-Hypothese. In der Arbeit, deren Hauptbeweis auf eine mit Mathematik gefüllte Seite passt, zeigt er, wie man eine spezielle Art von Tensorprodukt herstellt, dessen Lackierung weniger Farbe erfordert als jede seiner Komponenten.

Shitov beginnt seine Arbeit mit der Beobachtung, was passieren wird, wenn wir den Graphen G mit einem seiner Exponentialgraphen kombinieren und ihr Tensorprodukt erhalten. Der Exponentialgraph hat einen Knoten für jede der möglichen Färbungen G mit einer bestimmten festen Anzahl von Farben (alle möglichen Färbungen sind zulässig, nicht nur diejenigen, für die die verbundenen Scheitelpunkte unterschiedliche Farben haben). Wenn der Graph G beispielsweise 7 Eckpunkte hat und unsere Palette 5 Farben enthält, hat der Exponentialgraph 5 ⁷ Eckpunkte - weshalb er als Exponential bezeichnet wird.


Stephen Hedetniemis Hypothese der Mindestanzahl von Farben zum Färben des Tensorprodukts von Graphen ist seit über 50 Jahren unbestätigt

Wenn wir zur Farboption zurückkehren, bei der die verbundenen Scheitelpunkte unterschiedliche Farben haben müssen, können wir nicht garantieren, dass die fünf Farben unserer Palette ausreichen, um den Graphen G zu färben, und auf die gleiche Weise reichen sie möglicherweise nicht aus, um den Exponentialgraphen mit 5 bis ⁷ Scheitelpunkten zu färben . Mathematiker wissen jedoch seit langem, dass es einen Graphen gibt, für den fünf Farben ausreichen: Es ist ein Tensorprodukt, das aus G und seinem Exponentialgraphen besteht.

Tatsächlich haben alle Exponentialgraphen diese Eigenschaft: Ein Tensorprodukt, das einen Exponentialgraphen mit dem Graphen kombiniert, aus dem er erstellt wurde, kann mit genau der gleichen Anzahl von Farben wie der Originaldiagramm gefärbt werden. Shitov widerlegte die Hedetniemi-Hypothese und zeigte, wie es möglich ist, einen solchen Graphen G zu erstellen, dass mehr Farben erforderlich sind, um ihn und seinen Exponentialgraphen zu färben.

Hedetniemi erklärte, er sei mit seiner Hypothese nach so vielen Jahrzehnten „völlig begeistert“ von der Lösung der Situation. Shitovs Beweise "haben eine gewisse Eleganz, Einfachheit und Qualität", schrieb er in einer E-Mail.

Das neue Gegenbeispiel erwies sich laut Mathematikern als gerissen und erfinderisch und benötigt keine komplexen fortgeschrittenen mathematischen Werkzeuge. "Für einen Spezialisten für Graphentheorie kann dieses Design in zwei Sätzen erklärt werden", sagte Kalai.

Warum dieses Argument seit mehr als 50 Jahren niemand mehr bemerkt hat, ist Mathematikern ein Rätsel. "Manchmal versteckt sich ein kleiner Edelstein unter einem Laubhaufen", sagte die Hölle. "Shitov hat es einfach geschafft, diese Frage tiefer zu verstehen als alle anderen."

Shitovs Graphen erweisen sich als gigantisch: Er hat ihre genaue Größe nicht berechnet, schätzt jedoch, dass Graph G wahrscheinlich ungefähr ^4.100 Eckpunkte haben wird und Exponentialgraphen mindestens ^4.000 Eckpunkte haben werden, d. H. Viel mehr als die ungefähre Anzahl von Elementarteilchen in beobachtbares Universum [ ca. 10 ⁸⁰ / ca. perev. ].

Aber natürlich hängt alles vom Beobachter ab. Shitov glaubt, dass sein Gegenbeispiel „nicht so groß ist. In der Mathematik gibt es Gegenbeispiele, bei denen dies sehr klein sein wird. "

Und obwohl es unwahrscheinlich ist, dass Sie ^4.000 in Ihr Landhaus einladen können, lehnt Shitovs Arbeit die Existenz von Gegenbeispielen von viel kleinerer Größe nicht ab. Aber jetzt, da Mathematiker wissen, dass die Hedetniemi-Hypothese falsch ist, wird die natürliche Frage sein, wie genau sie falsch ist: Wie weniger Farben können benötigt werden, um ein Tensorprodukt im Vergleich zu seinen konstituierenden Graphen zu färben, und wie viele Knoten und Kanten können solche Gegenbeispiele mindestens haben?

In der Zwischenzeit sagte Elon, dass die neue Arbeit eine wichtige Lektion für alle Mathematiker enthält: "Manchmal ist der Grund, warum eine Hypothese so schwer zu beweisen ist, dass sie falsch ist."