Some preliminary definitions.
Let $G$ be a graph, and let $X,Y\subseteq V(G)$ be sets of vertices in $G$.
Let $$e(X,Y):=\bigl|\{(x,y)\in X\times Y:xy\in E(G)\}\bigr|,$$
and define the edge density between $X$ and $Y$ by
$$d(X,Y):=\frac{e(X,Y)}{|X||Y|}.$$
We call the pair $(X,Y)$ $\epsilon$-regular if, for every $A\subseteq X$ and $B\subseteq Y$ such that $|A|\ge\epsilon|X|$ and $|B|\ge\epsilon|Y|$, we have $$\bigl|d(A,B)-d(X,Y)\bigr|\le\epsilon.$$
Notice that $\epsilon$-regularity holds trivially with this definition for $\epsilon\ge1$, so we only have to consider $\epsilon<1$.
Question. How do I prove that regularity is inherited? More precisely, if $(X,Y)$ is an $\epsilon\eta$-regular pair, then I want to show that $(X',Y')$ is $\epsilon$-regular for all $X'\subseteq X$ and $Y'\subseteq Y$ with $|X'|\ge\eta|X|$ and $|Y'|\ge\eta|Y|$.
What I’ve tried. It is easy to prove this when $\eta<1/2$, since we can use $\epsilon\eta$-regularity to show that
$$\bigl|d(X',Y')-d(X,Y)\bigr|\le\epsilon\eta
\quad\text{and}\quad
\bigl|d(X'',Y'')-d(X,Y)\bigr|\le\epsilon\eta;$$
here $X''\subseteq X'$ and $Y''\subseteq Y'$ with $|X''|\ge\epsilon|X'|$ and $|Y''|\ge\epsilon|Y'|$. Also, when $\eta\approx1$, then $X'$ and $Y'$ constitute large portions of $X$ and $Y$, so the densities of $(X,Y)$ and $(X',Y')$ should be similar. We can compute
$$d(X,Y)
=\frac{e(X,Y)}{|X||Y|}
\le\frac{e(X',Y')+(1-\eta)^2|X||Y|}{|X||Y|}
\le d(X',Y')+(1-\eta)^2$$
and
$$d(X',Y')
=\frac{e(X',Y')}{|X'||Y'|}
\le\frac{e(X,Y)}{\eta^2|X||Y|}
=d(X,Y)+\Bigl(\frac{1}{\eta^2}-1\Bigr)d(X,Y),$$
but I'm not sure what to do from here.
How should I approach this problem when $1/2<\eta<1$? Thank you.
Best Answer
I think there is a counterexample
For simplicity consider the graph is weighted, that is, every edge can be any rational between -1 and 1.
Let $\eta=1/\sqrt2$.the $\eta\times\eta$ part on the left up side is $+\epsilon\eta$, and rest part is $-\epsilon\eta$.
Then let the $\epsilon\eta\times\epsilon\eta$ part of the left up side be $-\epsilon\eta$.