WikiSort.ru - Не сортированное

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

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

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

Задача Нелсона — Эрдёша — Хадвигера ставит вопрос о минимальном числе цветов, в которые можно раскрасить 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 года. При этом высказывались предположения, что ответ может зависеть от выбора аксиом теории множеств^[1][2]. В 2018 году Обри ди Грей показал, что 4 цветов недостаточно^[3].

История

Ещё в начале сороковых годов XX века её поставили Хуго Хадвигер и Пал Эрдёш. Независимо от Эрдёша и Хадвигера ей занимались приблизительно в то же время Эдуард Нелсон (англ. Edward Nelson) и Дж. Р. Исбелл. После работы Хадвигера 1961 года, посвящённой нерешённым задачам, хроматические числа стали активно изучаться.

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

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

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

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

Примечания