# Many nodal domains in random regular graphs

@article{Ganguly2021ManyND, title={Many nodal domains in random regular graphs}, author={Shirshendu Ganguly and Theo McKenzie and Sidhanth Mohanty and Nikhil Srivastava}, journal={ArXiv}, year={2021}, volume={abs/2109.11532} }

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

#### References

SHOWING 1-10 OF 41 REFERENCES

Size of nodal domains of the eigenvectors of a graph

- Computer Science, Mathematics
- Random Struct. Algorithms
- 2020

It is proved that with high probability, the sizes of these nodal domains are approximately equal to each other. Expand

Eigenvectors of the discrete Laplacian on regular graphs?a statistical approach

- Physics, Mathematics
- 2008

In an attempt to characterize the structure of eigenvectors of random regular graphs, we investigate the correlations between the components of the eigenvectors associated with different vertices. In… Expand

A proof of alon's second eigenvalue conjecture

- Mathematics, Computer Science
- STOC '03
- 2003

This paper shows the following conjecture of Alon: for sufficiently large n the authors have that "most" d-regular graphs on n vertices have all their eigenvalues except λ1 = d bounded above by 2√d-1 + ε. Expand

Eigenvectors of Random Graphs: Nodal Domains

- Mathematics, Computer Science
- APPROX-RANDOM
- 2007

The main theorem asserts that there is a constant c such that for almost every graph G, each eigenfunction of G has at most 2 nodal domains, together with at most cexceptional vertices falling outside these primary domains. Expand

Eigenvectors of Random Graphs : Delocalization and Nodal Domains

- 2012

We study properties of the eigenvectors of adjacency matrices of G(n, p) random graphs, for p = ω(logn)/n. This connects to similar investigations for other random matrix models studied in physics… Expand

Local Kesten–McKay Law for Random Regular Graphs

- Mathematics, Physics
- Communications in Mathematical Physics
- 2019

We study the adjacency matrices of random d-regular graphs with large but fixed degree d. In the bulk of the spectrum $${[-2\sqrt{d-1}+\varepsilon, 2\sqrt{d-1}-\varepsilon]}$$[-2d-1+ε,2d-1-ε] down to… Expand

On the almost eigenvectors of random regular graphs

- Mathematics
- The Annals of Probability
- 2019

Let $d\geq 3$ be fixed and $G$ be a large random $d$-regular graph on $n$ vertices. We show that if $n$ is large enough then the entry distribution of every almost eigenvector $v$ of $G$ (with entry… Expand

Gaussian Waves on the Regular Tree

- Mathematics, Physics
- 2009

We consider the family of real (generalized) eigenfunctions of the adjacency operator on $T_d$ - the $d$-regular tree. We show the existence of a unique invariant Gaussian process on the ensemble and… Expand

Nodal domains on graphs - How to count them and why?

- Mathematics, Physics
- 2007

Several methods for counting nodal domains will be presented, and their relevance as a tool in spectral analysis will be discussed. Expand

The expected eigenvalue distribution of a large regular graph

- Mathematics
- 1981

Abstract Let K 1 , K 2 ,... be a sequence of regular graphs with degree v ⩾2 such that n(X i ) →∞ and ck(X i )/n(X i ) →0 as i ∞ for each k ⩾3, where n(X i ) is the order of X i , and c k (X i ) is… Expand