A Proof of Alon's Second Eigenvalue Conjecture and Related Problems |
|
Author:
| Friedman, Joel |
Series title: | Memoirs of the American Mathematical Society Ser. |
ISBN: | 978-0-8218-4280-5 |
Publication Date: | Dec 2008 |
Publisher: | American Mathematical Society
|
Book Format: | Paperback |
List Price: | AUD $97.90 |
Book 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...
More DescriptionA $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.