Counting Lemma Clause Samples

Counting Lemma. In this section we state the graph counting lemma for the special case of triangles for ε-regularity introduced by Szemerédi. Roughly speaking it says that a sufficiently ε-regular tripartite graph contains approximately as many triangles as one would expect in a random graph with the corresponding den- sity. Gowers formally showed in [14] a graph counting lemma for quasiran- dom graphs but due to the equivalence of ε-regularity and ε-quasirandomness discussed earlier we may simply apply the well-known graph counting lemma for ε-regular graphs although we consider ε-quasirandom graphs.