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.

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