Проблема Нелсона — Эрдёша — Хадвигера

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

Проблема Нелсона — Эрдёша — Хадвигера — фундаментальная проблема комбинаторной геометрии, первоначально поставленная как задача о раскраске или хроматическом числе Евклидова пространства. В дальнейшем задача была обобщена на произвольное метрическое пространство. Эта проблема может быть поставлена и как задача теории графов. Проблема связана также с другой классической нерешённой задачей комбинаторной геометрии - проблемой Борсука. Несмотря на усилия ряда выдающихся математиков в настоящее время (2013) проблема Нелсона — Эрдёша — Хадвигера далека от решения.

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

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

В общем случае, пусть (X,\rho) - метрическое пространство и a >0. Каково минимальное число цветов \chi(( X,\rho),a), в которые можно раскрасить (X, \rho) так, чтобы между точками одного цвета не могло быть фиксированного расстояния a? Или каково хроматические число метрического пространства (X,\rho) по отношению к запрещенному расстоянию a?

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

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

\chi((\mathbb R^n,l_p),a)\leqslant(3+o(1))^n

И доказана нижняя оценка [2]

\chi((\mathbb R^n,l_p),a)\geqslant(1,207...+o(1))^n

Для некоторых конкретных значений p, a оценки снизу несколько усилены. [3] Таким образом, установлено, что хроматическое число пространства растёт асимптотически экспоненциально, в то время как для проблемы Борсука оценки сверху и снизу имеют разную скорость роста. Для малых размерностей пространства известно также не очень много. Нетрудно доказать, что на плоскости требуется не менее 4 и не более 7 цветов, но дальше продвинуться не могут. Ответ на вопрос может зависеть от выбора аксиом теории множеств[4][5]

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

У данной задачи авторов было несколько. Во-первых, ещё в начале сороковых годов XX века её поставили Хуго Хадвигер (англ. Hugo Hadwiger) и Пал Эрдёш, во-вторых, независимо от Эрдёша и Хадвигера ей занимались приблизительно в то же время Эдуард Нелсон (англ. Edward Nelson) и Дж. Р. Исбелл. В сороковые годы шла Мировая война, и этим обстоятельством обусловлен тот факт, что поначалу хроматические числа не вызвали слишком сильного интереса. Потребовалось около 15 лет, чтобы положение изменилось кардинально: после работы Хадвигера 1961 года, посвящённой нерешённым задачам, хроматические числа стали активно изучаться, и в последующие десятилетия комбинаторная геометрия стала одной из самых популярных математических дисциплин в мире, а задачей Эрдёша — Хадвигера занимались многие известные математики. В 1976 году М. Бенда и М. Перлес предложили рассматривать её в максимально общем контексте метрических пространств. О проблеме написаны сотни статей, выпущены монографии, и всё же эта нетривиальная и глубокая проблема далека от окончательного решения.

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

  1. Larman D. G., Rogers C. A.The realization of distances within sets in Euclidean space// Mathematika. — 1972. —19. — C. 1–24.
  2. Frankl P., Wilson R. M.Intersection theorems with geometric consequences// Combinatorica. — 1981. — 1. — C. 357–368.
  3. А. М. Райгородский, "ВОКРУГ ГИПОТЕЗЫ БОРСУКА"
  4. 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> .
  5. 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