Electronic ISBN:  9781470405168 
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{d1}\;+\epsilon\) with probability \(1O(n^{\tau})\), where \(\tau=\lceil \bigl(\sqrt{d1}\;+1\bigr)/2 \rceil1\). He also shows that this probability is at most \(1c/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 reviewers who would like to review an AMS bookPermission – 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{d1}\;+\epsilon\) with probability \(1O(n^{\tau})\), where \(\tau=\lceil \bigl(\sqrt{d1}\;+1\bigr)/2 \rceil1\). He also shows that this probability is at most \(1c/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