Get best of the week

Der Regenbogennachweis zeigt das Vorhandensein von Standardkomponenten in Diagrammen

Mathematiker haben bewiesen, dass Kopien kleinerer Diagramme immer idealerweise größere Diagramme abdecken können.



Am 8. Januar veröffentlichten drei Mathematiker einen Beweis für einen Satz aus der Kombinatorik, der vor fast 60 Jahren formuliert wurde und als Ringel-Hypothese bekannt ist. Grob gesagt sagt sie voraus, dass Graphen - Konstruktionen aus Punkten und Linien - idealerweise aus identischen Stücken kleinerer Größe gefaltet werden können.

Mathematiker akzeptierten begeistert die Bestätigung dieser Hypothese.

"Das Glück ist, dass diese Arbeit eine sehr alte Hypothese löst, die mit anderen Methoden nicht verifiziert werden konnte", sagte Gil Kalai , Mathematiker an der Hebräischen Universität in Jerusalem, ohne Bezug zu dieser Arbeit.

Ringels Hypothese sagt voraus, dass spezielle Arten komplexer Graphen - mit Billionen von Eckpunkten und Kanten - "gekachelt" werden können, d.h. vollständig abdecken, mit separaten Kopien kleinerer Grafiken eines bestimmten Typs. Aus konzeptioneller Sicht ähnelt diese Frage der folgenden: Kann ich den Boden in der Küche mit denselben Kopien aller Fliesen im Geschäft vollständig verfliesen? Im wirklichen Leben sind die meisten Arten von Fliesen nicht für Ihre Küche geeignet. Um den Boden vollständig zu bedecken, müssen Sie ihre verschiedenen Formen kombinieren. In der Welt der Graphentheorie sagt die Hypothese jedoch voraus, dass Sie immer einen Graphen kacheln können.

In der Küche und in den Grafiken ist es wichtig, wo genau Sie die erste Fliese platzieren. Die neue Arbeit hebt dieses entscheidende Thema hervor - und zwar so, dass es sowohl überraschend als auch überraschend intuitiv ist.

Wald mit Bäumen


In der Kombinatorik untersuchen Mathematiker, wie sich Eckpunkte (Punkte) und Kanten (Linien) zu komplexeren Objekten zusammenfügen, die als Graphen bezeichnet werden. Sie können viele Fragen zu Grafiken stellen. Eine der grundlegenden: In welchen Fällen sind kleinere und einfachere Diagramme idealerweise in größere und komplexere Diagramme eingebettet?

"Sie haben eine Reihe von Puzzleteilen und wissen nicht, ob Sie sie aus diesen Teilen zusammensetzen können", sagte Jacob Fox von der Stanford University.

1963 wurde der deutsche Mathematiker Gerhard RingelEr stellte eine einfache, aber umfassendere Frage dieser Art. Beginnen wir, sagte er, mit einer ungeraden Anzahl von Eckpunkten größer als 3 (für die Plausibilität der Hypothese muss die Anzahl der Eckpunkte ungerade sein, wie wir später sehen werden). Verbinden Sie sie mit Kanten, sodass jeder Scheitelpunkt mit allen anderen verbunden ist. Dann erhalten wir ein Objekt, das als vollständiger Graph bezeichnet wird .



Stellen Sie sich dann ein Diagramm eines anderen Typs vor. Es kann ein einfacher Weg sein - mehrere Kanten in einer Linie verbunden. Oder ein Weg mit verzweigten Rippen. Zweige können zu anderen Zweigen hinzugefügt werden. Sie können ein beliebig komplexes Diagramm erstellen und dabei nur geschlossene Schleifen vermeiden. Solche Graphen werden Bäume genannt.



Ringels Frage bezieht sich auf die Beziehung von vollständigen Graphen und Bäumen. Er sagte: Stellen Sie sich zunächst einen vollständigen Graphen von 2n + 1 Eckpunkten vor (eine ungerade Zahl). Stellen Sie sich dann einen Baum vor, der aus n + 1 Eckpunkten besteht - und solche Bäume können sehr unterschiedlich sein.

Nehmen Sie nun einen dieser Bäume und platzieren Sie ihn so, dass jede Kante des Baums mit der Kante des gesamten Diagramms übereinstimmt. Dann platzieren wir eine weitere Kopie desselben Baums auf einem anderen Teil des gesamten Diagramms.

Ringel sagte voraus, dass Sie auf diese Weise und an der richtigen Stelle idealerweise den gesamten vollständigen Graphen überbrücken könnten. Dies bedeutet, dass jede Kante des gesamten Diagramms von der Kante des Baums abgedeckt wird und sich Kopien der Bäume nicht überlappen.



„Ich kann Kopien des Baumes machen. Ich habe eine Kopie in die vollständige Grafik eingefügt. Sie bedeckt einige Rippen. Dann wiederhole ich den Vorgang. Die Hypothese legt nahe, dass dies alles abdecken kann “, sagte Benny Sudakov von der Eidgenössischen Technischen Hochschule, Co-Autor der neuen Beweise, zusammen mit Richard Montgomery von der Universität Birmingham und Alexei Pokrovsky vom Birkbeck College der Universität London.

Schließlich sagte Ringel voraus, dass das Diagramm unabhängig von den vielen Baumoptionen, die Sie verwenden werden, gekachelt werden kann. Eine solche Aussage mag zu allgemein erscheinen. Ringels Vermutung gilt sowohl für vollständige Diagramme mit 11 Eckpunkten als auch für vollständige Diagramme mit 11 Billionen + 1 Eckpunkten. Und je größer das vollständige Diagramm ist, desto mehr mögliche Bäume können für n + 1 Eckpunkte gezeichnet werden. Wie kann jeder von ihnen idealerweise den entsprechenden vollständigen Graphen überbrücken?

Es gab jedoch Gründe zu der Annahme, dass Ringels Hypothese wahr sein könnte. Die allererste Bestätigung war, dass die einfachste kombinatorische Arithmetik eine solche Option nicht ausschloss: Die Anzahl der Kanten in einem vollständigen Diagramm mit 2n + 1 Eckpunkten kann immer vollständig durch die Anzahl der Kanten in einem Baum mit n + 1 Eckpunkten geteilt werden.

"Die Tatsache, dass die Anzahl der Kanten eines vollständigen Diagramms durch die Anzahl der Kanten eines Baums geteilt wird, ist sehr wichtig", sagte Montgomery.

Mathematiker fanden schnell weitere Beweise für die Plausibilität der Hypothese, was eine Reihe von Entdeckungen auslöste, die schließlich zum Beweis führten.

Platzieren und wenden


Einer der einfachsten Bäume ist ein Stern: ein zentraler Gipfel, von dem Kanten ausgehen. Es unterscheidet sich jedoch vom typischen Bild eines Sterns, da die Kanten nicht gleichmäßig über die Oberseite verteilt sein müssen. Sie müssen alle nur von einem Ort kommen und sollten sich nur auf dem zentralen Gipfel kreuzen. Wenn Sie die Richtigkeit der Ringel-Hypothese beweisen möchten, ist ein sternförmiger Baum ein natürlicher Ausgangspunkt.



Und natürlich entdeckten Mathematiker schnell, dass ein Stern mit n + 1 Eckpunkten immer einen vollständigen Graphen mit 2n + 1 Eckpunkten perfekt abbildet. Diese Tatsache ist an sich interessant, aber ihre Beweise ließen Mathematiker weiter nachdenken.

Nehmen Sie ein einfaches Beispiel. Beginnen wir mit 11 Peaks. Wir platzieren sie in einem Kreis und verbinden jeden Scheitelpunkt mit allen anderen, um ein vollständiges Diagramm zu erhalten.



Betrachten Sie nun den ihm entsprechenden Stern: den Mittelpunkt mit fünf von ihm ausgehenden Kanten.



Jetzt platzieren wir den Stern so, dass der zentrale Scheitelpunkt mit einem der Scheitelpunkte des gesamten Graphen übereinstimmt. Wir werden mehrere Kanten abdecken, aber nicht alle. Bewegen Sie nun den Stern um einen Scheitelpunkt, als ob Sie das Kompassrad drehen würden. Wir erhalten eine neue Kopie des Sterns, der einem völlig anderen Satz von Kanten des gesamten Graphen überlagert ist.

Wir werden den Stern weiter drehen. Wenn wir wieder dort sind, wo wir angefangen haben, werden wir das gesamte Diagramm ohne Überlagerung von Sternen pflastern - genau wie Ringel es vorhergesagt hat.



"Wir wissen, dass eine Hypothese nicht sofort verworfen werden kann, zumindest wenn wir einen Baum in Form eines Sterns nehmen", sagte Sudakov. "Darüber hinaus können wir dies sogar sehr schön demonstrieren: Zeichnen Sie eine Grafik auf einen Kreis, verschieben Sie einen Stern, erhalten Sie neue Kopien und ersetzen Sie die gesamte Grafik."

Kurz nachdem Ringel seine Hypothese aufgestellt hatte, verwendete der slowakisch-kanadische Mathematiker Anton Kotzig dieses Beispiel für eine noch kühnere Vorhersage als die von Ringel. Ringel sagte, dass jeder vollständige Graph mit einem 2n + 1-Scheitelpunkt mit jedem Baum mit einem n + 1-Scheitelpunkt gekachelt werden kann. Kotzig schlug vor, dass er genauso gekachelt werden kann wie mit einem Stern: indem man den Baum auf einen vollständigen Graphen legt und ihn einfach dreht.

Die Idee schien unrealistisch. Der Stern ist symmetrisch, egal wie er platziert werden soll. Die meisten Bäume sind schief. Sie müssen auf eine ganz bestimmte Weise platziert werden, damit die Rotationsmethode funktioniert.

"Der Stern war eine einfache Struktur, die manuell platziert werden kann. Wenn Sie jedoch einen sich ausbreitenden Baum mit einer Reihe von Zweigen unterschiedlicher Länge an Ihren Händen haben, ist es schwer vorstellbar, wie er sorgfältig platziert werden kann", sagte Pokrovsky.

Um die Ringel-Hypothese mit der Kotsig-Rotationsmethode zu lösen, mussten Mathematiker herausfinden, wie die erste Kopie des Baumes platziert werden sollte, damit keine unpassierbaren Dickichte entstehen. Zum Glück fanden sie eine farbenfrohe Lösung.

Regenbogenfarben erleichtern oft das Leben. Es hilft Ihnen, einen Kalender zu organisieren oder einen Lebensmittelbehälter in einer großen Familie schnell von einem anderen zu unterscheiden. Es stellt sich heraus, dass dies auch ein effektiver Weg sein kann, um herauszufinden, wie der erste Baum korrekt in einem vollständigen Diagramm platziert wird.

Stellen Sie sich noch einmal ein vollständiges Diagramm mit 11 in einem Kreis angeordneten Eckpunkten vor. Markieren Sie die Kanten mit Farbcodes nach einer einfachen Regel, die den Abstand zwischen zwei Scheitelpunkten berücksichtigt.

Dieser Abstand wird durch die Anzahl der Schritte bestimmt, die ausgeführt werden müssen, um in einem Kreis von einem Scheitelpunkt zum anderen zu gelangen (ohne den Pfad innerhalb des Kreises zu schneiden). Natürlich können Sie in einem Kreis immer in zwei Richtungen gehen, daher definieren wir die Entfernung als den kürzesten Weg zwischen zwei Gipfeln. Wenn dies benachbarte Scheitelpunkte sind, beträgt der Abstand zwischen ihnen 1 und nicht 10. Wenn sie durch einen Scheitelpunkt getrennt sind, beträgt der Abstand 2.



Nun färben wir die Kanten des Diagramms entsprechend dem Abstand. Wir malen alle Kanten, die die in einem Abstand von 1 befindlichen Spitzen verbinden, in einer Farbe - zum Beispiel blau. Wir malen alle Kanten, die die Spitzen verbinden, die sich in einem Abstand von zwei Einheiten in der anderen befinden - zum Beispiel gelb.

Wir färben das Diagramm weiterhin so, dass alle Kanten, die die Scheitelpunkte verbinden, die sich im gleichen Abstand befinden, dieselbe Farbe haben. Unterschiedliche Abstände werden in unterschiedlichen Farben codiert. Für ein vollständiges Diagramm mit 2n + 1 Eckpunkten benötigen Sie dafür n Farben. Das Ergebnis ist ein schönes und nützliches Bild.



Kurz nachdem Ringel und Kotzig ihre Hypothesen aufgestellt hatten, erkannte Kotzig, dass das Färben seines vollständigen Diagramms ein Leitfaden für das Platzieren eines Baumes sein könnte.

Die Idee ist, den Baum so anzuordnen, dass er eine Kante jeder Farbe bedeckt und keine Farbe zweimal bedeckt. Mathematiker nennen dieses Arrangement eine Regenbogennachbildung eines Baumes. Da für das Färben n Farben erforderlich sind und ein Baum mit n + 1 Eckpunkten n Kanten hat, wissen wir sofort, dass mit hoher Wahrscheinlichkeit eine Regenbogenkopie gefunden werden kann.



Ende der 1960er Jahre haben Mathematiker verstanden, dass eine Regenbogenkopie eines Baumes eine besondere Eigenschaft hat: Sie gibt nur die Position an, von der aus Sie den gesamten Graphen durch Drehen des Baums überbrücken können.

"Wenn Sie eine Regenbogenkopie machen, wird alles funktionieren", sagte Pokrovsky.

Danach wussten die Mathematiker bereits, dass sie die Ringel-Hypothese beweisen konnten, indem sie bewiesen, dass jeder vollständige Graph mit 2n + 1 Eckpunkten eine Regenbogenkopie eines Baumes mit n + 1 Eckpunkten enthielt. Und wenn immer eine Regenbogenkopie vorhanden ist, können Sie die Grafik jederzeit überbrücken.

Es ist jedoch schwierig zu beweisen, dass immer etwas existiert. Dafür müssten Mathematiker zeigen, dass vollständige Grafiken einfach nur Regenbogenkopien von Bäumen enthalten können. Es hat mehr als 40 Jahre gedauert, aber genau das haben Sudakov und seine Mitautoren in einer neuen Arbeit erreicht.

Perfekte Verpackung


Angenommen, Sie haben ein vollständiges Diagramm mit 11 Eckpunkten und einen Baum mit sechs erhalten. Das vollständige Diagramm ist in fünf verschiedenen Farben dargestellt. Der Baum hat fünf Kanten. Ihre Aufgabe ist es, eine Regenbogenkopie des Baums in der vollständigen Grafik zu finden.

Sie können einfach die Ränder des Baums der Reihe nach in das Diagramm einfügen. Die erste ist einfach zu platzieren: Sie können eine beliebige Kante einer beliebigen Farbe dafür auswählen. Der zweite wird etwas schwieriger sein. Es kann fast überall liegen, außer an der Rippe mit der gleichen Farbe wie die gerade bedeckte. Und je mehr Sie die Kanten des Baumes platzieren, desto schwieriger wird die Aufgabe. Wenn Sie die letzte Rippe erreicht haben, verlieren Sie die Wahl der Farbe vollständig - es wird nur eine geben. Es bleibt zu hoffen, dass Sie alles frühzeitig geplant haben.

Diese Idee, dass das Auffinden einer Regenbogenkopie eines Baums komplizierter wird, wenn Sie mehr und mehr Kanten des Baums in der Grafik platzieren, war ein notwendiger Teil der Methode, mit der drei Mathematiker dieses Problem lösten. Sie suchten nach Möglichkeiten, um gegen Ende des Prozesses so viel Flexibilität wie möglich zu erhalten.

Von Anfang an wussten sie, dass Regenbogenkopien sehr einfacher Bäume leicht zu finden sein würden - Bäume, die wie ein langer Weg aussahen, ohne Äste oder mit einer kleinen Anzahl von ihnen. Am schwierigsten war es, die Bäume mit vielen Kanten, die an einem Punkt zusammenlaufen, richtig zu platzieren - wie Sterne, nur mit einer unebeneren und unregelmäßigeren Form. Sie zu platzieren ist, als würde man einen Kinderwagen in einen halb gefüllten Kofferraum eines Autos schieben.

"Die Schwierigkeit beginnt, wenn Sie versuchen, ein vollständiges Diagramm mit so unangenehmen Dingen zu füllen, die wie Sterne aussehen", sagte Pokrovsky.

Jeder, der den Kofferraum füllt, weiß, dass Sie immer mit den komplexesten Objekten beginnen müssen - großen Koffern und großen unflexiblen Dingen wie Fahrrädern. Jacken können dann immer geschoben werden. Und Mathematiker haben diese Philosophie übernommen.

Stellen Sie sich einen Baum mit 11 Kanten vor. Sechs von ihnen laufen an einem zentralen Punkt zusammen. Fast alle anderen bilden eine einzige Form, die von der Hauptform entfernt ist.



Am schwierigsten zu platzieren ist der Teil des Baumes, der aus einem Gipfel mit sechs Kanten besteht. Daher trennten Mathematiker es vom Rest des Baumes und platzierten es zuerst, um diesen Teil später zu befestigen - als ob Sie beschlossen hätten, das Bett auseinanderzunehmen, bevor Sie es in den zweiten Stock ziehen und es dann im gewünschten Raum wieder zusammenbauen. Sie haben diesen Teil des Sterns nicht einmal in der Grafik platziert - sie haben verschiedene Stellen gefunden, an denen die Kopien in der gesamten Grafik platziert werden können.

Und dann wählten sie zufällig eine Kopie aus. Auf diese Weise stellten sie sicher, dass der verbleibende freie Speicherplatz im Diagramm ebenfalls zufällig war - dh mit einer ungefähr gleichen Verteilung der Kanten verschiedener Farben. An diesem Ort mussten sie den Rest des Baumes platzieren - den Weg, den sie zuerst beiseite legten.

Bei der Auswahl der Optionen für die Platzierung waren sie Einschränkungen ausgesetzt. Der Pfad sollte mit dem Stern verbunden sein - dem Teil des Baumes, den sie bereits platziert haben, und er musste auch Farben abdecken, die zuvor nicht von dem Stern bedeckt waren, mit dem er verbunden ist.

Aber Mathematiker haben Optionen für sich gelassen. Sie konnten den Weg mit fast jeder der verschiedenen Kopien des Sterns verbinden. Was noch besser ist, da der Raum um den Stern zufällig war, hatten sie die Möglichkeit, verschiedene Farben auszuwählen, um sie mit dem Rest des Baumes zu bedecken.

"Gegen Ende des Baumbaus, wenn die Situation kompliziert wird, habe ich nicht mehr eine obligatorische Farbe, sondern eine kleine Auswahl", sagte Montgomery.

Drei Mathematiker vervollständigen ihren Beweis mit einem Argument aus der Wahrscheinlichkeitstheorie. Sie zeigten, dass Sie nach dem Einbetten der komplexesten Teile der Bäume, sofern der in der vollständigen Spalte verbleibende Platz im Wesentlichen zufällig war, immer einen Weg finden können, den Rest der Bäume einzubauen, um eine Regenbogenkopie zu erhalten.

"Jetzt können Sie erzwingen, was Sie von Anfang an verschoben haben, als ob Sie die Reste des Baumes aufsaugen und eine vollständige Regenbogenfarbe erhalten möchten", sagte Noga Alon von der Princeton University.

Mathematiker haben nicht genau beschrieben, wie eine Regenbogenkopie für jeden Baum mit n + 1 Eckpunkten in jedem vollständigen Diagramm mit 2n + 1 Eckpunkten gefunden werden kann. Sie haben jedoch bewiesen, dass eine Regenbogenkopie darin sein muss.

Und wenn immer eine Regenbogenkopie vorhanden ist, können Sie den Graphen immer mit der von Ringel vorhergesagten Methode überbrücken. Somit ist seine Hypothese wahr.

Der Beweis bietet auch neue Werkzeuge zur Lösung ähnlicher ungelöster Probleme in der Kombinatorik - zum Beispiel das Problem des „anmutigen Markups“, das vorhersagt, dass ein vollständiger Graph auch unter strengeren Bedingungen gekachelt werden kann, nach denen die Bäume noch genauer platziert werden müssen.

"Es zeigt, dass die Methoden, über die die Menschen lange nachgedacht haben, wirklich ein großes Potenzial haben", sagte Fox. "Wenn Sie sie richtig anwenden, können Sie Probleme lösen, die zuvor uneinnehmbar erschienen."

More articles:


All Articles