Computer Science/Discrete Mathematics Seminar I

A nodal domain of a Laplacian eigenvector of a graph is a maximal connected component where it does not change sign.  Sparse random regular graphs have been proposed as discrete toy models of "quantum chaos", and it has accordingly been conjectured by Y. Elon and experimentally observed by Dekel, Lee, and Linial that the high energy eigenvectors of such graphs have many nodal domains.

We prove superconstant (in fact, nearly linear in the number of vertices) lower bounds on the number of nodal domains of sparse random regular graphs, for sufficiently large Laplacian eigenvalues. The proof combines two different notions of eigenvector delocalization in random matrix theory as well as tools from graph limits and combinatorics. This is in contrast to what is known for dense Erdos-Renyi graphs, which have been shown to have only two nodal domains with high probability.

Joint work with Shirshendu Ganguly, Theo McKenzie, and Sidhanth Mohanty.