Elementary Number Theory, Group Theory and Ramanujan Graphs

by Giuliana Davidoff , Peter Sarnak , Alain Valette

• ISBN13: 9780521824262
• ISBN10: 0521824265
• eBook ISBN(s): 9780511075551
• Format: Hardcover
• Copyright: 2003-01-27
• Publisher: Cambridge University Press
• More Book Details

Summary

This text is a self contained treatment of expander graphs and in particular their explicit construction. Expander graphs are both highly connected but sparse, and besides their interest within combinatorics and graph theory, they also find various applications in computer science and engineering. The reader needs only a background in elementary algebra, analysis and combinatorics; the authors supply the necessary background material from graph theory, number theory, group theory and representation theory. The text can therefore be used as a brief introduction to these subjects as well as an illustration of how such topics are synthesised in modern mathematics.

Table of Contents

Preface	ix
An Overview	1	(131)
Graph Theory	8	(30)
The Adjacency Matrix and Its Spectrum	8	(4)
Inequalities on the Spectral Gap	12	(6)
Asymptotic Behavior of Eigenvalues in Families of Expanders	18	(2)
Proof of the Asymptotic Behavior	20	(10)
Independence Number and Chromatic Number	30	(2)
Large Girth and Large Chromatic Number	32	(4)
Notes on Chapter 1	36	(2)
Number Theory	38	(34)
Introduction	38	(1)
Sums of Two Squares	39	(9)
Quadratic Reciprocity	48	(4)
Sums of Four Squares	52	(5)
Quaternions	57	(2)
The Arithmetic of Integer Quaternions	59	(11)
Notes on Chapter 2	70	(2)
PSL2(q)	72	(36)
Some Finite Groups	72	(1)
Simplicity	73	(3)
Structure of Subgroups	76	(9)
Representation Theory of Finite Groups	85	(17)
Degrees of Representations of PSL2(q)	102	(5)
Notes on Chapter 3	107	(1)
The Graphs Xp,q	108	(24)
Cayley Graphs	108	(4)
Construction of Xp,q	112	(3)
Girth and Connectedness	115	(7)
Spectral Estimates	122	(8)
Notes on Chapter 4	130	(2)
Appendix 4. Regular Graphs with Large Girth	132	(6)
Bibliography	138	(5)
Index	143