You are here

Elementary Number Theory, Group Theory and Ramanujan Graphs

Giuliana Davidoff, Peter Sarnak. and Alain Valette
Publisher: 
Cambridge University Press
Publication Date: 
2003
Number of Pages: 
154
Format: 
Paperback
Series: 
London Mathematical Society Student Texts 55
Price: 
25.00
ISBN: 
0521531438
Category: 
Monograph
[Reviewed by
Thomas J. Pfaff
, on
04/1/2004
]

Loosely speaking, a family of k-regular graphs is called a family of expanders if the size of the vertex sets goes to infinity, while the graphs maintain good connectedness. Such graphs are important in engineering applications such as network designs, complexity theory, derandomization, coding theory and cryptography. Elementary Number Theory, Group Theory, and Ramanujan Graphs is devoted to constructing the Ramanujan graphs which are a family of expanders. Moreover, these graphs provide an explicit example of an infinite family of graphs with large girth and large chromatic number. The large girth and chromatic number problem was originally solved by Erdös using the probabilistic method, but this does not provide a construction of such graphs.

The book covers a considerable amount of mathematical ground in order to construct and prove the results about the Ramanujan graphs: linear algebra (eigenvalues and spectral gaps), number theory (sums of two and four squares and quadratic reciprocity), and group theory (general linear groups and representation theory of finite groups). Along the way the reader will also see operators between L2 spaces, Chebyshev polynomials, the ring of quaternions, metabelian groups, and Cayley graphs. The fact that all these topics are used to prove graph theory results is what makes this book so interesting. The book is broken up into four chapters covering graph theory, number theory, group theory, and the Ramanujan graphs. In fact, the first three chapters can be read independently and each one is interesting.

The preface of the book claims that this book could be used for an undergraduate course. Based on the topics above I will let you decide if it is appropriate for an undergraduate course at your institution. I think that it would be difficult to use at most undergraduate colleges even as a senior capstone type course. On the other hand, any of the first three chapters could be used for an independent study course with undergraduates. The book would make a nice elective course for graduate students since it pulls so many topics together. If you are looking for a book for a faculty seminar that isn't too discipline-specific, this would be a good choice.

Overall, the book is a well written and stimulating book. My only complaint is that the book doesn't actually give any examples of the applications. It does give references for the applications, but a couple of pages devoted to enlightening the reader about the applications would have been worthwhile.


Thomas J. Pfaff (tpfaff@ithaca.edu) teaches at Ithaca College.

Preface page ix
An Overview 1
Chapter 1. Graph Theory 8
1.1. The Adjacency Matrix and Its Spectrum 8
1.2. Inequalities on the Spectral Gap 12
1.3. Asymptotic Behavior of Eigenvalues in Families
of Expanders 18
1.4. Proof of the Asymptotic Behavior 20
1.5. Independence Number and Chromatic Number 30
1.6. Large Girth and Large Chromatic Number 32
1.7. Notes on Chapter 1 36
Chapter 2. Number Theory 38
2.1. Introduction 38
2.2. Sums of Two Squares 39
2.3. Quadratic Reciprocity 48
2.4. Sums of Four Squares 52
2.5. Quaternions 57
2.6. The Arithmetic of Integer Quaternions 59
2.7. Notes on Chapter 2 70
Chapter 3. PSL2(q) 72
3.1. Some Finite Groups 72
3.2. Simplicity 73
3.3. Structure of Subgroups 76
3.4. Representation Theory of Finite Groups 85
3.5. Degrees of Representations of PSL2(q) 102
3.6. Notes on Chapter 3 107
Chapter 4. The Graphs Xp, q 108
4.1. Cayley Graphs 108
4.2. Construction of X p,q 112
4.3. Girth and Connectedness 115
4.4. Spectral Estimates 122
4.5. Notes on Chapter 4 130
Appendix 4. Regular Graphswith Large Girth 132
Bibliography 138
Index