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.
Best Answer
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.