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

# FOCS 2008 Tutorial

Last week I gave a tutorial on average-case complexity at FOCS’08.

I have now posted online the slides, along with links to some survey papers.

In my talk I discussed the following four open problems, which are among my favorite. Continue reading