The most pseudorandom subgraph of a dense graph

Question

A bipartite graph $(A,B)$ is $(p, \beta)$-jumbled if for all subsets $A'\subseteq A$ and $B'\subseteq B$ we have that $\left|\mathrm{E}(A',B')-p|A'||B'|\right|\leq \beta \sqrt{|A'||B'|}$. A easy corollary of Szemerédi regularity lemma is that a dense graph (with $\Omega(n^2)$ edges) contains a $\Omega(n)$-sized balanced bipartite graph which is $(p,o(n))$-jumbled, for some $p>0$. In fact, any dense graph can essentially be partitioned into such jumbled bipartite graphs.

My question is the following: Do dense graphs contain jumbled balanced linear sized bipartite graphs with smaller values of $\beta$? Say $\beta=O(n^{1-\varepsilon})$?

In case this is impossible, what about polynomially sized jumbled graphs? That is, let $m=\Omega(n^{\varepsilon})$. Does a dense graph necessarily contain a balanced bipartite graph on $m$ vertices which is $(p,m^{1-\gamma})$-jumbled, for some $p>0$?

Answer 1

The following paper of Peng, Rödl, and Ruciński answers my question as it turns out. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v9i1r1

Applying Theorem 1.3 there with $\varepsilon=\log{n}/d^d$ implies that dense graphs contain polynomially large subgraphs where each $\Omega(n/\log n)$ sized pair of subsets have a positive density of edges between them. This is weaker than the jumbled-ness condition I was defining above, but for most applications, this is sufficient control over the distribution.

On the other hand, Theorem 1.4 shows that this is the best one can hope for.