# Eigenfunctions of random graphs

Consider a random $d$-regular graph on $n$ vertices. What can be said about its nontrivial (i.e. orthogonal to the constant) eigenfunctions? For example, I'm interested whether there are "nodal zones", i.e. if the graph can be divided into groups such that the eigenfunction has the same sign on every vertex of the same groups. Are there any results of this kind?

Another question - suppose I divide the graph arbitrarily into $k$ groups of vertices ($k$ may depend on $n$); is it possible to say something about how large the sum of eigenfunction's values on one group typically is?

-
Dekel, Lee, and Linial proved that for an Erdos-Renyi random graph there are essentially at most two nodal zones for each eigenfunction: arxiv.org/abs/0807.3675 – alex o. Sep 13 '11 at 19:16

## 3 Answers

While there is vast knowledge and literature on eigenvalues of adjacenct matrices and Laplacians of graphs, the study of eigenfunctions of graphs is still largly an uncharted territory. I am aware about two direction of research. The first direction about nodal domains in Random graphs was studied (as mentioned by Alex O in his comment) by Yael Dekel, James R. Lee, and Nati Linial in their paper Eigenvectors of random graphs: Nodal domains. The second direction (which may be little relevant to the last part of the question) is about the phenomenon of "unique quantum ergodicity". There are two papers by Shimon Brooks and Elon Lindenstrauss: Non-localization of eigenfunctions on large regular graphs,and Graph eigenfunctions and quantum unique ergodicity.

-

Laplacian eigenvectors tend to localize over nodes with similar degrees. Some illustrations and exposition begin on page two in this paper: doi:10.1038/nphys1651 with a more detailed explanation here: 10.1103/PhysRevE.77.031102

-

In the following reference we studied in detail certain properties of the eigenfunctions of adjacency matrices of Newman-Watts small-world graphs: http://dx.doi.org/10.1103/PhysRevB.75.144204.

-