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

Abstract

The size-Ramsey number $\widehat{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\"{o}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 $$ \widehat{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$.