New bounds for the distance Ramsey number

Abstract

In this paper we study the distance Ramsey number $R_D(s,t,d)$. The \textit{distance Ramsey number} $R_D(s,t,d)$ is the minimum number $n$ such that for any graph $G$ on $n$ vertices, either $G$ contains an induced $s$-vertex subgraph isomorphic to a distance graph in $ \Real^d $ or $\bar{G}$ contains an induced $t$-vertex subgraph isomorphic to the distance graph in $ \Real^d $. We obtain the upper and lower bounds on $R_D(s,s,d),$ which are similar to the bounds for the classical Ramsey number $R(\lceil \frac{s}{[d/2]}\rceil ,\lceil \frac{s}{[d/2]}\rceil )$.