# Definitions of $\epsilon$-regular partition

I am wondering about the equivalence between two definitions of an $$\epsilon$$-regular partition of a graph.

First of all, if $$G$$ is a graph and $$A$$ and $$B$$ are subsets of its vertex set, the density of edges between $$A$$ and $$B$$ is defined as $$d(A,B)=\frac{|E(A,B)|}{|A||B|},$$ where $$|E(A,B)|$$ is the number of edges between $$A$$ and $$B$$.

Given some $$\epsilon>0$$, the pair $$(A,B)$$ is said to be $$\epsilon$$-regular if, for every $$A'\subseteq A$$ and $$B'\subseteq B$$ with $$|A'|\geq \epsilon |A|$$ and $$|B'|\geq \epsilon |B|$$, we have that $$|d(A',B')-d(A,B)|\leq \epsilon.$$

Now, what we want to do next is to define what it means for a partition of the vertex set to be $$\epsilon$$-regular, and I have found two different definitions (from different sources).

Definition 1. Given a graph $$G$$ on $$n$$ vertices and an $$\epsilon>0$$, a partition $$\{X_1, \dots, X_k\}$$ of its vertex set is $$\epsilon$$-regular if $$\sum \frac{|X_i||X_j|}{n^2} \leq \epsilon,$$ where the sum is taken over all pairs $$(X_i,X_j)$$ which are not $$\epsilon$$-regular.

Definition 2. Given a graph $$G$$ on $$n$$ vertices and an $$\epsilon>0$$, a partition $$\{V_0, V_1, \dots, V_k\}$$ of its vertex set $$V$$ is $$\epsilon$$-regular if:

• $$|V_0|\leq \epsilon |V|$$
• $$|V_1| = \dots = |V_k|$$
• at most $$\epsilon\binom{k}{2}$$ pairs $$(V_i,V_j)$$ are not $$\epsilon$$-regular.

I am assuming that these definitions are equivalent, and they are both used in various different sources in order to prove Szemeredi's regularity lemma, but I cannot see if that is indeed true.

Can anyone help?

Any help is much appreciated.

It is easy to check that for each $$\epsilon>0$$ each graph, which is $$\epsilon$$-regular according to Definition 2 is $$\epsilon$$-regular according to Definition 1. But not conversely, because according to Definition 1, any partition of any finite graph is $$1$$-regular, whereas Definition 2 imposes additional restrictions on the sizes of partition members.