I've noticed that the name 'Szemeredi's regularity lemma' is used for several closely related yet different statements about graphs. 


Specifically, I'm interested in the distinction between two of them:


**Variant 1** Given $\varepsilon>0$ and $l>0$, there exists an $L=L(\varepsilon,l)$ such that any graph $G$ can be partitioned into sets $V\_1,\ldots,V\_k$ of as-equal-as-you-can-get sizes for some $l\leq k\leq L$, such that at most $\varepsilon {k\choose 2}$ of the pairs $(V\_i,V\_j)$ are not $\varepsilon$-regular.


**Variant 2** As above, except that we have an additional "junk" part $V\_0$ of size $\leq \varepsilon |G|$, and the $V\_i$ have equal sizes. In this case we consider only regular pairs $(V\_i,V\_j)$ for $1\leq i<j\leq k$.


Can anybody with more experience of using the lemma weigh in? Specifically, under what parameters are these two equivalent, and what are the benefits of using one over the other? Cheers!



Variants of Szemeredi's regularity lemma
I think this recent arXiv paper <http://arxiv.org/abs/1604.00733v1> explains precisely the relationship between these two versions of the regularity lemma.


