The Chromatic Number of ${\mathbb{R}}^n$ with Multiple Forbidden Distances

Abstract

Let $A\subset {\mathbb{R}}_{>0}$ be a finite set of distances, and let $G_A({\mathbb{R}}^n)$ be the graph with vertex set ${\mathbb{R}}^n$ and edge set $\{(x,y)\in {\mathbb{R}}^n:\Vert x-y{\Vert }_2\in A\}$, and let $\chi ({\mathbb{R}}^n,A)=\chi \left(G_A({\mathbb{R}}^n)\right)$. Erdős asked about the growth rate of the $m$-distance chromatic number \[ \barχ(\mathbb{R}^{n};m)=\max_{|A|=m}χ(\mathbb{R}^{n},A). \] We improve the best existing lower bound for $\bar{\chi }({\mathbb{R}}^n;m)$, and show that \[ \barχ(\mathbb{R}^{n};m)\geq\left(Γ_χ\sqrt{m+1}+o(1)\right)^{n} \] where ${\Gamma }_{\chi }=0.79983\dots$ is an explicit constant. Our full result is more general, and applies to cliques in this graph. Let ${\chi }_k(G)$ denote the minimum number of colors needed to color $G$ so that no color contains a $(k+1)$-clique, and let ${\bar{\chi }}_k({\mathbb{R}}^n;m)$ denote the largest value this takes for any distance set of size $m$ . Using the Partition Rank Method, we show that \[ \barχ_{k}(\mathbb{R}^{n};m)>\left(Γ_χ\sqrt{\frac{m+1}{k}}+o(1)\right)^{n}. \]

21 pages. Removed section 2. To appear in Mathematika