An error was encountered while trying to add the item to the cart. Please try again.
Copy To Clipboard
Successfully Copied!
A Proof of Alon’s Second Eigenvalue Conjecture and Related Problems

Joel Friedman University of British Columbia, Vancouver, BC, Canada
Available Formats:
Electronic ISBN: 978-1-4704-0516-8
Product Code: MEMO/195/910.E
List Price: $68.00 MAA Member Price:$61.20
AMS Member Price: $40.80 Click above image for expanded view A Proof of Alon’s Second Eigenvalue Conjecture and Related Problems Joel Friedman University of British Columbia, Vancouver, BC, Canada Available Formats:  Electronic ISBN: 978-1-4704-0516-8 Product Code: MEMO/195/910.E  List Price:$68.00 MAA Member Price: $61.20 AMS Member Price:$40.80
• Book Details

Memoirs of the American Mathematical Society
Volume: 1952008; 100 pp
MSC: Primary 68; 05;

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.

• Chapters
• 1. Introduction
• 2. Problems with the standard trace method
• 3. Background and terminology
• 4. Tangles
• 5. Walk sums and new types
• 6. The selective trace
• 7. Ramanujan functions
• 8. An expansion for some selective traces
• 9. Selective traces in graphs with (without) tangles
• 10. Strongly irreducible traces
• 11. A sidestepping lemma
• 12. Magnification theorems
• 13. Finishing the $\mathcal {G}_{n,d}$ proof
• 14. Finishing the proofs of the main theorems
• 15. Closing remarks
• Requests

Review Copy – for reviewers who would like to review an AMS book
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
Volume: 1952008; 100 pp
MSC: Primary 68; 05;

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.

• Chapters
• 1. Introduction
• 2. Problems with the standard trace method
• 3. Background and terminology
• 4. Tangles
• 5. Walk sums and new types
• 6. The selective trace
• 7. Ramanujan functions
• 8. An expansion for some selective traces
• 9. Selective traces in graphs with (without) tangles
• 10. Strongly irreducible traces
• 11. A sidestepping lemma
• 12. Magnification theorems
• 13. Finishing the $\mathcal {G}_{n,d}$ proof
• 14. Finishing the proofs of the main theorems
• 15. Closing remarks
Review Copy – for reviewers who would like to review an AMS book
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
Please select which format for which you are requesting permissions.