Задача Нелсона — Эрдёша — Хадвигера
Задача Нелсона — Эрдёша — Хадвигера — задача комбинаторной геометрии, первоначально поставленная как задача о раскраске или хроматическом числе евклидова пространства.
По состоянию на 2024 год задача остаётся открытой.
Постановка проблемы
Задача Нелсона — Эрдёша — Хадвигера ставит вопрос о минимальном числе цветов, в которые можно раскрасить n-мерное евклидово пространство так, чтобы не было одноцветных точек, отстоящих друг от друга на расстоянии 1. Это число называется хроматическим числом n-мерного евклидова пространства.
Та же задача имеет смысл для произвольного метрического пространства. В общем случае, пусть [math]\displaystyle{ (X,\rho) }[/math] — метрическое пространство и [math]\displaystyle{ a \gt 0 }[/math]. Каково минимальное число цветов [math]\displaystyle{ \chi(( X,\rho),a) }[/math], в которые можно раскрасить [math]\displaystyle{ (X, \rho) }[/math] так, чтобы между точками одного цвета не могло быть фиксированного расстояния [math]\displaystyle{ a }[/math]? Или каково хроматические число метрического пространства [math]\displaystyle{ (X,\rho) }[/math] по отношению к запрещенному расстоянию [math]\displaystyle{ a }[/math]?
По теореме де Брёйна — Эрдёша, достаточно решить задачу для всех конечных подмножеств точек.
Некоторые результаты
Малые размерности
Очевидно, что хроматическое число одномерного пространства равно двум, однако уже для плоскости ответ неизвестен. Нетрудно доказать, что для раскраски плоскости требуется не менее 4 и не более 7 цветов, но дальше продвинуться не удавалось до 2018 года. При этом высказывались предположения, что ответ может зависеть от выбора аксиом теории множеств[1][2]. В 2018 году Обри ди Грей показал, что 4 цветов недостаточно[3].
Асимптотика
Пусть [math]\displaystyle{ l_p }[/math] — гёльдерова метрика. Доказана верхняя оценка[4]:
- [math]\displaystyle{ \chi((\mathbb R^n,l_p),a)\leqslant(3+o(1))^n }[/math],
и доказана нижняя оценка[5]:
- [math]\displaystyle{ \chi((\mathbb R^n,l_p),a)\geqslant(1,207...+o(1))^n }[/math]
Для некоторых конкретных значений [math]\displaystyle{ p, a }[/math] оценки снизу несколько усилены.[6] Таким образом, установлено, что хроматическое число n-мерного пространства растёт асимптотически экспоненциально, в то время как для проблемы Борсука оценки сверху и снизу имеют разную скорость роста.
История
В начале 1940-х годов её поставили Хуго Хадвигер и Пал Эрдёш, независимо от них, приблизительно в то же время, ей также занимались Эдуард Нелсон[англ.] и Джон Исбелл.
В 1961 году вышла известная работа Хадвигера, посвящённая нерешённым математическим задачам, после этого хроматические числа стали активно изучаться.
В 1976 году М. Бенда и М. Перлес предложили рассматривать её в максимально общем контексте метрических пространств.
В 2018 году Обри ди Грей получил граф единичных расстояний с 1581 вершиной, который невозможно покрасить в 4 цвета. Математическое сообщество улучшило результат ди Грея, по состоянию на 2021 год самый маленький известный граф, который невозможно покрасить в 4 цвета имеет 509 вершин[7].
После доказательства Обри ди Грея, ответ к задаче Нелсона — Эрдёша — Хадвигера может быть только 5, 6 или 7.
Вариации и обобщения
- Задача Нелсона — Эрдёша — Хадвигера связана также с другой классической задачей комбинаторной геометрии — гипотезой Борсука, опровергнутой в общем случае в 1993 году.
Примечания
- ↑ Shelah, Saharon & Soifer, Alexander (2003), Axiom of choice and chromatic number of the plane, Journal of Combinatorial Theory, Series A Т. 103 (2): 387–391, doi:10.1016/S0097-3165(03)00102-X, <http://www.uccs.edu/~faculty/asoifer/docs/AXIOMOFCHOICEinJCT.pdf>. Проверено 29 апреля 2013. Архивная копия от 14 июня 2011 на Wayback Machine.
- ↑ 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
- ↑ Владимир Королёв. Математикам не хватило четырех цветов для раскраски плоскости. N+1 (10 апреля 2018). Дата обращения: 10 апреля 2018. Архивировано 10 апреля 2018 года.
- ↑ Larman D. G., Rogers C. A.The realization of distances within sets in Euclidean space// Mathematika. — 1972. —19. — C. 1-24.
- ↑ Frankl P., Wilson R. M.Intersection theorems with geometric consequences// Combinatorica. — 1981. — 1. — C. 357—368.
- ↑ А. М. Райгородский, «Вокруг гипотезы Борсука». Дата обращения: 24 мая 2013. Архивировано 14 декабря 2014 года.
- ↑ Hadwiger-Nelson problem - Polymath Wiki. Дата обращения: 24 марта 2021. Архивировано 12 апреля 2021 года.
Литература
- А. Райгородский, В. Воронов, А. Савватеев. Прорыв в задаче о раскраске плоскости // Квант. — 2018. — № 11. — С. 2–9. — doi:10.4213/kvant20181101.