Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
6  
Order of quantifiers. –  Boris Bukh Nov 28 '09 at 11:17
    
@Boris: oops, our responses crossed –  Yemon Choi Nov 28 '09 at 11:20

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.