Ramsey numbers with prescribed rate of growth

Abstract

Let $R(G)$ be the two-colour Ramsey number of a graph $G$. In this note, we prove that for any non-decreasing function $n\le f(n)\le R(K_n)$, there exists a sequence of connected graphs $(G_n{)}_{n\in \mathbb{N}}$, with $|V(G_n)|=n$ for all $n\ge 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 a question posed by DeBiasio about the existence of sequences of graphs whose $2$-colour Ramsey number is linear whereas their $3$-colour Ramsey number has superlinear growth.

arXiv commentAccepted to The Electronic Journal of Combinatorics