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]