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

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

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

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

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

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

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

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

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

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

Асимптотика

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

,

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

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

История

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

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

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

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

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

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

Примечания
  1. 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.
  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.
  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. А. М. Райгородский, «Вокруг гипотезы Борсука»
  7. Hadwiger-Nelson problem - Polymath Wiki

Литература
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.