Suppose $G$ is a bipartite graph with bipartition $(A,B)$ with $|A|=|B|=n$, show that if the maximum degree of $G$ is at most $\epsilon^2n$ then the pair $(A,B)$ is $\epsilon$-regular.
So here’s my thought process:
Let $A’\subseteq A$ and $B’\subseteq B$ with $|A’|\geq\epsilon |A|$ and $|B’|\geq\epsilon |B|$. Now I need to show that $|d(A,B)-d(A’,B’)|<\epsilon$.
I have $d(A,B)-d(A’,B’)=\frac{||G||}{n^2}-\frac{||A’,B’||}{|A’||B’|}\leq\frac{||G||}{n^2}-\frac{||A’,B’||}{\epsilon^2n^2}$. I don’t know if I should say $||G||\leq\epsilon^2n^2$ based on the degree condition, and therefore I have $d(A,B)-d(A’,B’)\leq\epsilon^2-\frac{||A’,B’||}{\epsilon^2n^2}$. But even then, I’m not sure how to proceed from there.
Any help would be appreciated!
First, you aren't being very careful: $d(A', B') = \frac{\|A', B'\|}{|A'| |B'|}$, which is not necessarily the same as $\frac{\|A',B'\|}{\epsilon^2 n^2}$. It's true that $\frac{\|A',B'\|}{\epsilon^2 n^2}$ is an upper bound, but it's not one we want to use at this stage, because $\|A',B'\|$ can be much larger when $A'$ and $B'$ are closer to $n$ than $\epsilon n$ in size.
Second, in order to bound $\frac{\|A', B'\|}{|A'| |B'|}$: every vertex in $A'$ has at most $\epsilon^2 n$ neighbors; in particular, at most $\epsilon^2 n$ neighbors in $B'$. Therefore $\|A', B'\| \le \epsilon^2 n |A'|$.
You should be able to use this to show that $d(A', B') \le \epsilon$, and conclude $|d(A,B) - d(A',B')| \le \epsilon$ from there.