We consider the ensemble of adjacency matrices of Erd{\H o}s-R\'enyi 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{\H o}s-R\'enyi 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{\H o}s-R\'enyi 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.

We consider a general class of $N\times N$ random matrices whose entries $h_{ij}$ are independent up to a symmetry constraint, but not necessarily identically distributed. Our main result is a local semicircle law which improves previous results [14] both in the bulk and at the edge. The error bounds are given in terms of the basic small parameter of the model, $\max_{i,j} \E \abs{h_{ij}}^2$. As a consequence, we prove the universality of the local $n$-point correlation functions in the bulk spectrum for a class of matrices whose entries do not have comparable variances, including random band matrices with band width $W\gg N^{1-\e_n}$ with some $\e_n>0$ and with a negligible mean-field component. In addition, we provide a coherent and pedagogical proof of the local semicircle law, streamlining and strengthening previous arguments from [17,19,6].

We determine the asymptotics of the independence number of the random d-regular graph for all d≥d0. It is highly concentrated, with constant-order fluctuations around nα∗−c∗logn for explicit constants α∗(d) and c∗(d). Our proof rigorously confirms the one-step replica symmetry breaking heuristics for this problem, and we believe the techniques will be more broadly applicable to the study of other combinatorial properties of random graphs.

Let $D={\mathbb H} \setminus \cup_{k=1}^N C_k$ be a standard slit domain where $\mathbb H$ is the upper half plane and $C_k$, $1\leq k\leq N$, are mutually disjoint horizontal line segments in $\HH$. Given a Jordan arc $\gamma\subset D$ starting at $\partial {\mathbb H},$ let $g_t$ be the unique conformal map from $D\setminus \gamma[0,t]$ onto a standard slit domain $D_t$ satisfying the hydrodynamic normalization. We prove that $g_t$ satisfies an ODE with the kernel on its righthand side being the complex Poisson kernel of the Brownian motion with darning (BMD) for $D_t$, generalizing the chordal Loewner equation for the simply connected domain $D={\mathbb H}.$ Such a generalization has been obtained by Y. Komatu in the case of circularly slit annuli and by R. O. Bauer and R. M. Friedrich in the present chordal case, but only in the sense of the left derivative in $t$. We establish the differentiability of $g_t$ in $t$ to make the equation a genuine ODE. To this end, we first derive the continuity of $g_t(z)$ in $t$ with a certain uniformity in $z$ from a probabilistic expression of $\Im g_t(z)$ in terms of the BMD for $D$, which is then combined with a Lipschitz continuity of the complex Poisson kernel under the perturbation of standard slit domains to get the desired differentiability.

We consider the ensemble of adjacency matrices of Erdős–Rényi random graphs, that is, 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. We prove that, as long as $pN\to\infty$ (with a speed at least logarithmic in $N$), the density of eigenvalues of the Erdős–Rényi ensemble is given by the Wigner semicircle law for spectral windows of length larger than $N^{-1}$ (up to logarithmic corrections). As a consequence, all eigenvectors are proved to be completely delocalized in the sense that the $\ell^{\infty}$-norms of the $\ell^{2}$-normalized eigenvectors are at most of order $N^{-1/2}$ with a very high probability. The estimates in this paper will be used in the companion paper [Spectral statistics of Erdős–Rényi graphs II: Eigenvalue spacing and the extreme eigenvalues (2011) Preprint] to prove the universality of eigenvalue distributions both in the bulk and at the spectral edges under the further restriction that $pN\gg N^{2/3}$.