Задача о хроматическом числе плоскости формулируется следующим образом: в какое наименьшее число цветов можно раскрасить плоскость так, чтобы любые две точки на расстоянии 1 были покрашены в различные цвета?
Эту задачу сформулировали Хуго Хадвигер и Пал Эрдёш в сороковых годах XX века. Независимо от них примерно в то же самое время этой задачей занимались Эдуард Нелсон и Дж. Р. Исбелл. После работы Хадвигера 1961 года об открытых на тот момент проблемах, хроматическое число плоскости стало активно изучаться.
Сразу же было показано, что в 3 цвета плоскость требуемым образом раскрасить нельзя, однако 7 цветов достаточно. Действительно, легко выбрать на плоскости несколько точек так, что некоторые из них находятся на расстоянии ровно 1 (такая конструкция точек называется графом единичных расстояний), и затем перебором показать, что в 3 цвета эти точки раскрасить невозможно. Примеры таких графов — веретено Мозера и граф Голомба приведены на картинке ниже. Чтобы показать, что 7 цветов достаточно, замостим плоскость правильными шестиугольниками со стороной 0.4 и закрасим их по определенному паттерну, как на картинке ниже. Тогда, как несложно убедиться, концы любого отрезка длины 1 будут лежать в разных шестиугольниках различных цветов.
Однако, с тех пор никто не мог уточнить ни верхнюю, ни нижнюю границы. Задача получила название Проблема Нелсона — Эрдёша — Хадвигера. Прошло 60 лет, и вот, в апреле 2018 года математик-любитель Обри де Грей предъявил граф единичных расстояний, который нельзя покрасить в 4 цвета.
Геронтология и математика
Обри Дэвид Николас Джаспер ди Грей — британский геронтолог, исследует различные аспекты старения человека. Является разработчиком концепции SENS — «стратегии достижения пренебрежимого старения инженерными методами» (strategies for engineered negligible senescence). Председатель и директор по науке Фонда SENS, главный редактор академического журнала «Rejuvenation Research». Автор научно-популярной книги «Ending Aging», в которой в деталях рассматривается вопрос о полной победе над старением средствами медицины в течение ближайших нескольких десятилетий. (инфо из вики)
Как оказалось, этот почтенный бородатый дядька еще и увлекается математикой в свободное время. 8 апреля 2018 года он выложил на arXiv статью, в которой описывает способ построения графа единичных расстояний, для покраски которого нужно как минимум 5 цветов.
Давайте разберемся подробнее, что же это за граф такой.
Граф, который построил Джек
Все начинается с простого графа H, состоящего из 7 вершин и 12 ребер:
Давайте попробуем раскрасить его в не более чем в 4 цвета всевозможными способами. Оказывается, различных (в точностью до поворотов, отражений и порядка цветов) способов это сделать всего 4:
Заметим, что в верхних двух вариантах у нас есть тройки одноцветных вершин, которые расположены в вершинах правильного треугольника, а в нижних двух — нет. Назовем раскраску графа H плохой, если там есть такая одноцветная тройка, иначе раскраска H — хорошая. Итого, у нас 2 плохие раскраски и 2 хорошие.
Хорошо, идем дальше. Рассмотрим граф J, склеенный из 13 графов H (найдите их все!):
Давайте попробуем покрасить граф J так, чтобы покраски всех входящих в него подграфов H были хорошие. Немного терпения, и мы получаем 6 различных вариантов (опять же с точностью до всяких эквивалентных преобразований, указанных выше; плюс цветов вершин, отмеченных черным):
Черные вершины могут быть покрашены несколькими способами, но их покраска нам не особо важна. Тем не менее, выкидывать их из графа J нежелательно — тогда появляются «лишние» варианты покраски. Которые, к тому же, портят все дальнейшие построения. Поэтому пусть черные вершины остаются.
Теперь давайте внимательно посмотрим на получившиеся варианты. А именно, на центральную вершину и на 6 вершин, удаленных от центральной на расстояние 2 (этаких граф H, увеличенный в два раза). Мы видим, что там всегда используется не более двух цветов. Более того, все варианты можно разбить на 3 случая:
- a). Все 7 вершин одного цвета.
- b). 4 вершины из 6 по краям того же цвета, что и центральная, и они идут подряд по обходу по часовой или против часовой стрелки. Остальные 2 вершины другого цвета.
- c). 2 вершины из 6 по краям того же цвета, что и центральная, и они расположены по диагонали друг относительно друга. Остальные 4 вершины другого цвета.
Запомним эти наблюдения и перейдем к графу K, который составлен из двух копий графа J следующим образом: мы накладываем одну копию J на другую так, чтобы центральные вершины совпали, а затем крутим их друг относительно друга так, чтобы каждая из 6 вершин, которые мы рассматривали чуть выше, одного графа отъехала от соответствующей вершины другого графа на расстояние ровно 1 (я отметил эти расстояние чуть ниже голубым цветом). И вот он граф K:
Уже становится немного сложно, не правда ли?
Теперь давайте опять немного помедитируем на получившуюся конструкцию. А именно давайте поймем какие типы раскрасок у каждой копии графа J могли быть из тех трёх, что были перечислены выше. Типа a) раскраски там нет, так как какой бы тип ни был у второй копии, мы получим две вершины одного цвета на расстоянии 1. Типа b) там тоже нет: если у второй копии тоже тип b), то какие-то 2 вершины цвета центра «мешают» друг на другу; если у второй копии тип c), то хотя бы одна вершина на концах одноцветной диагонали будет соответствовать одной из четырех вершин первой копии. Стало быть, у обеих копий графа J тип покраски c)! И такие покраски возможны, поскольку 4 вершины, которые покрашены в цвет, отличный от центрального, хотя и имеют один цвет, в каждой из копий этот цвет может быть разным.
Теперь, раз у двух копий графа J в графе K тип c), то пары противоположных вершин (из 6 нами рассматриваемых в каждой копии) имеют один и тот же цвет. Воспользуемся этим наблюдением и сделаем еще один шаг. А именно, построим граф L из двух копий графа K:
Мы накладываем графы 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, которые совмещены центрами и повернуты на хитрые углы друг относительно друга:
Далее мы строим граф W следующим образом: делаем 31 копию графа V и помещаем центр каждой копии в каждую вершину еще одного графа V (такая операция называется суммой Минковского двух графов единичных расстояний, т.е. мы делаем 
), после чего удаляем все вершины, которые удалены от центра на расстояние больше 
. Итого теперь у нас есть граф W на 301 вершину:
Теперь берем граф H и заменяем каждую его вершину на копию графа W (т.е. делаем 
). В итоге получаем граф M на 1345 вершин:
Полученный граф M в сущности является объединением большой кучи веретён Мозера в различных положениях. И, если мы покрасим в один цвет три вершины на попарном расстоянии 
изначального графа 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 вершин. Вот его картинка (кликабельно):
Работа продолжается. Может быть в скором времени удастся построить граф единичных расстояний, который нельзя покрасить в 5 цветов. А затем — в 6, и тогда задача о хроматическом числе плоскости будет решена полностью.
Автор: Артём Рипатти
