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

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

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

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

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

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

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

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

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

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

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

АсимптотикаПравить

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

 ,

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

 

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

ИсторияПравить

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

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

В 2018 году Обри ди Грей получил граф единичных расстояний с 1581 вершиной, который невозможно покрасить в 4 цвета. Таким образом он доказал, что ответ в задаче может быть только 5, 6 или 7. В 2019 математическое сообщество Polymath улучшило результат ди Грея до графа с 510 вершинами, который невозможно покрасить в 4 цвета[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

ЛитератураПравить