Przypuszczenia sugerujące twierdzenie o czterech kolorach

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$G$$C$$f : C \rightarrow C$$L = (L_v : v \in V(G))$

• dla wszystkich v ∈ V i$|L_v| \geq 4$$v \in V$
• Jeśli czym F ( alfa ) ∈ L V dla wszystkich v ∈ V , dla wszystkich alfa ∈ C .$\alpha \in L_v$$f(\alpha) \in L_v$$v \in V$$\alpha \in C$

Następnie istnieje -coloring grafu G .$L$$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ń.

4CT odpowiada:

• Zabarwienie hipergrafu wywołanego przez skończoną rodzinę dysków (niekoniecznie wewnętrznych rozłącznych, ale także dysków, które mogą mieć dowolne nakładanie się) co najwyżej czterema kolorami .$[1]$
• Twierdzenie, że każda płaska triangulacja z więcej niż trzema wierzchołkami jest sumą dwóch połączonych dwudzielnych grafów, każdy bez przesmyku .$[2]$
• Problem kombinatoryczny dotyczący algebry trójwymiarowego wektora krzyżowego .$[3]$
• Twierdzenie, że gramatyka G jest całkowicie niejednoznaczna .$[4]$
• Dla każdej dodatniej liczby całkowitej istnieje co najmniej znaczalna ścieżka łącząca dwie permutacje S n .$n$$S_n$

• 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]$

  1. Smorodinsky S. Na chromatycznej liczbie geometrycznych hipergraphów .
  2. Grafy dwudzielne Mabry R. i twierdzenie o czterech kolorach .
  3. Kolorowanki Kauffman LH Map i wektorowy krzyżowy produkt .
  4. Cooper BJ i in. W stronę teoretycznego dowodu językowego twierdzenia o czterech kolorach .
  5. Eliahou S. i in. Podpisane permutacje i twierdzenie o czterech kolorach .
  6. Howard L. Algebraiczna reforma twierdzenia o czterech kolorach .

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.

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/

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.

Przypuszczenie Hadwiger .

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:

Każdy wykres płaski jest 4-kolorowy (4CT), jeśli istnieje absolutne wycofanie płaskie.

$H$$G$$G$$r: V(G)\to V(H)$$r(v)=v$$v\in V(H)$

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.)

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.

Twierdzenie 2.4 w tym dokumencie http://www.sciencedirect.com/science/article/pii/0012365X9500109A# daje inną formułę dla 4CT.

$G$$\Delta(G)$$G$$G$$\Delta(G)$$G$$G$$\Delta(G)$$\Delta(G)$

$G$$K(G)$$G$$K(G)$$G$
$G$$K(G)$

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.

• Georges Gonthier, Formal Proof - The Four-Colour Theorem , Notices of the American Mathematical Society 55 (11) 1382–1393, 2008.
• Yuri Matiyasevich, One Probabilistic Equivalent of Four Colour Conjecture , tłumaczenie papieru w Teoriya Veroyatnostei i ee Primeneniya 48 411–416, 2003.
• Yuri Matiyasevich, Some Probabilistic Retatements of Four Colour Conjecture , Journal of Graph Theory 46 167–179, 2004. ( preprint )

Właśnie przeczytałem w artykule Chalopina i Gonçalvesa (STOC '09) następującą hipotezę Zachodu:

Każdy wykres płaski jest wykresem przecięcia segmentów w płaszczyźnie przy użyciu tylko czterech kierunków.

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.

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:

Każdy snark ma podgraf, który można utworzyć z wykresu Petersena, dzieląc niektóre jego krawędzie.

Ponownie, zgodnie z wikipedią, dowód tej przypuszczenia został ogłoszony w 2001 roku przez Robertsona, Sandersa, Seymour i Thomasa.

„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

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.

• S. Eliahou, Podpisane przekątne i twierdzenie o czterech kolorach, Europejski J. Combin. 20 (1999) 641–646.
• SI Kryuchkov, Twierdzenie o czterech kolorach i drzewa, IV Kruchatov, Instytut Energii Atomowej, Moskwa, 1992, IAE-5537/1.
• G. Spencer-Brown, Laws of Form, Gesetze der Form, Bohmeier Verlag, 1997.

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:

Domysł 6.4. Dla każdej pary skończonych, dwójkowych drzew (D, R) o tej samej liczbie liści przypisano znak D i słowo w symbolach obrotu ważnych dla D, tak że Dw = R.

Stwierdzono, że domniemanie 6.4 wynikające z wcześniejszych twierdzeń i twierdzeń w pracy jest równoważne 4CT.

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.

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/ .