Gowers at 23:46, 14 February 2009

2009-02-14T23:46:14Z

@@ Line 1: / Line 1: @@
-'''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.
+'''Triangle removal lemma''': If a graph on <math>n</math> vertices contains <math>o(n^3)</math> triangles, then all triangles can be deleted by removing at most <math>o(n^2)</math> edges. That is, for every <math>a>0</math> there exists <math>c>0</math> such that if <math>G</math> is any graph with <math>n</math> vertices and at most <math>cn^3</math> triangles, then it is possible to remove at most <math>an^2</math> edges and end up with a graph that is triangle free.
 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.]
+===Deducing the corners theorem===

Teorth: New page: '''Triangle removal lemma''': If a graph on n vertices contains $o(n^3)$ triangles, then all triangles can be deleted by removing at most $o(n^2)$ edges. This lemma ...

2009-02-14T16:49:31Z

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 ...

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 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.]

Triangle removal lemma - Revision history

Gowers at 23:46, 14 February 2009

Teorth: New page: '''Triangle removal lemma''': If a graph on n vertices contains o(n^3) triangles, then all triangles can be deleted by removing at most o(n^2) edges. This lemma ...

Teorth: New page: '''Triangle removal lemma''': If a graph on n vertices contains $o(n^3)$ triangles, then all triangles can be deleted by removing at most $o(n^2)$ edges. This lemma ...