| Russian Mathematical Surveys |
|
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper) Brief Communications Infinite sets can be Ramsey in the Chebyshev metric A. B. Kupavskiiab, A. A. Sagdeeva, N. Franklc a Moscow Institute for Physics and Technology (National Research University) b CNRS, Grenoble, France c Alfréd Rényi Institute of Mathematics, Budapest, Hungary
Russian version:
Uspekhi Matematicheskikh Nauk, 2022, Volume 77, Issue 3(465), DOI: https://doi.org/10.4213/rm10055 
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$. Theorem 1. For any natural number $n$, (a) if $\lim_{i} \lambda_i/\lambda_{i+1} \leqslant 1+5^{-n}$, then $\chi(\mathbb{R}_\infty^n,\mathcal{B}(\boldsymbol{\lambda}))=2$; (b) if $\lambda_i \geqslant 32\lambda_{i+1}$ for all $i \in \mathbb{N}$, then $\chi(\mathbb{R}_\infty^n,\mathcal{B}(\boldsymbol{\lambda})) \geqslant \log_3 n$; (c) if $\lambda_i \geqslant 2^{n}\lambda_{i+1}$ for all $i \in \mathbb{N}$, then $\chi(\mathbb{R}_\infty^n,\mathcal{B}(\boldsymbol{\lambda})) \geqslant n+1$; (d) if $|Y|\geqslant n^n$, then $\chi(\mathbb{R}_\infty^n,\mathcal Y) \leqslant n+1$. 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$? 
Citation in format AMSBIB
\Bibitem{KupSagFra22} |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|