Theory Lunch Seminar

October 20, 2021 12:00pm — 1:00pm

Location:
In Person and Virtual ET - Gates Hillman 8102 and Zoom

Speaker:
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.

Reference

In Person and Zoom Participation. See announcement.

Event Website:
https://www.cs.cmu.edu/~./theorylunch/

For More Information:
pkacham@andrew.cmu.edu