Dugaan menyiratkan Teorema Empat Warna

Four Color Theorem (4CT) menyatakan bahwa setiap grafik planar adalah empat yang dapat diwarnai. Ada dua bukti yang diberikan oleh [Appel, Haken 1976] dan [Robertson, Sanders, Seymour, Thomas 1997]. Kedua bukti ini dibantu oleh komputer dan cukup menakutkan.

Ada beberapa dugaan dalam teori grafik yang menyiratkan 4CT. Penyelesaian dugaan ini mungkin membutuhkan pemahaman yang lebih baik tentang bukti 4CT. Inilah satu dugaan seperti itu:

Dugaan : Misalkan menjadi grafik planar, misalkan adalah seperangkat warna dan merupakan involusi bebas titik tetap. Biarkan menjadi sedemikian rupaC f : C → C L = ( L v : v ∈ V ( G ) $G$$C$$f : C \rightarrow C$$L = (L_v : v \in V(G))$

• $|L_v| \geq 4$ untuk semua dan$v \in V$
• jika maka untuk semua , untuk semua . f ( α ) ∈ L v v ∈ V α ∈ $\alpha \in L_v$$f(\alpha) \in L_v$$v \in V$$\alpha \in C$

Maka terdapat -coloring grafik .$L$$G$

Jika Anda tahu dugaan seperti itu menyiratkan 4CT, harap sebutkan satu di setiap jawaban. Saya tidak dapat menemukan daftar dugaan seperti itu.

4CT setara dengan:

• Mewarnai hypergraph yang diinduksi oleh keluarga terbatas disk (tidak harus terpisah secara interior tetapi juga disk yang mungkin memiliki tumpang tindih sewenang-wenang) dengan paling banyak empat warna .$[1]$
• Proposisi bahwa setiap triangulasi planar dengan lebih dari tiga simpul adalah penyatuan dua grafik bipartit yang terhubung, masing-masing tanpa isthmus .$[2]$
• Masalah kombinatorial tentang aljabar produk lintas vektor tiga dimensi .$[3]$
• Proposisi bahwa tata bahasa G benar-benar ambigu .$[4]$
• Untuk bilangan bulat positif , setidaknya ada jalur signable yang menggabungkan dua permutasi dari S n .$n$$S_n$

• Persamaan aljabar dari teorema empat warna disajikan. Yang sederajat adalah pernyataan non-keanggotaan keluarga polinomial dalam keluarga ideal polinomial atas bidang terbatas tertentu .$[6]$

  1. Smorodinsky S. Pada jumlah kromatik geometri hypergraphs .
  2. Grafik Mabry R. Bipartit dan Teorema Empat Warna .
  3. Mewarnai Peta Kauffman LH dan produk lintas vektor .
  4. Cooper BJ et al. Menuju bukti teoritik bahasa dari teorema empat warna .
  5. Eliahou S. et al. Permutasi yang ditandatangani dan teorema empat warna .
  6. Howard L. An Reformulasi Aljabar dari Teorema Empat Warna .

Verifikasi mekanis lain dari teorema 4-warna telah dilakukan oleh George Gonthier di Microsoft Research Cambridge. Perbedaannya dengan buktinya adalah bahwa seluruh teorema telah dinyatakan dan diverifikasi secara mekanis menggunakan asisten Coq proof, sedangkan bukti lainnya hanya berisi perhitungan kernel yang ditulis dalam Bahasa Assembly dan C, dan dengan demikian memiliki risiko menjadi buggy. Bukti Gonthier mencakup aspek perhitungan dan yang logis hanya dalam 60.000 baris Coq.

Saya telah membicarakan hal ini di blog saya dan wawasan kami adalah: misalnya kondisi Tait dapat melemah hingga ada pewarnaan yang memiliki paling banyak kesalahan (n). Lihat di sini: http://rjlipton.wordpress.com/2009/04/24/the-four-color-theorem/

Lihatlah T. Saaty, Tiga belas variasi warna pada dugaan 4-warna Guthrie, American Math. Bulanan, 79 (1972) 2-43 untuk banyak contoh.

Juga, dalam buku David Barnette, Peta Pewarnaan, Polyhedra, dan Masalah Empat-Warna, MAA, Seri Dolciani, Volume 8, 1983 banyak contoh diberikan. Salah satu hasil yang sangat menarik dalam buku Barnete adalah: Jika selalu mungkin untuk memotong simpul dari polyhedron cembung sehingga untuk menghasilkan polyhedron cembung 3-valent sehingga jumlah sisi masing-masing wajah adalah kelipatan dari tiga, itu menyiratkan bahwa kebenaran dugaan empat warna.

The Hadwiger dugaan .

Dalam makalah Absolute Planar Retracts dan Four Color Conjecture , Pavol Hell membuktikan beberapa formulasi yang setara untuk 4CT. Salah satunya berbunyi sebagai berikut:

Setiap grafik planar 4-colorable (The 4CT) jika ada planar mutlak menarik.

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

Setiap grafik planar kubik tanpa jembatan adalah 3-edge-colourable. (Ini setara dengan 4CT, karena Tait.)

Makalah Dror Bar-Natan "Lie Algebras and the Four Color Theorem" (Combinatorica 17-1 (1997) 43-52, terakhir diperbarui Oktober 1999, arXiv: q-alg / 9606016 ) berisi pernyataan menarik tentang Lie algebras yang setara dengan Teorema Empat Warna. Gagasan yang muncul dalam pernyataan juga muncul dalam teori invarian tipe terbatas knot (invarian Vassiliev) dan 3-manifold.

Proposisi 2.4 dalam makalah ini http://www.sciencedirect.com/science/article/pii/0012365X9500109A# memberikan rumusan lain untuk 4CT.

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

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

Deskripsi tingkat tinggi dari bukti otomatis oleh Gonthier patut dibaca, jika Anda mencari lebih banyak wawasan.

Yuri Matiyasevich mempelajari beberapa penyajian kembali probabilistik dari Teorema Empat Warna, yang melibatkan korelasi positif antara dua gagasan kesamaan antara pewarnaan. Bukti kesetaraannya bergantung pada polinomial grafik yang terkait, yang menyediakan kemungkinan penunjuk lain untuk dugaan yang menyiratkan teorema.

• Georges Gonthier, Bukti Resmi — Teorema Empat Warna , Pemberitahuan Masyarakat Matematika Amerika 55 (11) 1382–1393, 2008.
• Yuri Matiyasevich, Satu Setara Probabilistik dari Konjektur Empat Warna , terjemahan makalah dalam Teoriya Veroyatnostei i ee Primeneniya 48 411-416, 2003.
• Yuri Matiyasevich, Beberapa Penyajian Kembali Probabilistik dari Konjektur Empat Warna , Jurnal Teori Grafik 46 167–179, 2004. ( pracetak )

Saya baru saja membaca di koran Chalopin dan Gonçalves (STOC '09) tentang dugaan Barat berikut ini:

Setiap grafik planar adalah grafik persimpangan segmen di pesawat menggunakan hanya empat arah.

Karena segmen paralel membentuk set independen dalam representasi seperti itu, dugaan ini menyiratkan 4CT, tetapi mungkin bahkan lebih kuat.

Referensi: Masalah Barat, Terbuka . SIAM J Discrete Math Newsletter, 2 (1): 10-12, 1991.

Sebuah snark adalah terhubung, bridgeless grafik kubik yang tidak 3--edge yg berhasil. Berikut wikipedia, dugaan snark , generalisasi 4CT, adalah sebagai berikut:

Setiap snark memiliki subgraf yang dapat dibentuk dari grafik Petersen dengan membagi beberapa tepinya.

Sekali lagi menurut wikipedia, bukti dugaan ini diumumkan pada tahun 2001 oleh Robertson, Sanders, Seymour dan Thomas.

"The Face Labeling Of Maximal Planar Graphs" adalah judul tulisan lama saya yang telah diterbitkan baru-baru ini di mana saya telah mengubah 4 pewarnaan grafik planar maksimal menjadi konsistensi pelabelan wajah. Tautan ke makalah ini adalah http://www.math.nsysu.edu.tw/~amen/2011/091021-3.pdf

Sebagai

LH Kauffman, Merumuskan kembali teorema warna peta , Discrete Mathematics 302 (2005) 145–172

menunjukkan, Prinsip Utama karena G. Spencer-Brown serta dugaan Eliahou-Kryuchkov adalah reformulasi setara FCT.

• S. Eliahou, Flips diagonal yang ditandatangani dan teorema empat warna, European J. Combin. 20 (1999) 641-646.
• SI Kryuchkov, Teorema dan pohon empat warna, IV Kruchatov, Institut Energi Atom, Moskow, 1992, IAE-5537/1.
• G. Spencer-Brown, Hukum Bentuk, Gesetze der Form, Bohmeier Verlag, 1997.

Garry Bowlin dan makalah Matthew G. Brin "Mewarnai Grafik Planar melalui Jalur Berwarna di Associahedra", terakhir direvisi 12 Mei 2013, arXiv: 1301.3984 math.CO berisi dugaan berikut di halaman 26:

Dugaan 6.4. Untuk setiap pasangan pohon biner terbatas (D, R) dengan jumlah daun yang sama, ada penandaan tanda D dan kata w dari simbol rotasi yang berlaku untuk D sehingga Dw = R.

Dinyatakan bahwa dugaan 6.4 mengikuti dari proposisi sebelumnya dan teorema dalam makalah ini setara dengan 4CT.

Sebuah k Alir pada sebuah grafik diarahkan G adalah grafik diarahkan berasal dengan mengganti setiap sisi di G dengan busur dan menugaskan integer antara -k dan k , eksklusif, sehingga, untuk setiap titik di G, jumlah dari bilangan bulat ditugaskan untuk busur menunjuk ke simpul yang sama dengan jumlah bilangan bulat yang ditugaskan untuk busur menunjuk. NWZ (tidak ada nol) k -flow adalah k -flow di mana tidak ada arc yang diberi nomor 0.

Untuk setiap graf planar G , dual G adalah grafik yang berisi satu simpul untuk setiap wajah dalam penyisipan planar G , dan dua simpul dalam pembagian ganda satu sisi yang menghubungkan mereka untuk setiap tepi yang menghadapinya sesuai di G berbagi di antara mereka di batas-batas mereka. Menurut Teorema Dualitas Aliran Tutte, grafik planar tanpa isthmus (yaitu sisi yang penghapusannya akan menambah jumlah komponen) memiliki aliran NWZ k jika dan hanya jika dualnya k -warna. Dengan kata lain, grafik planar 4-colourable jika dan hanya jika dual-nya memiliki NWZ 4-flow.

Perhatikan bahwa 4CT memerlukan grafik planar yang dipermasalahkan untuk tidak memiliki loop (tepi yang menghubungkan setiap simpul ke dirinya sendiri) karena setiap grafik dengan loop tidak dapat diwarnai dengan set warna, karena setiap simpul dengan loop akan berdekatan dengan vertex dengan warna yang sama, terlepas dari warnanya.

Saya sedang mengerjakan ini:

Jika Anda dapat membuktikan teorema untuk peta persegi panjang, yaitu peta yang terbuat dari lembaran kertas yang tumpang tindih, Anda juga telah membuktikan 4ct. Selain itu, hanya peta dengan wajah yang memiliki semua 5 tepi atau lebih yang dapat dipertimbangkan dalam pencarian.

Lihat http://4coloring.wordpress.com/ untuk detailnya.