Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
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
A Proof of Alon's Second Eigenvalue Conjecture and Related Problems
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
A Proof of Alon's Second Eigenvalue Conjecture and Related Problems
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
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 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.

  • 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
  • Requests
     
     
    Review Copy – for publishers of book reviews
    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 publishers of book reviews
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.