Question

Hi

Does anyone know of any statement relating the probability that the second largest eigenvalue of a random graph is bigger than x to the parameter p in the G_np model?

Thanks

Answer 1

Provided $pN$ is large in comparison to $N^{2/3}$ it looks like this paper by László Erdős, Antti Knowles, Horng-Tzer Yau, and Jun Yin has what you need. Here's the abstract:

We consider the ensemble of adjacency matrices of Erdős–Rényi random graphs, i.e.\ graphs on $N$ vertices where every edge is chosen independently and with probability $p \equiv p(N)$. We rescale the matrix so that its bulk eigenvalues are of order one. Under the assumption $p N \gg N^{2/3}$, we prove the universality of eigenvalue distributions both in the bulk and at the edge of the spectrum. More precisely, we prove (1) that the eigenvalue spacing of the Erdős–Rényi graph in the bulk of the spectrum has the same distribution as that of the Gaussian orthogonal ensemble; and (2) that the second largest eigenvalue of the Erdős–Rényi graph has the same distribution as the largest eigenvalue of the Gaussian orthogonal ensemble. As an application of our method, we prove the bulk universality of generalized Wigner matrices under the assumption that the matrix entries have at least $4 + \epsilon$ moments.

Skimming their introduction it seems that the distribution in question is the Tracy-Widom distribution. They also say that this result is expected to hold for $pN\gg1$, citing private communication by P. Sarnak.

More explicitly, theorem 2.7 of the paper in your notation says the following. Let $A$ be the adjacency matrix of $G_{n,p}$ multiplied by the factor $\gamma/q=\frac{1}{\sqrt{(1-p)pn}}$ where $p=q^2/n$ and $\gamma=(1-q^2/n)^{-1/2}$. Let $\mu_{n-1}$ be the second largest eigenvalue of $A$ (note that they index from the smallest to largest). Suppose that $q\geq n^\phi$ with $1/3<\phi\leq 1/2$. Then there exists $\delta>0$ such that for any $s$:

$F_1(s-n^{-\delta})-n^{-\delta}\leq PR[n^{2/3}(\mu_{n-1}-2)\leq s]\leq F_1(s+n^{-\delta})+n^{-\delta}$

Here $F_1(s)$ is the cumulative distribution function for the Tracy-Widom distribution for the orthogonal ensemble. The Wikipedia article I linked above has formulas for $F_1(s)$.

Because of the scale factor in front of $A$, their $\mu_{n-1}$ should be related to your $\lambda_2$ by the factor $\gamma/q=\frac{1}{\sqrt{(1-p)pn}}$. Thus after a bit of algebra, for large $n$:

$PR\left[\lambda_2\leq (s n^{-2/3}+2)\sqrt{(1-p)pn}\right]\approx F_1(s)$

Letting $x=(sn^{-2/3}+2)\sqrt{(1-p)pn}$, and noting that you want the probability that $\lambda_2$ is greater than $x$, if I haven't made any mistakes in transcription:

$PR\left[\lambda_2>x\right]\approx 1-F_1\left(n^{2/3}\left(\frac{x}{\sqrt{(1-p)pn}}-2\right)\right)$