Compactness of abundance in asymmetric hypergraph removal lemmas

Abstract

Fix an integer $r\ge 2$ and a finite simple $r$-uniform hypergraph $F$ with at least one edge and no isolated vertices. An $n$-vertex $r$-graph is $\epsilon$-far from being $F$-free if at least $\epsilon n^r$ edges must be deleted to destroy every copy of $F$. A finite $r$-graph $H$ is $F$-abundant if there are constants $c,C>0$ such that every sufficiently large $\epsilon$-far host contains at least $c{\epsilon }^C{n}^{v(H)}$ labelled copies of $H$. A family is $F$-abundant when one member has this lower bound in each host, although the member may depend on the host and on $\epsilon$, while $c$ and $C$ are common to the family. We prove that every abundant family contains an abundant member. We prove the analogous coloured theorem for $F$-partite hosts containing edge-disjoint part-respecting copies of $F$ such that every vertex lies in at least $\epsilon n^{r-1}$ of them. The case $r=2$ yields the coloured and uncoloured graph compactness theorems, answers Question 5.2 of Girão, Hurley, Illingworth and Michel, and proves their Conjecture 5.1 [J. Lond. Math. Soc., 2024]. We also obtain an explicit bound $\lfloor 2r(C+1)\rfloor$ for the order of the non-isolated core of a selected witness. Moreover, we give several applications. For example, we construct translation-invariant linear systems from abundant coloured hypergraphs, obtain a square-root bound for an equation associated with a cycle of bounded length, give a one-sided tester based on one fixed graph when distance from the property gives a polynomial lower bound on distance from being $F$-free, and prove that no algorithm decides whether a family of finite simple graphs enumerated by a Turing machine is $K_3$-abundant.

arXiv comment23 pages. Comments welcome!