Twierdzenie o czterech kolorach (4CT) stwierdza, że każdy płaski wykres jest czterokolorowy. Istnieją dwa dowody podane przez [Appel, Haken 1976] i [Robertson, Sanders, Seymour, Thomas 1997]. Oba te dowody są wspierane komputerowo i dość przerażające.
Istnieje kilka domysłów w teorii grafów, które sugerują 4CT. Rozwiązanie tych przypuszczeń wymaga prawdopodobnie lepszego zrozumienia dowodów 4CT. Oto jedna z takich hipotez:
Hipoteza : Niech będzie płaskim planem, niech C będzie zbiorem kolorów, a f : C → C inwolucją swobodną o stałym punkcie. Niech L = ( L v : v ∈ V ( G ) ) będzie takie, że
- dla wszystkich v ∈ V i
- Jeśli czym F ( alfa ) ∈ L V dla wszystkich v ∈ V , dla wszystkich alfa ∈ C .
Następnie istnieje -coloring grafu G .
Jeśli znasz takie domniemania sugerujące 4CT, proszę wymienić je po jednym w każdej odpowiedzi. Nie mogłem znaleźć wyczerpującej listy takich przypuszczeń.
źródło
Odpowiedzi:
4CT odpowiada:
Przedstawiono algebraiczny odpowiednik twierdzenia o czterech kolorach. Odpowiednikiem jest twierdzenie o braku członkostwa w rodzinie wielomianów w rodzinie wielomianowych ideałów na określonym polu skończonym .[6]
źródło
Kolejną mechaniczną weryfikację 4-kolorowego twierdzenia przeprowadził George Gonthier w Microsoft Research Cambridge. Różnica w stosunku do jego dowodu polega na tym, że całe twierdzenie zostało stwierdzone i zweryfikowane mechanicznie za pomocą asystenta dowodu Coq, podczas gdy inne dowody zawierają tylko obliczenia jądra napisane w asemblerze i języku C, a zatem grozi im błąd. Dowód Gonthiera obejmuje zarówno aspekty obliczeniowe, jak i logiczne w zaledwie 60 000 linii Coq.
źródło
Mówiłem o tym na moim blogu, a nasza wiedza jest następująca: na przykład stan Tait może zostać osłabiony, ponieważ występuje zabarwienie z co najwyżej o (n) błędami. Zobacz tutaj: http://rjlipton.wordpress.com/2009/04/24/the-four-color-theorem/
źródło
Spójrz na T. Saaty'ego, Trzynaście kolorowych odmian 4-kolorowej hipotezy Guthrie, American Math. Monthly, 79 (1972) 2-43 dla wielu przykładów.
Również w książce Davida Barnette'a Map Coloring, Polyhedra, and the Four-Color Problem, MAA, Dolciani Series, tom 8, 1983 podano wiele przykładów. Jednym szczególnie interesującym wynikiem w książce Barnete jest: Jeśli zawsze można obciąć wierzchołki wypukłego wielościanu, aby wytworzyć 3-walentny wypukły wielościan, tak że liczba boków każdej powierzchni jest wielokrotnością trzech, oznacza to, że prawda o domysłach czterech kolorów.
źródło
Przypuszczenie Hadwiger .
źródło
W pracy Absolute Planar Retracts i Four Colour Conjecture Pavol Hell udowodnił kilka równoważnych sformułowań dla 4CT. Jeden z nich brzmi następująco:
źródło
Każdy sześcienny płaski wykres bez mostków jest trójwymiarowy. (Jest to równoważne z 4CT, ze względu na Tait.)
źródło
Artykuł Drora Bar-Natana „Lie Algebras and the Four Colour Theorem” (Combinatorica 17-1 (1997) 43-52, ostatnio zaktualizowany w październiku 1999 r., ArXiv: q-alg / 9606016 ) zawiera interesujące stwierdzenie o algebrach Lie równoważne z twierdzenie o czterech kolorach. Pojęcia pojawiające się w stwierdzeniu pojawiają się również w teorii niezmienników skończonych typu węzłów (niezmienników Wasiliewa) i 3-rozmaitości.
źródło
Twierdzenie 2.4 w tym dokumencie http://www.sciencedirect.com/science/article/pii/0012365X9500109A# daje inną formułę dla 4CT.
źródło
Opis wysokiego poziomu automatycznego dowodu autorstwa Gonthiera jest wart przeczytania, jeśli szukasz więcej wglądu.
Yuri Matiyasevich zbadał kilka probabilistycznych powtórzeń twierdzenia o czterech kolorach, obejmujących dodatnie korelacje między dwoma pojęciami podobieństwa między kolorami. Jego dowody równoważności opierają się na powiązanym wielomianu grafowym, który stanowi kolejny prawdopodobny wskaźnik do przypuszczeń sugerujących twierdzenie.
źródło
Właśnie przeczytałem w artykule Chalopina i Gonçalvesa (STOC '09) następującą hipotezę Zachodu:
Ponieważ równoległe segmenty tworzą niezależny zestaw w takiej reprezentacji, ta hipoteza implikuje 4CT, ale być może jest jeszcze silniejsza.
Odniesienie: Zachód, problemy otwarte . SIAM J Discrete Math Newsletter, 2 (1): 10-12, 1991.
źródło
Snark jest połączony bezmostkowego sześcienny wykres, który nie jest 3-krawędzi colorable. Zgodnie z wikipedią domniemanie snark , uogólniające 4CT, wygląda następująco:
Ponownie, zgodnie z wikipedią, dowód tej przypuszczenia został ogłoszony w 2001 roku przez Robertsona, Sandersa, Seymour i Thomasa.
źródło
„The Face Labeling of Maximal Planar Graphs” to tytuł mojego starego artykułu, który został niedawno opublikowany, w którym przekształciłem 4 kolory maksymalnych płaskich wykresów w spójność etykietowania twarzy. Link do artykułu to http://www.math.nsysu.edu.tw/~amen/2011/091021-3.pdf
źródło
Tak jak
LH Kauffman, Przeformułowanie twierdzenia o kolorze mapy , Discrete Mathematics 302 (2005) 145–172
zwraca uwagę, że zasada pierwszeństwa z powodu G. Spencera-Browna, a także domysł Eliahou – Kryuchkowa są równoważnymi przeformułowaniami FCT.
źródło
Artykuł Garry'ego Bowlina i Matthew G. Brina „Kolorowanie płaskich wykresów za pomocą kolorowych ścieżek w Associahedra”, ostatnio zmieniony 12 maja 2013 r., ArXiv: 1301.3984 math.CO zawiera następujące przypuszczenie na stronie 26:
Stwierdzono, że domniemanie 6.4 wynikające z wcześniejszych twierdzeń i twierdzeń w pracy jest równoważne 4CT.
źródło
K -flow nieukierunkowane na wykresie G jest kierowany wykres uzyskany przez zastąpienie każdej krawędzi w G łukiem i przypisując mu liczbę całkowitą pomiędzy -k i K , z wyłączeniem, tak, że dla każdego wierzchołka w G, przy czym suma liczb całkowitych przypisane do łuków wskazujących na ten wierzchołek jest równe sumie liczb całkowitych przypisanych do wskazujących łuków. N-Z (nigdzie zero) k- flow to k- flow, w którym żadnemu łukowi nie przypisano liczby 0.
Dla każdego płaskiego wykresu G , podwójność G jest wykresem zawierającym jeden wierzchołek dla każdej ściany w płaszczyźnie osadzenia G , i dwa wierzchołki w podwójnym współdzieleniu jedna krawędź łącząca je dla każdej krawędzi, którą odpowiednie ściany w G dzielą między sobą w ich granicach. Według tutte za Flow-Kolorowanka Duality twierdzenia, płaskiego wykresu bez przesmyku (czyli krawędzi, którego usunięcie zwiększyłoby liczbę komponentów) posiada NWZ k -flow wtedy i tylko wtedy, gdy jest podwójny k -colourable. Innymi słowy, wykres płaski jest 4-kolorowy, tylko wtedy, gdy jego podwójny ma przepływ 4 NWZ.
Zauważ, że 4CT wymaga, aby dany planarny wykres nie miał pętli (krawędzi łączących dowolny wierzchołek ze sobą), ponieważ żaden wykres z pętlą nie może być pokolorowany wierzchołkiem dowolnym zestawem kolorów, ponieważ każdy wierzchołek z pętlą przylegałby do wierzchołek tego samego koloru, niezależnie od jego koloru.
źródło
Pracuję nad tym:
Jeśli możesz udowodnić twierdzenie o mapach prostokątnych, które są mapami wykonanymi z nakładających się arkuszy papieru, udowodniłeś również, że 4ct. Ponadto podczas wyszukiwania można brać pod uwagę tylko mapy z powierzchniami posiadającymi wszystkie 5 krawędzi lub więcej.
Szczegółowe informacje można znaleźć na stronie http://4coloring.wordpress.com/ .
źródło