Ramsey Numbers with Prescribed Rate of Growth

Abstract

Let $R(G)$ be the $2$-colour Ramsey number of a graph $G$.
In this note, we prove that for any non-decreasing function $n \leq f(n) \leq R(K_n)$, there exists a sequence of connected graphs $(G_n)_{n\in\mathbb N}$, with $|V(G_n)| = n$ for all $n \geq 1$, such that $R(G_n) = \Theta(f(n))$. In contrast, we also show that an analogous statement does not hold for hypergraphs of uniformity at least $5$.

We also use our techniques to answer in the affirmative a question posed by DeBiasio about the existence of sequences of graphs, but whose $2$-colour Ramsey number is linear whereas their $3$-colour Ramsey number has superlinear growth.