Задача о хроматическом числе плоскости формулируется следующим образом: в какое наименьшее число цветов можно раскрасить плоскость так, чтобы любые две точки на расстоянии 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, и тогда задача о хроматическом числе плоскости будет решена полностью.