Why is the spectrum of Erdős–Renyi random graph approximately symmetric?

Question

I am recently self-learning random matrix theory and made some simulations about the spectrum of Erdős–Renyi random graph $G(n,p)$ when $np\to\infty$,

and $np\to c=2,3$.

The plots above are already normalized such that the $y$-axis is about the frenquency and the $x$-axis is the eigenvalues divided by $\sqrt{np(1-p)}$.

Now it turns out that, although the spectrum itself is not symmetric (like the largest eigenvalue is far away from the bulk), the limiting shape is asymptotically symmetric. I wonder whether we can read this property out from the ER graph or its adjacency matrix directly, before we show that e.g. in the dense case the limiting distribution is the semi-circle law.

I kind of get why the atoms in sparse case are symmetric, because they come from small components of the graph which are trees, thus bipartite and bipartite graphs have symmetric spectrum.

But why is the continuous part in the sparse case, as well as the dense one, still symmetric?

For the sparse one I probably can explain it like, the contiuous part should be the contribution of the giant component which is also locally tree-like, but still not very promising (like, why is locally tree-like enough to guarantee symmetry?). And for the dense case I have no clue—the graph does not seem bipartite to me.

Answer 1

The Erdős–Renyi random matrix $G$ is a rank-one perturbation of a matrix $H$ with zero mean, $$G=H+pv^\top v,\;\;v=(1,1,\ldots 1)^\top.$$ The spectrum of $H$ is symmetric, while the eigenvalues $\lambda_k(G)$ of $G$ (numbered in ascending order) are interlaced with those of $H$, $$\lambda_k(H)\leq\lambda_{k+1}(G)\leq\lambda_{k+2}(H),\;\;1\leq k\leq n-2.$$ So except for the largest eigenvalue $\lambda_n(G)$, which is an outlier, the spectrum of $G$ will be approximately symmetric.

Answer 2

For $np\rightarrow\infty$, it is a very classical result that it converges to the semi-circle law. If you just want the symmetry in a general case, I suppose one should just estimate $$\frac{1}{n}\mathbb{E}(\text{Tr}H^k)=o(1)$$ for any $k\in 2\mathbb{N}+1$.

In the sparse case, I think I can propose another sketch for a proof:

1. Let $x\in \mathbb{R}$, the number of eigenvalues close to $x$ (in a neighborhood of typical size $\eta$) can be estimate using the resolvent $$\sum_{\lambda_i\in\sigma(H)}\frac{\eta}{(\lambda_i-x)^2+\eta^2} = \Im m\text{Tr}((H-x-i\eta)^{-1})=\sum_{i\leq n} \Im m \langle i,(H-x-i\eta)^{-1}i \rangle $$
2. For $\eta>0$, the resolvent decays exponentially by Combes-Thomas estimate, and we have $$\langle i,(H-x-i\eta)^{-1}i \rangle \approx \langle i,(H|_{B_r(i)}-x-i\eta)^{-1}i \rangle $$ where $H|_{B_r(i)}$ is the matrix restricted on $B_r(i)$ a large ball (for the graph distance) around the vertex $i$.
3. Localy (on the balls), the Erdos-Renyi graph is a tree and therefore a bipartite graph so its spectrum is symmetric. In particular
   $$ \langle i,(H|_{B_r(i)}-x-i\eta)^{-1}i \rangle = \langle i,(H|_{B_r(i)}+x-i\eta)^{-1}i \rangle$$