5
$\begingroup$

Given a graph $H$, let $R_k(H)$ be the smallest integer $N$ such that in every $k$-coloring of the edges $K_N$ there is a monochromatic copy of $H$ (in other words, $R_k(H)$ is the ordinary $k$-color Ramsey number of $H$).

Does there exist a sequence of graphs $(H_n)_{n\in \mathbb{N}}$ (where $H_n$ has $n$ vertices) such that $R_2(H_n)=O(n)$, but $R_3(H_n)=\omega(n)$?

$\endgroup$
6
$\begingroup$

There is an almost example, 'almost' in three senses: it's for $3$-uniform hypergraphs rather than graphs; for $4$ colours rather than $3$; and the $2$-colour case isn't quite known to be linear (though it is conjectured to be).

To be more specific, the example is the $3$-uniform hypergraph known as the hedgehog. This is the $3$-uniform hypergraph $H_t$ with vertex set $[t + \binom{t}{2}]$ such that for every pair $(i, j)$ with $1 \leq i < j \leq t$ there is a unique vertex $k > t$ for which $ijk$ is an edge. It is known that $R_2(H_t) = O(t^2 \log t)$, which is almost linear in the number of vertices, while $R_4(H_t) \geq 2^{\Omega(t)}$.

For more information, see https://arxiv.org/pdf/1511.00563.pdf and https://arxiv.org/pdf/1902.10221.pdf.

$\endgroup$
1
  • $\begingroup$ I just read the fantastically titled "Hedgehogs are not colour blind" paper. This is a very nice example with such a short, simple proof. Based on what you say in the abstract, there won't be a result in the literature which already answers my question (and thus it seems unlikely that my question has an easy answer). $\endgroup$ – Louis D Mar 4 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.