MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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?

share|cite|improve this question
up vote 1 down vote accepted

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)$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.