Задача Нелсона — Эрдёша — Хадвигера

Задача Нелсона — Эрдёша — Хадвигера — задача комбинаторной геометрии, первоначально поставленная как задача о раскраске или хроматическом числе евклидова пространства.

По состоянию на 2024 год задача остаётся открытой.

Постановка проблемы

Задача Нелсона — Эрдёша — Хадвигера ставит вопрос о минимальном числе цветов, в которые можно раскрасить n-мерное евклидово пространство так, чтобы не было одноцветных точек, отстоящих друг от друга на расстоянии 1. Это число называется хроматическим числом n-мерного евклидова пространства.

Та же задача имеет смысл для произвольного метрического пространства. В общем случае, пусть $(X,\rho )$ — метрическое пространство и $a>0$. Каково минимальное число цветов $\chi ((X,\rho ),a)$, в которые можно раскрасить $(X,\rho )$ так, чтобы между точками одного цвета не могло быть фиксированного расстояния $a$? Или каково хроматические число метрического пространства $(X,\rho )$ по отношению к запрещенному расстоянию $a$?

По теореме де Брёйна — Эрдёша, достаточно решить задачу для всех конечных подмножеств точек.

Некоторые результаты

Малые размерности

Пример раскраски плоскости в 7 цветов (диаметр шестиугольников немного меньше 1) и веретено Мозера — граф единичных расстояний с хроматическим числом 4, который доказывает, что плоскость нельзя раскрасить в 3 цвета.

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

После доказательства Обри ди Грея, ответ к задаче Нелсона — Эрдёша — Хадвигера может быть только 5, 6 или 7.

Асимптотика

Пусть $l_{p}$ — гёльдерова метрика. Доказана верхняя оценка:

$\chi ((\mathbb {R} ^{n},l_{p}),a)\leqslant (3+o(1))^{n}$,

и доказана нижняя оценка:

$\chi ((\mathbb {R} ^{n},l_{p}),a)\geqslant (1,207...+o(1))^{n}$

Для некоторых конкретных значений $p,a$ оценки снизу несколько усилены. Таким образом, установлено, что хроматическое число n-мерного пространства растёт асимптотически экспоненциально, в то время как для проблемы Борсука оценки сверху и снизу имеют разную скорость роста.

История

В начале 1940-х годов её поставили Хуго Хадвигер и Пал Эрдёш, независимо от них, приблизительно в то же время, ей также занимались Эдуард Нелсон и Джон Исбелл.

В 1961 году вышла известная работа Хадвигера, посвящённая нерешённым математическим задачам, после этого хроматические числа стали активно изучаться.

В 1976 году М. Бенда и М. Перлес предложили рассматривать её в максимально общем контексте метрических пространств.

В 2018 году Обри ди Грей получил граф единичных расстояний с 1581 вершиной, который невозможно покрасить в 4 цвета. Математическое сообщество улучшило результат ди Грея, по состоянию на 2021 год самый маленький известный граф, который невозможно покрасить в 4 цвета имеет 509 вершин.

Вариации и обобщения

• Задача Нелсона — Эрдёша — Хадвигера связана также с другой классической задачей комбинаторной геометрии — гипотезой Борсука, опровергнутой в общем случае в 1993 году.

Литература

• А. Райгородский, В. Воронов, А. Савватеев. Прорыв в задаче о раскраске плоскости (рус.) // Квант. — 2018. — № 11. — С. 2–9. — doi:10.4213/kvant20181101.