Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Theorem (Triangle-free Lemma). For all $\eta>0$ there exists $c > 0$ and $n_0$ so that every graph $G$ on $n>n_0$ vertices, which contains at most $cn^3$ triangles can be made triangle free by removing at most $\eta\binom{n}{2}$ edges.

I am trying to find some information related to this topic, I am unable to access the orignal paper by Ruzsa & Szemeredi.

Does anyone know any useful papers/books on the triangle-free lemma?

share|improve this question

5 Answers 5

up vote 7 down vote accepted

Possibly an even better place to look is in surveys on graph property testing; this is by far the most common use nowadays of the triangle removal lemma, and any sufficiently good introduction to the subject should have some information on it. (I haven't actually read it, but I believe the most recent edition of Alon and Spencer's The Probabilistic Method has a chapter on property testing. If you have access to a copy, assuming the new chapter is anywhere near as good as the rest of the book, that would be my first recommendation.)

If you want a proof and some applications to more traditional combinatorics, Tim Gowers has a wonderful two-paragraph sketch and some discussion here (about halfway down the post).

share|improve this answer

If you're already comfortable with ultrafilters, the new proof of Elek and Szegedy (on the arxiv) derives this (and the more general simplex removal lemma for hypergraphs) from Lebesgue's "points of density" theorem. It's not an easy read, but it is a nice proof.

share|improve this answer
I agree it is an interesting perspective on the subject, but I am unsure whether one can call it a truly different proof, as it still hides the regularity lemma underneath. –  Boris Bukh Nov 26 '09 at 12:09
@Boris: Last I checked, though, there wasn't a proof of triangle removal that didn't go through a regularity lemma, so this isn't a particularly useful argument against it... :) –  Harrison Brown Nov 26 '09 at 18:07
@Boris: hides how? As I read Elek/Szegedy, they get a simplex removal lemma without needing to state regularity (for hypergraphs). Is there some sense in which "points of density" should feel like regularity? –  Kevin O'Bryant Nov 26 '09 at 20:51
@Harrison: I agree that there are none, but that was not an argument against Elek-Szegedy. It was an observation that the proof is in essence 'same', though of course the framework of Elek-Szegedy is more general, and thus potentially might offer insight in other settings. @Kevin: Yes, there is such a sense. The Lebesgue density theorem essentially says that one can approximate every measurable set by union of boxes. For more detailed connection, see terrytao.wordpress.com/2007/06/18/… –  Boris Bukh Nov 27 '09 at 10:10

Jacob Fox has just posted A new proof of the graph removal lemma to the arXiv, containing a proof that does not use regularity directly, and thereby accomplishes some more effective bounds.

share|improve this answer

The standard name is 'triangle removal lemma'. Google search gives many results. The original paper of Ruzsa and Szemerédi is not the best reference, as they use an early version of Szemerédi regularity lemma, rather than the more convenient modern version. I recommend reading some surveys on the regularity lemma. A good example is one by Komlós and Simonovits.

share|improve this answer

The recent survey paper

D. Conlon and J. Fox, Graph removal lemmas, Surveys in Combinatorics, Cambridge University Press, 2013, 1-50

is on the triangle removal lemma and its various extensions.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.