Let $G = (V,E)$ be a graph, and let $A,B \subset V$ be two disjoint non-empty sets of vertices, of sizes $a$ and $b$ respectively. Show that in order to check whether or not the pair $(A,B)$ is $\epsilon$-regular, it suffices to check if $|d(X,Y) − d(A,B)| \leq \epsilon$ for every pair $(X,Y)$ with $X \subset A$ of size precisely $\lceil \epsilon a \rceil$ and $Y \subset B$ of size precisely $\lceil \epsilon b \rceil$.
The original definition of $\epsilon$-regularity requires checking all sets $X,Y$ of size greater or equal to $\epsilon a$ and $\epsilon b$, respectively.
Please comment on my attempt below.
I've managed to show that if the graph $G$ has the stated property, then $|d(X^m,Y^n) − d(A,B)| \leq \epsilon$ for every pair $(X^m,Y^n)$ of size $m\lceil \epsilon a \rceil$ and $n\lceil \epsilon b \rceil$ respectively, where $m,n \in \mathbb{Z}^+$, i.e. $\epsilon$-regularity holds for "multiples" of $X$ and $Y$. In my proof for this statement, $d(X^m, Y^n)$ would be expressed as $$d(X^m, Y^n) = \frac{e(X_1,Y_1) + e(X_1, Y_2) + ... + e(X_m,Y_n)}{mn\lceil \epsilon a \rceil\lceil \epsilon b \rceil} = \frac{1}{mn}(d(X_1,Y_1)+d(X_1,Y_2)+...+d(X_m,Y_n)),$$
and so by the pigeonhole principle, if $\epsilon$-regularity doesn't hold for the pair $(X^m,Y^n)$, it would also not hold for one of the densities above.
My idea for the proof of the original problem is again by contradiction, assuming $\epsilon$-regularity doesn't hold for $A' \subset A$, $A' = X_1 \cup X_2 \cup ... \cup X_m \cup X'(= X^m \cup X')$, $|X'| < \lceil \epsilon a \rceil$, and $B' \subset B$, $B' = Y_1 \cup Y_2 \cup ... \cup Y_n \cup Y' (= Y^n \cup Y')$, $|Y'| < \lceil \epsilon b \rceil$. But then at the step where I have to analyze $\frac{e(A',B')}{|A'|\cdot|B'|} = \frac{e(X^m \cup X',Y^n \cup Y')}{|A'|\cdot|B'|}$, there would be a constant factor that does not exist in the previous proof (since now there would be multiple $d(X^m,Y^n)$ in play), and so I can't use the same trick. This is where I got stuck.
The easiest way to apply your trick for "non-multiples" is to do the following: for every $ X\subseteq A$ and $Y \subseteq B$ with $|X| \ge \epsilon|A|$ and $|Y| \ge \epsilon |B|$, average over the $\binom{|X|}{\lceil \epsilon a \rceil} \cdot \binom{|Y|}{\lceil \epsilon b \rceil}$ pairs $(X', Y')$ where:
This is a lot more averaging, but if we're averaging a bunch of densities in the range $[d(A,B) - \epsilon, d(A,B) + \epsilon]$, the result will still be in that range. Moreover, the result of averaging should be exactly $d(X,Y)$, because each edge is counted uniformly: each edge between $X$ and $Y$ affects the density of exactly $\binom{|X|-1}{\lceil \epsilon a \rceil-1} \cdot \binom{|Y|-1}{\lceil \epsilon b \rceil-1}$ terms in the average.
There is also a fairly different argument to make. If we have a pair $(X,Y)$ with $X \subseteq A$ and $Y \subseteq B$, then we can observe that deleting the highest-degree vertex of $X$ (or the highest-degree vertex of $Y$) can only decrease the density (or keep it the same).
We can repeat this process until we're left with a pair $(X',Y')$ such that $|X'| = \lceil \epsilon a \rceil$ and $|Y'| = \lceil \epsilon b \rceil$. Then because the density did not increase at any step, we have $$d(X,Y) \ge d(X',Y') \ge d(A,B) - \epsilon.$$ We can make the same argument, but deleting lowest-degree vertices, to show that $d(X,Y) \le d(A,B)+\epsilon$.