# Graphs with linear Ramsey number for two colors, but super-linear Ramsey number for three colors?

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)$$?

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)}$$.