Infinitely many size-Ramsey numbers of $k$-uniform relaxed $\ell$-trees are not polynomial

Abstract

The size-Ramsey number ${\hat{R}}_k(\mathcal{G})$ of a $k$-uniform hypergraph $\mathcal{G}$ is the minimum number of edges in a $k$-uniform hypergraph $\mathcal{H}$ such that every $2$-edge-coloring of $\mathcal{H}$ contains a monochromatic copy of $\mathcal{G}$. The following question was pointed out by Fox and recorded by Dudek, La Fleur, Mubayi and Rödl~\cite{Dudek-Fleur-Mubayi-Rodl}: for fixed $2\le \ell <k$, is the size-Ramsey number of every $k$-uniform relaxed $\ell$-tree bounded by a polynomial in $n$? We answer this question in the range \[ \ell\geq3 \quad\text{and}\quad \ell+1\leq k\leq2\ell-2. \] For every sufficiently large $n$, we construct a $k$-uniform relaxed $\ell$-tree ${\bar{\mathcal{T}}}_{n,\ell }^{(k)}$ on exactly $n$ vertices such that $${\hat{R}}_k({\bar{\mathcal{T}}}_{n,\ell }^{(k)})\ge 2^{c_{k,\ell }{n}^{1/\ell }}$$ for a constant $c_{k,\ell }>0$ depending only on $k$ and $\ell$.

7 pages