Успехи математических наук, 2022, том 77, выпуск 3(465), страницы 175–176 DOI: https://doi.org/10.4213/rm10055 (Mi rm10055)

DOI: https://doi.org/10.4213/rm10055

Финансовая поддержка	Номер гранта
Российский научный фонд	22-21-00368
Конкурс «Молодая математика России»
Работа второго автора выполнена при поддержке РНФ (грант № 22-21-00368). Второй автор также является победителем конкурса “Молодая математика России” и благодарит его спонсоров и жюри.

Англоязычная версия:
Russian Mathematical Surveys, 2022, Volume 77, Issue 3, Pages 549–551
DOI: https://doi.org/10.1070/RM10055

Реферативные базы данных:

Зародившись с группы на первый взгляд не связанных между собой результатов из разных областей математики (теорема Рамсея, появление которой было продиктовано нуждами математической логики, теоретико-числовая теорема Шура, геометрическая “задача со счастливым концом”), во второй половине двадцатого века теория Рамсея оформилась в самостоятельную дисциплину (см. классическую книгу [1]). В настоящей работе рассматриваются рамсеевские задачи геометрического типа, обобщающие известную открытую проблему хроматического числа плоскости (см. обзор [2]) и продолжающие линию исследований, заложенную в классических работах [3], [4] Пола Эрдёша и его соавторов.

Дадим формальные определения. Пусть $\mathbb{X}=(X,\rho_X)$, $\mathcal{Y}=(Y,\rho_Y)$ – произвольные метрические пространства. Подмножество $Y' \subset X$ называется копией пространства $\mathcal{Y}$, если существует сохраняющая расстояния биекция $f\colon Y \to Y'$. Хроматическим числом $\chi(\mathbb{X},\mathcal{Y})$ пространства $\mathbb{X}$ с запрещенным подпространством $\mathcal{Y}$ называется минимальное $k$, для которого существует раскраска элементов $X$ в $k$ цветов без одноцветных копий $Y' \subset X$ пространства $\mathcal{Y}$. В рамках евклидовой теории Рамсея рассматривается случай, когда $\mathbb{X}$ – это $n$-мерное евклидово пространство $\mathbb{R}_2^n$. Несмотря на то, что задача классификации конечных рамсеевских пространств, т. е. таких $\mathcal{Y}$, что $\chi(\mathbb{R}_2^n,\mathcal{Y})\to \infty$ при $n \to \infty$, привлекает внимание крупных специалистов на протяжении нескольких десятков лет, на сегодняшний день не существует даже общепринятой гипотезы об ответе на этот вопрос (см. [5]–[11]). Однако если запрещаемое пространство $\mathcal{Y}$ является бесконечным, то ситуация оказывается несравненно более простой: в работе [4] доказано, что в этом случае в любой размерности справедливо точное равенство $\chi(\mathbb{R}_2^n,\mathcal{Y})=2$. Гипотеза о том, что последнее равенство справедливо не только для бесконечных, но и для всех достаточно больших (в терминах размерности $n$) пространств $\mathcal{Y}$, остается открытой (см. [12]).

В недавней серии работ [13], [14] авторы перенесли задачи евклидовой теории Рамсея на случай метрического пространства $\mathbb{R}_\infty^n=(\mathbb{R}^n,\ell_\infty)$, где $\ell_\infty$ – стандартная чебышёвская метрика, определяемая равенством $\ell_\infty(\mathbf{x},\mathbf{y})=\max_{i}|x_i-y_i|$ для всех $\mathbf{x}=(x_1,\dots,x_n)$, $\mathbf{y}=(y_1,\dots,y_n)$ из $\mathbb{R}^n$. Среди прочего им удалось доказать, что для любого конечного метрического пространства $\mathcal{Y}$ существует константа $c=c(\mathcal Y)>1$ такая, что для любого $n\in \mathbb N$ верно неравенство $\chi(\mathbb{R}_\infty^n,\mathcal Y)>c^n$. Однако ситуация с бесконечными запрещаемыми пространствами $\mathcal{Y}$ оставалась непроясненной. Настоящая работа устраняет этот пробел.

Одними из наиболее естественных и поддающихся изучению бесконечных метрических пространств являются подмножества $\mathcal{B}(\boldsymbol{\lambda})= \{0,\lambda_1,\lambda_1+\lambda_2,\dots\}$ прямой, где $\boldsymbol{\lambda}=(\lambda_1,\lambda_2,\dots)$ – произвольная бесконечно убывающая последовательность положительных чисел. Без ограничения общности можно считать, что ряд $\sum_i\lambda_i$ сходится, так как простейшая двухцветная раскраска пространства попарно вложенными друг в друга цветочередующимися кубами с достаточно быстро растущей длиной стороны показывает, что $\chi(\mathbb{R}_\infty^n,\mathcal Y)=2$ при всех $\mathcal{Y}$ таких, что $\operatorname{diam}(\mathcal{Y})=\infty$.

Отметим два следствия этого результата, иллюстрирующие принципиальную разницу между евклидовой и чебышёвской теориями Рамсея.

Во-первых, наилучшей верхней оценкой величины $\chi(\mathbb{R}_\infty^n,\mathcal Y)$, справедливой для всех бесконечных метрических пространств $\mathcal{Y}$, является оценка $\chi(\mathbb{R}_\infty^n,\mathcal Y) \leqslant n+1$. В частности, эта оценка зависит от размерности $n$. Более того, ее достижимость, в отличие от евклидова случая, удается доказать не только для бесконечных, но и для всех достаточно больших пространств $\mathcal{Y}$.

Во-вторых, утверждение (b) теоремы 1 гарантирует существование бесконечного рамсеевского в метрике Чебышёва пространства, т. е. такого $\mathcal{Y}$, что $\chi(\mathbb{R}_\infty^n,\mathcal Y) \to \infty$ при $n \to \infty$. Действительно, достаточно положить $\mathcal{Y}=\mathcal{B}(\boldsymbol{\lambda})$, где $\boldsymbol{\lambda}$ – бесконечно убывающая геометрическая прогрессия со знаменателем $1/32$ (или с любым меньшим знаменателем). Скорость роста величины $\chi(\mathbb{R}_\infty^n,\mathcal Y)$ при этом оказывается по крайней мере логарифмической.

Данный результат оставляет открытыми следующие вопросы. Как ведет себя с ростом размерности величина $\chi(\mathbb{R}_\infty^n,\mathcal{B}(\boldsymbol{\lambda}))$, где $\boldsymbol{\lambda}$ – бесконечно убывающая геометрическая прогрессия со знаменателем $1/32 < q < 1$? Существует ли такое бесконечное метрическое пространство $\mathcal{Y}$, что $\chi(\mathbb{R}_\infty^n,\mathcal Y)=n+1$ при всех натуральных $n$?

Список литературы
1.	R. L. Graham, B. L. Rothschild, J. H. Spencer, Ramsey theory, Wiley-Intersci. Ser. Discrete Math. Optim., 2nd ed., John Wiley & Sons, Inc., New York, 1990, xii+196 pp.
2.	A. M. Raigorodskii, Thirty essays on geometric graph theory, Springer, New York, 2013, 429–460
3.	P. Erdős, R. L. Graham, P. Montgomery, B. L. Rothschild, J. Spencer, E. G. Straus, J. Combin. Theory Ser. A, 14:3 (1973), 341–363
4.	P. Erdős, R. L. Graham, P. Montgomery, B. L. Rothschild, J. Spencer, E. G. Straus, Infinite and finite sets (Keszthely, 1973), Colloq. Math. Soc. János Bolyai, 10, North-Holland, Amsterdam, 1975, 529–557, 559–583
5.	I. Leader, P. A. Russell, M. Walters, J. Combin. Theory Ser. A., 119:2 (2012), 382–396
6.	P. Frankl, V. Rödl, J. Amer. Math. Soc., 3:1 (1990), 1–7
7.	I. Kříž, Proc. Amer. Math. Soc., 112:3 (1991), 899–907
8.	Р. И. Просанов, Матем. заметки, 103:2 (2018), 248–257
9.	А. А. Сагдеев, Пробл. передачи информ., 54:4 (2018), 82–109
10.	А. А. Сагдеев, Пробл. передачи информ., 55:4 (2019), 86–106
11.	E. Naslund, Bull. Lond. Math. Soc., 52:4 (2020), 687–692
12.	D. Conlon, J. Fox, Discrete Comput. Geom., 61:1 (2019), 218–225
13.	А. Б. Купавский, А. А. Сагдеев, УМН, 75:5(455) (2020), 191–192
14.	A. Kupavskii, A. Sagdeev, Forum Math. Sigma, 9 (2021), e55, 12 pp.

Цитирование в формате AMSBIB

\RBibitem{KupSagFra22}
\by А.~Б.~Купавский, А.~А.~Сагдеев, Н.~Франкл
\paper Бесконечные множества могут быть~рамсеевскими в~метрике Чебышёва
\jour УМН
\yr 2022
\vol 77
\issue 3(465)
\pages 175--176
\mathnet{http://mi.mathnet.ru/rm10055}
\crossref{https://doi.org/10.4213/rm10055}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4602197}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2022RuMaS..77..549K}
\transl
\jour Russian Math. Surveys
\yr 2022
\vol 77
\issue 3
\pages 549--551
\crossref{https://doi.org/10.1070/RM10055}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000992284200006}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85148985800}


Эта публикация цитируется в следующих 1 статьяx: