# Do sparse graphs contain a single regular pair?

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.

• How large should $k$ be? Otherwise one can just take an edge. Jul 7, 2020 at 10:40
• 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$. Jul 7, 2020 at 13:06

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.