
eBook 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 |

eBook 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 DetailsMemoirs of the American Mathematical SocietyVolume: 195; 2008; 100 ppMSC: 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.
-
Table of Contents
-
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
-
-
RequestsReview Copy – for publishers of book reviewsPermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
- Book Details
- Table of Contents
- Requests
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