Get best of the week

Regenbogenfarben sind die besten Freunde der Mathematiker

In letzter Zeit haben Regenbogenfarben dazu beigetragen, einen neuen Beweis zu erbringen. Und sie sind nicht das erste Mal, dass sie nützlich sind.



Die Farbcodierung des lateinischen Quadrats und seiner Grafik kann viel darüber aussagen.

Kürzlich haben wir über einen neuen Beweis der Ringel-Hypothese gesprochen . Ein Teil der Beweise war mit der Verwendung von Regenbogenfarben verbunden, einer speziellen Art der Farbcodierung zur Visualisierung von Informationen. Solche Malbücher werden jedoch seit langem von Mathematikern verwendet, um das Lösen von Rätseln zu erleichtern, und jetzt versuchen sie, diese Technik auf das mit dem vorherigen Problem verbundene Problem anzuwenden.

Die Ringel-Hypothese ist ein Problem aus dem Bereich der Kombinatorik im Zusammenhang mit der Konstruktion von Graphen - Punkten (Eckpunkten), die durch Linien (Kanten) verbunden sind. Es wird eine spezielle Beziehung zwischen großen Graphen eines bestimmten Typs mit 2n + 1 Eckpunkten und proportional kleineren Graphen mit n + 1 Eckpunkten vorhergesagt.

Beginnen wir zum Beispiel mit 11 Peaks. Verbinden Sie jeden Scheitelpunkt mit allen anderen, um den sogenannten zu erhalten vollständige Grafik. Nehmen Sie als nächstes sechs der verfügbaren Scheitelpunkte und verbinden Sie sie nach Belieben, damit wir keine geschlossenen Schleifen erhalten. So bekommen wir das sogenannte "Holz".


Beispiele für vollständige Grafiken und Bäume.

Ringels Hypothese besagt, dass Kopien eines jeden Baumes idealerweise alle Kanten der entsprechenden vollständigen Grafik bedecken oder kacheln können - genauso wie Sie den Küchenboden mit denselben Fliesen kacheln können.



Wie beim Küchenboden ist es für den Erfolg notwendig, die richtige Position der ersten Fliese zu wählen. Die drei Mathematiker, die den Proof erstellt haben, haben die Kanten des gesamten Diagramms anhand des Abstands zwischen den Scheitelpunkten codiert, um diesen Ort zu finden.



Dann versuchten sie, den Baum so im gesamten Diagramm anzuordnen, dass er eine Kante jeder Farbe bedeckte. Nachdem sie gezeigt hatten, dass eine solche „Regenbogen“ -Anordnung auf jeden Fall möglich ist, haben sie bewiesen, dass die von Ringel vorhergesagten idealen Kacheln immer funktionieren.

Diese Technik der Regenbogenfärbung kam jedoch nicht zum ersten Mal zur Rettung.

Im 18. Jahrhundert interessierte sich Leonard Euler für etwas wie Sudoku für Kinder. Nimm ein Quadrat mit 3x3 Zellen. Euler füllte es so, dass es in jeder Zeile und jeder Spalte Zahlen von 1 bis 3 gab, die sich nie wiederholten. Dieses Puzzle heißt das lateinische Quadrat . Muster und Techniken, die Euler und andere Mathematiker beim Studium der lateinischen Quadrate entdeckt haben, haben einen Zusammenhang mit vielen verschiedenen Bereichen der Mathematik.



Dann fragte sich Euler: Ist es möglich, drei Zellen auszuwählen, eine aus jeder Spalte und jeder Zeile, damit sich die Zahlen in ihnen nicht wiederholen? Angenommen, Sie können eine Zelle aus der ersten Spalte der ersten Zeile mit 1, eine Zelle aus der zweiten Zeile der zweiten Spalte mit 3 und aus der dritten Zeile der dritten Spalte mit 2 auswählen. Wir haben also drei Zellen ausgewählt, von denen jede zu verschiedenen Zeilen und Spalten gehört. und enthält seine Nummer - 1, 3, 2. Diese Gruppe von Zellen wird als transversal bezeichnet.



Euler wollte wissen, ob es möglich ist, das gesamte 3x3-Gitter (oder ein quadratisches Gitter beliebiger Größe) vollständig in Quersätze zu unterteilen, sodass jeder Satz eine Nummer aus jeder Zeile und jeder Spalte enthält. Das heißt, im Fall eines 3x3-Quadrats möchte ich hoffen, dass wir drei verschiedene Transversalsätze finden können, die alle Zellen des Quadrats zusammen abdecken.

Infolgedessen haben Mathematiker herausgefunden, dass eine Möglichkeit, dieses Problem zu untersuchen, darin besteht, ein Quadrat in ein Diagramm umzuwandeln. Zeichnen Sie dazu links drei Eckpunkte mit drei Spalten. Dann zeichnen wir rechts drei Eckpunkte, die die Linien darstellen. Zeichnen Sie die Kanten, die jeden Scheitelpunkt rechts mit jedem Scheitelpunkt links verbinden. Jede Kante ist eine Kombination aus einer bestimmten Zeile und Spalte und repräsentiert eine von neun Zellen. Beispielsweise entspricht die Kante zwischen dem oberen rechten Scheitelpunkt und dem oberen linken Scheitelpunkt der Zelle der ersten Zeile der ersten Spalte (obere linke Zelle des lateinischen Quadrats).



Jetzt holen wir die Buntstifte heraus und codieren die Farben der Rippen entsprechend der Anzahl der Quadrate, die sie bezeichnen. Angenommen, wir färben die Linien, die 1 bedeuten, mit Blau, Rot mit 2, Gelb mit 3. Wenn sich 1 in der oberen linken Zelle befindet, ist die Kante zwischen den oberen Eckpunkten blau.



Schauen wir uns die Farben der Kanten an. Ist es möglich, drei Kanten jeder der drei Farben so auszuwählen, dass sie an verschiedenen Eckpunkten beginnen und enden? Dieses Set heißt Rainbow Matching. Wenn Sie es finden, wird klar, dass es auf dem entsprechenden lateinischen Quadrat eine Transversale gibt. Wenn Sie drei verschiedene Regenbogenkorrespondenzen finden, wird außerdem klar, dass das gesamte lateinische Quadrat aus Transversalen besteht.



Die Regenbogenfärbung half Forschern, Probleme in der Vergangenheit zu untersuchen, und wurde auch zu einem Schlüsselelement für den neuen Beweis von Ringels Hypothese. Sie spielen auch eine Rolle bei einer noch komplexeren Aufgabe, der anmutigen Markup- Hypothese .

Um die Essenz des Problems zu verstehen, zeichnen Sie zuerst sechs Eckpunkte und verbinden Sie sie dann zu einem Baum. Weisen Sie jedem Scheitelpunkt auf irgendeine Weise eine Zahl zu. Markieren Sie dann jede Kante mit der Differenz zwischen den Nummern der Scheitelpunkte, die sie verbindet. Das heißt, wenn eine Kante die Eckpunkte 6 und 2 verbindet, markieren wir diese Kante mit der Nummer 4.

Ihr Ziel ist es, die Kantenbeschriftungen nacheinander zu platzieren und ihre Nummern nicht zu wiederholen. In diesem Fall 1, 2, 3, 4, 5. Wenn Sie dies tun können, ist für Ihren Baum ein ordnungsgemäßes Markup vorhanden.



In den 1960er Jahren schlugen Gerhard Ringel - derjenige, der die Hypothese aufstellte - und Anton Kotsig gemeinsam vor, dass jeder Baum, unabhängig von der Anzahl der Kanten oder der Form, elegant markiert werden kann.

Die anmutige Markup-Hypothese impliziert die Ringel-Hypothese - das heißt, wenn die erste Hypothese wahr ist, dann ist auch die Ringel-Hypothese wahr. Um dies zu verstehen, kehren wir zu einem anmutig markierten Baum mit sechs Eckpunkten und einem vollständigen Diagramm mit elf Eckpunkten zurück. Wir verteilen diese 11 Scheitelpunkte über den Umfang und nummerieren sie von 1 bis 11. Nun platzieren wir eine Kopie des Baums auf dem vollständigen Diagramm, sodass die Beschriftungen der Scheitelpunkte übereinstimmen: Der Scheitelpunkt 5 des Baums überlappt den Scheitelpunkt 5 des vollständigen Diagramms und so weiter. Diese Platzierung ist eine Regenbogenkopie eines anmutig markierten Baumes.



Wenn Sie also wissen, dass Bäume mit der Anzahl der Eckpunkte n + 1 immer elegant markiert werden können, wissen Sie, dass sie immer innerhalb des entsprechenden vollständigen Diagramms mit 2n + 1 Eckpunkten platziert werden können, um eine Regenbogenkopie des Baums zu erhalten. Und eine solche Platzierung ist genau die Position, mit der der Prozess des Kachelns von Ringel beginnen soll.

"Wenn Sie ein elegantes Markup finden, kann ich Ihnen sagen, wie Sie Ihre Regenbogenkopie finden", sagte Benny Sudakov von der Eidgenössischen Technischen Hochschule, einer der drei Autoren des Beweises der Ringel-Hypothese.

Natürlich konnten Mathematiker letztendlich die Wahrheit der Ringel-Hypothese beweisen, ohne die Hypothese eines anmutigen Aufschlags beweisen zu müssen, so dass diese Frage unbeantwortet blieb.

"Graceful Markup ist ein attraktives und schönes Thema für sich und bleibt immer noch offen", sagte Sudakov.

Die Methoden, die zum Beweis der Ringel-Hypothese geführt haben, können jedoch wahrscheinlich auf ein anmutiges Markup angewendet werden - und Mathematiker sind gespannt, wie weit diese Methoden sie führen können.

More articles:


All Articles