Pseudo-random graphs.

*(English)*Zbl 1098.05075
Győri, Ervin (ed.) et al., More sets, graphs and numbers. A salute to Vera Sós and András Hajnal. Berlin: Springer. Budapest: János Bolyai Mathematical Society (ISBN 3-540-32377-5/hbk). Bolyai Society Mathematical Studies 15, 199-262 (2006).

This important paper (mainly a survey: many of the results are due to one or both of the authors, often with co-workers) is a substantial contribution to the theory of pseudo-random graphs. These are, very roughly, particular graphs \(G=(V,E)\) which behave similarly to an Erdős-Rényi random graph \(G(n,p)\) where \(n=| V|\) and \(p=| E|/{n\choose 2}\). This subject started in the 1980s when Thomason published two key articles [A. Thomason, Random graphs ’85, Lect. 2nd Int. Semin., Poznan/Pol. 1985, Ann. Discrete Math. 33, 307–331 (1987; Zbl 0632.05045), and Surveys in combinatorics 1987, Pap. 11th Br. Combin. Conf., London/Engl. 1987, Lond. Math. Soc. Lect. Note Ser. 123, 173-195 (1987; Zbl 0672.05068)] where one precise form of this idea, the so-called \((p,\alpha)\)-jumbled graphs, were introduced. The definition is that, for any \(U\subseteq V(G)\), we have

\[ \left| e(U)-p{u\choose 2}\right| \leq \alpha u. \]

Here \(e(U)\) is the number of edges in the subgraph induced by \(U\): so \(\alpha\) is controlling how close to the ‘expected value\' \(p{u\choose 2}\) this number is. Crudely, the smaller \(\alpha\) the more like a random graph the graph is. We usually consider a family of such graphs for various \(n\) and consider how \(\alpha\) grows with \(n\): for example, a (typical) random graph \(G(n,p)\) with \(0<p<1\) constant, say, is \((p,\alpha)\)-jumbled for \(\alpha=C\sqrt{n}\) for some constant \(C\), and this \(\alpha\) can be shown to be within a constant multiple of the best possible. Another key step in the evolution of the subject was the paper [F. R. K. Chung, R. L. Graham and R. M. Wilson, “Quasi-random graphs”, Combinatorica 9, 345–362 (1989; Zbl 0715.05057)]. Here a number of properties, all of which would hold for a typical random graph as above, were shown to be equivalent to each other (and a graph satisfying any (all) of them was defined to be quasi-random): for example, having (roughly) the expected number of \(4\)-cycles as subgraphs is (perhaps surprisingly) equivalent to having (roughly) the expected number of copies of any fixed graph as subgraphs.

The main aim of the paper under review is to discuss the properties of a new notion of pseudo-random graphs, based on graph eigenvalues. Formally, following N. Alon, an \((n,d,\lambda)\)-graph is defined to be a graph on \(n\) vertices, which is \(d\)-regular, and for which, if \(\lambda_{1}\geq \lambda_{2}\geq \cdots \geq \lambda_{n}\) is the spectrum of the adjacency matrix \(A=A(G)\), we have \(\lambda=\max_{2\leq i\leq d}| \lambda_{i}|\). (Note that as \(G\) is \(d\)-regular, \(\lambda_{1}=d\) automatically, and if \(G\) is connected (as is usually true) the other eigenvalues will be smaller in modulus by Perron-Frobenius.) A short argument then shows a key result linking spectral properties and edge distribution: in particular, this implies that an \((n,d,\lambda)\)-graph is also \((d/n,\lambda)\)-jumbled, so \(\lambda\) is again a quantity measuring how close to random the graph is, with small values of \(\alpha\) suggesting very random-like graphs. Crudely speaking, the advantages of the new approach include that the machinery of spectral graph theory can be applied, and that since of course eigenvalues can be computed quickly, it is algorithmically appealing. A limitation is that the results (at least) need further work if they are to be generalised to pseudo-random graphs which are irregular.

Results, for an \((n,d,\lambda)\)-graph \(G\) include: a proof that the vertex connectivity is (at least for large \(d\)) not much less than the (common, and hence minimum) degree \(d\) (Theorem 4.1); a (very mild) condition \(d-\lambda\geq 2\) giving that the graph is \(d\)-edge connected (and has a perfect matching if \(n\) is even) (Theorem 4.3); an upper bound on the size of the largest cut in the graph (i.e. \(\max_{S\subseteq V(G)}e(S,V\backslash S)\) where \(e(A,B)\) denotes the number of edges from \(A\) to \(B\)) (Proposition 4.4); upper and lower bounds (some distance apart in general) on the independence number of \(G\) (Propositions 4.5 and 4.6); an upper bound on the chromatic number \(\chi(G)\) (Theorem 4.8); a similar upper bound on the choice number of such graphs, at least for largish \(d\) (Theorem 4.9); a result of Alon to the effect that every large subset of \(V(G)\) contains roughly the expected number of copies of any fixed graph \(H\) (Theorem 4.10) and some extensions for particular \(H\); a condition on \(\lambda\) guaranteeing that the largest number of edges in a \(K_{t}\)-free subgraph of \(G\) is \((1+o(1))\frac{t-2}{t-1}| E(G)|\) (Theorem 4.13) (this is as one might naively hope by analogy with Turán’s theorem, though of course there is a non-trivial statement to prove); a proof that, if \(H\) is a fixed graph on \(h\) vertices then, under mild conditions on \(d\) and \(\lambda\), if \(h| n\) \(G\) contains \(n/h\) copies of \(H\) (Corollary 4.15 - again more can be said in particular cases, e.g. \(H\) a triangle); a result saying that if \(\lambda\) is suitably small compared with \(d\), \(G\) is Hamiltonian (Theorem 4.20). Also addressed are questions about random subgraphs \(G_{p}\) of the \((n,d,\lambda)\)-graph \(G\), formed by retaining each edge of \(G\) with probability \(p=p(n)\): for example, it is found (Theorem 4.23) that \(p^{*}(n)=\frac{1}{d}(\log(n)+\log\log(n))\) is a (sharp) threshold for Hamiltonicity in that if, for some function \(\omega(n)\) tending to infinity with \(n\), we have \(p(n)-p^{*}(n)=\omega(n)/d\), then \(G_{p}\) is Hamiltonian with probability tending to 1, but if \(p(n)-p^{*}(n)=-\omega(n)/d\), then with probability tending to 1 it is not Hamiltonian. Similar results about component sizes of \(G(p)\) are stated (Theorem 4.24): again they extend, provided \(\lambda=o(d)\), the known results for component sizes in random graphs. Also discussed are sharpness of thresholds: the weight of a minimum spanning tree when independent random weights are attached to individual edges (Theorem 4.27); and enumerative aspects, such as estimating the number of maximum matchings (Theorem 4.29) and Hamilton cycles (Theorem 4.30).

Much remains open: in particular, many of the results only really work for \(d\) at least reasonably large compared with \(n\). When the graph is sparse, the picture is more complicated: for example, there are graphs which are pseudo-random on any reasonable measure but do not have (anything like) the expected number of copies of some particular graphs. A recent paper [F. R. K. Chung and R. L. Graham, Combinatorica 22, 217–244 (2002; Zbl 0997.05090)] shows that obvious analogues of the equivalent conditions in the Quasi-random graphs paper are not in general equivalent when the graphs are sparse (this point has been reinforced by the authors, and by B. Bollobás and V. Nikiforov). Indeed some of the equivalent properties are hard to find meaningful analogues of. There is much still to be said in this area.

This paper has taken a fair time to fight its way through the refereeing process: let us briefly mention some very recent related work. Work has started on generalising the results to pseudo-random graphs with slightly unequal degrees: see, for example, http://www.inf.ethz.ch/personal/zuphilip/main.pdf or

http:///www.ucsd.edu/ fan/wp/smallgap.pdf.

The work on Turán properties for pseudo-random graphs has been generalised considerably in

http://www2.informatik.hu-berlin.de/ schacht/pub/preprints/turan/underscore

pseudo.pdf.

For the entire collection see [Zbl 1086.05003].

\[ \left| e(U)-p{u\choose 2}\right| \leq \alpha u. \]

Here \(e(U)\) is the number of edges in the subgraph induced by \(U\): so \(\alpha\) is controlling how close to the ‘expected value\' \(p{u\choose 2}\) this number is. Crudely, the smaller \(\alpha\) the more like a random graph the graph is. We usually consider a family of such graphs for various \(n\) and consider how \(\alpha\) grows with \(n\): for example, a (typical) random graph \(G(n,p)\) with \(0<p<1\) constant, say, is \((p,\alpha)\)-jumbled for \(\alpha=C\sqrt{n}\) for some constant \(C\), and this \(\alpha\) can be shown to be within a constant multiple of the best possible. Another key step in the evolution of the subject was the paper [F. R. K. Chung, R. L. Graham and R. M. Wilson, “Quasi-random graphs”, Combinatorica 9, 345–362 (1989; Zbl 0715.05057)]. Here a number of properties, all of which would hold for a typical random graph as above, were shown to be equivalent to each other (and a graph satisfying any (all) of them was defined to be quasi-random): for example, having (roughly) the expected number of \(4\)-cycles as subgraphs is (perhaps surprisingly) equivalent to having (roughly) the expected number of copies of any fixed graph as subgraphs.

The main aim of the paper under review is to discuss the properties of a new notion of pseudo-random graphs, based on graph eigenvalues. Formally, following N. Alon, an \((n,d,\lambda)\)-graph is defined to be a graph on \(n\) vertices, which is \(d\)-regular, and for which, if \(\lambda_{1}\geq \lambda_{2}\geq \cdots \geq \lambda_{n}\) is the spectrum of the adjacency matrix \(A=A(G)\), we have \(\lambda=\max_{2\leq i\leq d}| \lambda_{i}|\). (Note that as \(G\) is \(d\)-regular, \(\lambda_{1}=d\) automatically, and if \(G\) is connected (as is usually true) the other eigenvalues will be smaller in modulus by Perron-Frobenius.) A short argument then shows a key result linking spectral properties and edge distribution: in particular, this implies that an \((n,d,\lambda)\)-graph is also \((d/n,\lambda)\)-jumbled, so \(\lambda\) is again a quantity measuring how close to random the graph is, with small values of \(\alpha\) suggesting very random-like graphs. Crudely speaking, the advantages of the new approach include that the machinery of spectral graph theory can be applied, and that since of course eigenvalues can be computed quickly, it is algorithmically appealing. A limitation is that the results (at least) need further work if they are to be generalised to pseudo-random graphs which are irregular.

Results, for an \((n,d,\lambda)\)-graph \(G\) include: a proof that the vertex connectivity is (at least for large \(d\)) not much less than the (common, and hence minimum) degree \(d\) (Theorem 4.1); a (very mild) condition \(d-\lambda\geq 2\) giving that the graph is \(d\)-edge connected (and has a perfect matching if \(n\) is even) (Theorem 4.3); an upper bound on the size of the largest cut in the graph (i.e. \(\max_{S\subseteq V(G)}e(S,V\backslash S)\) where \(e(A,B)\) denotes the number of edges from \(A\) to \(B\)) (Proposition 4.4); upper and lower bounds (some distance apart in general) on the independence number of \(G\) (Propositions 4.5 and 4.6); an upper bound on the chromatic number \(\chi(G)\) (Theorem 4.8); a similar upper bound on the choice number of such graphs, at least for largish \(d\) (Theorem 4.9); a result of Alon to the effect that every large subset of \(V(G)\) contains roughly the expected number of copies of any fixed graph \(H\) (Theorem 4.10) and some extensions for particular \(H\); a condition on \(\lambda\) guaranteeing that the largest number of edges in a \(K_{t}\)-free subgraph of \(G\) is \((1+o(1))\frac{t-2}{t-1}| E(G)|\) (Theorem 4.13) (this is as one might naively hope by analogy with Turán’s theorem, though of course there is a non-trivial statement to prove); a proof that, if \(H\) is a fixed graph on \(h\) vertices then, under mild conditions on \(d\) and \(\lambda\), if \(h| n\) \(G\) contains \(n/h\) copies of \(H\) (Corollary 4.15 - again more can be said in particular cases, e.g. \(H\) a triangle); a result saying that if \(\lambda\) is suitably small compared with \(d\), \(G\) is Hamiltonian (Theorem 4.20). Also addressed are questions about random subgraphs \(G_{p}\) of the \((n,d,\lambda)\)-graph \(G\), formed by retaining each edge of \(G\) with probability \(p=p(n)\): for example, it is found (Theorem 4.23) that \(p^{*}(n)=\frac{1}{d}(\log(n)+\log\log(n))\) is a (sharp) threshold for Hamiltonicity in that if, for some function \(\omega(n)\) tending to infinity with \(n\), we have \(p(n)-p^{*}(n)=\omega(n)/d\), then \(G_{p}\) is Hamiltonian with probability tending to 1, but if \(p(n)-p^{*}(n)=-\omega(n)/d\), then with probability tending to 1 it is not Hamiltonian. Similar results about component sizes of \(G(p)\) are stated (Theorem 4.24): again they extend, provided \(\lambda=o(d)\), the known results for component sizes in random graphs. Also discussed are sharpness of thresholds: the weight of a minimum spanning tree when independent random weights are attached to individual edges (Theorem 4.27); and enumerative aspects, such as estimating the number of maximum matchings (Theorem 4.29) and Hamilton cycles (Theorem 4.30).

Much remains open: in particular, many of the results only really work for \(d\) at least reasonably large compared with \(n\). When the graph is sparse, the picture is more complicated: for example, there are graphs which are pseudo-random on any reasonable measure but do not have (anything like) the expected number of copies of some particular graphs. A recent paper [F. R. K. Chung and R. L. Graham, Combinatorica 22, 217–244 (2002; Zbl 0997.05090)] shows that obvious analogues of the equivalent conditions in the Quasi-random graphs paper are not in general equivalent when the graphs are sparse (this point has been reinforced by the authors, and by B. Bollobás and V. Nikiforov). Indeed some of the equivalent properties are hard to find meaningful analogues of. There is much still to be said in this area.

This paper has taken a fair time to fight its way through the refereeing process: let us briefly mention some very recent related work. Work has started on generalising the results to pseudo-random graphs with slightly unequal degrees: see, for example, http://www.inf.ethz.ch/personal/zuphilip/main.pdf or

http:///www.ucsd.edu/ fan/wp/smallgap.pdf.

The work on Turán properties for pseudo-random graphs has been generalised considerably in

http://www2.informatik.hu-berlin.de/ schacht/pub/preprints/turan/underscore

pseudo.pdf.

For the entire collection see [Zbl 1086.05003].

Reviewer: David B. Penman (Colchester)

##### MSC:

05C80 | Random graphs (graph-theoretic aspects) |

05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |