Multiple Distance Ramsey Bounds For Graphs in Euclidean Spaces

Abstract

For a finite set $A\subset {\mathbb{R}}_{>0}$ and a finite graph $H$, let ${\chi }_H({\mathbb{R}}^n;A)$ be the minimum number of colors required to color ${\mathbb{R}}^n$ while avoiding a monochromatic copy of $H$ whose edges have distances in $A$. Extending the graph-copy framework of Axenovich, Liu, and Sagdeev and a multiple distance theorem of Naslund, we prove for any positive integer $m$, \[χ_H(\mathbb{R}^n;m):=\max_{\substack{A \subseteq \mathbb{R}_{>0} \\ |A|=m}} χ_H(\mathbb{R}^n;A) \geq \left(Γ_χ\sqrt{\frac{m+1}{Ξ(H)}}+o(1)\right)^n.\] Here, ${\Gamma }_{\chi }$ is a constant and $\Xi (H)$ is an explicit structural parameter that can be substantially smaller than $|V(H)|-1$, thereby recovering Naslund's similar bound for complete graphs and improving the general bound inherited from the corresponding clique for many graph families. Along the way, we construct a weighted strengthening of the semi-diagonal flattening rank theorem of Correia, Sudakov, and Tomon.

21 pages