This text is a self-contained study of expander graphs, specifically, their explicit construction. Expander graphs are highly connected but sparse, and while being of interest within combinatorics and graph theory, they can also be applied to computer science and engineering. Only a knowledge of elementary algebra, analysis and combinatorics is required because the authors provide the necessary background from graph theory, number theory, group theory and representation theory. Thus the text can be used as a brief introduction to these subjects and their synthesis in modern mathematics.
Author(s): Giuliana Davidoff
Series: London Mathematical Society student texts 55
Publisher: Cambridge University Press
Year: 2003
Language: English
Commentary: 87023
Pages: 154
City: New York
Cover......Page 1
Series-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
Preface......Page 9
An Overview......Page 11
1.1. The Adjacency Matrix and Its Spectrum......Page 18
Exercises on Section 1.1......Page 21
1.2. Inequalities on the Spectral Gap......Page 22
1.3. Asymptotic Behavior of Eigenvalues in Families of Expanders......Page 28
Exercises on Section 1.3......Page 29
1.4. Proof of the Asymptotic Behavior......Page 30
Exercises on Section 1.4......Page 39
1.5. Independence Number and Chromatic Number......Page 40
1.6. Large Girth and Large Chromatic Number......Page 42
1.7. Notes on Chapter 1......Page 46
2.1. Introduction......Page 48
2.2. Sums of Two Squares......Page 49
Exercises on Section 2.2......Page 57
2.3. Quadratic Reciprocity......Page 58
2.4. Sums of Four Squares......Page 62
2.5. Quaternions......Page 67
2.6. The Arithmetic of Integer Quaternions......Page 69
2.7. Notes on Chapter 2......Page 80
3.1. Some Finite Groups......Page 82
3.2. Simplicity......Page 83
3.3. Structure of Subgroups......Page 86
Exercises on Section 3.3......Page 94
3.4. Representation Theory of Finite Groups......Page 95
Exercises on Section 3.4......Page 110
3.5. Degrees of Representations of PSL(q)......Page 112
Exercises on Section 3.5......Page 116
3.6. Notes on Chapter 3......Page 117
4.1. Cayley Graphs......Page 118
Exercises on Section 4.1......Page 121
4.2. Construction of X......Page 122
Exercises on Section 4.2......Page 124
4.3. Girth and Connectedness......Page 125
Exercises on Section 4.3......Page 131
4.4. Spectral Estimates......Page 132
4.5. Notes on Chapter 4......Page 140
Appendix 4-Regular Graphs with Large Girth......Page 142
Exercises on Appendix......Page 147
Bibliography......Page 148
Index......Page 153
