Sarnak's conjecture on Ramanujan random regular graphs

At least 19 years old · documented by

Let Gn,dG_{n,d} be a uniformly random simple dd-regular graph, and write

λ(G)=max⁡{∣λ2∣,∣λn∣}\lambda(G)=\max\{|\lambda_2|,|\lambda_n|\}

for the maximum absolute value of its nontrivial adjacency eigenvalues. A dd-regular graph is Ramanujan when λ(G)≤2d−1\lambda(G)\le 2\sqrt{d-1}. Sarnak's conjecture. For fixed dd and no~∞n{\tilde o}\infty, Gn,dG_{n,d} is Ramanujan with positive constant probability. Random regular graphs are natural candidates for producing Ramanujan graphs, but the source gives no resolution of this probabilistic assertion.

References

Primary source

V. Vu, “Random Discrete Matrices”, arXiv:math/0611321 (2006).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.