A Proof of Alon's Second Eigenvalue Conjecture and Related Problems (Memoirs of the American Mathematical Society 195, 910)

A Proof of Alon's Second Eigenvalue Conjecture and Related Problems (Memoirs of the American Mathematical Society 195, 910)

By: Joel Friedman (author)Paperback

1 - 2 weeks availability

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.

Create a review

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

Product Details

  • publication date: 15/12/2008
  • ISBN13: 9780821842805
  • Format: Paperback
  • Number Of Pages: 100
  • ID: 9780821842805
  • weight: 182
  • ISBN10: 0821842803

Delivery Information

  • Saver Delivery: Yes
  • 1st Class Delivery: Yes
  • Courier Delivery: Yes
  • Store Delivery: Yes

Prices are for internet purchases only. Prices and availability in WHSmith Stores may vary significantly

Close