$\epsilon$ vs. $n$ in Szemeredi's regularity lemma

Question

In many of the application to Szemeredi's regularity lemma, we use the fact that the number of edges in the graph that does not connect a $\epsilon$-uniform pair is of order $\propto \epsilon n^2$, where $n$ is the number of vertices in the graph, which obey the constraint $n>n_0(\epsilon)$. However, for $\epsilon n^2$ to be arbitrarily small, we need that $\epsilon\rightarrow 0$ faster $n^2\rightarrow\infty$. Is this really the case?

Answer 1

This is definitely not the case. First of all, for any $\epsilon>0$ we pick, we can and often do then apply the regularity lemma to graphs with arbitrarily many vertices $n$, provided $n > n_0(\epsilon)$. Second, if you look at what happens as $\epsilon \to 0$, even $\epsilon n_0^2 \to \infty$.

It also wouldn't make much sense for $\epsilon n^2$ to be arbitrarily small. If the number of "bad edges" were approaching $0$, that would mean it would eventually be $0$, since it's an integer, and that would imply silly things about the structure of all sufficiently large graphs.

Rather, in applications of the regularity lemma, we use the fact that the number of bad edges is $O(\epsilon n^2)$, which we can make an arbitrarily small fraction of the total number of vertex pairs.