Обновление : теперь известен набор препятствий (то есть «барьер» NxM между размерами окрашиваемой и неокрашиваемой сетки) для всех четырехцветных цветов без монохроматического прямоугольника .
Кто-нибудь испытывает желание попробовать 5 цветов? ;)
Следующий вопрос возникает из теории Рамсея .
Рассмотрим -раскраска в п матрицу с размерностью м сетки графика. A существует всякий раз, когда четыре ячейки одного цвета расположены как углы некоторого прямоугольника. Например, ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 1 ) , и ( 1 , 0 ) образуют монохроматический прямоугольник , если они имеют один и тот же цвет. Аналогично, ( 2 , 2 ) , ( 2 , 6 ) ,monochromatic rectangle
и ( 3 , 2 ) образуют монохроматический прямоугольник, если цвета с тем же цветом.
Вопрос : существует ли - цвет сетки 17 на 17 , который не содержит монохроматического прямоугольника? Если так, предоставьте явную раскраску.
Некоторые известные факты:
- матрицаразмерностью 17 является 4 -раскрашиваемым без монохроматического прямоугольника, но известная схема окраски не представляется распространяться на 17 матрицуразмерностью 17 случая. (Я опускаю известные 16 матрицуразмерностью 17 окраскупотому что это очень вероятнобудет отвлекающим маневр для принятия решения 17 матрицыразмерностью 17 )
- матрицыразмерностью 19 этоНЕ 4 -раскрашиваемыми без монохроматического прямоугольника.
- - 18 и 18 - 18 также неизвестные случаи; ответ на них был бы также интересен.
Отказ от ответственности: Билл Гасарч имеет вознаграждение в размере 289 долларов США за положительный ответ на этот вопрос; Вы можете связаться с ним через его блог. Примечание по этикету: я позабочусь, чтобы он знал источник любого правильного ответа (если он возникнет).
Он снова поднял этот вопрос во время сногсшибательного сеанса на «Барьерах II», и я нахожу это интересным, поэтому я задаю этот вопрос здесь (без его ведома, хотя я сильно сомневаюсь, что он будет против).
источник
Ответы:
Некоторые из вас, вероятно, знают об этом, но проблема раскраски 17 x 17 была решена Берндом Штейнбахом и Кристианом Постхоффом. Смотрите сообщение в блоге Gasarch здесь .
источник
На самом деле это не ответ на вопрос, но я закодировал задачу 4-раскраски 17x17 как 4-CNF (в стандартном формате DIMACS для SAT-решателей) и загрузил ее здесь . Если у кого-то есть доступ к хорошему SAT-решателю (и суперкомпьютеру!), Возможно, мы сможем добиться определенного прогресса.
источник
Это тоже не настоящий ответ. Конечно, проблема здесь заключается в наличии астрономического числа симметрий, которые обманывают даже лучшие решатели SAT на лучших суперкомпьютерах. Такие симметрии отображают решения для решений и не решения для не-решений: в этом случае, вероятно, существует огромное количество почти-решений (т.е. присваиваний, удовлетворяющих всем, кроме небольшого количества предложений), каждое из которых может быть получено любым другим применяя правильную симметрию. Следовательно, решатель тратит огромное количество времени, пытаясь найти каждое из этих почти решений, хотя в определенном смысле они все одинаковы.
Использование симметрий (см. Эту статью) должно стать способом исследования, чтобы атаковать этот жесткий экземпляр 17x17 и добиться некоторого прогресса в этом. Интересно, кто-нибудь уже пытался это сделать?
источник
Опять же, не реальный ответ, но в любом случае, вот некоторые мысли о принятии алгоритмов раскраски графа для этой проблемы.
Если семейство всего (максимального) независимого множества имеет достаточно красивую структуру, также может быть возможно точно настроить алгоритм произведения покрытия.
источник
Сетка 21x12 также 4-цветная без монохроматических прямоугольников !!!
Смотрите последний пост Бернда Стейнбаха в блоге Гасарха !
источник
Это Билл Бурис. Привет, Дэн. Я работаю над программой, которая ищет подходящую матрицу 17x17, которая показывает раскраску без 4 в соответствии с теорией Рэмси. Я использую позиционную матрицу, изображающую все связи между точками, и фиксирую основную диагональ и позволяю верхнему ряду матрицы проходить через все возможные комбинации из 16 вариантов выбора; Я фиксирую только те матрицы, которые соответствуют следующим критериям: no-XRRR, no-RXRR, no-RRXR, no-RRRX, no-XBBB, no-BXBB и т. Д., А затем пролистываю матрицу, используя следующую самые слабые критерии ... no-XBRR, noBXRR, no-BBXR, no-BBRX, no-XRBB, no-RXBB и т. д. В общей сложности 32 развертки, пока компьютер автоматически не закрасит окраску. Я заметил, что на каждые 400 матриц есть возможный кандидат из 12780, и для поиска кандидата требуется 0,95 часа или 1 на каждые 8. 644 секунды Это идет вперед, но у меня не так много времени, чтобы программировать это ... так как я работаю полный рабочий день. Мы должны работать вместе ... Я мог бы использовать $ 289,00!
источник