Uniform regular weighted graphs with large degree: Wigner's law, asymptotic freeness and graphons limit

Abstract

For each $N\ge 1$, let $G_N$ be a simple random graph on the set of vertices $[N]=\{1,2,...,N\}$, which is invariant by relabeling of the vertices. The asymptotic behavior as $N$ goes to infinity of correlation functions: $${\mathfrak{C}}_N(T)=\mathbb{E}\left[\prod _{(i,j)\in T}\right(1_{(\{i,j\}\in G_N)}-\mathbb{P}(\{i,j\}\in G_N)\left)\right],T\subset [N{]}^2\text{finite}$$ furnishes informations on the asymptotic spectral properties of the adjacency matrix $A_N$ of $G_N$. Denote by $d_N=N\times \mathbb{P}(\{i,j\}\in G_N)$ and assume $d_N,N-d_N\underset{N\to \infty }{⟶}\infty$. If ${\mathfrak{C}}_N(T)=(\frac{d_N}{N}{)}^{|T|}\times O(d_N^{-\frac{|T|}{2}})$ for any $T$, the standardized empirical eigenvalue distribution of $A_N$ converges in expectation to the semicircular law and the matrix satisfies asymptotic freeness properties in the sense of free probability theory. We provide such estimates for uniform $d_N$-regular graphs $G_{N,d_N}$, under the additional assumption that $|\frac{N}{2}-d_N-\eta \sqrt{d_N}|\underset{N\to \infty }{⟶}\infty$ for some $\eta >0$. Our method applies also for simple graphs whose edges are labelled by i.i.d. random variables.

21 pages, 7 figures