Regular pairs in sparse random graphs I

The notion of a quasi-random graph is now established as central in combinatorics. The idea is that such a graph has the properties of a ``typical random graph. It is a well-known observation, going back to e.g. \textit{F. R. K. Chung, R. L. Graham} and \textit{R. M. Wilson} [Combinatorica 9, 345-362 (1989; Zbl 0715.05057)] and \textit{A. G. Thomason} [Lect. Note Ser. 123, 173-195 (1987; Zbl 0672.05068)], that (in the context of mimicking a random graph \(G(n,1/2)\)) many of these ``typical properties are deterministically equivalent, in that any large enough graph having one of them must have the others also. Perhaps the most obvious such ``typical property is that all (not too small) subgraphs have roughly the same density as the overall graph. For notational convenience, let throughout this review \(B=(U,W,E)\) be a bipartite graph with vertex classes \(U\) and \(W\) and edge set \(E\), \(u=|U|\), \(v=|V|\), \(w=|W|\) and \(T=|E|\). If \(U'\subseteq U\) and \(W'\subseteq W\), let \(u'=|U'|\) and \(w'=|W'|\). Then if, for example, \(p\in (0,1)\) is constant and \(B\) is a random bipartite graph with \(u=v=m\) and each possible edge being in \(E\) with probability \(p\) independent of all other edges, this condition is that \(e(U',W')=pu'w'+o(m^{2})\), and the random bipartite graph satisfies this with probability tending to 1 as \(m\rightarrow\infty\). The fundamental nature of this property is made clear by Szemerédi's regularity lemma, a key tool in modern extremal graph theory, which (very crudely) states that any graph can have its vertex set partitioned into a limited number of subsets \(V_{i}\) such that `most' of the bipartite graphs between \(V_{i}\) and \(V_{j}\) have a closely related property called \(\varepsilon\)-regularity. This kind of condition is obviously rather time-consuming to check as there are exponentially many such subgraphs. However it transpires that, in the dense case we have discussed so far, (for any bipartite graph, not just a random one) having this property is equivalent (in roughly the sense indicated in the first paragraph) to the (much easier to check) condition that the degrees \(d(u)\) of vertices \(u\in U\) and codegrees \(d(u,v)\) of pairs \((u,v)\) of distinct vertices in \(U\) (codegree = the number of common neighbours of \(u\) and \(v\)), have the property that the degrees sum up to (asymptotically) their expected value and similarly for the codegrees. The substantial and technically demanding paper under review deals with the question of how far this kind of equivalence can be extended to the case of sparse graphs. In this context, we redefine density by saying that \(B\) is \((\varepsilon,T)\)-regular if whenever \(u'\geq \varepsilon u\) and \(w'\geq \varepsilon w\), we have \[ \left||E(U',W')|- \frac{u'w'T}{uw}\right|\leq \varepsilon \frac{u'w'T}{uw}. \] The naive hope would be that in an \((\varepsilon,T)\)-regular graph, all degrees and codegrees are close to their expected values. This is not, unfortunately, true; the authors use a probabilistic construction to show (Theorem \(\text{A}'\)) that (roughly) given a constant \(\alpha\in (0,1)\) there is a constant \(p\in (0,1)\) such that there exists an \((\varepsilon,T)\)-regular \(B\) with \(u=v=m\) and (roughly) \(pm^{2}\) edges, but all but \(\leq \alpha m^{2}\) pairs \((u,v)\) of vertices in \(U\) have \(d(u,v)=0\). The question then arises as to whether one can salvage a partial result. It turns out (Theorem \(\text{A}\), the core of the paper) that (crudely) the counterexamples in the last paragraph are extremely rare, so if we restrict attention to \((\varepsilon,T)\)-regular bipartite graphs \(B\) \textit{which arise as subgraphs of a} \(G(n,p)\) (for not too small \(p\)) then we do get most codegrees being roughly equal to their expected value. The main idea in the proof (due to Füredi) is that if one wishes to show that for almost all \(G(n,p)\) some property \(S\) holds for all large enough subgraphs, then one can proceed by showing that the family of counterexamples to \(S\) is so small that such rare subgraphs do not occur as subgraphs of \(G(n,p)\). The long and complex detailed proof requires, amongst other tools, a sparse version of the regularity lemma due to the authors (independently), several ingenious and slightly unusual concentration inequalities, and a series of `one-sided neighbourhood lemmas' which show that almost every random graph has the property that any large and dense enough \(\varepsilon\)-regular bipartite subgraph \(H=(U,W,F)\) of it is such that the neighbourhood of almost all vertices \(w\in W\), together with \(W\), induces an \(\varepsilon'\)-regular bipartite subgraph of \(H\); that is, the notion of \(\varepsilon\)-regularity has a strong hereditary flavour. It is natural also to ask (in the converse direction) if there is a local condition (similar to the condition on degrees and codegrees in the dense case) which implies that a (possibly sparse) bipartite graph is \(\varepsilon\)-regular. Such a condition is given in Section 4.2; it depends on the cherries (length 2 paths) in the bipartite graph as well as more obvious `well-behaved degrees and codegrees' conditions. The authors mention several applications of their results to fault tolerance, extremal problems for subgraphs of random graphs and size Ramsey numbers. They also promise a future paper in which an analogue of the embedding lemma (a key tool in the practical use of the regularity lemma in the dense case) will be established for the sparse case using `two-sided neighbourhood lemmas' generalising those mentioned two paragraphs ago.

Recommendations

Cites work

Cited in

(27)

This page was built for publication: Regular pairs in sparse random graphs I

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4419289)