Przypuszczenia sugerujące twierdzenie o czterech kolorach

38

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, żeGCf:CCL=(Lv:vV(G))

  • dla wszystkich v V i|Lv|4vV
  • Jeśli czym F ( alfa ) L V dla wszystkich v V , dla wszystkich alfa C .αLvf(α)LvvVαC

Następnie istnieje -coloring grafu G .LG

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

Shiva Kintali
źródło
6
„Nie mieli błędu w Coq i żadne promienie kosmiczne nie przelatywały przez ich komputer, gdy sprawdzili twierdzenie o 4 kolorach” - to jedna z takich hipotez.
Andrej Bauer,
ref dla podanego przypuszczenia?
vzn
Powiązane pytanie zadawane jest na stronie mathoverflow: mathoverflow.net/q/189097/1345
Ian Agol

Odpowiedzi:

28

4CT odpowiada:

Oleksandr Bondarenko
źródło
20

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.

Dave Clarke
źródło
18

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.

Joseph Malkevitch
źródło
12

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.

HGGr:V(G)V(H)r(v)=vvV(H)

Peng O
źródło
11

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

Andrew D. King
źródło
11

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.

Gil Kalai
źródło
11

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

GΔ(G)GGΔ(G)GGΔ(G)Δ(G)


GK(G)GK(G)G
GK(G)

vb le
źródło
4
Czy możesz to opisać tutaj, dla tych z nas, którzy nie mają dostępu (lub tacy jak ja są zbyt leniwi, aby włączyć VPN, aby uzyskać dostęp)?
David Eppstein,
9

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.

András Salamon
źródło
8

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.

RJK
źródło
6

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.

Hermann Gruber
źródło
Twierdzenie Snarka nie wydaje się sugerować 4CT, prawda?
Hsien-Chih Chang 張顯 之
W rzeczywistości implikuje 4CT: Każda podgrupa wykresu Petersena jest wyraźnie niepłaska, więc domniemanie snarków zakłada następującą przeformułowanie 4CT (z powodu Tait): Każdy snark jest nieplanarny.
Hermann Gruber
1
Ach, teraz widzę, gdzie jest mój problem. Dowód twierdzenia o snarkach jest ponownie dowodem wspomaganym komputerowo. Mam wrażenie, że nie ma żadnego możliwego do zweryfikowania przez człowieka dowodu na 4CT i źle zrozumiałem twoją odpowiedź. Dzięki!!
Hsien-Chih Chang 張顯 之
3

„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

Cahit
źródło
3

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.
Hermann Gruber
źródło
3

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.

David Clark
źródło
1

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.

Jordan Longstaff
źródło
0

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

Mario Stefanutti
źródło