Vertex-Ramsey theorems for Cartesian powers of graphs

Abstract

For graphs $G,H$ and positive integers $r$ and $n$ we write $G^{\square n}\stackrel{r}{\to }H$ if every $r$-vertex-coloring of the Cartesian power $G^{\square n}$ of $G$ contains a monochromatic copy of $H$. Since chromatic number $\chi$ of $G^{\square n}$ is the same as $\chi (G)$, there is an $r$-vertex coloring of $G^{\square n}$ for $r=\chi (G)$, such that each color class is an independent set. We prove that for $r<\chi (G)$ there is a large class of graphs $H$ such that $G^{\square n}\stackrel{r}{\to }H$. These graphs are so-called layered graphs in a hypercube. We also show that for some graphs $G$, such as for example odd cycles or cliques, the class of layered graphs $H$ is the only one satisfying the above Ramsey property when $\chi (G)/2<r<\chi (G)$. In addition, we prove a more general result relating Ramsey properties of $G$ and graphs $H$ such that $G^{\square n}\stackrel{r}{\to }H$. One of the technical tools is a Ramsey-type statement for discrete cubes $[m{]}^n$ that we call the Cube Layered Lemma, which is of independent interest. One of the original motivations for studying Ramsey properties of Cartesian powers of $G$ is the fact that $G^{\square n}$ is a unit distance graph if $G$ is a unit distance graph. This provides applications in Euclidean Ramsey theory.

16 pages