I am struggling to understand how we apply Szemeredi's regularity lemma (SRL) for other results like the graph building (counting) lemma and removal lemmas. The statement of SRL is:
Let $\epsilon>0$ and $l\in \mathbb{N}$. Then $\exists L(\epsilon,l)$ such that for any graph $G$ such that $|G|=n\geq l$, $\exists m, \ l\leq m \leq L$ so that G has an $\epsilon$ uniform equipartition into $m$ parts.
Now an $\epsilon$ uniform equipartition $V_1,...,V_r$ is one which has $\leq \epsilon {r \choose 2}$ not $\epsilon$ uniform pairs $(V_i,V_j)$.
Notice that this definition says nothing about $G$ having some minimal edge density. I have also looked at the proof of SRL using the energy increment argument. Nothing about that proof struck me as requiring G to have many edges.
However some bounded edge density is clearly needed for application to the counting/building lemma below:
Let H be a graph with $\Delta (H) = d$, and which has a r colouring so that no colour is used more than s times. Then if a graph G consists of vertex classes $V1_,...,V_r$ with $|V_i|=n$ such that each pair is $\epsilon$ uniform and has a mutual density $d(V_i,jV)_\geq am\lambda$.
Then if $\lambda ^d \geq \epsilon (d+1)$ and $s\leq \lceil \epsilon n \rceil$, then G contains a copy f H.
Now the point I am struggling with, which is required for the counting lemma to apply, is ensuring that we have sufficiently many mutually $\epsilon$ uniform and sufficiently large density $d$ parts. Clearly, the only thing which we can control in Szemeredi's lemma is the smallest number of parts $l$, if we fix $\epsilon$. We are allowed to always take $n$ to be large enough for everything to work.
Working backwards, if we take an $k$ partition and we join any two vertex clusters by an edge of they are both mutually $\epsilon$ uniform and have a mutual edge density $\geq \lambda$ , then by Erdos Stone having at least $(1-\frac{1}{r-1}+\delta){k \choose 2}$ edges (for any $\delta$ if we make $k$ large enough) contains a $K_{r}$.
This is precisely what we need: r mutually $\epsilon$ uniform and $\geq \lambda$ density pairs. But of course to achieve $\epsilon$ uniformity, we need to make sufficiently many partitions. The only guarantee of how many pairs of parts have a mutual degree at least $\lambda$, is that when we start the proof we have an initial partition on $t \geq l $ parts. And we can choose this partition to have all pairs at least $\lambda$ density. Then we always have at least $t\choose 2$ pairs of $\geq \lambda$ density as we repartition. But this does not grow with n as would be required.
So it just seems that to use the counting/building lemma as stated, we need G to have a minimal edge density depending on $r,s,d$ to then apply Szemeredi?
An explanation or link to discussion about this would be useful. At the moment it just seems incredibly circular to me, or that some important assumptions are simply not being stated.
(P.S. In my reading I have come across papers on 'Szemeredi's lemma for sparse graphs'. I will link when I can but my internet is barely coping with a single web page at the moment. However it seemed that 'sparse graphs' in these papers meant that the graph we were trying to embed, H was sparse. And seeing if we can do better than the embedding lemma for such graphs.)
Sorry, this question is really confusing and hard to understand. Maybe try to work out a precise and concrete question? Maybe this helps you: Suppose you have a pair $(V_i, V_j)$ with $|V_i|=|V_j|=n$ with density $d(V_i, V_j) \rightarrow 0$ for $n \rightarrow \infty$. Then by the definition of $\epsilon$-regularity it is easy to see that this pair will be $\epsilon$-regular for all $n$ big enough. Therefore, in a family of non-dense graphs, basically any partition into parts of (almost) equal size is $\epsilon$-regular for $n$ big enough, and Szemeredi's regularity lemma is true, but it won't help you very much in proving anything else, because the statement is trivial.