Theory Lunch Seminar

  • Gates Hillman 8102 and Zoom
  • In Person and Virtual ET
  • THEO McKENZIE
  • Ph.D. Student
  • Department of Mathematics
  • University of California, Berkeley
Seminars

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.

For More Information, Please Contact: 
Keywords: