Elementary number theory, group theory and Ramanujan graphs.

*(English)*Zbl 1032.11001
London Mathematical Society Student Texts. 55. Cambridge: Cambridge University Press. 144 p. (2003).

Let \(X= (V,E)\) be an (undirected) graph with set of vertices \(V\) and set of edges \(E\). For \(F\subset V\) the boundary \(\partial F\) is the set of edges connecting a vertex from \(F\) to a vertex in \(V\setminus F\). The expanding constant \(h(X)\) is defined to be the infimum of all quotients \(|\partial F|/ \min(|F|,|V\setminus F|)\), where \(F\) runs over all nonempty finite subsets of \(X\). If \(h(X)\) is large the graph \(X\) symbolizes a network in which information propagates well. Hence a family of (finite, connected, \(k\)-regular) graphs \(X_m= (V_m,E_m)\) \((m\in \mathbb{N})\) is called a family of expanders if \(|V_m|\rightarrow \infty\) for \(m\rightarrow \infty\) and if there exists some \(\varepsilon>0\) such that \(h(X_m)\geq \varepsilon\) for all \(m\geq 1\). The book under review deals with the solution of the following

Main Problem: Give explicit constructions for families of expanders.

This problem is solved by appealing to the adjacency matrix \(A\) of \(X\). If \(X\) is \(k\)-regular on \(n\) vertices, the matrix \(A\) has \(n\) eigenvalues \[ k= \mu_0\geq \mu_1\geq\cdots\geq \mu_{n-1}\geq -k \] (repeated according to multiplicities). It turns out that the expanding constant can be estimated spectrally from above and from below, and rephrasing the Main Problem in terms of the spectrum, one has to construct \(X_m\) such that the spectral gap \(k- \mu_1(X_m)\) is as large as possible. This will yield a family of good expanders. However, the spectral gap cannot be too large since it can be shown that \[ \liminf_{m\rightarrow \infty} \mu_1(X_m)\geq 2\sqrt{k-1}. \] This leads to the notion of Ramanujan graph: A finite connected \(k\)-regular graph \(X\) is a Ramanujan graph if, for every eigenvalue \(\mu\neq \pm k\) of its adjacency matrix one has \(|\mu|\leq 2\sqrt{k-1}\).

The purpose of the book under review is to describe the Ramanujan graphs of A. Lubotzky, R. Phillips and P. Sarnak [Combinatorica 8, 261-277 (1988; Zbl 0661.05035)] and of G. A. Margulis [Probl. Inf. Transm. 24, No. 1, 39-46 (1988; Zbl 0708.05030)]. While the description of these graphs is elementary, the proof that they have the desired properties is not. It is the authors’ aim here to give elementary proofs of most of the properties enjoyed by these graphs, and the authors achieve this aim admirably. Moreover they deal with the problem of the construction of finite graphs with large girth and large chromatic number.

We briefly indicate the contents of the various chapters. Chapter 1 treats the relevant graph theory. It deals with the adjacency matrix and its spectrum, inequalities on the spectral gap and asymptotic behaviour of eigenvalues in families of expanders. One section is addressed to the existence of graphs with large girth and large chromatic number (probabilistic method due to Erdős).

Chapter 2 deals with some relevant number theory. Topics covered include sums of two squares, quadratic reciprocity, sums of four squares and arithmetic of integer quaternions (following Dickson). The properties of the graphs \(X^{p,q}\) to be constructed in Chapter 4 depend heavily on some structural properties of the groups \(\text{PSL}_2 (q)\). These are developed in Chapter 3; topics include simplicity, structure of subgroups, a concise introduction to the representation theory of finite groups, and Frobenius’ theorem on the degree of a nontrivial representation of \(\text{PSL}_2 (q)\).

Chapter 4 on the graphs \(X^{p,q}\) is the heart of the matter. For distinct odd primes \(p\), \(q\) the graph \(X^{p,q}\) is defined as the Cayley graph of the group \(\text{PSL}_2 (q)\) (case \((\frac {p}{q})=1\)) or \(\text{PGL}_2 (q)\) (case \((\frac {p}{q})= -1\)), respectively, with respect to a suitable symmetric subset \(S_{p,q}\) which has \(p+1\) elements (at least for \(q> 2\sqrt{p}\)). The Main Theorem of the book now states that these graphs \(X^{p,q}\) are simple \((p+1)\)-regular connected Ramanujan graphs. Moreover, the Main Theorem gives the number of vertices of the \(X^{p,q}\), states when \(X^{p,q}\) is bipartite or not and contains girth estimates.

On the elementary level of the book the Ramanujan property of the \(X^{p,q}\) cannot be fully reached. Yet the authors indicate how this can be deduced from the Ramanujan conjecture, now Deligne’s Theorem, on the Fourier coefficients of holomorphic modular cusp forms. Nevertheless, the authors prove by purely elementary means that for fixed \(p\) the family of the \(X^{p,q}\) (\(q\) odd prime) is a family of expanders, and they get an explicit lower bound on the spectral gap when \(q\) is large enough with respect to \(p\).

The book contains only very few misprints. The funniest of these appears in item [57] in the bibliography where you can read: “Cambridge Trusts in Math”.

The book under review is an attractively written excellent text which successfully bridges the gap between undergraduate instruction and current research. Hence it is very well suited to bring a fresh breeze into the classroom. The reviewer warmly recommends this text to any lecturer looking for an attractive theme and to everybody else for great supplementary reading. Of course, this book should not be missed in any institutional library.

Main Problem: Give explicit constructions for families of expanders.

This problem is solved by appealing to the adjacency matrix \(A\) of \(X\). If \(X\) is \(k\)-regular on \(n\) vertices, the matrix \(A\) has \(n\) eigenvalues \[ k= \mu_0\geq \mu_1\geq\cdots\geq \mu_{n-1}\geq -k \] (repeated according to multiplicities). It turns out that the expanding constant can be estimated spectrally from above and from below, and rephrasing the Main Problem in terms of the spectrum, one has to construct \(X_m\) such that the spectral gap \(k- \mu_1(X_m)\) is as large as possible. This will yield a family of good expanders. However, the spectral gap cannot be too large since it can be shown that \[ \liminf_{m\rightarrow \infty} \mu_1(X_m)\geq 2\sqrt{k-1}. \] This leads to the notion of Ramanujan graph: A finite connected \(k\)-regular graph \(X\) is a Ramanujan graph if, for every eigenvalue \(\mu\neq \pm k\) of its adjacency matrix one has \(|\mu|\leq 2\sqrt{k-1}\).

The purpose of the book under review is to describe the Ramanujan graphs of A. Lubotzky, R. Phillips and P. Sarnak [Combinatorica 8, 261-277 (1988; Zbl 0661.05035)] and of G. A. Margulis [Probl. Inf. Transm. 24, No. 1, 39-46 (1988; Zbl 0708.05030)]. While the description of these graphs is elementary, the proof that they have the desired properties is not. It is the authors’ aim here to give elementary proofs of most of the properties enjoyed by these graphs, and the authors achieve this aim admirably. Moreover they deal with the problem of the construction of finite graphs with large girth and large chromatic number.

We briefly indicate the contents of the various chapters. Chapter 1 treats the relevant graph theory. It deals with the adjacency matrix and its spectrum, inequalities on the spectral gap and asymptotic behaviour of eigenvalues in families of expanders. One section is addressed to the existence of graphs with large girth and large chromatic number (probabilistic method due to Erdős).

Chapter 2 deals with some relevant number theory. Topics covered include sums of two squares, quadratic reciprocity, sums of four squares and arithmetic of integer quaternions (following Dickson). The properties of the graphs \(X^{p,q}\) to be constructed in Chapter 4 depend heavily on some structural properties of the groups \(\text{PSL}_2 (q)\). These are developed in Chapter 3; topics include simplicity, structure of subgroups, a concise introduction to the representation theory of finite groups, and Frobenius’ theorem on the degree of a nontrivial representation of \(\text{PSL}_2 (q)\).

Chapter 4 on the graphs \(X^{p,q}\) is the heart of the matter. For distinct odd primes \(p\), \(q\) the graph \(X^{p,q}\) is defined as the Cayley graph of the group \(\text{PSL}_2 (q)\) (case \((\frac {p}{q})=1\)) or \(\text{PGL}_2 (q)\) (case \((\frac {p}{q})= -1\)), respectively, with respect to a suitable symmetric subset \(S_{p,q}\) which has \(p+1\) elements (at least for \(q> 2\sqrt{p}\)). The Main Theorem of the book now states that these graphs \(X^{p,q}\) are simple \((p+1)\)-regular connected Ramanujan graphs. Moreover, the Main Theorem gives the number of vertices of the \(X^{p,q}\), states when \(X^{p,q}\) is bipartite or not and contains girth estimates.

On the elementary level of the book the Ramanujan property of the \(X^{p,q}\) cannot be fully reached. Yet the authors indicate how this can be deduced from the Ramanujan conjecture, now Deligne’s Theorem, on the Fourier coefficients of holomorphic modular cusp forms. Nevertheless, the authors prove by purely elementary means that for fixed \(p\) the family of the \(X^{p,q}\) (\(q\) odd prime) is a family of expanders, and they get an explicit lower bound on the spectral gap when \(q\) is large enough with respect to \(p\).

The book contains only very few misprints. The funniest of these appears in item [57] in the bibliography where you can read: “Cambridge Trusts in Math”.

The book under review is an attractively written excellent text which successfully bridges the gap between undergraduate instruction and current research. Hence it is very well suited to bring a fresh breeze into the classroom. The reviewer warmly recommends this text to any lecturer looking for an attractive theme and to everybody else for great supplementary reading. Of course, this book should not be missed in any institutional library.

Reviewer: Jürgen Elstrodt (Münster)

##### MSC:

11-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to number theory |

05-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics |

11E25 | Sums of squares and representations by other particular quadratic forms |

11F30 | Fourier coefficients of automorphic forms |

05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |

05C35 | Extremal problems in graph theory |