Many nodal domains in random regular graphs

Stochastics Seminar
Thursday, October 28, 2021 - 3:30pm for 1 hour (actually 50 minutes)
Theo McKenzie – Berkeley –
Konstantin Tikhomirov

If we partition a graph according to the positive and negative components of an eigenvector of the adjacency matrix, the resulting connected subcomponents are called nodal domains. Examining the structure of nodal domains has been used for more than 150 years to deduce properties of eigenfunctions. Dekel, Lee, and Linial observed that according to simulations, most eigenvectors of the adjacency matrix of random regular graphs have many nodal domains, unlike dense Erdős-Rényi graphs. In this talk, we show that for the most negative eigenvalues of the adjacency matrix of a random regular graph, there is an almost linear number of nodal domains. Joint work with Shirshendu Ganguly, Sidhanth Mohanty, and Nikhil Srivastava.