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

Joel Friedman (Autor)

Buch | Softcover

100 Seiten

2008
American Mathematical Society (Verlag)
978-0-8218-4280-5 (ISBN)

Titel ist leider vergriffen;
keine Neuauflage

Artikel merken

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 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

Erscheint lt. Verlag	30.12.2008
Reihe/Serie	Memoirs of the American Mathematical Society
Verlagsort	Providence
Sprache	englisch
Gewicht	180 g
Themenwelt	Mathematik / Informatik ► Informatik ► Theorie / Studium
Themenwelt	Mathematik / Informatik ► Mathematik ► Graphentheorie
ISBN-10	0-8218-4280-3 / 0821842803
ISBN-13	978-0-8218-4280-5 / 9780821842805
Zustand	Neuware