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$

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .