Раскраска для математиков

Одна из самых красивых и до сих пор не решенных задач математики формулируется следующим образом. Попытаемся раскрасить плоскость так, чтобы никакие две точки, находящиеся на расстоянии одного сантиметра друг от друга, не оказались покрашены в один цвет. Какое минимальное число цветов для этого потребуется? Несмотря на кажущуюся простоту, за почти 70 лет существования этой задачи точного ответа до сих пор нет, притом что над ним работала целая плеяда выдающихся ученых, в том числе и Пал Эрдёш, один из крупнейших математиков XX века.

Примерно 60 лет назад математики выяснили, что это минимальное число цветов равно или четырем, или пяти, или шести, или семи — и до последнего момента этот результат не удавалось улучшить. Но на прошлой неделе британец Обри ди Грей опубликовал статью, в которой доказал, что четырех красок тоже не хватает, сократив число вариантов до трех: пять, шесть или семь.

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

Редакция N + 1 решила разобраться в истории задачи о раскрашивании плоскости (и не только) и рассказать о том, как математик-любитель смог сделать новый важный шаг к ее решению, в некотором смысле опередив многих профессионалов.

Формулировка проблемы

Сегодня никто не сомневается в том, что задача о раскрашивании плоскости — из области теории графов. Она возникла в середине XX века, причем, по всей видимости, независимо друг от друга ее придумали сразу несколько математиков — к числу авторов причисляют и самого Пала Эрдёша. В «Математической книге раскрасок» Александр Сойфер рассказывает о результатах своих попыток установить авторство задачи — опросив несколько математиков, Александр пришел к выводу, что первым сформулировал задачу Эдвард Нельсон — тогда студент Университета Чикаго. В 1950 году Эдвард Нельсон занимался проблемой раскрасок планарных графов, которая позднее получила название теоремы о четырех красках.

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

У этой проблемы есть более простая эквивалентная формулировка: возьмем некоторую карту, нарисованную на плоскости. Она состоит из замкнутых областей, граничащих друг с другом. Всегда ли эту карту можно раскрасить в четыре цвета так, чтобы никакие две страны одного цвета не имели общей границы?

Нельсон предположил, что вместо того, чтобы раскрашивать всевозможные планарные графы, можно построить один огромный граф, в котором содержатся все возможные планарные графы. И тогда, если доказать, что этот «суперграф» раскрашиваем по правилам в четыре цвета, то утверждение теоремы станет очевидным следствием.

Кандидатом на роль «большого-большого» графа стала такая конструкция: возьмем все (без исключения) точки плоскости. Они станут вершинами нашего графа. Если пара точек находится на расстоянии длиной в единицу (например, в один сантиметр), то мы соединим их отрезком — эти отрезки станут ребрами нашего графа. Конечно, он не будет планарным. Вопрос, который задал Нельсон: можно ли раскрасить вершины такого графа в четыре цвета?

Эта формулировка, при внимательном рассмотрении, полностью совпадает с обычной задачей о раскрашивании плоскости. Просто нам надо увидеть за каждой из точек плоскости вершину графа, соединенную огромным числом ребер с другими вершинами.

Сразу стоит заметить — к сожалению, идея Нельсона не помогла в решении задачи о четырех красках. Настоящее доказательство было представлено лишь 26 лет спустя Кеннетом Аппелем и Вольфгангом Хакеном и оно было основано на классификации всех возможных планарных графов (карт) на 1936 различных категорий (позднее упрощено до 633), раскрашиваемость каждой из которых можно проверить. Это доказательство стало первым компьютерным доказательством сложной математической задачи. Так перебор победил любимое математиками обобщение.

Первые результаты

Первые шаги к решению задачи о раскрашивании плоскости сделать очень просто. Задумаемся над тем, какого количества цветов точно не хватит. Очевидно, одной краски будет мало. А хватит ли двух?

Легко показать, что и двух цветов недостаточно. Для этого потребуется доказательство от противного. Пусть мы раскрасили нашу плоскость в два цвета. Тогда возьмем на ней равносторонний треугольник со стороной равной одному сантиметру. Первая вершина — синяя, вторая — красная. А какого цвета третья вершина? Так как она находится на расстоянии одного сантиметра от первых двух, то ни синей, ни красной быть не может. Налицо логическое противоречие.

Немного сложнее показать, что и трех красок недостаточно. Возьмем ромб, состоящий из двух склеенных между собой по стороне правильных единичных треугольников, и попытаемся его раскрасить. Две склеенных вершины пусть будут синего и красного цвета, а оставшиеся две совершенно точно окажутся третьего, например зеленого, цвета. Расстояние между этими двумя зелеными вершинами равно квадратному корню из трех — никаких противоречий с условием теоремы здесь не возникает.

Но на самом деле мы только что доказали, что любые две точки на плоскости, расположенные друг от друга на расстоянии квадратного корня из трех, будут одноцветными. Значит, если мы возьмем одну зеленую точку и построим вокруг нее окружность диаметром корень из трех, окажется что она тоже будет зеленой! Но между некоторыми точками этой окружности точно будет единичное расстояние (у каждой точки окружности будет минимум две таких соседки). А это уже противоречит условию. Этот результат был получен Гуго Хадвигером в 1961 году — кстати, Хадвигера считают вторым автором задачи о хроматическом числе.

Это построение можно легко упростить — тогда мы получим известную фигуру под названием «веретено Мозера». Возьмем две копии нашего ромба с общей зеленой вершиной и немного повернем их друг относительно друга — так, чтобы расстояние между двумя другими «зелеными» вершинами стало единицей. Вершины такого графа, конечно же, нельзя раскрасить в три цвета — красок потребуется как минимум четыре.

Итак, мы выяснили, что при соблюдении исходного условия нельзя раскрасить плоскость в три цвета. Но можно ли вообще хоть как-то раскрасить плоскость так, чтобы эта раскраска соответствовала требованию задачи? Ответ: да, конечно. Простейшая раскраска, приходящая в голову, — сетка из квадратов со стороной 0,51 сантиметра, состоящая из повторяющихся сегментов 3x3, покрашенных в девять разных цветов. Минимальное количество цветов, для которого известна раскраска плоскости, равно семи: в ее основе лежит замощение плоскости шестиугольниками, на манер пчелиных сот.

Математики пытались сократить число цветов для верхней границы, но это оказалось не так просто. Например, в одной из раскрасок плоскости семиугольниками и квадратами доля площади, покрашенной в седьмой цвет, не превышает 0,3 процента. Им окрашены лишь маленькие квадраты. Но полностью избавиться от него не выходит.

Все эти простые результаты были получены еще до 1962 года. И на протяжении более полувека продвинуться в решении этой задачи не удавалось.

Неуловимое число

Особенность задачи о хроматическом числе заключается в том, что, по всей видимости, какого-то общего подхода или инструмента для ее решения нет (или пока нет). С другой стороны, раскрашивание графов было неплохо исследовано, и открыта важная теорема, которая появилась независимо от задачи про плоскость в 1951 году и указывает некоторый путь к тому, как может выглядеть решение. Это теорема де Брёйна-Эрдёша.

Вернемся к формулировке, которую дал для задачи о хроматическом числе Эдвард Нельсон. По сути, наша цель — раскрасить огромный бесконечный граф, в котором вершинами являются все, без исключения, точки действительной плоскости. Николаас де Брёйн и Пал Эрдёш исследовали, как соотносится раскраска бесконечного графа и отдельных его частей, субграфов. Оказывается, хроматическое число бесконечного графа — если оно вообще конечно — равно максимальному хроматическому числу его конечных подграфов.

Мы уже знаем, что хроматическое число плоскости конечно, не превышает семи. Значит, если оно равно, скажем, шести, то мы точно сможем построить конечный граф с единичными расстояниями между связанными вершинами, для «правильной» покраски которого потребуется как минимум шесть цветов. К сожалению, доказать, что другого графа с хроматическим числом, равным семи, не существует, с помощью этой теоремы не выйдет. Зато, если найти такой граф с хроматическим числом, равным семи, то задача о хроматическом числе плоскости будет наконец-то решена.

Стоит заметить, что доказательство теоремы требует использования специальной аксиомы теории множеств — аксиомы выбора. Не вдаваясь в подробности, заметим, что не все системы аксиом включают ее и в некоторых специальных случаях эта теорема может оказаться неверна. А значит, и хроматическое число плоскости, в теории, может зависеть от выбора аксиом.

Другие хроматические числа

Задача о раскрасках плоскости легко расширяется. Например, можно попробовать раскрашивать с теми же требованиями пространства высших размерностей: ничто не мешает раскрашивать трехмерное или четырехмерное пространства. Больше того, можно рассматривать не только плоскости действительных чисел, но и ограничиться только рациональными числами. Для этого случая хроматическое число окажется удивительным образом равным двум. Есть и некоторые другие специальные формулировки задачи, в которых запрещается не одно, а несколько расстояний.

Пятицветный граф

Теорема де Брёйна-Эрдёша словно бы предлагает строить все более и более сложные графы с единичными расстояниями между связанными вершинами и исследовать их хроматические числа. Именно этим и решил заняться Обри ди Грей. По сути, он сделал следующее: нашел маленький граф, в котором есть два разных типа раскрасок в четыре цвета, и вплел его сначала в один огромный граф, который запретил первый тип раскрасок, а потом в другой, запретивший второй тип раскрасок. Объединив эти два графа, ди Грей получил новый, еще более монструозный, граф с 20 тысячами вершин, в котором для исходного маленького графа запрещены обе раскраски в четыре цвета. А значит, без пятого цвета не обойтись.

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

Построим правильный шестиугольник со стороной, равной одному сантиметру, поставим точку в его центре и соединим ее с вершинами. Все нарисованные нами отрезки имеют единичную длину, перед нами граф с 7 вершинами и 12 ребрами. Попытаемся раскрасить его в четыре цвета всеми возможными способами. Оказывается, есть всего лишь четыре принципиально различных раскраски шестиугольника, причем в двух из них возникают равносторонние треугольники со стороной, равной квадратному корню из трех, все вершины которых окрашены в один цвет. Их ди Грей называет монохроматическими тройками.

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

Затем ди Грей построил другой граф, в котором монохроматические тройки запрещены. Первая попытка построить этот граф компьютерным перебором, взяв за основу много веретен Мозера, провалилась. Но затем ди Грей заменил их на граф, в котором одна вершина окружена тридцатью другими, лежащими на единичной окружности определенным образом. Затем он взял еще тридцать таких сеток и совместил их центры с вершинами исходного 31-вершинного графа. Получилась 1345-вершинная конструкция — она называется графом W. Семь копий W ди Грей поместил в вершины самого первого единичного шестиугольника с седьмой вершиной в центре и проверил, как его можно раскрасить. Компьютерный перебор показал, что в центральном шестиугольнике не может возникнуть монохроматической тройки.

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

В конце статьи ди Грей также приводит упрощенный 1567-вершинный граф, который также требует для раскрашивания пять цветов. Правда, как оказалось, в этом месте британец немного ошибся и удалил слишком много вершин.

А что дальше?

Сразу после публикации препринта на arXiv.org профессиональные математики приступили к проверке доказательства. Несмотря на некоторый скепсис — любитель продвинулся в задаче, в которой никто не мог продвинуться почти 60 лет? — оказалось, что решение в целом верно. Это подтвердила многократная независимая компьютерная проверка построения. Правда, с упрощенным графом вышла ошибка — оказалось, что он все же раскрашиваем в четыре цвета. Но этот «баг», как его назвали математики, легко исправляется добавлением 18 вершин, которые ди Грей удалил на последних шагах упрощения.

Вслед за этим ди Грей, посоветовавшись с Терренсом Тао, опубликовал новую задачу на сайте проекта Polymath Projects по поиску возможных упрощений пятицветного графа. На сегодняшний момент лучший результат предложил Марайн Хюле (Marijn Heule) из Университета Техаса, сократив число вершин до 826. Кстати, про работы Марайна мы писали два года назад — он является автором самого большого компьютерного доказательства.

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

Важный результат?

Мы обратились за комментарием о значении результатов Обри ди Грея к Андрею Райгородскому, заведующему лабораторией продвинутой комбинаторики и сетевых приложений и директору Физтех-школы прикладной математики и информатики. Публикуем ниже его расширенный комментарий.

«Для плоскости это выдающийся результат, безусловно. Удивительно, что за 70 лет математики — любители и профессионалы — так и не продвинулись. Другое дело, что на большие размерности всерьез это не обобщить. Может быть, если c помощью такой же идеи повозиться с компьютером, то получится улучшить нижнюю границу с шестерки до семерки в размерности три, но это уже не так ярко. В размерности четыре сейчас оценка девять, и она тоже компьютерная, ее сделал Джоффри Экзу, который сейчас активно участвует в обсуждении работы ди Грея на polymathprojects.org и пытается сделать количество вершин поменьше. Но в асимптотике это ничего не даст, это точно.

Когда мы хотим сделать что-то для хроматического числа N-мерного пространства (Rⁿ), то мы хотим получить какое-то улучшение асимптотики. Сейчас есть экспоненциальная оценка, некая константа в степени n. Улучшить константу в основании экспоненты способом ди Грея нельзя. Но в малых размерностях, может быть, это стимулирует какую-то деятельность на компьютере и улучшит оценки.

Но этот результат — ровно для плоскости. Даже если мы возьмем хроматическое число четырехмерного пространства, то нижняя оценка для него сейчас девять, а верхняя порядка тридцати-сорока. И разрыв между нижними и верхними оценками растет экспоненциально. От того, что кто-то улучшит нижнюю оценку на единичку, великого прорыва не случится.

Задачу о хроматическом числе можно расширять. Даже на плоскости есть масса нетривиальных вопросов. Вот, например, давайте у нас раскраска будет устроена не абы как, а так, чтобы точки каждого цвета соответствовали измеримому множеству. Тогда нам потребуется не меньше пяти цветов. Но раз уж мы теперь выяснили, что нам и так надо не меньше пяти цветов, то надо думать, почему число цветов для раскраски измеримыми множествами меньше шести.

Мы можем ограничивать суть цвета. Называть цветом на плоскости множества каких-то хороших точек, например, измеримые, как в примере выше, или ограниченные жордановыми кривыми. Это означает, что мы будем красить плоскость какими-то кляксами, это еще более сильное ограничение, чем измеримость. Для покраски кляксами, например, известно, что хроматическое число не может быть меньше шести (и, конечно, не больше семи).

Алексей Белов-Канель предложил еще один любопытный результат — для покраски прослойки. Возьмем тонкую прослойку в трехмерном пространстве с ненулевой толщиной, причем толщина может быть сколь угодно маленькой. Ясно, что верхняя оценка для хроматического числа такой фигуры тоже семь: мы можем покрасить ее так же, как и плоскость в шестиугольники, а затем построить над ними такие призмы. Когда мы красим плоскость, то шестиугольное замощение оставляет у нас некоторый запас, позволяющий заполнить пространство прослойки. Оказалось, что если рассматривать такую прослойку в трехмерном пространстве, то на ее покраску уйдет минимум от пяти до семи цветов, а в четырехмерном — от шести до семи.

Может быть, на основе компьютерного вычисления можно сделать что-то еще лучшее. Может, получится придумать, как умножить плоскость на какую-то [0, ε²⁵], чтобы в этой размерности в точности семь цветов было. Сейчас у меня куча народу этим занимается и проверяет.

Если есть желание найти точное хроматическое число, то это только про плоскость или про трехмерное пространство. В общем случае не видно вообще никаких инструментов. То, что сделал Обри ди Грей, — он просто придумал некий способ конструирования конкретного графа. Хорошо, что он сработал для размерности два, но это никак не обобщается на размерность N. Это вполне стандартная идея, она витала в воздухе.

Есть шанс, что мы найдем когда-нибудь хроматическое число плоскости. Но я не верю, что у нас есть хоть какой-то шанс найти хроматическое число Rⁿ в точности. Асимптотические оценки сверху и снизу будут.

Есть похожие классические задачи в комбинаторике, такие как число Рамсея. Никто не знает, чему равно число Рамсея от параметров (5, 5). Общей формулы для числа Рамсея для параметров S и T никто не ожидает получить в ближайшем будущем. И это не вопрос о построении конкретного графа, как это сделал Обри ди Грей. Это вопрос о том, как в принципе устроен мир. Это гораздо сложнее.

Надо сказать, что Сойфер верил, что хроматическое число будет не меньше пяти. В каком то смысле Александр предсказал то, что сделал ди Грей. Я верил, что хроматическое число будет равно четырем, — потому что долгое время никто не мог сделать пять. Сейчас не очень понятно, во что верить. Наверное, не семь — пять или шесть, трудно судить, непонятно пока», — завершил свою мысль Андрей Райгородский.

Зачем?

Задача раскрасок графов, на самом деле, имеет вполне конкретные применения в программировании и оптимизации. В некотором смысле, даже судоку можно свести к раскраске графа. Но, конечно же, многие математические задачи решаются совсем не ради практических применений. Лучшей иллюстрацией этого положения будет цитата из книги Александра Сойфера «Математическая книга раскрасок»:

«Уже много лет я убежден, что хроматическое число будет равно 7 или 6. Как-то раз Пал Эрдёш сказал, что у Бога есть бесконечная книга, в которой содержатся все теоремы и самые лучшие их доказательства, и некоторым Он показывает ее на мгновение. Если бы я был удостоен такой чести и у меня был бы выбор, я бы попросил заглянуть на страницу с задачей о хроматическом числе плоскости. А вы?»

Владимир Королёв