Kisi-

Pembaruan : Perangkat penghalang (yaitu "penghalang" NxM antara ukuran kotak yang dapat diwarnai dan yang tidak dapat diwarnai) untuk semua pewarnaan-empat-bebas-persegi monokromatik sekarang dikenal .

Adakah yang mau mencoba 5 warna? ;)

Pertanyaan berikut muncul dari Ramsey Theory .

Pertimbangkan -coloring dari n -by- m grafik jaringan. A ada setiap kali empat sel dengan warna yang sama disusun sebagai sudut beberapa persegi panjang. Misalnya, ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 1 ) , dan ( 1 , 0 ) membentuk persegi panjang monokromatik jika mereka memiliki warna yang sama. Demikian pula, ( 2 , 2 ) , ( 2 , 6 ) $k$$n$$m$monochromatic rectangle$(0,0), (0,1), (1,1),$$(1,0)$ dan ( 3 , 2 ) membentuk persegi panjang monokromatik, jika diwarnai dengan warna yang sama.$(2,2), (2,6), (3,6),$$(3,2)$

Pertanyaan : Apakah ada grafik warna dari grafik 17 -by- 17 yang tidak mengandung persegi panjang monokromatik? Jika demikian, berikan pewarnaan eksplisit.$4$$17$$17$

Beberapa fakta yang diketahui:

• -by- 17 adalah 4 -colorable tanpa persegi panjang monokromatik, tapi skema mewarnai dikenal tidak muncul untuk memperpanjang ke 17 -by- 17 kasus. (Saya menghilangkan dikenal 16 -by- 17 pewarnaan karena akan sangat mungkin menjadi herring merah untuk memutuskan 17 -by- 17 .) $16$$17$ $4$$17$$17$$16$$17$$17$$17$
• -by- 19 adalahTIDAK 4 -colorable tanpa persegi panjang monokromatik. $18$$19$ $4$
• -dengan 18 dan 18 -dengan 18 juga merupakan kasus yang tidak diketahui; jawaban untuk ini juga akan menarik. $17$$18$$18$$18$

Penafian: Bill Gasarch memiliki hadiah $ 289 (USD) untuk jawaban positif atas pertanyaan ini; Anda dapat menghubunginya melalui blog-nya. Catatan tentang etiket: Saya akan memastikan dia tahu sumber jawaban yang benar (jika ada yang muncul).

Dia mengangkatnya lagi selama sesi pantat di Barriers II, dan saya menemukan itu menarik, jadi saya meneruskan pertanyaan di sini (tanpa sepengetahuannya; meskipun saya sangat ragu dia akan keberatan).

Beberapa dari Anda mungkin menyadari hal ini, tetapi masalah pewarnaan 17 x 17 telah diselesaikan oleh Bernd Steinbach dan Christian Posthoff. Lihat posting blog Gasarch di sini .

Ini sebenarnya bukan jawaban untuk pertanyaan, tetapi saya telah meng-encode masalah 17x17 4-warna sebagai 4-CNF (dalam format DIMACS standar untuk SAT-solver) dan mengunggahnya di sini . Jika ada yang memiliki akses ke pemecah SAT yang baik (dan superkomputer!) Mungkin kita dapat membuat beberapa kemajuan.

Catatan: dalam pengkodean saya, jika GridPoint ditugaskan warna c ∈ { 0 , 1 , 2 , 3 } , maka variabel ( 17 i + j + 289 c + 1 ) mengambil nilai 1 , dan 0 jika tidak .$(i,j)$$c \in \{0,1,2,3\}$$(17i+j+289c+1)$$1$$0$

Ini juga bukan jawaban nyata. Tentu saja masalah di sini adalah adanya sejumlah simetri astronomi, yang menipu bahkan pemecah SAT terbaik pada superkomputer terbaik. Simetri memetakan solusi untuk solusi dan non-solusi untuk non-solusi: dalam hal ini mungkin ada sejumlah besar hampir solusi (yaitu penugasan memenuhi semua kecuali sejumlah kecil klausa), yang masing-masing dapat diperoleh oleh yang lain menerapkan simetri yang tepat. Oleh karena itu pemecah limbah menghabiskan banyak waktu untuk mencoba masing-masing dari hampir solusi ini, sementara dalam arti tertentu mereka semua sama.

Mengeksploitasi simetri (lihat makalah ini ) harus menjadi jalan untuk mengeksplorasi untuk menyerang contoh sulit 17x17 ini dan membuat beberapa kemajuan di atasnya. Saya bertanya-tanya apakah ada yang sudah mencoba melakukannya.

Sekali lagi, bukan jawaban yang nyata, tetapi bagaimanapun, berikut adalah beberapa pemikiran untuk mengadopsi algoritma pewarnaan grafik untuk masalah ini.

Mari kita mengatakan bahwa satu set dari posisi grid set independen jika set Aku tidak mengandung keempat penjuru beberapa persegi panjang. Tentukan set independen maksimal dengan cara yang jelas. Sekarang, ini adalah klaim yang setara:$I$$I$

1. -by- m grid dapat diwarnai dengan k warna.$n$$m$$k$
2. -by- m grid dapat ditutupi dengan k set independen.$n$$m$$k$
3. -by- m grid dapat ditutupi dengan k set independen maksimal.$n$$m$$k$

$\log k\ \text{poly}(nm)2^{nm}$$k^{mn}$$2^{289}$

Jika keluarga semua set independen (maksimal) memiliki struktur yang cukup bagus, mungkin juga dapat menyempurnakan algoritma produk penutup.

Kisi 21x12 4-warna tanpa persegi panjang monokromatik, juga !!!

Lihat posting Bernd Steinbach terakhir di blog Gasarch !

Ini Bill Bouris. Hai, Dan. Saya sedang mengerjakan sebuah program yang mencari matriks 17x17 yang cocok yang menunjukkan pewarnaan no-4 sesuai dengan Teori Ramsey. Saya menggunakan matriks posisional yang menggambarkan semua koneksi antara titik dan memperbaiki diagonal utama dan memungkinkan baris atas matriks untuk menjalankan semua kemungkinan kombinasi 16choose8; Saya hanya menangkap matriks yang memenuhi kriteria berikut ... no-XRRR, no-RXRR, no-RRXR, no-RRRX, no-XBBB, no-BXBB, dll., Lalu saya menyapu matriks menggunakan berikutnya kriteria terlemah ... no-XBRR, noBXRR, no-BBXR, no-BBRX, no-XRBB, no-RXBB, dll. untuk total 32 sapuan hingga komputer mengisi pewarnaan secara otomatis. Saya perhatikan ada kemungkinan kandidat per setiap 400 matriks dari total 12780, dan butuh 0,95 jam untuk menemukan kandidat atau 1 per setiap 8. 644 detik. Itu datang, tapi saya tidak punya banyak waktu untuk memprogramnya ... karena saya bekerja penuh waktu. Kita harus bekerja bersama ... Saya bisa menggunakan $ 289,00!