Polynomial-in-$r$ bounds for forbidden traces of uniform hypergraphs

Abstract

We give a general principle that converts fixed-uniformity bounds for forbidden traces into bounds with polynomial dependence on the uniformity. More precisely, let $H$ be a fixed set system on $h\ge1$ vertices, and suppose that, for some $\alpha\ge0$, $\operatorname{ex}_j(m,\operatorname{Tr}(H))=O_{H,j}(m^\alpha)$ for every fixed integer $j\ge1$. Then, for every $\varepsilon>0$, there is a constant $C_{H,\alpha,\varepsilon}$ such that \[ \operatorname{ex}_r(m,\operatorname{Tr}(H)) \le C_{H,\alpha,\varepsilon} r^{h-1-\alpha+\varepsilon}m^\alpha \] for all $m\ge r\ge2$. In particular, for trace-$C_4$-free hypergraphs and every $\varepsilon>0$ there is a constant $C_\varepsilon$ such that \[ \operatorname{ex}_r(m,\operatorname{Tr}(C_4)) \le C_\varepsilon r^{3/2+\varepsilon}m^{3/2} \] for all $m\ge r\ge2$. We also construct trace-$C_4$-free $r$-graphs showing that \[ \operatorname{ex}_r(m,\operatorname{Tr}(C_4)) \ge c r^{1/2}m^{3/2} \] for an absolute constant $c>0$, for every fixed $r\ge3$ and all sufficiently large $m$ (depending on $r$).