MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Theorem: (SRL) For every $\epsilon>0$ and integer $m\geq 1$ there is an $M$ such that every graph $G$, with $|G|\geq m$ has an $\epsilon$-regular partition $V(G)=V_0\cup\ldots\cup V_k$ for some $m\leq k\leq M$.

Can someone explain to me why this statement is not trivial? For instance, what stops me choosing $M$ larger than $|G|$ and picking $k=|G|$, so I can split $G$ up into singletons, which is trivally $\epsilon$-regular for any $\epsilon>0$.

share|cite|improve this question
Order of quantifiers. – Boris Bukh Nov 28 '09 at 11:17
@Boris: oops, our responses crossed – Yemon Choi Nov 28 '09 at 11:20
up vote 5 down vote accepted

Quantifier error. You have to fix your M before you are given a graph G; whereas your approach would require one to have the graph G at hand, before choosing M.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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