Preface......Page 5
Chapter 1. Introduction and motivation......Page 6
Prerequisites and notation......Page 13
2.1. Graphs......Page 15
2.2. Metric, diameter, and so on......Page 24
2.3. Cayley graphs, action graphs, Schreier graphs......Page 33
3.1. Expansion in graphs......Page 44
3.2. Random walks......Page 55
3.3. Random walks and expansion......Page 76
3.4. The discrete Laplace operator......Page 84
3.5. Expansion of Cayley graphs......Page 88
3.6. Matchings......Page 95
4.1. Probabilistic existence of expanders......Page 99
4.2. Ramanujan graphs......Page 102
4.3. Cayley graphs of finite linear groups......Page 108
4.4. Property (T)......Page 111
5.1. The Barzdin-Kolmogorov graph-embedding theorem......Page 121
5.2. Error reduction in probabilistic algorithms......Page 123
5.3. Sieve methods......Page 129
5.4. Geometric applications......Page 137
5.5. Diophantine applications......Page 148
6.2. Preliminaries and strategy......Page 154
6.3. The Bourgain-Gamburd argument......Page 159
6.4. Implementing the Bourgain-Gamburd argument......Page 170
6.5. Quasi-random groups......Page 175
6.6. Growth of generating subsets of 3942"613A``4547"603ASL2(Fp)......Page 178<br>6.7. Proof of the growth theorem......Page 187<br>A.1. Introduction......Page 202<br>A.2. Diagrams......Page 203<br>A.3. Statements and proofs......Page 204<br>B.1. Free groups......Page 212<br>B.2. Properties of3942"613A`4547`"603ASL2......Page 215
C.2. Finite-dimensional unitary representations of abelian groups......Page 219
C.3. Algebraic integers......Page 220
C.4. Real stable polynomials......Page 221
C.5. Mixed characteristic polynomials......Page 223
Bibliography......Page 228
Index of notation......Page 233