Russian Mathematical Surveys, 2022, Volume 77, Issue 3, Pages 549–551 DOI: https://doi.org/10.1070/RM10055 (Mi rm10055)

DOI: https://doi.org/10.1070/RM10055

Funding agency	Grant number
Russian Science Foundation	22-21-00368
Contest «Young Russian Mathematics»
The second author was supported by the Russian Science Foundation (grant no. 22-21-00368). The second author was also a winner of the Young Russian Mathematics Contest, and he would like to thank the sponsors and jury of the contest.

Bibliographic databases:

Ramsey theory, which originated from a group of unrelated (at first glance) results from different areas of mathematics (Ramsey’s theorem, which appeared due to the intrinsic development of mathematical logic, the number-theoretic Schur theorem, the geometric ‘happy ending problem’), evolved into a separate discipline in the second half of the 20th century (see the classical book [1]). The present study is concerned with geometric Ramsey problems, which encompass the well-known currently open problem of the chromatic number of the plane (see the survey [2]) and can be traced back to the classical studies in [3] and [4] by Erdős with coauthors.

Let us give the formal definitions. Let $\mathbb{X}=(X,\rho_X)$, $\mathcal{Y}=(Y,\rho_Y)$ be metric spaces. A subset $Y'$ of $X$ is called a copy of $\mathcal{Y}$ if there exists a bijection $f\colon Y \to Y'$ that preserves distances. The chromatic number $\chi(\mathbb{X},\mathcal{Y})$ of $\mathbb{X}$ with forbidden space $\mathcal{Y}$ is by definition the smallest $k$ such that the elements of $X$ can be coloured with $k$ colours so that no monochromatic copy $Y' \subset X$ of $\mathcal{Y}$ arises. The Euclidean Ramsey theory treats the case where $\mathbb{X}$ is an $n$-dimensional Euclidean space $\mathbb{R}_2^n$. At present, there is no answer (nor even a generally accepted conjecture) in the problem of the classification of the finite Ramsey spaces (that is, spaces $\mathcal{Y}$ such that $\chi(\mathbb{R}_2^n,\mathcal{Y})\to \infty$ as $n \to \infty$), even though this problem has been drawing the attention of many prominent mathematicians for several decades (see [5]–[11]). However, the situation turns out to be much simpler if the forbidden space $\mathcal{Y}$ is infinite: in [4] it was shown that in this case the exact equality $\chi(\mathbb{R}_2^n,\mathcal{Y})=2$ holds. The conjecture that this equality holds not only for infinite, but also for all sufficiently large spaces $\mathcal{Y}$ (in terms of the dimension $n$) is still open (see [12]).

Recently [13], [14] the authors of the present paper have extended problems in the Euclidean Ramsey theory to the metric spaces $\mathbb{R}_\infty^n=(\mathbb{R}^n,\ell_\infty)$, where $\ell_\infty$ is the standard Chebyshev metric defined by $\ell_\infty(\mathbf{x},\mathbf{y})=\max_{i}|x_i-y_i|$ for all $\mathbf{x}=(x_1,\dots,x_n)$ and $\mathbf{y}=(y_1,\dots,y_n)$ in $\mathbb{R}^n$. It particular, they showed that for any finite metric space $\mathcal{Y}$ there exists a constant $c=c(\mathcal Y)>1$ such that $\chi(\mathbb{R}_\infty^n,\mathcal Y)>c^n$ for any $n\in \mathbb N$. However, the situation with infinite forbidden spaces $\mathcal{Y}$ remained unclear. Our paper fills this gap.

The subsets $\mathcal{B}(\boldsymbol{\lambda})= \{0,\lambda_1,\lambda_1+\lambda_2,\dots\}$ of the real line, where $\boldsymbol{\lambda}=(\lambda_1,\lambda_2,\dots)$ is an arbitrary decreasing sequence of positive numbers, provide an example of most natural resolvable infinite metric spaces. It can be assumed without loss of generality that the series $\sum_i\lambda_i$ is convergent, because a simple $2$-colouring of the space by nested colour-alternating cubes with sufficiently rapidly growing side lengths shows that $\chi(\mathbb{R}_\infty^n,\mathcal Y)=2$ for all $\mathcal{Y}$ such that $\operatorname{diam}(\mathcal{Y})=\infty$.

We note two corollaries of this result, which illustrate the fundamental difference between the Euclidean and Chebyshev Ramsey theories.

First, the estimate $\chi(\mathbb{R}_\infty^n,\mathcal Y) \leqslant n+1$ is the best upper estimate for $\chi(\mathbb{R}_\infty^n,\mathcal Y)$ that holds for all infinite metric spaces $\mathcal{Y}$. In particular, this estimate depends on the dimension $n$. Moreover, by contrast to the Euclidean case, one can prove its attainability not only for infinite spaces, but also for all sufficiently large spaces $\mathcal{Y}$.

Second, assertion (b) of Theorem 1 guarantees the existence of an infinite Ramsey space (in the Chebyshev metric), that is, a set $\mathcal{Y}$ such that $\chi(\mathbb{R}_\infty^n,\mathcal Y) \to \infty$ as $n \to \infty$. In fact, it suffices to put $\mathcal{Y}=\mathcal{B}(\boldsymbol{\lambda})$, where $\boldsymbol{\lambda}$ is an infinite decreasing geometric progression with ratio $1/32$ (or with any smaller ratio). Here the growth rate of $\chi(\mathbb{R}_\infty^n,\mathcal Y)$ is at least logarithmic.

This result leaves open the following questions. How the quantity $\chi(\mathbb{R}_\infty^n,\mathcal{B}(\boldsymbol{\lambda}))$ behaves with respect to the dimension, where $\boldsymbol{\lambda}$ is an infinite decreasing geometric progression with ratio $1/32 < q < 1$? Does there exist an infinite metric space $\mathcal{Y}$ such that $\chi(\mathbb{R}_\infty^n,\mathcal Y)=n+1$ for all natural numbers $n$?

Bibliography
1.	R. L. Graham, B. L. Rothschild, and 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, and 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, and 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, and M. Walters, J. Combin. Theory Ser. A., 119:2 (2012), 382–396
6.	P. Frankl and 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.	R. I. Prosanov, Mat. Zametki, 103:2 (2018), 248–257        ; English transl. in Math. Notes, 103:2 (2018), 243–250
9.	A. A. Sagdeev, Problemy Peredach Informatsii, 54:4 (2018), 82–109      ; English transl. in Problems Inform. Transmission, 54:4 (2018), 372–396
10.	A. A. Sagdeev, Problemy Peredachi Infornatsii, 55:4 (2019), 86–106      ; English transl. in Problems Inform. Transmission, 55:4 (2019), 376–395
11.	E. Naslund, Bull. Lond. Math. Soc., 52:4 (2020), 687–692
12.	D. Conlon and J. Fox, Discrete Comput. Geom., 61:1 (2019), 218–225
13.	A. B. Kupavskii and A. A. Sagdeev, Uspekhi Mat. Nauk, 75:5(455) (2020), 191–192        ; English transl. in Russian Math. Surveys, 75:5 (2020), 965–967
14.	A. Kupavskii and A. Sagdeev, Forum Math. Sigma, 9 (2021), e55, 12 pp.

Citation in format AMSBIB

\Bibitem{KupSagFra22}
\by A.~B.~Kupavskii, A.~A.~Sagdeev, N.~Frankl
\paper Infinite sets can be Ramsey in the Chebyshev metric
\jour Russian Math. Surveys
\yr 2022
\vol 77
\issue 3
\pages 549--551
\mathnet{http://mi.mathnet.ru/eng/rm10055}
\crossref{https://doi.org/10.1070/RM10055}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4602197}
\zmath{https://zbmath.org/?q=an:1520.05096}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2022RuMaS..77..549K}
\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

CITATION

1 Total citation

1 Recent citation

0.98 Field Citation Ratio

n/a Relative Citation Ratio