Do sparse graphs contain regular pairs? An easy corollary of the Szemerédi Regularity Lemma is that dense graphs contain linear sized $\varepsilon$-regular bipartite subgraphs whose density is similar to that of the parent graph. As noted by Tim Gowers in (https://mathoverflow.net/questions/291467/is-there-a-weak-strong-regularity-lemma) there are easier ways of seeing this, with better bounds.
I'm wondering if a meaningful statement with the above flavor holds for sparse graphs, of density $\Omega(n^{-1/t})$. That is, graphs which are dense enough to necessarily contain $K_{t,t}$ subgraphs.
What I'm looking for exactly is a subgraph $(A,B)$ that satisfies $|A|=|B|=k$, $e(A,B)=\Omega(k^{2-1/t})$, and further, $(A,B)$ is $\varepsilon$-regular, in the sense that any subgraph $(A', B')$ with $\varepsilon k$ vertices on each side satisfies $e(A,B)=\Omega(k^{2-1/t})$. Note that this is a lot weaker than the usual notion of $\varepsilon$-regularity in that we allow that the density of a subgraph to be off by a constant factor from the density of the the parent graph, all that we insist on is that they are of the same order of magnitude.
I'm okay with aiming for a sub-linear sized regular pair (i.e. take $k=o(n)$) as the graph itself could be almost entirely filled with isolated vertices, except for a small clique, as Misha says. I would expect one could take $k$ polynomial in $n$, but I'm interested in any range where $k$ grows with $n$.
I'm also okay with assuming that the graph is $K_{10t, 10t}$-free (say), although I cannot tell if there is an easy construction that shows the necessity of such an assumption.
From what I can tell, the sparse versions of Regularity Lemma do not say anything immediately meaningful here, as they do not forbid all edges of the sparse graph being between non-regular pairs.
 A: Well, without ruling out big complete bipartite graphs, one counterexample is the following sparse graph: a complete graph on about $n^{1-1/(2t)}$ vertices, together with enough isolated vertices to bring the total to $n$.
There are plenty of ways to pick a bipartite subgraph with $\epsilon n$ vertices in each part that has the correct density. However, all of these will include a linear number of isolated vertices in each part, so all of them will have linear-sized subgraphs with $0$ edges, and the thing you want cannot hold.
A: Theorem 1.1 here answers (a very close approximation of) my question. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v9i1r1
In the regime where $1/t \ll \varepsilon$, in a graph with density $\Omega(n^{-1/t})$, we may find a subgraph $(A,B)$ with $k$ vertices on each part, where $k\geq n^{1-\gamma}$, and $(A,B)$ is $\varepsilon$-regular, and has density $\Omega(n^{-1/t})$.
The first caveat is that we need $1/t \ll \varepsilon$ to apply this theorem so that $\gamma$ is small. The second is that the density of $(A,B)$ is not $\Omega(k^{-1/t})$, but $\Omega(n^{-1/t})$, hence polynomially smaller than what I asked for. Still, this is a lot of  useful information.
