Hypergraph removal

For each fixed finite uniform hypergraph $F$, having few copies of $F$ forces small edge-edit distance from an $F$-free hypergraph. More precisely, for every $\eta >0$ there is $\rho >0$ such that fewer than $\rho v^{|V(F)|}$ copies can be eliminated by deleting fewer than $\eta v^r$ edges in an $r$-uniform hypergraph. Strong regularity for three-uniform hypergraphs and a relative counting lemma prove the case $r=3$.

For every $\eta >0$, some $\rho >0$ has this property: a three-uniform hypergraph on $v$ vertices with fewer than $\rho v^4$ copies of the three-uniform tetrahedron can be made tetrahedron-free by removing fewer than $\eta v^3$ hyperedges. The four-term progression hypergraph encoding converts this into the length-four case of the Szemerédi theorem.