Хабрахабр

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

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

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

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

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

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

imageОбри Дэвид Николас Джаспер ди Грей — британский геронтолог, исследует различные аспекты старения человека. Является разработчиком концепции 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 (найдите их все!): Хорошо, идем дальше.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Может быть в скором времени удастся построить граф единичных расстояний, который нельзя покрасить в 5 цветов. Работа продолжается. А затем — в 6, и тогда задача о хроматическом числе плоскости будет решена полностью.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть