Expander graphs, random matrices and quantum chaos
Seminar Room 1, Newton Institute
A basic problem in the theory of expander graphs, formulated by Lubotzky and Weiss, is to what extent being an expander family for a family of Cayley graphs is a property of the groups alone, independent of the choice of generators. While recently Alon, Lubotzky and Wigderson constructed an example demonstrating that expansion is not in general a group property, the problem is open for "natural" families of groups. In particular for SL(2, p) numerical experiments indicate that it might be an expander family for "generic" choices of generators (Independence Conjecture).
A basic conjecture in Quantum Chaos, formulated by Bohigas, Giannoni, and Shmit, asserts that the eigenvalues of a quantized chaotic Hamiltonian behave like the spectrum of a typical member of the appropriate ensemble of random matrices. Both conjectures can be viewed as asserting that a deterministically constructed spectrum "generically" behaves like the spectrum of a large random matrix: "in the bulk" (Quantum Chaos Conjecture) and at the "edge of the spectrum" (Independence Conjecture). After explaining this approach in the context of the spectra of random walks on groups, we review some recent related results and numerical experiments.