An efficient asymmetric removal lemma and its limitations
Lior Gishboliner, A. Shapira, Yuval Wigderson · Forum of Mathematics Sigma · 2025
Abstract The triangle removal states that if G contains $\varepsilon n^2$ edge-disjoint triangles, then G contains $\delta (\varepsilon )n^3$ triangles. Unfortunately, there are no sensible bounds on the order of growth of $\delta (\varepsilon )$ , and at any rate, it is known that $\delta (\varepsilon )$ is not polynomial in $\varepsilon $ . Csaba recently obtained an asymmetric variant of the triangle removal, stating that if G contains $\varepsilon n^2$ edge-disjoint triangles, then G contains $2^{-\operatorname {\mathrm {poly}}(1/\varepsilon )}\cdot n^5$ copies of $C_5$ . To this end, he devised a new variant of Szemerédi’s regularity lemma. We obtain the following results: • We first give a regularity-free proof of Csaba’s theorem, which improves the number of copies of $C_5$ to the optimal number $\operatorname {\mathrm {poly}}(\varepsilon )\cdot n^5$ . • We say that H is $K_3$ -abundant if every graph containing $\varepsilon n^2$ edge-disjoint triangles has $\operatorname {\mathrm {poly}}(\varepsilon )\cdot n^{\lvert V(H)\rvert }$ copies of H. It is easy to see that a $K_3$ -abundant graph must be triangle-free and tripartite. Given our first result, it is natural to ask if all triangle-free tripartite graphs are $K_3$ -abundant. Our second result is that assuming a well-known conjecture of Ruzsa in additive number theory, the answer to this question is negative. Our proofs use a mix of combinatorial, number-theoretic, probabilistic and Ramsey-type arguments.