TIME: 1:30-2:20 pm, May 1, 2007 PLACE: CSE 403 SPEAKER: James Lee University of Washington TITLE: In which directions does a random graph resonate? ABSTRACT: Much attention has been paid to the distribution of the eigenvalues of (the adjacency matrix) of random graphs and random Bernoulli matrices, but the eigenvectors of such objects have received somewhat less coverage. We consider the natural question: Do the (normalized) eigenvectors of G(n,1/2) look roughly like random vectors on the sphere? Similar questions have connections to problems in quantum chaos, geometric functional analysis, hardness of approximation, and spectral heuristics for random instances of NP-hard problems. I will focus mainly on the nodal domains associated with the eigenvectors of G(n,p). In the analogous realm of Laplacians on Riemannian manifolds, nodal domains have been the subject of intensive research for well over a hundred years. Graphical nodal domains turn out to have interesting and unexpected properties. Our main theorem asserts that there is a constant C such that for almost every graph G, each eigenvector of G has at most two nodal domains, together with at most C exceptional vertices falling outside these primary domains. In the remainder of the talk, I'll discuss the connections between random discrete matrices, the Littlewood-Offord problem, and discrete "quantum ergodicity" on random graphs. [joint work with Yael Dekel and Nati Linial]