New Titles  |  FAQ  |  Keep Informed  |  Review Cart  |  Contact Us Quick Search (Advanced Search ) Browse by Subject General Interest Logic & Foundations Number Theory Algebra & Algebraic Geometry Discrete Math & Combinatorics Analysis Differential Equations Geometry & Topology Probability & Statistics Applications Mathematical Physics Math Education

A Proof of Alon's Second Eigenvalue Conjecture and Related Problems
Joel Friedman, University of British Columbia, Vancouver, BC, Canada
 SEARCH THIS BOOK:
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$64 Individual Members: US$38.40
Institutional Members: US\$51.20
Order Code: MEMO/195/910

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.

• 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
 AMS Home | Comments: webmaster@ams.org © Copyright 2012, American Mathematical Society Privacy Statement