Max-norm Ramsey Theory

Abstract

Given a metric space $\mathcal{M}$ that contains at least two points, the chromatic number $\chi \left({\mathbb{R}}_{\infty }^n,\mathcal{M}\right)$ is defined as the minimum number of colours needed to colour all points of an $n$-dimensional space ${\mathbb{R}}_{\infty }^n$ with the max-norm such that no isometric copy of $\mathcal{M}$ is monochromatic. The last two authors have recently shown that the value $\chi \left({\mathbb{R}}_{\infty }^n,\mathcal{M}\right)$ grows exponentially for all finite $\mathcal{M}$. In the present paper we refine this result by giving the exact value ${\chi }_{\mathcal{M}}$ such that $\chi \left({\mathbb{R}}_{\infty }^n,\mathcal{M}\right)=({\chi }_{\mathcal{M}}+o(1){)}^n$ for all 'one-dimensional' $\mathcal{M}$ and for some of their Cartesian products. We also study this question for infinite $\mathcal{M}$. In particular, we construct an infinite $\mathcal{M}$ such that the chromatic number $\chi \left({\mathbb{R}}_{\infty }^n,\mathcal{M}\right)$ tends to infinity as $n\to \infty$.

32 pages. v3: a few modifications based on the reviews

References in corpus (2)

• Odd-distance and right-equidistant sets in the maximum and Manhattan metrics
• Two-colorings of normed spaces without long monochromatic unit arithmetic progressions