The random-vector model conjecture for eigenvectors of sparse random graphs

Let G(n,p)G(n,p) be an Erdős–Rényi random graph. Assume

p(1+ϵ)lognnp\geq \frac{(1+\epsilon)\log n}{n}

for some constant ϵ>0\epsilon>0. Let vv be a random unit vector uniformly distributed on the (n1)(n-1)-dimensional unit sphere, let uu be a unit eigenvector of G(n,p)G(n,p), and let ww be any fixed nn-dimensional vector. The random-vector model conjecture. For every δ>0\delta>0,

P(wuwv>δ)=o(1).\mathbf{P}(|w\cdot u-w\cdot v|>\delta)=o(1).

This conjecturally says that projections of eigenvectors have the same asymptotic behavior as projections of a uniformly random unit vector above the connectivity threshold; the source presents it as a generalization of preceding eigenvector-delocalization questions.

Sources & referencesView supporting material

Primary source

Linh Tran, Van Vu and Ke Wang, “Sparse random graphs: Eigenvalues and Eigenvectors”, arXiv:1011.6646 (2010).

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.