Tracy–Widom limit and Ramanujan proportions for random regular graphs

About 20 years old · traced to

Let FN,d\mathcal{F}_{N,d} be one of the families of dd-regular graphs CIN,d\mathcal{CI}_{N,d}, SCIN,d\mathcal{SCI}_{N,d}, or SCBN,d\mathcal{SCB}_{N,d}, and let λ±(G)\lambda_\pm(G) be the largest non-trivial positive and most negative eigenvalues. Write

λ±~(G)=λ±(G)−2d−1+cμ,N,d,±Nm±(FN,d)cσ,N,d,±Ns±(FN,d).\widetilde{\lambda_\pm}(G)=\frac{\lambda_\pm(G)-2\sqrt{d-1}+c_{\mu,N,d,\pm}N^{m_\pm(\mathcal{F}_{N,d})}}{c_{\sigma,N,d,\pm}N^{s_\pm(\mathcal{F}_{N,d})}}.

Tracy–Widom and proportion conjecture. The distribution of λ±(G)\lambda_\pm(G), normalized in this way, converges as N→∞N\to\infty to the β=1\beta=1 Tracy–Widom distribution rather than a normalized β=2\beta=2 or β=4\beta=4 Tracy–Widom distribution or the standard normal distribution. For non-bipartite graphs, λ+(G)\lambda_+(G) and λ−(G)\lambda_-(G) are statistically independent. The constants satisfy cμ,N,d,±<0c_{\mu,N,d,\pm}<0 and s±(FN,d)>m±(FN,d)s_\pm(\mathcal{F}_{N,d})>m_\pm(\mathcal{F}_{N,d}), so approximately 52%52\% of graphs in bipartite families and 27%27\% otherwise are Ramanujan, meaning λ(G)≤2d−1\lambda(G)\leq 2\sqrt{d-1}. The bipartite percentage is 51.9652%51.9652\% to six digits, and the non-bipartite percentage is its square. This conjecture predicts the limiting edge-eigenvalue laws and hence the asymptotic proportion of Ramanujan graphs in the specified families; the source presents it as motivated by numerical evidence, and no proof or resolution is supplied.

References

Primary source

Steven J. Miller, Tim Novikoff and Anthony Sabelli, “The Distribution of the Largest Non-trivial Eigenvalues in Families of Random Regular Graphs”, arXiv:math/0611649 (2008).

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.