The Triangle Removal Lemma

[At the end of a survey paper on additive combinatorics and computational complexity which is to appear in SIGACT News, I list three major open questions in additive combinatorics which might be amenable to a “computer science proof.” They are all extremely well studied questions, by very smart people, for the past several years, so they are all very long shots. I don’t recommend anybody to start working on them, but I think it is good that as many people as possible know about these questions, because when the right technique comes along its applicability can be more quickly realized.]

The first question is to improve the Triangle Removal Lemma. I have talked here about what the triangle removal lemma is, how one can prove it from the Szemerédi Regularity Lemma, and how it implies the length-3 case of Szemerédi’s Theorem.

As a short recap, the Triangle Removal Lemma states that if {G} is an {n}-vertex graph with {o(n^3)} triangles, then there is a set of {o(n^2)} edges such that the removal of those edges eliminates all the triangles. Equivalently, it says that if a graph has {\Omega(n^2)} triangles which are all pair-wise edge-disjoint, then there must be {\Omega(n^3)} triangles overall.

The connection with Szemerédi’s Theorem is that if {H} is an abelian group with {n} elements, and {A} is a subset of {H} with no length-3 arithmetic progressions (i.e., {A} is such that there are no three distinct elements {a,b,c} in {A} such that {b-a = c-b}), then we can construct a graph {G=(V,E)} that has {3n} vertices, {|A| \cdot n} pair-wise edge-disjoint triangles, and no other triangles. This contradicts the triangle removal lemma if {|A| = \Omega(n)}, and so we must have {|A| = o(n)}.

This is great, until we start looking at the relationships between the constants hidden by the {o(\cdot )} notation. Quantitatively, the Triangle Removal Lemma states that for every {\epsilon} there is a {\delta = \delta(\epsilon)} such that if a graph has at least {\epsilon \cdot n^2} pair-wise edge-disjoint triangles, then it has at least {\delta \cdot n^3} triangles. The only known proof, however, has {\delta} incredibly small: {1/\delta} grows like a tower of exponentials of height polynomial in {1/\epsilon}. The proof uses the Szemerédi Regularity Lemma, and the Regularity Lemma is known to require such very bad dependencies.

63 years ago, Behrend showed that {{\mathbb Z}/N{\mathbb Z}}, {N} prime, has a subset {A} that contains no length-3 arithmetic progression and whose size is {N/2^{O(\sqrt {\log N})}}. (Last year, Elkin gave the first improvement in 62 years to Behrend’s bound, but the improvement is only a multiplicative polylog {N} factor.) Combined with the graph construction mentioned above, this gives a graph with {3N} vertices, {N^2/^{O(\sqrt {\log N})}} edge-disjoint triangles, and no other triangle. Thus, the graph has {\leq \delta N^3} triangles where {\delta < 1/N}, but one needs to remove {> \epsilon N^2} edges to make it triangle-free, where {\epsilon > 2^{-O(\sqrt{\log N})}}. This shows that, in the Triangle Removal Lemma, {1/\delta} must grow super-polynomially in {1/\epsilon}, and be at least {1/\epsilon^{\log 1/\epsilon}}.

The question is to shorten the gap between the tower-of-exponential relationship between {1/\delta} and {1/\epsilon} coming from the proof via the Szemerédi Regularity Lemma and the mildly super-polynomial lower bound coming from the above argument.

Continue reading

Advertisements