# The most pseudorandom subgraph of a dense graph

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$$?

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.