Triangle removal lemma

From Polymath Wiki
Revision as of 08:49, 14 February 2009 by Teorth (talk | contribs) (New page: '''Triangle removal lemma''': If a graph on n vertices contains <math>o(n^3)</math> triangles, then all triangles can be deleted by removing at most <math>o(n^2)</math> edges. This lemma ...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Triangle removal lemma: If a graph on n vertices contains [math]\displaystyle{ o(n^3) }[/math] triangles, then all triangles can be deleted by removing at most [math]\displaystyle{ o(n^2) }[/math] edges.

This lemma was first proven by Ruzsa and Szemerédi, who observed that it implies Roth's theorem. Solymosi later observed that it also implies the corners theorem.

[Discussion about how one might hope to use the triangle removal lemma for DHJ needed here.]