|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Сообщения Московского математического общества
Бесконечные множества могут быть рамсеевскими в метрике Чебышёва
А. Б. Купавскийab, А. А. Сагдеевa, Н. Франклc a Московский физико-технический институт (национальный исследовательский университет)
b CNRS, Grenoble, France
c Институт математики им. А. Реньи, Будапешт, Венгрия
Поступила в редакцию: 04.04.2022
Зародившись с группы на первый взгляд не связанных между собой результатов из разных областей математики (теорема Рамсея, появление которой было продиктовано нуждами математической логики, теоретико-числовая теорема Шура, геометрическая “задача со счастливым концом”), во второй половине двадцатого века теория Рамсея оформилась в самостоятельную дисциплину (см. классическую книгу [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$.
Теорема 1. Для любого натурального $n$ справедливы следующие утверждения: (a) если $\lim_{i} \lambda_i/\lambda_{i+1} \leqslant 1+5^{-n}$, то $\chi(\mathbb{R}_\infty^n,\mathcal{B}(\boldsymbol{\lambda}))=2$; (b) если $\lambda_i \geqslant 32\lambda_{i+1}$ при всех $i \in \mathbb{N}$, то $\chi(\mathbb{R}_\infty^n,\mathcal{B}(\boldsymbol{\lambda})) \geqslant \log_3 n$; (c) если $\lambda_i \geqslant 2^{n}\lambda_{i+1}$ при всех $i \in \mathbb{N}$, то $\chi(\mathbb{R}_\infty^n,\mathcal{B}(\boldsymbol{\lambda})) \geqslant n+1$; (d) если $|Y|\geqslant n^n$, то $\chi(\mathbb{R}_\infty^n,\mathcal Y) \leqslant n+1$.
Отметим два следствия этого результата, иллюстрирующие принципиальную разницу между евклидовой и чебышёвской теориями Рамсея. Во-первых, наилучшей верхней оценкой величины $\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. |
Образец цитирования:
А. Б. Купавский, А. А. Сагдеев, Н. Франкл, “Бесконечные множества могут быть рамсеевскими в метрике Чебышёва”, УМН, 77:3(465) (2022), 175–176; Russian Math. Surveys, 77:3 (2022), 549–551
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/rm10055https://doi.org/10.4213/rm10055 https://www.mathnet.ru/rus/rm/v77/i3/p175
|
Статистика просмотров: |
Страница аннотации: | 261 | PDF русской версии: | 21 | PDF английской версии: | 32 | HTML русской версии: | 85 | HTML английской версии: | 104 | Список литературы: | 45 | Первая страница: | 23 |
|