3
$\begingroup$

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!

$\endgroup$
3
  • 2
    $\begingroup$ This paper of Fox and Lovász discusses a few different versions of the regularity lemma, and why it is preferable to state the lemma one way rather than another: arxiv.org/abs/1403.1768 $\endgroup$ Jan 16, 2016 at 21:18
  • 1
    $\begingroup$ I'll just quote that paper: "A vertex partition of a graph is equitable if any two parts differ in size by at most one. In the statement of the regularity lemma, it is often added that the vertex partition is equitable. There are several good reasons not to add this requirement to the regularity lemma. First, our main result, which gives a lower bound on M(epsilon) whose height is on the same order as the upper bound, does not need this requirement. Second, the proof of the upper bound is cleaner without it.... $\endgroup$ Jan 17, 2016 at 0:24
  • 1
    $\begingroup$ ... Finally, it is further shown in [6] that whether or not an equitable partition is required has a negligible effect on M(epsilon)." [6] cites J Fox, A. Grinshpun, L. M. Lovász, and Y. Zhao, On regularity lemmas and their applications, In preparation. $\endgroup$ Jan 17, 2016 at 0:25

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.