Hypergraph Ramsey numbers of cliques versus stars

Abstract

Let $K_m^{(3)}$ denote the complete $3$-uniform hypergraph on $m$ vertices and $S_n^{(3)}$ the $3$-uniform hypergraph on $n+1$ vertices consisting of all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges incident to a given vertex. Whereas many hypergraph Ramsey numbers grow either at most polynomially or at least exponentially, we show that the off-diagonal Ramsey number $r(K_4^{(3)},S_n^{(3)})$ exhibits an unusual intermediate growth rate, namely, \[ 2^{c \log^2 n} \le r(K_{4}^{(3)},S_n^{(3)}) \le 2^{c' n^{2/3}\log n} \] for some positive constants $c$ and $c^{\prime }$. The proof of these bounds brings in a novel Ramsey problem on grid graphs which may be of independent interest: what is the minimum $N$ such that any $2$-edge-coloring of the Cartesian product $K_N\square K_N$ contains either a red rectangle or a blue $K_n$?

13 pages