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

  • $\begingroup$ How large should $k$ be? Otherwise one can just take an edge. $\endgroup$ Commented Jul 7, 2020 at 10:40
  • $\begingroup$ It's of course only sensible if $k$ grows with $n$. I would expect that one can take $k$ to be polynomial in $n$, the exponent being a constant depending on $t$. $\endgroup$
    – alpmu
    Commented Jul 7, 2020 at 13:06

1 Answer 1


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.


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.