Small subsets inherit sparse \(\varepsilon\)-regularity (Q858679)

Nowadays, even babies know the Szemerédi regularity lemma. Roughly: If \(G\) is a large enough graph, its vertex set can be broken down into a constant number of blocks \(V_{0},\dots V_{k}\) such that most pairs induce so-called \(\varepsilon\)-regular graphs, that is ones where the number of edges between two sets of vertices is close to what it would be if the graph were a random graph of the same density. This fact is, in the context of dense graphs (those which have \(n\) vertices and \(\geq cn^{2}\) edges for some constanc \(c>0\)) used to show that the graph induced by an \(\varepsilon\)-regular pair \((V_{i},V_{j})\) contains every fixed \(k\)-chromatic graph, provided the \(V_{i}\) are sufficiently large and \(\varepsilon\) is sufficiently small relative to the densities of edges between the partition classes: this last fact is called the embedding lemma. It has been known for a long time that the situation becomes harder when the graph is sparse. Crudely speaking, this is because the definition of \(\varepsilon\)-regular is that, for subsets \(A\) and \(B\) we have \[ \left| \frac{e(A,B)}{| A| | B|}-d\right| \leq \varepsilon \] where \(e(A,B)\) denotes the number of edges from \(A\) to \(B\) and \(d\) is the density. The point is that if \(e(G)=o(n^{2})\), this is too easy to get: very often, both terms on the left hand-side will be \(o(1)\) so their difference will indeed be \(o(1)\). Further complications include the fact that there is no sensible embedding lemma here. Thus we need a more sophisticated definition in these cases. This is done by considering bipartite graphs \((V_{1}\cup V_{2},E)\) with density \(d=| E|/| V_{1}| | V_{2}|\) and saying it is \((\varepsilon,p)\)-regular if we have \[ \left| \frac{e(A,B)}{| A| | B|}-d\right| \leq \varepsilon \] so that the old definition of \(\varepsilon\)-regular is equivalent to our new \((\varepsilon,1)\)-regularity. A special case is \((\varepsilon,d)\)-regular, which we call \((\varepsilon)\)-regular (note the brackets, to distinguish it from the old notion of \(\varepsilon\)-regular). If only the lower bound \[ \frac{e(A,B)}{| A| | B|}\geq (1-\varepsilon)p \] holds, we say the graph is \((\varepsilon,p)\)-lower regular. Some unsurprising pseudo-randomness properties of such graphs are then proved: most vertices have the expected, or at least the expected, number of neighbours in any decently large subset, etc. Section 3 pushes this through to the idea of a cover in a bipartite graph \(G=(V_{1}\cup V_{2},E)\): for \(\nu>0\), \(D\geq 0\), \(C\subseteq V_{1}\) is said to be a \((\nu,D)\)-cover if at least \((1-\nu)| V_{2}|\) vertices of \(V_{2}\) have degree at least \((1-\nu)D\) into \(C\). A Lemma (3.3) is used to show that for all \(\beta,\nu>0\) there is \(D=D(\nu)\) and \(\varepsilon_{0}=\varepsilon_{0}(\nu,\beta)\) such that, for all \(0\leq \varepsilon\leq \varepsilon_{0}\) and \(0<p<1\) every \((\varepsilon,p)\)-lower-regular graph \((V_{1}\cup V_{2},E)\) has at least \((1-\beta^{c}){| V_{1}| \choose c}\) sets \(C\subseteq V_{1}\) of size \(c=\lceil D/p\rceil\) that are \((\nu,cp)\)-covers of \(V_{2}\). Similarly \(S\subseteq V_{1}\) is called a \((\nu,D,c)\)-supercover of \(V_{2}\) if every subset of \(S\) of size \(c\) is a \((\nu,D)\)-cover: again it is shown that (given \(\beta,\mu>0\)) there are \(D=D(\nu)\) and \(\varepsilon_{0}=\varepsilon_{0}(\nu,\beta)\) such that, for \(\varepsilon<\varepsilon_{0}\) and \(0<p<1\), every \((\varepsilon,p)\)-lower-regular graph has, for any \(s\leq \nu^{-1}c\), at least \((1-\beta^{s}){| V_{1}| \choose s}\) \((\nu,cp,c)\)-supercovers \(S\subseteq V_{1}\) of \(V_{2}\) of size \(s\). This now leads to the first main result, namely that for \(0<\beta\), \(\varepsilon <1\), there exist \(\varepsilon_{0}=\varepsilon_{0}(\beta,\varepsilon)>0\) and \(C=C(\varepsilon)\) such that for \(0<\varepsilon\leq \varepsilon_{0}\) and \(0<p<1\), every \((\varepsilon,p)\)-lower-regular graph \(G=(V_{1}\cup V_{2},E)\) satisfies that, for \(q\geq Cp^{-1}\), the number of sets \(Q\subseteq V_{1}\) of size \(q\) that form an \((\varepsilon ',p)\)-lower-regular graph with \(V_{2}\) is at least \((1-\beta^{q}){| V_{1}| \choose q}\). In summary, lower-regularity is hereditary. The next aim is to show that regularity is also hereditary, but a complication arises in the proof, namely that some vertices have to be removed from the sets \(Q\subseteq V_{1}\) before one can claim that they typically form a regular pair together with \(V_{2}\). It is subsequently shown that this is not just an accident of the proof, but a genuinely necessary condition. The authors give two applications of their results. The first is a result, mimicking a result for dense graphs in [\textit{V. Rödl} and \textit{R. A. Duke} , Graph Comb. 1, 91--96 (1985; Zbl 0581.05023)] which shows that if a graph has chromatic number \(\geq k\) and so does any graph obtained from it by omitting a proportion at most \(\varepsilon\) of its edges, then there is a small subgraph which witnesses that the chromatic number is at least \(k\). The technical details are in Theorem 4.2. The second application is to enumeration and structure of \(C_{\ell}\)-free graphs. It has long been suspected that if one starts with a fixed graph \(H\) and looks at a graph with \(n| V(H)|\) vertices, all \(n\) above a given vertex \(v\in V(H)\) being an independent set, with an \((\varepsilon)\)-regular graph with \(m\) vertices between two \(n\)-sets whenever the corresponding vertices of \(H\) are adjacent, then only superexponentially few of these graphs have no subgraph isomorphic to \(H\). In Section 5 of the paper under review, the authors give a proof of this fact for the case when \(H\) is a cycle \(C_{\ell}\). This paper is an interesting development of the recent ideas about regularity properties in sparse graphs, and the ideas in it may yet find further applications.