About the regularity of a pair of vertex subset when the density between them is less than epsilon

Question

Given a graph $G=(V,E)$. Let $X, Y\subset V$. Recall that the density of a pair of vertex subsets $(X, Y)$ is defined as $$ d(X,Y)=\frac{e(X,Y)}{|X|Y|}, $$ where $e(X,Y)$ counts the number of edges between $X$ and $Y$.

The following definition is credited to Wikipedia:

We call a pair of parts $\varepsilon$-regular if, whenever you take a large subset of each part, their edge density isn't too far off the edge density of the pair of parts. Formally, for $\varepsilon>0$, a pair of vertex subsets $X$ and $Y$ is called $\varepsilon$-regular, if for all subsets $A \subseteq X, B \subseteq Y$ satisfying $|A| \geq \varepsilon|X|,|B| \geq \varepsilon|Y|$, we have $$ |d(X, Y)-d(A, B)| \leq \varepsilon. $$

My question is that, if $d(X,Y)\leq\varepsilon$, then what can we say about the $\varepsilon$-regularity of $(X,Y)$? Like, is it $\varepsilon$-regular? This is trivially true when $d(X,Y)=0$, and intuitively, this kind of $\varepsilon$-regularity is likely to be 'continuous' in some sense. But I haven't found any proof.

Thanks for your help!

Answer 1

If $d(X,Y)$ is sufficiently small, then $(X,Y)$ is also guaranteed to be $\varepsilon$-regular, but merely knowing $d(X,Y) \le \varepsilon$ is not yet "sufficiently small".

In order for a pair $(A,B)$ with $A \subseteq X$ and $B \subseteq Y$ to be a counterexample to the $\varepsilon$-regularity of $(X,Y)$, three minimum requirements must be met:

• $|A| \ge \varepsilon |X|$;
• $|B| \ge \varepsilon |Y|$;
• $d(A,B) > \varepsilon$. (If $d(X,Y) \le \varepsilon$ and $d(A,B) \le \varepsilon$, then we must have $|d(X,Y) - d(A,B)| \le \varepsilon$, and we don't get a counterexample.)

There are $|A||B|$ potential edges between $A$ and $B$, and we need more than $\varepsilon |A||B|$ of them to be present for this to work out: more than $\varepsilon^3 |X||Y|$ edges.

So if $d(X,Y) \le \varepsilon^3$, we cannot have $\varepsilon^3 |X||Y|$ edges between $A$ and $B$, because there are not $\varepsilon^3 |X||Y|$ edges between $X$ and $Y$. Therefore, any pair with density $\varepsilon^3$ or less is $\varepsilon$-regular.

If $d(X,Y) > \varepsilon^3$ (but still small), then we can cause $\varepsilon$-regularity to fail by picking two sets $A \subseteq X$ and $B \subseteq Y$, then making sure that all edges between $X$ and $Y$ are between $A$ and $B$.

Finally, if $d(X,Y) \ge 1 - \varepsilon^3$, then $(X,Y)$ is once again guaranteed to be $\varepsilon$-regular, because there are not enough missing edges to reduce the density $d(A,B)$, for any $(A,B)$, to be lower than $1-\varepsilon$.