vote up 0 vote down
star

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$.

flag
5 
Order of quantifiers. – Boris Bukh Nov 28 at 11:17
@Boris: oops, our responses crossed – Yemon Choi Nov 28 at 11:20

1 Answer

vote up 5 vote down
check

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.

link|flag

Your Answer

Get an OpenID
or

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