Memoirs of the American Mathematical Society 2008; 100 pp; softcover Volume: 195 ISBN10: 0821842803 ISBN13: 9780821842805 List Price: US$68 Individual Members: US$40.80 Institutional Members: US$54.40 Order Code: MEMO/195/910
 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{d1}\;+\epsilon\) with probability \(1O(n^{\tau})\), where \(\tau=\lceil \bigl(\sqrt{d1}\;+1\bigr)/2 \rceil1\). He also shows that this probability is at most \(1c/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 standard 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}\) proof
 Finishing the proofs of the main theorems
 Closing remarks
 Glossary
 Bibliography
