Counting lemmas and graph removal

Suppose A, B, and C are disjoint nonempty sets and each of their three pairs is epsilon-regular, with each density at least twice epsilon. All but at most epsilon times |A| vertices have at least density-minus-epsilon times |B| neighbors in B. Otherwise that exceptional subset and all of B would witness irregularity. The same assertion holds for C, so at least a one-minus-two-epsilon fraction of A is good for both neighbor sets.

For a good vertex, its B-neighborhood and C-neighborhood both satisfy the size thresholds needed to apply regularity of the pair B,C. Their crossing edge density is at least d(B,C) minus epsilon, so many choices close a triangle. Multiplying these three density-minus-epsilon factors and summing over good A vertices gives the displayed bound. Each triangle using one vertex from each declared part is counted once. The assumption that the densities dominate epsilon is essential to keep the neighborhoods above the regularity threshold.

The triangle removal lemma says that for every positive deletion tolerance eta there exists a positive delta such that any n-vertex graph with at most delta n cubed triangles can be made triangle-free by deleting at most eta n squared edges. The small copy tolerance is chosen in response to the desired edit tolerance. It is not an assertion that delta equals eta, nor that one can delete a number of edges proportional to the observed triangle count with a uniform constant.

For a fixed graph H the analogous statement uses at most delta n to the v(H) copies and permits eta n squared edge deletions. Ordinary copies and induced copies require different statements: deleting edges cannot create an ordinary H, but it can create an induced H by removing an unwanted edge. The ordinary removal lemma therefore does not directly establish induced removal. A graph with few copies can still contain some; the conclusion concerns the existence of a nearby pattern-free graph, not that the original was already free.

Choose eta first. Next choose a density threshold much smaller than eta, a regularity accuracy sufficiently smaller than that threshold, and a sufficiently large minimum partition size. The regularity lemma then supplies a bounded maximum number M of parts. Delete edges touching exceptional vertices, lying inside parts, crossing irregular pairs, or crossing pairs below the density threshold. With the choices made in that order, the total deletions fit the eta budget. This describes a proof architecture rather than every constant in its bookkeeping.

If a triangle survived, its three parts would form regular dense pairs. The counting lemma would then force at least a fixed constant times (n/M) cubed original triangles. Choose delta still smaller than that guaranteed coefficient, after M has been determined, to contradict the assumed small count. A sufficiently large host order handles rounding; finitely many smaller cases can be absorbed by decreasing delta. Reversing this order by choosing delta before the partition bound would leave the contradiction unjustified.