$\epsilon$-regular pairs

graph theory

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)$:

  • The statement of $(A,B)$'s regularity applies to all $A'\subseteq A$ and $B' \subseteq B$ with $|A'| \ge \epsilon |A|$ and $|B'| \ge \epsilon |B|$. Relative to $C$ and $D$, these subsets would be larger: if $C' \subseteq C$, then to guarantee $|C'|\ge \epsilon |A|$, we need to require $|C'| \ge 3\epsilon |C|$. Similarly, if we choose $D' \subseteq D$, we want $|D'| \ge 3\epsilon |D|$ for the statement of regularity to apply.
  • The statement of regularity says something weaker. For all such $(C',D')$, we have $$|d(C',D') - d(C,D)| \le |d(C',D') - d(A,B)| + |d(A,B) - d(C,D)| \le \epsilon + \epsilon = 2\epsilon.$$ (But there is still some density $d$ such that $d(C',D')$ is within $\epsilon$ of $d$, it's just that we need to change $\epsilon$ to $2\epsilon$ if we want to make $d = d(C,D)$ as in the definition.)

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.

Related Question