Доклады Российской академии наук. Математика, информатика, процессы управления, 2022, T. 506, № 1, стр. 54-56

1. ВВЕДЕНИЕ

Задача Нельсона о хроматическом числе плоскости является одной из центральных проблем современной комбинаторной геометрии. Одна из наиболее общих ее постановок звучит следующим образом. Для n-мерного нормированного пространства $\mathbb{R}_{N}^{n}$ требуется найти его хроматическое число $\chi (\mathbb{R}_{N}^{n})$, определяемое как наименьшее r, для которого существует раскраска точек $\mathbb{R}_{N}^{n}$ в r цветов, так называемая r-раскраска, при которой никакая пара точек на единичном расстоянии не оказалась бы покрашена в один и тот же цвет. Наиболее активно эта проблема изучалась для ${{\ell }_{p}}$-пространств $\mathbb{R}_{p}^{n}$. Напомним, что ${{\ell }_{p}}$-норма точки ${\mathbf{x}} \in {{\mathbb{R}}^{n}}$ определяется равенством ${\text{||}}{\mathbf{x}}{\text{|}}{{{\text{|}}}_{p}} = {{\left( {\sum\nolimits_i {\text{|}}{{x}_{i}}{{{\text{|}}}^{p}}} \right)}^{{1/p}}}$ при всех действительных $p \geqslant 1$, а при $p = \infty $ – равенством ${\text{||}}{\mathbf{x}}{\text{|}}{{{\text{|}}}_{\infty }} = \mathop {\max }\nolimits_i {\text{|}}{{x}_{i}}{\text{|}}$. Известно, что при всех $1 \leqslant p \leqslant \infty $ величина $\chi (\mathbb{R}_{p}^{n})$ растет экспоненциально с ростом n. Подробнее об этой и родственных задачах см. [1–11].

В качестве еще более далеко идущего обобщения Пол Эрдёш и соавт. в работах [12–14] предложили запрещать одноцветность более сложных конфигураций. Для подмножества $\mathcal{M} \subset \mathbb{R}_{N}^{n}$, его N-изометричной копией называется такое подмножество $\mathcal{M}{\kern 1pt} ' \subset {{\mathbb{R}}^{n}}$, что существует биекция $f{\kern 1pt} :\;\mathcal{M} \to \mathcal{M}{\kern 1pt} '$ такая, что ||x – y||_N = = ${\text{||}}f({\mathbf{x}}) - f({\mathbf{y}}){\text{|}}{{{\text{|}}}_{N}}$ при всех ${\mathbf{x}},{\mathbf{y}} \in \mathcal{M}$. Хроматическим числом $\chi (\mathbb{R}_{N}^{n},\mathcal{M})$ пространства $\mathbb{R}_{N}^{n}$ с запрещенным одноцветным множеством $\mathcal{M}$ называют наименьшее r, для которого существует r-раскраска $\mathbb{R}_{N}^{n}$, при которой ни одна N-изометричная копия $\mathcal{M}$ не оказалась бы полностью одноцветной. Систематическому изучению данной задачи посвящены статьи [15–25].

Одними из наиболее естественных для рассмотрения в данной задаче в качестве запрета $\mathcal{M}$ множеств являются арифметические прогрессии ${{\mathcal{B}}_{k}} = \{ 0,1, \ldots ,k\} $. В [12] было показано, что для евклидова пространства уже при k = 2 величина $\chi (\mathbb{R}_{2}^{n},{{\mathcal{B}}_{2}})$ не только не стремится к бесконечности экспоненциально быстро c ростом n, но и не стремится к ней вовсе, так как во всех размерностях справедливо неравенство $\chi (\mathbb{R}_{2}^{n},{{\mathcal{B}}_{2}}) \leqslant 4$. Более того, верно, что $\chi (\mathbb{R}_{2}^{n},{{\mathcal{B}}_{k}}) = 2$ при всех $k \geqslant 5$ и при всех натуральных n. Отметим, что открытым остается вопрос об оптимальности констант 4 и 5 в последних двух утверждениях, см. [19].

Целью настоящего исследования являлось обобщение последних неравенств со случая евклидова пространства на случай ${{\ell }_{p}}$-пространств при $p \ne 2$. Основным полученным нами результатом является следующий.

Теорема 1. Для любого $1 \leqslant p \leqslant \infty $ и любого натурального n, существует достаточно большое $k = k(p,n)$ такое, что $\chi (\mathbb{R}_{p}^{n},{{\mathcal{B}}_{k}}) = 2$.

2. ЭСКИЗ ДОКАЗАТЕЛЬСТВА ТЕОРЕМЫ

Для случая $p = \infty $ доказательство проводится с использованием явной, но технически сложной двухцветной раскраски, состоящей из одинаковых расположенных друг над другом слоев-‘змеек’, цвета которых мы чередуем. Показывается, что данная раскраска пространства ${{\mathbb{R}}^{n}}$ не содержит одноцветных ${{\ell }_{\infty }}$-изометричных копий прогрессий ${{\mathcal{B}}_{k}}$ при $k \geqslant {{5}^{n}}$.

Предположим теперь, что $1 < p < \infty $. Известно, что единичный шар ${{\ell }_{p}}$ нормы в этом случае является строго выпуклым. А значит, всякая ${{\ell }_{p}}$-изометричная копия множества ${{\mathcal{B}}_{k}}$ лежит на некоторой прямой. Как следствие, она является арифметической прогрессией в пространстве $\mathbb{R}_{\infty }^{n}$, длину звена (а значит – и диаметр) которой можно контролировать в терминах n и p. Здесь мы используем тот факт, что ${{\ell }_{p}}$- и ${{\ell }_{\infty }}$-нормы на ${{\mathbb{R}}^{n}}$ ‘эквивалентны’ друг другу, т.е. при некоторых положительных $c = c(n,p)$ и $C = C(n,p)$ верно, что $c{\text{||}}{\mathbf{x}}{\text{|}}{{{\text{|}}}_{\infty }} \leqslant {\text{||}}{\mathbf{x}}{\text{|}}{{{\text{|}}}_{p}} \leqslant C{\text{||}}{\mathbf{x}}{\text{|}}{{{\text{|}}}_{\infty }}$ при всех ${\mathbf{x}} \in {{\mathbb{R}}^{n}}$. А значит, из отсутствия в некоторой раскраске пространства ${{\mathbb{R}}^{n}}$ с нормой ${{\ell }_{\infty }}$ достаточно длинных одноцветных арифметических прогрессий действительно следует и отсутствие в ней одноцветных ${{\ell }_{p}}$-изометричных копий множеств ${{\mathcal{B}}_{k}}$ при всех достаточно больших значениях k.

Наконец, мы рассмотрим случай p = 1. Эта ситуация в некотором смысле диаметрально противоположна предыдущей, так как единичным шаром ${{\ell }_{1}}$-нормы является выпуклый центрально симметричный многогранник (точнее – гипероктаэдр или кросс-политоп). Известно, что всякий такой многогранник с f парами противоположных граней является центральным сечением f-мерного гиперкуба некоторой гиперплоскостью. А значит, пространство $\mathbb{R}_{1}^{n}$ может быть изометрично вложено в $\mathbb{R}_{\infty }^{m}$ при $m{{ = 2}^{{n - 1}}}$. Следовательно, для построения искомой двухцветной раскраски пространства $\mathbb{R}_{1}^{n}$ достаточно рассмотреть такую раскраску $\mathbb{R}_{\infty }^{m}$, а затем просто индуцировать ее на соответствующее подпространство.

3. ЗАКЛЮЧЕНИЕ

Наше доказательство оставляет открытым вопрос об асимптотическом повелении оптимальной константы $k(p,n)$ из теоремы 1. Наилучшие оценки для $p = \infty $, которых нам удалось добиться в рамках известных методов, таковы: $n{\text{/ln}}(2)\, \leqslant \,k(\infty ,n)\, \leqslant \,{{3}^{n}}$. При каждом фиксированном $1 < p < \infty $ можно показать, что $k(p,n) = o(n)$ при $n \to \infty $, однако не ясно, стремится ли эта величина к бесконечности с ростом n. Напомним, что в евклидовом случае это стремление отсутствует, так как из вышеупомянутых результатов Эрдёша следует, что $k(2,n) \leqslant 5$ при всех $n \in \mathbb{N}$. С учетом возросшего в последние годы интереса специалистов к так называемым полихроматическим раскраскам, уместным было бы рассмотреть следущее обобщение исходной задачи. Доказать, что для любого $1 \leqslant p \leqslant \infty $ и любых натуральных n и $t$, существует достаточно большое натуральное $k = k(p,n,t)$ и раскраска пространства ${{\mathbb{R}}^{n}}$ в t цветов такая, что всякая ${{\ell }_{p}}$-изометричная копия прогрессии ${{\mathcal{B}}_{k}}$ в ${{\mathbb{R}}^{n}}$ содержит точки всех t цветов. Отметим, что даже для евклидова случая вопрос об асимптотическом поведении величины $k(2,n,t)$ остается открытым.