Triangle removal lemma: Difference between revisions
From Polymath Wiki
Jump to navigationJump to search
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 ... |
(No difference)
|
Revision as of 09:49, 14 February 2009
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.]
