9
$\begingroup$

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?

Improve this question
$\endgroup$

5 Answers 5

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
9
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Boris Bukh
    Nov 26, 2009 at 12:09
  • $\begingroup$ @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... :) $\endgroup$
    – Harrison Brown
    Nov 26, 2009 at 18:07
  • $\begingroup$ @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? $\endgroup$
    – Kevin O'Bryant
    Nov 26, 2009 at 20:51
  • 2
    $\begingroup$ @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/… $\endgroup$
    – Boris Bukh
    Nov 27, 2009 at 10:10
9
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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