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

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

Задача Нельсона — Эрдёша — Хадвигера — классическая задача комбинаторной геометрии открытая (на 2014 год). Эта задача может быть сформулирована как задача определённого бесконечного раскраске графа построенного по Евклидову пространству.

Формулировка[править | править вики-текст]

Каким минимальным числом цветов можно раскрасить n-мерное евклидово пространство так, чтобы не было одноцветных точек, отстоящих друг от друга на расстояние 1?

Это число называется хроматическим числом n-мерного евклидова пространства.

Та же задача имеет смысл для произвольного метрического пространства.

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

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

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

  • В одномерном случае ответ равен двум.
  • Для раскраски плоскости требуется не менее 4 и не более 7 цветов.

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

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

,

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

Для некоторых конкретных значений оценки снизу несколько усилены.[5]

В частности хроматическое число n-мерного пространства растёт асимптотически экспоненциально.

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

В начале сороковых годов XX века её поставили Гуго Хадвигер и Пал Эрдёш. Независимо от Эрдёша и Хадвигера, приблизительно в то же время эта задача рассматривалась Эдуард Нельсон (англ. Edward Nelson) и Джон Избелл (англ. John R. Isbell).

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  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> .
  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. Larman D. G., Rogers C. A.The realization of distances within sets in Euclidean space// Mathematika. — 1972. —19. — C. 1-24.
  4. Frankl P., Wilson R. M.Intersection theorems with geometric consequences// Combinatorica. — 1981. — 1. — C. 357—368.
  5. А. М. Райгородский, «Вокруг гипотезы Борсука»