Одна из самых красивых и до сих пор не решенных задач математики формулируется следующим образом. Попытаемся раскрасить плоскость так, чтобы никакие две точки, находящиеся на расстоянии одного сантиметра друг от друга, не оказались покрашены в один цвет. Какое минимальное число цветов для этого потребуется? Несмотря на кажущуюся простоту, за почти 70 лет существования этой задачи точного ответа до сих пор нет, притом что над ним работала целая плеяда выдающихся ученых, в том числе и Пал Эрдёш, один из крупнейших математиков XX века.
Примерно 60 лет назад математики выяснили, что это минимальное число цветов равно или четырем, или пяти, или шести, или семи — и до последнего момента этот результат не удавалось улучшить. Но на прошлой неделе британец Обри ди Грей опубликовал статью, в которой доказал, что четырех красок тоже не хватает, сократив число вариантов до трех: пять, шесть или семь.
Примечателен также тот факт, что сам ди Грей далек от фундаментальной математики, область его профессиональных интересов больше связана с биомедициной — он является ведущим научным сотрудником фонда SENS борьбы со старением. Пожалуй, ближе всего к математике относятся его статьи, посвященные искусственному интеллекту в медицине.
Редакция решила разобраться в истории задачи о раскрашивании плоскости (и не только) и рассказать о том, как математик-любитель смог сделать новый важный шаг к ее решению, в некотором смысле опередив многих профессионалов.
Формулировка проблемы
Задача о хроматическом числе плоскости
Каково наименьшее число цветов, достаточное для раскрашивания плоскости таким образом, чтобы на ней не было двух точек одного цвета, расположенных на расстоянии 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. Кстати, про работы Марайна мы писали два года назад — он является автором самого большого компьютерного доказательства.