Wednesday, October 20, 2021 - 12:00pm to 1:00pm
Location:
In Person and Virtual ET Gates Hillman 8102 and ZoomSpeaker:
THEO McKENZIE, Ph.D. Student https://math.berkeley.edu/~mckenzie/Many nodal domains in random regular graphs
Graph partitioning algorithms often partition according to the entries of an eigenvector. If we partition a graph according to the positive and negative components of an eigenvector, the resulting connected subcomponents are called nodal domains. Dekel, Lee, and Linial observed that according to simulations, 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 is an almost linear number of nodal domains.
Joint work with Shirshendu Ganguly, Sidhanth Mohanty, and Nikhil Srivastava.
In Person and Zoom Participation. See announcement.