Polynomial-in- bounds for forbidden traces of uniform hypergraphs
In the authors' words
We give a general principle that converts fixed-uniformity bounds for forbidden traces into bounds with polynomial dependence on the uniformity. More precisely, let be a fixed set system on vertices, and suppose that, for some , for every fixed integer . Then, for every , there is a constant such that \[ \operatorname{ex}_r(m,\operatorname{Tr}(H)) \le C_{H,\alpha,\varepsilon} r^{h-1-\alpha+\varepsilon}m^\alpha \] for all . In particular, for trace--free hypergraphs and every there is a constant such that \[ \operatorname{ex}_r(m,\operatorname{Tr}(C_4)) \le C_\varepsilon r^{3/2+\varepsilon}m^{3/2} \] for all . We also construct trace--free -graphs showing that \[ \operatorname{ex}_r(m,\operatorname{Tr}(C_4)) \ge c r^{1/2}m^{3/2} \] for an absolute constant , for every fixed and all sufficiently large (depending on ).
Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 8 pages