Введение

Математическая задача

В геометрической теории графов задача Хадвигера — Нельсона, названная в честь Хьюго Хадвигера и Эдварда Нельсона, ставит вопрос о минимальном количестве цветов, необходимых для раскраски плоскости таким образом, чтобы никакие две точки на расстоянии 1 друг от друга не имели одинаковый цвет. Ответ неизвестен, но область возможных значений сужена до одного из чисел 5, 6 или 7. Истинное значение может зависеть от выбора аксиом теории множеств.

Отношение к конечным графам

Вопрос можно сформулировать в терминах теории графов следующим образом. Пусть G — граф единичного расстояния на плоскости: бесконечный граф, вершины которого — все точки плоскости, и между двумя вершинами существует ребро тогда и только тогда, когда расстояние между соответствующими точками равно 1. Задача Хадвигера — Нельсона состоит в нахождении хроматического числа графа G. Следовательно, эту задачу часто называют «нахождением хроматического числа плоскости». По теореме де Брюйна — Эрдоша, результат которой принадлежит , задача эквивалентна (при условии принятия аксиомы выбора) задаче нахождения максимально возможного хроматического числа графа единичного расстояния, состоящего из конечного числа вершин.

История

Согласно теории, проблема была впервые сформулирована Нельсоном в 1950 году и впервые опубликована в 1950 году. Ранее был опубликован связанный результат, показывающий, что любое покрытие плоскости пятью конгруэнтными замкнутыми множествами содержит пару точек на расстоянии единицы в одном из множеств, и он также упомянул эту проблему в более поздней статье. В работе подробно обсуждается проблема и её история. Одно из применений проблемы связывает её с теоремой Бекмана — Кварлеса, согласно которой любое отображение евклидовой плоскости (или пространства более высокой размерности) на себя, сохраняющее единичные расстояния, должно быть изометрией, сохраняющей все расстояния. Конечные раскраски этих пространств могут быть использованы для построения отображений из них в пространства более высокой размерности, сохраняющих расстояния, но не являющихся изометриями. Например, евклидову плоскость можно отобразить в шестимерное пространство, раскрасив её семью цветами так, чтобы никакие две точки на расстоянии единица не имели одного и того же цвета, а затем отобразить точки в соответствии с их цветами в семь вершин шестимерного правильного симплекса с рёбрами единичной длины. Это отображает любые две точки на расстоянии единица в различные цвета, а затем – в различные вершины симплекса, находящиеся на расстоянии единица друг от друга. Однако все остальные расстояния отображаются в ноль или единицу, поэтому это не изометрия. Если число цветов, необходимых для раскраски плоскости, удастся уменьшить с семи до меньшего числа, то такое же уменьшение применимо к размерности целевого пространства в данной конструкции.

Нижняя и верхняя границы

Тот факт, что хроматическое число плоскости должно быть не менее четырех, следует из существования графа единичных расстояний из семи вершин с хроматическим числом четыре, названного шпинделем Мозера в честь его открытия в 1961 году братьями Уильямом и Лео Мозером. Этот граф состоит из двух единичных равносторонних треугольников, соединенных общей вершиной, x. Каждый из этих треугольников соединен по другой стороне с другим равносторонним треугольником; вершины y и z этих соединенных треугольников находятся на единичном расстоянии друг от друга. Если бы плоскость можно было раскрасить в три цвета, то раскраска внутри треугольников вынудила бы y и z иметь тот же цвет, что и x, но тогда, поскольку y и z находятся на единичном расстоянии друг от друга, мы бы не получили правильную раскраску графа единичных расстояний плоскости. Следовательно, для раскраски этого графа и содержащей его плоскости требуется как минимум четыре цвета. Альтернативная нижняя граница в виде графа единичных расстояний из десяти вершин с хроматическим числом четыре, графа Голомба, была обнаружена примерно в то же время Соломоном В. Голомбом. Нижняя граница была повышена до пяти в 2018 году, когда ученый-компьютерщик и геронтолог Обри де Грей обнаружил граф единичных расстояний из 1581 вершины, который нельзя раскрасить в четыре цвета. Доказательство построено с использованием компьютера. Математик Гил Калай и ученый-компьютерщик Скотт Ааронсон опубликовали обсуждение результатов де Грея, а Ааронсон сообщил о независимой проверке результата де Грея с использованием SAT-решателей. Калай предоставил ссылки на дополнительные публикации Джордана Элленберга и Ноама Элкиса, при этом Элкис и (отдельно) де Грей предложили проект Polymath для поиска графов единичных расстояний, которые нельзя раскрасить в четыре цвета, с меньшим количеством вершин, чем в конструкции де Грея. По состоянию на 2021 год самый маленький известный граф единичных расстояний с хроматическим числом 5 имеет 509 вершин. Страница проекта Polymath, , содержит дальнейшие исследования, упоминания в СМИ и данные проверки. Верхняя граница в семь для хроматического числа следует из существования разбиения плоскости на правильные шестиугольники с диаметром чуть меньше единицы, которым можно назначить семь цветов в повторяющемся порядке, чтобы сформировать 7-раскраску плоскости. Согласно , эта верхняя граница была впервые отмечена Джоном Р. Избеллом.

Вариации

Проблема может быть легко расширена на более высокие размерности. Нахождение хроматического числа 3-мерного пространства является особенно интересной задачей. Как и в случае с версией на плоскости, ответ неизвестен, но было показано, что он не меньше 6 и не больше 15. В n-мерном случае задачи, простая верхняя оценка на количество необходимых раскрасок, полученная из мощения n-мерными кубами, равна . Нижняя оценка, основанная на симплексах, равна . Для , доступна нижняя оценка, использующая обобщение шпинделя Мозера: пара объектов (каждый из которых состоит из двух симплексов, склеенных по грани), соединенных с одной стороны точкой, а с другой – линией. Экспоненциальная нижняя оценка была доказана Франклом и Уилсоном в 1981 году. Можно также рассмотреть раскраски плоскости, в которых множества точек каждого цвета ограничены множествами определенного типа. Такие ограничения могут привести к увеличению необходимого количества цветов, поскольку они исключают некоторые раскраски из числа допустимых. Например, если раскраска плоскости состоит из областей, ограниченных кривыми Жордана, то требуется не менее шести цветов.