Triangle removal lemma

Triangle removal lemma: If a graph on [math]\displaystyle{ n }[/math] 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. That is, for every [math]\displaystyle{ a\gt 0 }[/math] there exists [math]\displaystyle{ c\gt 0 }[/math] such that if [math]\displaystyle{ G }[/math] is any graph with [math]\displaystyle{ n }[/math] vertices and at most [math]\displaystyle{ cn^3 }[/math] triangles, then it is possible to remove at most [math]\displaystyle{ 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.

Deducing the corners theorem

Let [math]\displaystyle{ A }[/math] be a subset of [math]\displaystyle{ [n]^2 }[/math] of density [math]\displaystyle{ \delta }[/math]. Define a tripartite graph [math]\displaystyle{ G }[/math] by taking its vertex sets to be [math]\displaystyle{ X=Y=[n] }[/math] and [math]\displaystyle{ Z=[2n] }[/math]. Join [math]\displaystyle{ x\in X }[/math] to [math]\displaystyle{ y\in Y }[/math] if and only if [math]\displaystyle{ (x,y)\in A }[/math]. Join [math]\displaystyle{ x\in X }[/math] to [math]\displaystyle{ z\in Z }[/math] if and only if [math]\displaystyle{ (x,z-x)\in A }[/math]. Join [math]\displaystyle{ y\in Y }[/math] to [math]\displaystyle{ z\in Z }[/math] if and only if [math]\displaystyle{ (z-y,y)\in A }[/math]. (One thinks of [math]\displaystyle{ X }[/math] as the set of vertical lines through [math]\displaystyle{ [n]^2 }[/math], [math]\displaystyle{ Y }[/math] as the set of horizontal lines, and [math]\displaystyle{ Z }[/math] as the set of lines of gradient [math]\displaystyle{ -1 }[/math]. Two vertices are joined if the corresponding lines intersect at a point in [math]\displaystyle{ A }[/math].)

Now suppose that we have a triangle [math]\displaystyle{ xyz }[/math] in the graph [math]\displaystyle{ G }[/math]. Then [math]\displaystyle{ (x,y), (x,y+d) }[/math] and [math]\displaystyle{ (x+d,y) }[/math] belong to [math]\displaystyle{ A }[/math], where [math]\displaystyle{ d=z-x-y }[/math]. This gives us a corner unless [math]\displaystyle{ x+y=z }[/math]. If [math]\displaystyle{ x+y=z }[/math] then the three lines corresponding to [math]\displaystyle{ x, y }[/math] and [math]\displaystyle{ z }[/math] all go through the same point. Let us call this a degenerate triangle in [math]\displaystyle{ G }[/math].

It is easy to check that the degenerate triangles are edge disjoint. Moreover, for each point of [math]\displaystyle{ A }[/math] there is a degenerate triangle. Therefore, one cannot remove fewer than [math]\displaystyle{ \delta n^2 }[/math] edges and end up with no triangles. By the triangle removal lemma, it follows that there are at least [math]\displaystyle{ c(\delta)n^3 }[/math] triangles in the graph [math]\displaystyle{ G }[/math]. If [math]\displaystyle{ n }[/math] is sufficiently large, this implies that there is at least one non-degenerate triangle in [math]\displaystyle{ G }[/math], and hence a corner in [math]\displaystyle{ A }[/math].

A triangle-removal lemma that would imply DHJ

Let [math]\displaystyle{ A }[/math] be a subset of [math]\displaystyle{ [3]^n }[/math]. Then we can define a tripartite graph as follows. Its three vertex sets [math]\displaystyle{ X, Y }[/math] and [math]\displaystyle{ Z }[/math] are all copies of the power set of [math]\displaystyle{ [n] }[/math]. We join [math]\displaystyle{ U\in X }[/math] to [math]\displaystyle{ V\in Y }[/math] if [math]\displaystyle{ U }[/math] and [math]\displaystyle{ V }[/math] are disjoint and the sequence that is 1 in [math]\displaystyle{ U }[/math], 2 in [math]\displaystyle{ V }[/math] and 3 in [math]\displaystyle{ [n]\setminus(U\cup V) }[/math] belongs to [math]\displaystyle{ A }[/math]. We join [math]\displaystyle{ V\in Y }[/math] to [math]\displaystyle{ W\in Z }[/math] if the sequence that is 2 on [math]\displaystyle{ V }[/math] and 3 on [math]\displaystyle{ W }[/math] and 1 elsewhere belongs to [math]\displaystyle{ A }[/math]. And we join [math]\displaystyle{ U\in X }[/math] to [math]\displaystyle{ W\in Z }[/math] if the sequence that is 1 on [math]\displaystyle{ U }[/math] and 3 on [math]\displaystyle{ W }[/math] and 2 elsewhere belongs to [math]\displaystyle{ A }[/math].

Suppose now that we have a triangle [math]\displaystyle{ U,V,W }[/math] in this graph and let [math]\displaystyle{ D }[/math] be the complement of [math]\displaystyle{ U\cup V\cup W }[/math]. Then the three sequences with 1-set, 2-set and 3-set equal to [math]\displaystyle{ (U,V,W\cup D), (U\cup D,V,W) }[/math] and [math]\displaystyle{ (U,V\cup D,W) }[/math] all belong to [math]\displaystyle{ A }[/math]. This gives us a combinatorial line unless [math]\displaystyle{ D=\emptyset }[/math]. Let us call such triangles degenerate.

This argument shows that if DHJ is false then there is a tripartite graph with degenerate triangles only, and its three parts are all dense subgraphs of the graph where you join two sets if they are disjoint. We cannot remove all degenerate triangles without removing [math]\displaystyle{ |A| }[/math] edges. If this is a contradiction, then DHJ is proved.