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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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