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


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.