Let $G=(V,E)$ be a (undirected and simplicial) graph and let $A,B\subseteq V$ be two subsets. The density of a pair of subsets $(X,Y)\subseteq A \times B$ is defined as $$d(X,Y):=\frac{|\{\text{edges between X} \text{ and }Y\}|}{|X| |Y|}.$$ The pair $\left(A,B\right)\subseteq V\times V$ is called $\epsilon$-regular if for all $X\subseteq A$, $Y\subseteq B$ the implication $$\left|X\right|\geq\epsilon\left|A\right|\text{ and }\left|Y\right|\geq\epsilon\left|B\right|\qquad\Longrightarrow\qquad\left|d(A,B)-d(X,Y)\right|\leq\epsilon$$ holds, i.e. for all subsets $X$ and $Y$ which are “large” the density of $(A,B)$ and the density of $(X,Y)$ are close to each other.
I want to prove the following statement:
Claim: Let $G=(V,E)$ be a graph and let $A,B\subseteq V$ be two disjoint subsets with $\left|A\right|=\left|B\right|=1000$ and $d\left(A,B\right)=1/2$. Then the pair $(A,B)$ is not $\frac{1}{100}$-regular.
My ideas: If we assume that $(A,B)$ is $\frac{1}{100}$-regular, then the definition implies that for all subsets $X\subseteq A,Y\subseteq B$ of size $10$ the number of edges between $A$ and $B$ is between $49$ and $51$. An idea might then be to partition both sets $A$ and $B$ into subsets of size $10$ and lead this to a contradiction. But I don't see where the contradiction could come from...
Since $\varepsilon$-regular pairs of density $d$ do exist when $n:=|A|=|B|$ is sufficiently large, we should expect the contradiction to use that $n$ is small. The idea is to find a vertex $v_1$ of small degree in $A$, focus on its non-neighbors, find a vertex of small degree to $N(v_1)$, and so on, until we have many vertices in $A$ with all of them not adjacent to many vertices in $B$, producing a contradiction.
Note that if $X \subseteq A$ and $Y \subseteq B$ are of size at least $\varepsilon n$, then the average degree of $X$ to $Y$ is at most $(1/2+\varepsilon)|Y|$. Thus there exists a vertex of $X$ with at least $(1/2-\varepsilon) |Y|$ non-neighbors in $Y$. We use this observation to find six vertices in $A$ and at least $$ (1/2-\varepsilon)^6 n \geq 10 $$ vertices in $B$ which are all not adjacent to each other. Including four more $A$ vertices can only give at most forty edges between two groups of ten vertices each, contradicting the $\varepsilon$-regularity.