## Triangle-free Lemma

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?

-

## 4 Answers

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

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-

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.

-
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 2009 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 2009 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 2009 at 20:51

1
@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 2009 at 10:10

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 7, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9345703125, "perplexity_flag": "middle"}