ISBN-10:
0821842803
ISBN-13:
9780821842805
Pub. Date:
08/08/2008
Publisher:
American Mathematical Society
A Proof of Alon's Second Eigenvalue Conjecture and Related Problems

A Proof of Alon's Second Eigenvalue Conjecture and Related Problems

by Joel Friedman

Paperback

Current price is , Original price is $73.0. You

Temporarily Out of Stock Online

Please check back later for updated availability.

This item is available online through Marketplace sellers.

Overview

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.

Product Details

ISBN-13: 9780821842805
Publisher: American Mathematical Society
Publication date: 08/08/2008
Series: Memoirs of the American Mathematical Society Series , #195
Edition description: New Edition
Pages: 100
Product dimensions: 6.90(w) x 9.90(h) x 0.10(d)

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews