Британcкий математик-любитель Обри ди Грей впервые за последние 60 лет улучшил результат решения известной математической задачи о хроматическом числе плоскости. Это число — наименьшее количество красок, с помощью которых можно так раскрасить плоскость, чтобы на фиксированной единице расстояния (например, сантиметр) нигде не нашлось двух точек одинакового цвета. Эту задачу не стоит путать с похожей, но уже решенной задачей о раскрашивании карт. Раньше было известно, что хроматическое число плоскости лежит между четырьмя и семью включительно, а теперь Ди Грей показал, что в четыре цвета плоскость точно раскрасить нельзя. Препринт работы опубликован на arXiv.org, сейчас построение проверяется другими математиками.
Исторически задача о раскрашивании плоскости была сформулирована в 1940-х годах Эрдёшем и, независимо от него, в 1950 году Нелсоном. Легко показать, что двух цветов не достаточно для раскрашивания плоскости. Пусть мы раскрасили нашу плоскость в два цвета. Тогда возьмем на ней равносторонний треугольник со стороной в одну единицу расстояния. Первая вершина — синяя, вторая — красная. А какого цвета третья вершина? Так как она находится на расстоянии один от первых двух, то ни синей, ни красной она быть не может. Немного сложнее показать, что и трех красок недостаточно. Для этого нужно построить веретено Мозера: возьмем ромб, состоящий из двух склеенных между собой по стороне правильных единичных треугольников. Сделаем его копию и немного повернем ее вокруг одной из вершин ромба (назовем ее верхней), при этом сделаем так, что расстояние между двумя нижними вершинами стало единицей. Легко увидеть, просто попытавшись раскрасить веретено Мозера, что трех цветов для этой фигуры не хватает.
Возможная раскраска из семи цветов устроена очень просто: она повторяет пчелиные соты. Достаточно просто выложить соты из правильных шестиугольников со стороной в 0,4. До работы Обри ди Грея это были самые сильные ограничения на хроматическое число плоскости в течение последних 67 лет.
В своей статье ди Грей показал, как построить конструкцию из 1567 вершин, которую невозможно раскрасить в четыре цвета так, чтобы никакие две точки на единичном расстоянии не оказались одного цвета. Построение состоит из четырех шагов.
Построим правильный шестиугольник с единичной стороной, поставим точку в его центре и соединим ее с вершинами — она находится на расстоянии единицы от вершин. Попытаемся раскрасить его в четыре цвета всеми возможными способами. Оказывается, есть всего лишь четыре принципиально различных раскраски шестиугольника, причем в двух из них возникают равносторонние треугольники со стороной равной квадратному корню из трех, все вершины которых окрашены в один цвет. Их ди Грей называет монохроматическими тройками.
Оказывается, можно построить такой граф, в котором обязательно найдется монохроматическая тройка. Он будет состоять из 52 таких шестиугольников, правильным образом расположенных на плоскости. Вкратце, построение начинается с шестиугольника, построенного из шестиугольников из абзаца выше, который затем удваивается и поворачивается относительно центра, а затем относительно вершины, лежащей на расстоянии два от центра.
Вторая часть доказательства — построить граф, в котором возникнет шестиугольник, в котором ни при каких раскрасках не может возникнуть монохроматическая тройка. Он состоит из большого количества особым образом расположенных веретен Мозера, которые располагаются вокруг единичного шестиугольника и насчитывает 1345 вершин. На следующем этапе ди Грей копирует этот граф 52 раза так, чтобы его частью оказался граф из предыдущего абзаца, в котором монохроматическая тройка обязательно возникнет. Получившийся 20425-вершинный каркас нельзя раскрасить в четыре цвета, так как иначе возникает противоречие.
Ди Грей также попробовал упростить этот каркас, наилучшим результатом стала конструкция с 1567 вершинами, полученная удалением части точек. Правда, при последующей проверке оказалось, что ее все же можно раскрасить в четыре цвета, но тут же был построен «работающий» пример с 1581-й вершиной.
Редакция N+1 обратилась за комментариями к математикам Андрею Райгородскому и Алексею Канелю-Белову, экспертам в этой области. По словам ученых, сейчас статью ди Грея проверяют компьютерными методами и полный прогон решения на компьютере может занять несколько дней. К проверке привлечены и школьники-олимпиадники, уточнил Канель-Белов.
Интересно, что точно та же задача может быть сформулирована и для пространств высших размерностей (трехмерного, четырехмерного и так далее). К примеру, для трех измерений границы хроматического числа установлены гораздо слабее — оно лежит между 6 и 15. Подробнее о хроматических числах можно почитать в брошюре Андрея Райгородского, изданной МЦНМО 15 лет назад. В общем случае задача не решена до сих пор. Более того, возможно, ее точное решение зависит от аксиоматики теории множеств.
Если утверждение статьи ди Грея подтвердится, то это будет один из редчайших случаев, когда в непростой математической проблеме, которой занималось большое число профессионалов, удалось продвинуться математику-любителю, рассказывает Константин Кноп, преподаватель и популяризатор математики из Санкт-Петербурга. Предыдущий такой случай был связан с замощением плоскости пятиугольными паркетами — в 1976 и 1977 годах новые замощения были открыты Марджори Райс, домохозяйкой без математического образования. А в 2017 году московский школьник-десятиклассник нашел новое ограничение в задаче Данцера и Грюнбаума об острых треугольниках в трехмерном пространстве, что подтолкнуло профессионалов к уточнению оценок в обобщенной задаче.
Обри ди Грей — не профессиональный математик, его интересы лежат скорее в области геронтологии и проблем старения. Он возглавляет фонд SENS, развивающий стратегии достижения пренебрежимого старения инженерными методами.
В математике есть ещё одна, немного похожая задача — о раскрасках карт (иначе, проблема четырех красок). Она была решена Кеннетом Аппелем и Вольфгангом Хакеном в 1972 году компьютерными методами — математики показали, что для любой карты достаточно четырёх красок, чтобы никакие две области одного цвета не граничили друг с другом. Это стало первым компьютерным доказательством крупной математической теоремы.
Владимир Королёв