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

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

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

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

Постановка проблемы[править | править код]

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

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

Некоторые результаты[править | править код]

Малые размерности[править | править код]

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

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

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

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

,

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

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

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

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

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

В 2018 году Обри ди Грей получил граф единичных расстояний с 1581 вершиной, который невозможно покрасить в 4 цвета. В частности ответ на задачу может быть только 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. .
  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. А. М. Райгородский, «Вокруг гипотезы Борсука»