10
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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 $\endgroup$
    – alex o.
    Commented Sep 13, 2011 at 19:16

3 Answers 3

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .