Tracy–Widom limit and Ramanujan proportions for random regular graphs

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)2d1+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 NN\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)2d1\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.

Sources & referencesView supporting material

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.