8
$\begingroup$

The Triangle Removal Lemma states that any graph with $o(n^3)$ triangles can be made triangle-free by removing only $o(n^2)$ edges. More generally, the Graph Removal Lemma states that for any graph $H$ on a constant $|V(H)| = k$ number of nodes, any graph with $o(n^k)$ copies of $H$ can be made $H$-free by removing at most $o(n^2)$ edges.

These theorems are proved using essentially the same set of techniques. However, I wonder if there is a direct proof of the Graph Removal Lemma, assuming the Triangle Removal Lemma, that does not need to pass through any of the usual regularity lemmas used to prove these things.

$\endgroup$
8
$\begingroup$

A proof of the Graph Removal Lemma that avoids using the regularity lemma can be found in A new proof of the graph removal lemma (2010). For an explanation why a direct proof of the Graph Removal Lemma from the Triangle Removal Lemma is not viable, see this discussion:

The proof of the Graph Removal Lemma is more intricate than that of the Triangle Removal Lemma. Actually, it depends on the structure of the graph $H$. If, for example, $H$ is a four-cycle, then the argument applied in the proof of the triangle removal lemma does not work, mainly because, once the "impure" edges are discarded, the copy of $H$ that remains may have two vertices in a same cluster. In other words, the connectivity properties of $H$ influence the distribution of the vertices along the clusters.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.