Siatka

37

Aktualizacja : Zestaw przeszkód (tj. „Bariera” NxM pomiędzy rozmiarami siatki do barwienia i bezbarwności) dla wszystkich 4-kolorów bez monochromatycznych prostokątów jest teraz znany .

Czy ktoś ma ochotę wypróbować 5 kolorów? ;)

Z teorii Ramseya wynika następujące pytanie .

Rozważmy -coloring z -by- wykres siatki. Występuje, gdy cztery komórki o tym samym kolorze są umieszczone w narożnikach pewnym prostokąta. Na przykład, i tworzą prostokąt monochromatycznego jeżeli mają one ten sam kolor. Podobnie $k$ $n$ $m$ monochromatic rectangle $(0,0), (0,1), (1,1),$ $(1,0)$ i tworzą monochromatycznego prostokąta, jeśli jest zabarwiona w tym samym kolorze. $(2,2), (2,6), (3,6),$ $(3,2)$

Pytanie : Czy istnieje kolorowy wykres siatki -na- , który nie zawiera monochromatycznego prostokąta? Jeśli tak, podaj wyraźne zabarwienie. $4$ $17$ $17$

Niektóre znane fakty:

-na- jest kolorowy bez monochromatycznego prostokąta, ale znany schemat kolorowania nie wydaje się rozciągać naprzypadek -na- . (Jestem z pominięciem znany -by- kolorystykę, ponieważ byłoby to bardzo prawdopodobne być czerwony śledź na decydując -by- ). $16$ $17$ $4$ $17$ $17$ $16$ $17$ $17$ $17$
-do- NIEjest -kolorowalny bez monochromatycznego prostokąta. $18$ $19$ $4$
-by- i -by- są również nieznane przypadki; odpowiedź na te pytania również byłaby interesująca. $17$ $18$ $18$ $18$

Oświadczenie: Bill Gasarch ma nagrodę w wysokości 289 USD (USD) za pozytywną odpowiedź na to pytanie; możesz do niego dotrzeć za pośrednictwem jego bloga. Uwaga na etykiecie: upewnię się, że zna źródło każdej poprawnej odpowiedzi (jeśli taka się pojawi).

Przywołał go ponownie podczas sesji kuponowej w Barriers II i uważam to za interesujące, więc przesyłam pytanie tutaj (bez jego wiedzy; choć bardzo wątpię, czy miałby coś przeciwko).

— Daniel Apon
źródło

11

Chcę tylko dodać kilka referencji / wskaźników: oprócz postów na blogu [1,2] aktualizacje na blogu bit-player [3,4] są szczegółowe i wnikliwe. Odbyła się znaczna dyskusja na temat wszystkich tych postów. [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 Uwaga: Brak formatowania przecen w komentarzach? Jak mogę tworzyć ładne linki?

— Neeldhara,

To są świetne linki. Dzięki Neeldhara! :)

— Daniel Apon

Podobnie, dziękuję za opublikowanie tego tutaj - od jakiegoś czasu śledziłem rozwój sytuacji i powinno to ponownie rozbudzić zainteresowanie problemem!

— Neeldhara,

2

@ Moron: Tak, wystarczy wziąć pod uwagę te prostokąty, których boki są równoległe do osi. BTW, istnieje również kąt teorii złożoności: Bill spekuluje, że biorąc pod uwagę częściowe zabarwienie k siatki m na n, ustalenie, czy zabarwienie można wykonać w sposób pozbawiony prostokąta, jest NP-całkowite.

— Kurt

2

2 \times 4! \times (17!)^{2} = 6.1 \times 10^{30}

$2\times 4! \times(17!)^2=6.1\times 10^{30}$

71, 72, 73, . . .

$71,72,73,...$

23

Niektórzy z was zapewne są tego świadomi, ale problem kolorowania 17 x 17 został rozwiązany przez Bernda Steinbacha i Christiana Posthoffa. Zobacz post na blogu Gasarcha tutaj .

— Lew Reyzin
źródło

8

Również siatka 18x18 jest 4-kolorowa bez monochromatycznych prostokątów ... teraz jedyną „brakującą płytką” jest siatka 21x12

— Marzio De Biasi

13

To nie jest tak naprawdę odpowiedź na pytanie, ale zakodowałem problem kolorowania 4 x 17x17 jako 4-CNF (w standardowym formacie DIMACS dla solverów SAT) i załadowałem go tutaj . Jeśli ktoś ma dostęp do dobrego rozwiązania SAT (i superkomputera!), Możemy zrobić postępy.

$(i,j)$ $c \in \{0,1,2,3\}$ $(17i+j+289c+1)$ $1$ $0$

— Lew Reyzin
źródło

3

Niesamowite. (Rzeczywiście mam dostęp do superkomputera.) Liczby bieżące następnego kroku, aby oszacować czas działania tej rzeczy na konkretnej maszynie. Kto wie, czy jest to uzasadnione, ale to inne podejście, na które patrzyłem. Teraz czas znaleźć to ostatnie pytanie na temat SAT-solverów, abym mógł przeczytać ... :)

— Daniel Apon

Okazuje się, że problem, o którym myślałem, dotyczył #SAT, więc zacząłem nowe pytanie o rozwiązaniach SAT na cstheory.stackexchange.com/questions/1719/…

— Daniel Apon

Świetnie - daj mi znać, jak to idzie!

— Lew Reyzin

4

@Lev, tylko losowa aktualizacja: wydaje się, że czas działania 17x17, nawet przy użyciu najlepszego możliwego superkomputera i naprawdę szybkiego solvera, jest wciąż astronomiczny. Plus plus: wydaje się, że uzasadnione jest atakowanie go superkomputerem w sposób ukierunkowany, tj. Znaleźć dokładne częściowe 1-kolorowanie, które zadziała (już wykonane ręcznie przez Beth Kupkin w Rutgers), a następnie znaleźć dokładne częściowe 2 -kolory, które będą od tego działać itp. Wadą: nie ma „szybkiego rozwiązania”; będzie to długoterminowy projekt z wieloma etapami wykonania superkomputera

— Daniel Apon

1

@Joe jednak! Oto „tabela liderów” aktualnych najlepszych przybliżonych kolorów: Tabela liderów - Wygląda na to, że symulowane wyżarzanie działa całkiem dobrze w celu znalezienia przybliżonych kolorów.

— Daniel Apon

4

To też nie jest prawdziwa odpowiedź. Z pewnością problemem tutaj jest obecność astronomicznej liczby symetrii, które oszukują nawet najlepsze rozwiązania SAT na najlepszych superkomputerach. Takie symetrie odwzorowują rozwiązania na rozwiązania i nierozwiązania na nierozwiązania: w tym przypadku prawdopodobnie istnieje ogromna liczba prawie rozwiązań (tj. Zadania spełniające wszystkie z wyjątkiem niewielkiej liczby klauzul), z których każde można uzyskać w dowolny inny sposób stosując odpowiednią symetrię. W związku z tym solver marnuje ogromną ilość czasu na wypróbowanie każdego z tych prawie rozwiązań, podczas gdy w pewnym sensie wszystkie są takie same.

Wykorzystanie symetrii (patrz ten artykuł) powinno być drogą do eksploracji, aby zaatakować tę trudną instancję 17x17 i poczynić pewne postępy. Zastanawiam się, czy ktoś już próbował to zrobić.

— Giorgio Camerani
źródło

Hej, to całkiem słodkie! :) Nie widziałem tego wcześniej.

— Daniel Apon

@Daniel: Nie ma za co! ;-) Mam nadzieję, że to pomoże.

— Giorgio Camerani

Użyłem programu „Shatter” Aloula do wielu kodowań problemu 17x17 i umieściłem kilka tygodni CPU w kilku różnych rozwiązaniach SAT i nie miałem szczęścia. Artykuł, do którego powołuje się Walter, jest właściwie pierwszym z kilkunastu lub czegoś, co napisał na ten temat, więc może być tam coś, co wykona zadanie, ale nie jest to nisko wiszący owoc.

— Jay Kominek

3

Ponownie, nie jest to prawdziwa odpowiedź, ale tak czy inaczej, oto kilka przemyśleń na temat przyjęcia algorytmów kolorowania wykresów dla tego problemu.

$I$ $I$

$n$ $m$ $k$
$n$ $m$ $k$
$n$ $m$ $k$

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

Jeśli rodzina wszystkich (maksymalnych) niezależnych zbiorów ma wystarczająco ładną strukturę, może być również możliwe dostrojenie algorytmu produktu pokrywającego.

— Janne H. Korhonen
źródło

W jaki sposób roszczenie 3 jest równoważne roszczeniu 2? Nawiasem mówiąc, maksymalny niezależny zestaw dla 17x17 ma rozmiar 74, jak pokazano w pracy Elizabeth Kupin (pdf) . Jest tylko jeden taki zestaw, nie licząc permutacji wierszy i kolumn jako odrębnych.

— Null Set

Mam na myśli maksimum w tym sensie, że żaden właściwy nadzbiór nie jest niezależny, jak to jest zwykle w informatyce. Maksymalne to słowo zwykle używane w znaczeniu „największego możliwego rozmiaru”.

— Janne H. Korhonen

W takim przypadku zestaw maksymalnych niezależnych zestawów zawiera wszystkie permutacje wierszy / kolumn unikalnego zestawu o rozmiarze 74 i żadnych niezależnych zestawów o rozmiarze 73, ponieważ wszystkie są podzestawami zestawu o rozmiarze 74. Nie jestem pewien, co ma od rozmiarów 67 do 72.

— Null Set

3

Siatka 21x12 jest również 4-kolorowa bez monochromatycznych prostokątów !!!

Zobacz ostatni post Bernda Steinbacha na blogu Gasarcha !

— Marzio De Biasi
źródło

-4

To jest Bill Bouris. Cześć, Dan. Pracuję nad programem, który szuka odpowiedniej matrycy 17x17, która wykazuje brak 4-kolorowania zgodnie z teorią Ramseya. Używam macierzy pozycyjnej przedstawiającej wszystkie połączenia między punktami i naprawiam główną przekątną i pozwalam, aby górny rząd matrycy przebiegał przez wszystkie możliwe kombinacje 16choose8; Przechwytuję tylko macierze, które przechodzą w odniesieniu do następujących kryteriów ... no-XRRR, no-RXRR, no-RRXR, no-RRRX, no-XBBB, no-BXBB itp., A następnie przeglądam macierz za pomocą następnego najsłabsze kryteria ... no-XBRR, noBXRR, no-BBXR, no-BBRX, no-XRBB, no-RXBB itp. dla łącznie 32 przeglądów, aż komputer automatycznie wypełni kolorowanie. Zauważyłem, że istnieje potencjalny kandydat na każde 400 macierzy z łącznej liczby 12780, a znalezienie kandydata lub 0,10 godziny zajmuje 0,95 godziny. 644 sekundy. Nadchodzi, ale nie mam dużo czasu na programowanie ... ponieważ pracuję na pełny etat. Powinniśmy współpracować ... Przydałbym się 289,00 $!

— William Bouris
źródło

Bill Gasarch powinien wypłacić tylko 128 USD.

— William Bouris

przepraszam za to ... 272/2 lub 136 $

— William Bouris

4

To nie jest odpowiedź na pytanie. najlepiej jako komentarz.

— Suresh Venkat