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

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

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

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

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

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

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

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

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

 

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

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

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

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

$\mathrm{\chi <!--\; \chi \; -->}(({\mathbb{R}}^n,l_p),a)⩽<!--\; ⩽\; -->(3+o(1){)}^n$$\chi ((\mathbb {R} ^{n},l_{p}),a)\leqslant (3+o(1))^{n}$ ,

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

$\mathrm{\chi <!--\; \chi \; -->}(({\mathbb{R}}^n,l_p),a)⩾<!--\; ⩾\; -->(1,\mathrm{207...}+o(1){)}^n$$\chi ((\mathbb {R} ^{n},l_{p}),a)\geqslant (1,207...+o(1))^{n}$ 

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

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

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

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

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

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

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

Вариации и обобщенияПравить

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

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

• А. Райгородский, В. Воронов, А. Савватеев. Прорыв в задаче о раскраске плоскости (рус.) // Квант. — 2018. — № 11. — С. 2–9. — doi:10.4213/kvant20181101.