MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Dekel, Lee, and Linial proved that for an Erdos-Renyi random graph there are essentially at most two nodal zones for each eigenfunction: – alex o. Sep 13 '11 at 19:16

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.

share|cite|improve this answer

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

share|cite|improve this answer

In the following reference we studied in detail certain properties of the eigenfunctions of adjacency matrices of Newman-Watts small-world graphs:

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.