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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

[править | править код]

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

Та же задача имеет смысл для произвольного метрического пространства. В общем случае, пусть  — метрическое пространство и . Каково минимальное число цветов , в которые можно раскрасить так, чтобы между точками одного цвета не могло быть фиксированного расстояния ? Или каково хроматические число метрического пространства по отношению к запрещенному расстоянию ?

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

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

[править | править код]

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

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

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

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

Асимптотика

[править | править код]

Пусть  — гёльдерова метрика. Доказана верхняя оценка[4]:

,

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

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

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

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

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

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

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

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

Примечания

[править | править код]
  1. Shelah, Saharon; Soifer, Alexander (2003), "Axiom of choice and chromatic number of the plane" (PDF), Journal of Combinatorial Theory, Series A, 103 (2): 387—391, doi:10.1016/S0097-3165(03)00102-X, Архивировано (PDF) 14 июня 2011, Дата обращения: 29 апреля 2013 Источник. Дата обращения: 29 апреля 2013. Архивировано из оригинала 14 июня 2011 года..
  2. Soifer, Alexander (2008), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators, New York: Springer, ISBN 978-0-387-74640-1
  3. Владимир Королёв. Математикам не хватило четырех цветов для раскраски плоскости. N+1 (10 апреля 2018). Дата обращения: 10 апреля 2018. Архивировано 10 апреля 2018 года.
  4. Larman D. G., Rogers C. A.The realization of distances within sets in Euclidean space// Mathematika. — 1972. —19. — C. 1-24.
  5. Frankl P., Wilson R. M.Intersection theorems with geometric consequences// Combinatorica. — 1981. — 1. — C. 357—368.
  6. А. М. Райгородский, «Вокруг гипотезы Борсука». Дата обращения: 24 мая 2013. Архивировано 14 декабря 2014 года.
  7. Hadwiger-Nelson problem - Polymath Wiki. Дата обращения: 24 марта 2021. Архивировано 12 апреля 2021 года.

Литература

[править | править код]