Suppose $G$ is a graph and $A,B$ are subsets of its vertex set. Given some $\epsilon >0$, the pair $(A,B)$ is called $\epsilon$-regular if for every $A'\subseteq A$ and $B'\subseteq B$ such that $|A'|\geqslant \epsilon |A|$ and $|B'| \geqslant \epsilon |B|$, we have that
$$|d(A',B')-d(A,B)| \leqslant \epsilon,$$
where $d(A,B)$ is defined as
$$d(A,B) = \frac{|E(A,B)|}{|A||B|}.$$
(We denote by $|E(A,B)|$ the number of edges between the vertex sets $A$ and $B$.)
My question is, is $\epsilon$-regularity preserved when taking subsets? That is, if the pair $(A,B)$ is $\epsilon$-regular and $C\subseteq A$, $D\subseteq B$, can we conclude that the pair $(C,D)$ is also $\epsilon$-regular (for the same value of $\epsilon$)?
Best Answer
When taking subsets, $\epsilon$-regularity is not preserved for the same $\epsilon$, but you can recover some sort of regularity statement if the subsets are large enough.
Say we choose $C \subseteq A$ and $D \subseteq B$ with $|C| \ge \frac13|A|$ and $|D| \ge \frac13|B|$. There are two things that change for the pair $(C,D)$:
So in this case, we can say that $(C,D)$ is a $3\epsilon$-regular pair.
In general, we can say that $(C,D)$ is a $\max\left\{2\epsilon, \frac{|A|}{|C|}\epsilon, \frac{|B|}{|D|}\epsilon\right\}$-regular pair by a similar argument.