442 SHLOMO HOORY.NATHAN LINIAL.AND AVI WIGDERSON 4.5.1.Large spectral gap implies high expansion 475 4.5.2.High expansion implies large spectral gap 475 4.6.Expansion of small sets 477 4.6.1.Connection with the spectral gap 477 4.6.2.Typical behavior 478 4.7.Expansion in hypergraphs? 481 5.Extremal problems on spectrum and expansion 481 5.1.The d-regular tree 482 5.1.1.The expansion of Ta 482 5.1.2.The spectrum of Td 483 5.2.The Alon-Boppana lower bound 484 5.2.1.Statement of the theorem 5.2.2.Proof I:Counting closed walks in Td 48 5.2.3.Proof II:Using spherical functions 5.2.4.Extensions of the Alon-Boppana theorem 5.3.Ramanujan graphs 488 6.Spectrum and expansion in lifts of graphs 489 6.1. Covering maps and lifts 489 6.2.Eigenvalues-old and new 490 6.3.The universal covering tree 6.3.1.Irregular Ramanujan graphs? 491 6.4.Nearly-Ramanujan graphs by way of 2-lifts 492 7.The spectrum of random graphs 493 7.1.The bulk of the spectrum 493 7.2.The extreme eigenvalues 496 7.2.1.An illustration of the trace method 7.3.Variations on a theme 6 7.3.1.Back to the irregular case 5 7.3.2.Are most regular graphs Ramanujan? 7.3.3.More on random lifts 591 7.3.4. The eigenvectors 502 8.The Margulis construction 503 8.1.A detour into harmonic analysis 504 8.1.1.Characters 604 8.2.Back to the proof 505 9.The zig-zag product 508 9.1.Introduction 508 9.2. Construction of an expander family using zig-zag 509 9.3.Definition and analysis of the zig-zag product 510 9.4.Entropy analysis 512 9.5.An application to complexity theory:SL=L 512 10.Lossless conductors and expanders 514 10.1.Conductors and lossless expanders 515 10.1.1.Conductors 515442 SHLOMO HOORY, NATHAN LINIAL, AND AVI WIGDERSON 4.5.1. Large spectral gap implies high expansion 475 4.5.2. High expansion implies large spectral gap 475 4.6. Expansion of small sets 477 4.6.1. Connection with the spectral gap 477 4.6.2. Typical behavior 478 4.7. Expansion in hypergraphs? 481 5. Extremal problems on spectrum and expansion 481 5.1. The d-regular tree 482 5.1.1. The expansion of Td 482 5.1.2. The spectrum of Td 483 5.2. The Alon-Boppana lower bound 484 5.2.1. Statement of the theorem 484 5.2.2. Proof I: Counting closed walks in Td 484 5.2.3. Proof II: Using spherical functions 485 5.2.4. Extensions of the Alon-Boppana theorem 487 5.3. Ramanujan graphs 488 6. Spectrum and expansion in lifts of graphs 489 6.1. Covering maps and lifts 489 6.2. Eigenvalues - old and new 490 6.3. The universal covering tree 491 6.3.1. Irregular Ramanujan graphs? 491 6.4. Nearly-Ramanujan graphs by way of 2-lifts 492 7. The spectrum of random graphs 493 7.1. The bulk of the spectrum 493 7.2. The extreme eigenvalues 496 7.2.1. An illustration of the trace method 496 7.3. Variations on a theme 500 7.3.1. Back to the irregular case 500 7.3.2. Are most regular graphs Ramanujan? 501 7.3.3. More on random lifts 501 7.3.4. The eigenvectors 502 8. The Margulis construction 503 8.1. A detour into harmonic analysis 504 8.1.1. Characters 504 8.2. Back to the proof 505 9. The zig-zag product 508 9.1. Introduction 508 9.2. Construction of an expander family using zig-zag 509 9.3. Definition and analysis of the zig-zag product 510 9.4. Entropy analysis 512 9.5. An application to complexity theory: SL = L 512 10. Lossless conductors and expanders 514 10.1. Conductors and lossless expanders 515 10.1.1. Conductors 515