A Proof of the Alon Second Eigenvalue Conjecture

Joel Friedman
University of British Columbia, Vancouver
Computer Science

In this talk we describe the Alon conjecture regarding the
second eigenvalue of a random regular graph, and give a brief
introduction to some aspects of its proof.

The main new feature of this paper is the analysis of what we call "tangles." Roughly speaking, a "tangle" is a finite graph such that any sufficiently large d-regular graph that contains this "tangle" must have second eigenvalue at least 2 sqrt(d-1). The probability that such a tangle appears in a random d-regular graph gives upper and lower bounds for the Alon conjecture.

Presentation (PDF File)

Back to Automorphic Forms, Group Theory and Graph Expansion