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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .