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

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

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

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

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

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

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

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

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

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

Асимптотика

Пусть ${\displaystyle l_{p}}$ — . Доказана верхняя оценка :

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

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

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

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

История

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

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

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

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

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

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

Примечания

Литература

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