Успехи математических наук
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



УМН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


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

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

Сообщения Московского математического общества

Бесконечные множества могут быть рамсеевскими в метрике Чебышёва

А. Б. Купавскийab, А. А. Сагдеевa, Н. Франклc

a Московский физико-технический институт (национальный исследовательский университет)
b CNRS, Grenoble, France
c Институт математики им. А. Реньи, Будапешт, Венгрия
Список литературы:
Финансовая поддержка Номер гранта
Российский научный фонд 22-21-00368
Конкурс «Молодая математика России»
Работа второго автора выполнена при поддержке РНФ (грант № 22-21-00368). Второй автор также является победителем конкурса “Молодая математика России” и благодарит его спонсоров и жюри.
Поступила в редакцию: 04.04.2022
Англоязычная версия:
Russian Mathematical Surveys, 2022, Volume 77, Issue 3, Pages 549–551
DOI: https://doi.org/10.1070/RM10055
Реферативные базы данных:
Тип публикации: Статья
MSC: 05D10

Зародившись с группы на первый взгляд не связанных между собой результатов из разных областей математики (теорема Рамсея, появление которой было продиктовано нуждами математической логики, теоретико-числовая теорема Шура, геометрическая “задача со счастливым концом”), во второй половине двадцатого века теория Рамсея оформилась в самостоятельную дисциплину (см. классическую книгу [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.  mathscinet  zmath
2. A. M. Raigorodskii, Thirty essays on geometric graph theory, Springer, New York, 2013, 429–460  crossref  mathscinet  zmath
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  crossref  mathscinet  zmath
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  mathscinet  mathscinet  zmath
5. I. Leader, P. A. Russell, M. Walters, J. Combin. Theory Ser. A., 119:2 (2012), 382–396  crossref  mathscinet  zmath
6. P. Frankl, V. Rödl, J. Amer. Math. Soc., 3:1 (1990), 1–7  crossref  mathscinet  zmath
7. I. Kříž, Proc. Amer. Math. Soc., 112:3 (1991), 899–907  crossref  mathscinet  zmath
8. Р. И. Просанов, Матем. заметки, 103:2 (2018), 248–257  mathnet  crossref  crossref  mathscinet  zmath
9. А. А. Сагдеев, Пробл. передачи информ., 54:4 (2018), 82–109  mathnet  crossref  mathscinet  zmath
10. А. А. Сагдеев, Пробл. передачи информ., 55:4 (2019), 86–106  mathnet  crossref  mathscinet  zmath
11. E. Naslund, Bull. Lond. Math. Soc., 52:4 (2020), 687–692  crossref  mathscinet  zmath
12. D. Conlon, J. Fox, Discrete Comput. Geom., 61:1 (2019), 218–225  crossref  mathscinet  zmath
13. А. Б. Купавский, А. А. Сагдеев, УМН, 75:5(455) (2020), 191–192  mathnet  crossref  crossref  mathscinet  zmath  adsnasa
14. A. Kupavskii, A. Sagdeev, Forum Math. Sigma, 9 (2021), e55, 12 pp.  crossref  mathscinet  zmath

Образец цитирования: А. Б. Купавский, А. А. Сагдеев, Н. Франкл, “Бесконечные множества могут быть рамсеевскими в метрике Чебышёва”, УМН, 77:3(465) (2022), 175–176; Russian Math. Surveys, 77:3 (2022), 549–551
Цитирование в формате 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}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/rm10055
  • https://doi.org/10.4213/rm10055
  • https://www.mathnet.ru/rus/rm/v77/i3/p175
  • Эта публикация цитируется в следующих 1 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Успехи математических наук Russian Mathematical Surveys
    Статистика просмотров:
    Страница аннотации:261
    PDF русской версии:21
    PDF английской версии:32
    HTML русской версии:85
    HTML английской версии:104
    Список литературы:45
    Первая страница:23
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024