A proof of Alon's second eigenvalue conjecture and related problems
Author(s)
Bibliographic Information
A proof of Alon's second eigenvalue conjecture and related problems
（Memoirs of the American Mathematical Society, no. 910）
American Mathematical Society, 2008
Available at / 12 libraries
-
No Libraries matched.
- Remove all filters.
Note
Includes bibliographical references (p. 99-100)
Description and Table of Contents
Description
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 stand 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}$ proofs
- Finishing the proofs of the main theorems
- Closing remarks
- Glossary
- Bibliography
by "Nielsen BookData"