All finite sets are Ramsey in the maximum norm

Abstract

For two metric spaces $\mathbb{X}$ and $\mathcal{Y}$, the chromatic number $\chi (\mathbb{X};\mathcal{Y})$ of $\mathbb{X}$ with forbidden $\mathcal{Y}$ is the smallest $k$ such that there is a coloring of the points of $\mathbb{X}$ with $k$ colors and no monochromatic copy of $\mathcal{Y}$. In this paper, we show that for each finite metric space $\mathcal{M}$ that contains at least two points the value $\chi \left({\mathbb{R}}_{\infty }^n;\mathcal{M}\right)$ grows exponentially with $n$. We also provide explicit lower and upper bounds for some special $\mathcal{M}$.

References in corpus (1)

• Graph minimization, focusing on the example of 5-chromatic unit-distance graphs in the plane

Cited by in corpus (3)

• Solution to a conjecture of Schmidt and Tuller on one-dimensional packings and coverings
• Two-colorings of normed spaces without long monochromatic unit arithmetic progressions
• Max-norm Ramsey Theory