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.
Copyright. All Rights Reserved.