PreprintCC BY 4.0arXiv
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≥1 vertices, and suppose that, for some α≥0, exj(m,Tr(H))=OH,j(mα) for every fixed integer j≥1. Then, for every ε>0, there is a constant CH,α,ε such that exr(m,Tr(H)) ≤ CH,α,ε rh−1−α+εmα for all m≥ r≥2. In particular, for trace-C4-free hypergraphs and every ε>0 there is a constant Cε such that exr(m,Tr(C4)) ≤ Cε r3/2+εm3/2 for all m≥ r≥2. We also construct trace-C4-free r-graphs showing that exr(m,Tr(C4)) ≥ c r1/2m3/2 for an absolute constant c>0, for every fixed r≥3 and all sufficiently large m (depending on r).
Related
- The upper bounds on occupancy fraction and variance fraction for linear regular uniform hypergraphs
- Degree profiles of uniform polynomial consequences: Linear lower bounds for Nullstellensatz and Polynomial Calculus
- Linear dependencies, polynomial factors in the Duke–Erdős forbidden sunflower problem – CORRIGENDUM
- Phase transition of random non-uniform hypergraphs
- Irregular Triads in 3-Uniform Hypergraphs
BibTeX
@misc{wu2026polynomialinr,
title = {{Polynomial-in-$r$ bounds for forbidden traces of uniform hypergraphs}},
author = {Pei Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08151},
eprint = {2610.08151},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08151},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Polynomial-in-r bounds for forbidden traces of uniform hypergraphs
AU - Pei Wu
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08151
UR - https://arxiv.org/abs/2610.08151
AB - 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≥1 vertices, and suppose that, for some α≥0, ex_j(m,Tr(H))=O_H,j(m^α) for every fixed integer j≥1. Then, for every ε>0, there is a constant C_H,α,ε such that ex_r(m,Tr(H)) ≤ C_H,α,ε r^h−1−α+εm^α for all m≥ r≥2. In particular, for trace-C_4-free hypergraphs and every ε>0 there is a constant C_ε such that ex_r(m,Tr(C_4)) ≤ C_ε r^3/2+εm^3/2 for all m≥ r≥2. We also construct trace-C_4-free r-graphs showing that ex_r(m,Tr(C_4)) ≥ c r^1/2m^3/2 for an absolute constant c>0, for every fixed r≥3 and all sufficiently large m (depending on r).
ER -