Many Nodal Domains in Random Regular Graphs

Let G be a random d-regular graph on n vertices. We prove that for every constant alpha > 0, with high probability every eigenvector of the adjacency matrix of G with eigenvalue less than -2 root d - 2 -alpha a has Omega (n/polylog(n)) nodal domains.

Automated summary

For a random d-regular graph G on n vertices, we prove that with high probability, every eigenvector of G's adjacency matrix with eigenvalue less than -2 root d - 2 - alpha has at least Omega (n/polylog(n)) nodal domains.