Many nodal domains in random regular graphs

Abstract: If we partition a graph according to the positive and
negative components of an eigenvector, nodal domains are the resulting
connected subcomponents. Nodal domains have been studied for over 200
years as a method of ascertaining the structure of eigenvectors.
Dekel, Lee, and Linial observed that according to simulations,
typically most eigenvectors of the adjacency matrix of random regular
graphs exhibit many nodal domains, unlike dense Erdős-Rényi graphs. In
this talk, we show how to prove that for the most negative eigenvalues
of the adjacency matrix of a random regular graph, there are an almost
linear number of nodal domains. Based on joint work with Shirshendu
Ganguly, Sidhanth Mohanty, and Nikhil Srivastava.