Raster

37

Update : Das Hindernisset (dh die NxM "Barriere" zwischen färbbaren und nicht färbbaren Rastergrößen) für alle einfarbigen, rechteckfreien 4-Farbtöne ist jetzt bekannt .

Möchte jemand 5-Farben probieren? ;)


Die folgende Frage ergibt sich aus der Ramsey-Theorie .

Betrachten Sie eine Färbung des n- mal- m- Graphen. A ist immer dann vorhanden, wenn vier Zellen mit derselben Farbe als Ecken eines Rechtecks ​​angeordnet sind. Beispielsweise ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 1 ) , und ( 1 , 0 ) ein monochromatisches Rechteck bilden , wenn sie die gleiche Farbe haben. Ebenso ( 2 , 2 ) , ( 2 , 6 ) ,knmmonochromatic rectangle(0,0),(0,1),(1,1),(1,0) und ( 3 , 2 ) bilden ein monochromatisches Rechteck, wennmit der gleichen Farbe gefärbt.(2,2),(2,6),(3,6),(3,2)

Frage : Gibt es eine farbige Darstellung des 17- mal- 17- Graphen, die kein monochromatisches Rechteck enthält? Wenn ja, geben Sie die explizite Färbung an.41717

Einige bekannte Fakten:

  • by- 17 ist 4- colorable ohne einfarbiges Rechteck, aber das bekannte Farbschema scheint sich nicht auf den 17- by- 17- Fall zu erstrecken. (Ich verzichte auf die bekannte 16- mal- 17- Färbung, da es sich höchstwahrscheinlich um einen roten Hering handelt, um 17- mal- 17 zu bestimmen.) 1617 4171716171717
  • -by- 19 istNICHT 4 -farbig ohne einfarbiges Rechteck. 1819 4
  • bis- 18 und 18- bis- 18 sind ebenfalls unbekannte Fälle; Eine Antwort auf diese Fragen wäre ebenfalls interessant. 17181818

Haftungsausschluss: Bei einer positiven Antwort auf diese Frage erhält Bill Gasarch ein Kopfgeld von 289 USD . Sie können ihn über seinen Blog erreichen. Ein Hinweis zur Etikette: Ich werde sicherstellen, dass er die Quelle jeder richtigen Antwort kennt (sollte eine auftauchen).

Er hat es während einer Rumpfsitzung bei Barriers II noch einmal angesprochen, und ich finde es interessant, deshalb leite ich die Frage hier weiter (ohne sein Wissen; obwohl ich sehr bezweifle, dass es ihm etwas ausmacht).

Daniel Apon
quelle
11
Ich möchte nur einige Verweise / Hinweise hinzufügen: Abgesehen von den Blog-Posts [1,2] sind die Updates im Bitplayer-Blog [3,4] detailliert und aufschlussreich. Zu all diesen Beiträgen wurde ausführlich diskutiert. [1]: blog.computationalcomplexity.org/2009/11/… [2]: blog.computationalcomplexity.org/2009/12/… [3]: bit-player.org/2009/the-17x17-challenge [4] : bit-player.org/2009/17-x-17-a-nonprogress-report Hinweis: Keine Abschriftenformatierung in Kommentaren? Wie kann ich hübsche Links machen?
Neeldhara
Das sind einige großartige Links. Danke Neeldhara! :)
Daniel Apon
Ebenso vielen Dank, dass Sie dies hier gepostet haben - ich habe die Entwicklungen dazu einige Zeit verfolgt, und dies sollte das Interesse an dem Problem wieder aufleben lassen!
Neeldhara
2
@Moron: Ja, Sie müssen nur die Rechtecke berücksichtigen, deren Seiten parallel zu den Achsen sind. Übrigens gibt es auch einen komplexitätstheoretischen Aspekt: ​​Bill hat spekuliert, dass bei einer partiellen k-Färbung eines mx n-Gitters die Feststellung, ob die Färbung rechteckfrei abgeschlossen werden kann, NP-vollständig ist.
Kurt
2
2×4!×(17!)2=6.1×103071,72,73,...

Antworten:

23

Einige von Ihnen wissen dies wahrscheinlich, aber das 17 x 17-Farbproblem wurde von Bernd Steinbach und Christian Posthoff gelöst . Den Blog-Beitrag von Gasarch finden Sie hier .

Lev Reyzin
quelle
8
Auch das 18x18-Raster ist ohne monochromatische Rechtecke 4-farbig ... Jetzt fehlt nur noch das 21x12-Raster
Marzio De Biasi
13

Das ist nicht wirklich eine Antwort auf die Frage, aber ich habe das 17x17 4-Färbungsproblem als 4-CNF (im Standard DIMACS Format für SAT-Solver) und hochgeladen es codierte hier . Wenn jemand Zugang zu einem guten SAT-Löser (und einem Supercomputer!) Hat, können wir vielleicht Fortschritte erzielen.

(i,j)c{0,1,2,3}(17i+j+289c+1)10

Lev Reyzin
quelle
3
Genial. (Ich habe in der Tat Zugang zu einem Supercomputer.) Die laufenden Nummern des nächsten Schritts, um die Laufzeit dieses Dings auf dem spezifischen Computer abzuschätzen. Wer weiß, ob dies im Rahmen des Zumutbaren liegt, aber es ist ein anderer Ansatz, den ich mir vorgestellt habe. Jetzt ist es an der Zeit, diese aktuelle Frage zu SAT-Lösern zu finden, damit ich nachlesen kann ... :)
Daniel Apon
Es stellte sich heraus, dass das Problem, an das ich gedacht hatte, bei #SAT war. Daher habe ich eine neue Frage zu SAT-Lösern unter cstheory.stackexchange.com/questions/1719/… gestartet
Daniel Apon,
Super - lass mich wissen wie es geht!
Lev Reyzin
4
@Lev, nur ein zufälliges Update: Es sieht so aus, als ob die Laufzeit des 17x17, selbst wenn der bestmögliche Supercomputer und ein wirklich schneller SAT-Löser verwendet werden, immer noch astronomisch ist. Pluspunkt: Es erscheint im Rahmen der Vernunft, dies mit einem Supercomputer gezielt anzugreifen, dh die genauen Teil-1-Färbungen zu finden, die funktionieren (bereits von Beth Kupkin bei Rutgers von Hand), und dann die genauen Teil-2-Färbungen zu finden -Farben, die dann funktionieren usw. Nachteil: Es gibt keine "schnelle Lösung". Es muss sich um ein langfristiges Projekt mit mehreren Phasen der Ausführung von Supercomputern handeln
Daniel Apon,
1
@ Joe, aber! Hier ist eine "Bestenliste" der aktuell besten ungefähren Farbtöne: Bestenliste - Es scheint, dass simuliertes Tempern recht gut funktioniert, um ungefähre Farbtöne zu finden.
Daniel Apon
4

Dies ist auch keine richtige Antwort. Das Problem hierbei ist sicherlich das Vorhandensein einer astronomischen Anzahl von Symmetrien, die selbst die besten SAT-Löser auf den besten Supercomputern zum Narren halten. Solche Symmetrien ordnen Lösungen Lösungen zu und Nichtlösungen Lösungen zu Nichtlösungen zu: In diesem Fall gibt es wahrscheinlich eine immense Anzahl von Fast-Lösungen (dh Zuordnungen, die alle bis auf eine kleine Anzahl von Klauseln erfüllen), von denen jede von jeder anderen erhalten werden kann Anwenden einer richtigen Symmetrie. Daher verschwendet der Löser eine enorme Menge an Zeit, um jede dieser Fast-Lösungen auszuprobieren, während sie in gewissem Sinne alle gleich sind.

Das Ausnutzen von Symmetrien (siehe dieses Dokument) sollte ein Weg sein, um diese harte 17x17-Instanz anzugreifen und Fortschritte zu erzielen. Ich frage mich, ob das schon jemand versucht hat.

Giorgio Camerani
quelle
Hey, das ist ziemlich süß! :) Hatte es noch nie gesehen.
Daniel Apon
@ Daniel: Gern geschehen! ;-) Ich hoffe es hilft.
Giorgio Camerani
Ich habe Alouls "Shatter" -Programm für mehrere Kodierungen des 17x17-Problems verwendet und einige CPU-Wochen in ein paar verschiedene SAT-Solver gesteckt und hatte kein Glück. Die Zeitung, auf die sich Walter bezieht, ist eigentlich die erste von vielleicht einem Dutzend oder etwas, das er zu diesem Thema geschrieben hat, also könnte etwas drin sein, das die Arbeit erledigt, aber es ist keine niedrig hängende Frucht.
Jay Kominek
3

Auch dies ist keine echte Antwort, aber hier sind einige Überlegungen zur Übernahme von Grafikfarbalgorithmen für dieses Problem.

II

  1. nmk
  2. nmk
  3. nmk

logk poly(nm)2nmkmn2289

Wenn die Familie aller (maximalen) unabhängigen Mengen eine ausreichend schöne Struktur aufweist, kann möglicherweise auch der Algorithmus für das abdeckende Produkt verfeinert werden.

Janne H. Korhonen
quelle
Wie entspricht Anspruch 3 Anspruch 2? Die maximale unabhängige Menge für 17x17 hat übrigens die Größe 74, wie in Elizabeth Kupins Artikel (pdf) gezeigt . Es gibt nur einen solchen Satz, bei dem die Permutationen der Zeilen und Spalten nicht als eindeutig gezählt werden.
Nullmenge
Ich meine maximal in dem Sinne, dass keine richtige Obermenge unabhängig ist, wie es in der Informatik üblich ist. Maximum ist das Wort, das normalerweise verwendet wird, wenn es "von größtmöglicher Größe" bedeutet.
Janne H. Korhonen
In diesem Fall enthält die Menge der maximalen unabhängigen Mengen alle Zeilen- / Spaltenpermutationen der eindeutigen Menge der Größe 74 und keine unabhängigen Mengen der Größe 73, da sie alle Teilmengen der Menge der Größe 74 sind. Ich bin nicht sicher, was es von den Größen 67 bis 72 hat.
Nullsatz
-4

Das ist Bill Bouris. Hi, Dan. Ich arbeite an einem Programm, das nach einer geeigneten 17x17-Matrix sucht, die nach Ramseys Theorie eine No-4-Färbung aufweist. Ich verwende eine Positionsmatrix, die alle Verbindungen zwischen Punkten darstellt, und fixiere die Hauptdiagonale, und lasse die obere Reihe der Matrix durch alle möglichen 16choose8-Kombinationen laufen. Ich nehme nur die Matrizen auf, die die folgenden Kriterien erfüllen ... no-XRRR, no-RXRR, no-RRXR, no-RRRX, no-XBBB, no-BXBB usw., dann gehe ich mit dem nächsten durch die Matrix schwächste Kriterien ... no-XBRR, noBXRR, no-BBXR, no-BBRX, no-XRBB, no-RXBB usw. für insgesamt 32 Sweeps, bis der Computer die Färbung automatisch ausfüllt. Mir ist aufgefallen, dass von insgesamt 12780 möglichen Kandidaten auf 400 Matrizen ein Kandidat kommt, und es dauert 0,95 Stunden, um den Kandidaten zu finden, oder 1 Kandidat auf 8. 644 Sekunden. Es kommt, aber ich habe nicht viel Zeit, es zu programmieren ... da ich Vollzeit arbeite. Wir sollten zusammenarbeiten ... ich könnte die 289,00 $ gebrauchen!

William Bouris
quelle
Bill Gasarch sollte nur 128 Dollar auszahlen.
William Bouris
Entschuldigung ... 272/2 oder $ 136
William Bouris
4
Dies ist keine Antwort auf die Frage. am besten als Kommentar.
Suresh Venkat