# A Proof of Alon’s Second Eigenvalue Conjecture and Related Problems

Share this page
*Joel Friedman*

A \(d\)-regular graph has largest or first (adjacency matrix) eigenvalue \(\lambda_1=d\). Consider for an even \(d\ge 4\), a random \(d\)-regular graph model formed from \(d/2\) uniform, independent permutations on \(\{1,\ldots,n\}\). The author shows that for any \(\epsilon>0\) all eigenvalues aside from \(\lambda_1=d\) are bounded by \(2\sqrt{d-1}\;+\epsilon\) with probability \(1-O(n^{-\tau})\), where \(\tau=\lceil \bigl(\sqrt{d-1}\;+1\bigr)/2 \rceil-1\). He also shows that this probability is at most \(1-c/n^{\tau'}\), for a constant \(c\) and a \(\tau'\) that is either \(\tau\) or \(\tau+1\) (“more often” \(\tau\) than \(\tau+1\)). He proves related theorems for other models of random graphs, including models with \(d\) odd.

#### Table of Contents

# Table of Contents

## A Proof of Alon's Second Eigenvalue Conjecture and Related Problems

- Contents v6 free
- Chapter 1. Introduction 110 free
- Chapter 2. Problems with the Standard Trace Method 716 free
- Chapter 3. Background and Terminology 1726
- Chapter 4. Tangles 2736
- Chapter 5. Walk Sums and New Types 3342
- Chapter 6. The Selective Trace 4756
- Chapter 7. Ramanujan Functions 5766
- Chapter 8. An Expansion for Some Selective Traces 5968
- Chapter 9. Selective Traces In Graphs With (Without) Tangles 6574
- Chapter 10. Strongly Irreducible Traces 7382
- Chapter 11. A Sidestepping Lemma 7786
- Chapter 12. Magnification Theorems 8190
- Chapter 13. Finishing the G[sub(n,d)] Proof 8796
- Chapter 14. Finishing the Proofs of the Main Theorems 91100
- Chapter 15. Closing Remarks 95104
- Glossary 97106
- Bibliography 99108