Entrywise bounds for eigenvectors of random graphs (Q2380297)

Summary: Let \(G\) be a graph randomly selected from \({\mathbf G}_{n,p}\), the space of Erdős-Rényi random graphs with parameters \(n\) an d\(p\), where \(p\geq \frac{\log^6n}{n}\). Also, let \(A\) be the adjacency matrix of \(G\), and \(v_1\) be the first eigenvector of \(A\). We provide two short proofs of the following statement: For all \(i\in[n]\), for some constant \(c>0\), \[ \bigg|v_1(i)- \frac{1}{\sqrt{n}}\bigg|\leq \frac{1}{\sqrt{n}} \frac{\log n}{\log(np)} \sqrt{ \frac{\log n}{np}} \] with probability \(1-o(1)\). This gives nearly optimal bounds on the entrywise stability of the first eigenvector of (Erdős-Rényi) random graphs. This question about entrywise bounds was motivated by a problem in unsupervised spectral clustering. We make some progress towards solving that problem.