AMS Bookstore LOGO amslogo
Return to List

AMS TextbooksAMS Applications-related Books

A Proof of Alon's Second Eigenvalue Conjecture and Related Problems
Joel Friedman, University of British Columbia, Vancouver, BC, Canada

Memoirs of the American Mathematical Society
2008; 100 pp; softcover
Volume: 195
ISBN-10: 0-8218-4280-3
ISBN-13: 978-0-8218-4280-5
List Price: US$68
Individual Members: US$40.80
Institutional Members: US$54.40
Order Code: MEMO/195/910
[Add Item]

Request Permissions

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

  • Introduction
  • Problems with the standard trace method
  • Background and terminology
  • Tangles
  • Walk sums and new types
  • The selective trace
  • Ramanujan functions
  • An expansion for some selective traces
  • Selective traces in graphs with (without) tangles
  • Strongly irreducible traces
  • A sidestepping lemma
  • Magnification theorem
  • Finishing the \({\cal G}_{n,d}\) proof
  • Finishing the proofs of the main theorems
  • Closing remarks
  • Glossary
  • Bibliography
Powered by MathJax

  AMS Home | Comments:
© Copyright 2014, American Mathematical Society
Privacy Statement

AMS Social

AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia