Хроматическое число плоскости не меньше 5

в 10:25, , рубрики: граф единичных расстояний, математика, нерешенная проблема, раскрашивание плоскости, хроматическое число

Задача о хроматическом числе плоскости формулируется следующим образом: в какое наименьшее число цветов можно раскрасить плоскость так, чтобы любые две точки на расстоянии 1 были покрашены в различные цвета?

Эту задачу сформулировали Хуго Хадвигер и Пал Эрдёш в сороковых годах XX века. Независимо от них примерно в то же самое время этой задачей занимались Эдуард Нелсон и Дж. Р. Исбелл. После работы Хадвигера 1961 года об открытых на тот момент проблемах, хроматическое число плоскости стало активно изучаться.

Сразу же было показано, что в 3 цвета плоскость требуемым образом раскрасить нельзя, однако 7 цветов достаточно. Действительно, легко выбрать на плоскости несколько точек так, что некоторые из них находятся на расстоянии ровно 1 (такая конструкция точек называется графом единичных расстояний), и затем перебором показать, что в 3 цвета эти точки раскрасить невозможно. Примеры таких графов — веретено Мозера и граф Голомба приведены на картинке ниже. Чтобы показать, что 7 цветов достаточно, замостим плоскость правильными шестиугольниками со стороной 0.4 и закрасим их по определенному паттерну, как на картинке ниже. Тогда, как несложно убедиться, концы любого отрезка длины 1 будут лежать в разных шестиугольниках различных цветов.

Хроматическое число плоскости не меньше 5 - 1

Однако, с тех пор никто не мог уточнить ни верхнюю, ни нижнюю границы. Задача получила название Проблема Нелсона — Эрдёша — Хадвигера. Прошло 60 лет, и вот, в апреле 2018 года математик-любитель Обри де Грей предъявил граф единичных расстояний, который нельзя покрасить в 4 цвета.

Геронтология и математика

imageОбри Дэвид Николас Джаспер ди Грей — британский геронтолог, исследует различные аспекты старения человека. Является разработчиком концепции SENS — «стратегии достижения пренебрежимого старения инженерными методами» (strategies for engineered negligible senescence). Председатель и директор по науке Фонда SENS, главный редактор академического журнала «Rejuvenation Research». Автор научно-популярной книги «Ending Aging», в которой в деталях рассматривается вопрос о полной победе над старением средствами медицины в течение ближайших нескольких десятилетий. (инфо из вики)

Как оказалось, этот почтенный бородатый дядька еще и увлекается математикой в свободное время. 8 апреля 2018 года он выложил на arXiv статью, в которой описывает способ построения графа единичных расстояний, для покраски которого нужно как минимум 5 цветов.

Давайте разберемся подробнее, что же это за граф такой.

Граф, который построил Джек

Все начинается с простого графа H, состоящего из 7 вершин и 12 ребер:

Хроматическое число плоскости не меньше 5 - 3

Давайте попробуем раскрасить его в не более чем в 4 цвета всевозможными способами. Оказывается, различных (в точностью до поворотов, отражений и порядка цветов) способов это сделать всего 4:

Хроматическое число плоскости не меньше 5 - 4

Заметим, что в верхних двух вариантах у нас есть тройки одноцветных вершин, которые расположены в вершинах правильного треугольника, а в нижних двух — нет. Назовем раскраску графа H плохой, если там есть такая одноцветная тройка, иначе раскраска H — хорошая. Итого, у нас 2 плохие раскраски и 2 хорошие.

Хорошо, идем дальше. Рассмотрим граф J, склеенный из 13 графов H (найдите их все!):

Хроматическое число плоскости не меньше 5 - 5

Давайте попробуем покрасить граф J так, чтобы покраски всех входящих в него подграфов H были хорошие. Немного терпения, и мы получаем 6 различных вариантов (опять же с точностью до всяких эквивалентных преобразований, указанных выше; плюс цветов вершин, отмеченных черным):

Хроматическое число плоскости не меньше 5 - 6

Черные вершины могут быть покрашены несколькими способами, но их покраска нам не особо важна. Тем не менее, выкидывать их из графа J нежелательно — тогда появляются «лишние» варианты покраски. Которые, к тому же, портят все дальнейшие построения. Поэтому пусть черные вершины остаются.

Теперь давайте внимательно посмотрим на получившиеся варианты. А именно, на центральную вершину и на 6 вершин, удаленных от центральной на расстояние 2 (этаких граф H, увеличенный в два раза). Мы видим, что там всегда используется не более двух цветов. Более того, все варианты можно разбить на 3 случая:

  • a). Все 7 вершин одного цвета.
  • b). 4 вершины из 6 по краям того же цвета, что и центральная, и они идут подряд по обходу по часовой или против часовой стрелки. Остальные 2 вершины другого цвета.
  • c). 2 вершины из 6 по краям того же цвета, что и центральная, и они расположены по диагонали друг относительно друга. Остальные 4 вершины другого цвета.

Запомним эти наблюдения и перейдем к графу K, который составлен из двух копий графа J следующим образом: мы накладываем одну копию J на другую так, чтобы центральные вершины совпали, а затем крутим их друг относительно друга так, чтобы каждая из 6 вершин, которые мы рассматривали чуть выше, одного графа отъехала от соответствующей вершины другого графа на расстояние ровно 1 (я отметил эти расстояние чуть ниже голубым цветом). И вот он граф K:

Хроматическое число плоскости не меньше 5 - 7

Уже становится немного сложно, не правда ли?

Теперь давайте опять немного помедитируем на получившуюся конструкцию. А именно давайте поймем какие типы раскрасок у каждой копии графа J могли быть из тех трёх, что были перечислены выше. Типа a) раскраски там нет, так как какой бы тип ни был у второй копии, мы получим две вершины одного цвета на расстоянии 1. Типа b) там тоже нет: если у второй копии тоже тип b), то какие-то 2 вершины цвета центра «мешают» друг на другу; если у второй копии тип c), то хотя бы одна вершина на концах одноцветной диагонали будет соответствовать одной из четырех вершин первой копии. Стало быть, у обеих копий графа J тип покраски c)! И такие покраски возможны, поскольку 4 вершины, которые покрашены в цвет, отличный от центрального, хотя и имеют один цвет, в каждой из копий этот цвет может быть разным.

Теперь, раз у двух копий графа J в графе K тип c), то пары противоположных вершин (из 6 нами рассматриваемых в каждой копии) имеют один и тот же цвет. Воспользуемся этим наблюдением и сделаем еще один шаг. А именно, построим граф L из двух копий графа K:

Хроматическое число плоскости не меньше 5 - 8

Мы накладываем графы K друг на друга следующим образом: берем в каждом из них пару противоположных вершин и первые вершины в каждой паре совмещаем (на картинке выше это отмечено буквой A), а вторые размещаем на расстоянии ровно 1 (они отмечены буквами B и C). Этот прием называется оверетенением графа (от англ. spindling, где spindle — веретено). Например, веретено Мозера — это оверетенение графа-ромбика, составленного из двух треугольников. По наблюдению чуть выше, вершины A, B и C должны быть одного цвета, B и C на расстоянии 1, значит граф L покрасить нельзя.

Итак, что же, мы все доказали? Да нет же, мы только доказали, что граф L нельзя покрасить в 4 цвета так, чтобы покраски всех копий графа H (а их уже насчитывается 52 штуки!) были хорошими. Значит, в любой покраске графа L покраска хотя бы одного графа H будет плохой!

Плохие покраски графа H

С этой частью, к сожалению, нельзя разобраться без помощи компьютера. Поэтому разберем кратко дальнейшую часть построений, за деталями можно обратиться к оригинальной статье, либо по ссылкам на Polymath чуть ниже. Картинки, взятые из оригинальной статьи, не очень высокого качества, но они позволяют примерно понять, что происходит.

Итак, сначала мы строим граф V на 31 вершину, который состоит из 5 графов H, которые совмещены центрами и повернуты на хитрые углы друг относительно друга:

Хроматическое число плоскости не меньше 5 - 9

Далее мы строим граф W следующим образом: делаем 31 копию графа V и помещаем центр каждой копии в каждую вершину еще одного графа V (такая операция называется суммой Минковского двух графов единичных расстояний, т.е. мы делаем $V oplus V$), после чего удаляем все вершины, которые удалены от центра на расстояние больше $sqrt{3}$. Итого теперь у нас есть граф W на 301 вершину:

Хроматическое число плоскости не меньше 5 - 12

Теперь берем граф H и заменяем каждую его вершину на копию графа W (т.е. делаем $W oplus H$). В итоге получаем граф M на 1345 вершин:

Хроматическое число плоскости не меньше 5 - 14

Полученный граф M в сущности является объединением большой кучи веретён Мозера в различных положениях. И, если мы покрасим в один цвет три вершины на попарном расстоянии $sqrt{3}$ изначального графа H, который мы распушивали до M, тем самым сделав покраску H плохой, то остальную часть графа M покрасить в 4 цвета не получится. Этот факт проверяется компьютерным перебором.

И, наконец, последний шаг: мы теперь берем вот эту жесть M на 1345 вершин и копируем поверх каждой из 52 копии графа H в графе L. В итоге получаем полную жесть на 20425 вершин, которая называется граф N. И этот граф нельзя покрасить в 4 цвета: при покраске каркаса L покраска хотя бы одного из подграфов H получится плохой, и для этого подграфа H соответствующую копию M докрасить до конца не получится.

Что и требовалось доказать.

Уменьшенный граф

Граф на 20425 вершин — довольно большой граф. Можно ли построить пример поменьше? Можно! Еще в оригинальной статье де Грей различными отсечками уменьшил пример до 1581 вершины.

После публикации статьи, математическое сообщество организовало проект Polymath16 (как это было, например, с задачей про простые числа близнецы) для того, чтобы коллективными усилиями уменьшить граф, полученный де Греем, обобщить результат на большие размерности (для трехмерного пространства, четырехмерного, и так далее), а то и улучшить нижнюю границу хроматического числа для плоскости до 6.

Кстати, там же независимо проверили при помощи SAT-солверов, что пример де Грея на 1581 вершину действительно можно покрасить только в 5 цветов, а также то, что его граф является графом единичных расстояний. Так что сомнений в корректности полученного результата нет.

Граф де Грея потихоньку уменьшают. Например, граф L на 121 вершину и 52 копии графа H можно слегка уменьшить до графа L' на 97 вершин и 40 копий графа H. Граф M с 1345 вершинами был уменьшен до графа M' с всего 278 вершинами.

После замещения всех подграфов H на M' а графе L', результат можно улучшать и далее. На момент написания данной статьи наименьший найденный граф единичных расстояний, который нельзя покрасить в 4 цвета, имеет 610 вершин. Вот его картинка (кликабельно):

Автор: Артём Рипатти

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js