eigenvalues of the induced graphon converge pointwise to the eigenvalues of the limit

Let $\{G_n\}$ be a convergent graph sequence with limit graphon $W$. Then

$$\underset{n\to \mathrm{\infty }}{lim}\frac{{\lambda }_j(A_n)}{n}={\lambda }_j(W)=\underset{n\to \mathrm{\infty }}{lim}{\lambda }_j(T_{W_n})$$

ie, the eigenvalues of the induced graphon converge to the eigenvalues of the limit.

Where

• $A_n$ is the adjacency matrix of $G_n$
• $W_n$ is the graphon induced by $A_n$
• $T_{W_n}$ the graphon shift operator for $W_n$

$$W_n(u,v)=\sum _{i,j=1}^n[A_n{]}_{ij}\mathbb{1}(u\in I_i)\mathbb{1}(v\in I_j)$$$$A_n=V_n{\mathrm{\Lambda }}_n{V}_n^{\ast }$$

Thus

$$\begin{array}{rlr}{T}_{W_n}\phi (v)& ={\int }_0^1{W}_n(u,v)\phi (u)du& =\lambda \phi (v)\\ & ={\int }_0^1\sum _{i,j=1}^n[A_n{]}_{ij}\mathbb{1}(u\in I_i)\mathbb{1}(v\in I_j)\phi (u)du& =\lambda \phi (v)\\ & =\mathbb{1}(v\in I_j){\int }_0^1\sum _{i,j=1}^n[A_n{]}_{ij}\mathbb{1}(u\in I_i)\phi (u)du& =\lambda \phi (v)\\ ⟹& =\sum _{i,j=1}^n[A_n{]}_{ij}{\int }_0^1\mathbb{1}(u\in I_i)\phi (u)du& =\lambda \phi (v\in I_j)\end{array}$$

LHS is a constant for each $v\in I_j$. This means that $\phi$ is a step function $\phi (v\in I_j)=x_j$. Thus, we can rewrite the last line as

$$\begin{array}{rl}\lambda x_j& =\sum _{i=1}^n[A_n{]}_{ij}{x}_i\frac{1}{n}\end{array}$$

since for each $i$ we have $\phi (u)=\{\begin{array}{l}{x}_i,x_i\in I_i\\ 0,\text{otherwise}\end{array}$ . The above is just a matrix multiplication, so we get

$$\begin{array}{rl}⟹\lambda x& =\frac{1}{n}{A}_{n}x\\ ⟹{\lambda }_j(T_{W_n})& =\frac{{\lambda }_j(A_n)}{n}\mathrm{\forall }j\end{array}$$

For convergence, this means that

$$\begin{array}{rlrl}(\text{1})& & t(c_k,G_n)& =\sum _{i=1}^n{\lambda }_i^k\\ (2)& & t(c_k,G_n)& \to \tilde{t}(c_k,W)\end{array}$$

where

• $c_k$ is the $k$-cycle graph
• $t$ is the graph homomorphism density
• $\tilde{t}$ is the graphon homomorphism density

(the full proof involves writing out the expressions for (1) and showing (2) that the elements in the sum converge pointwise. We do not show this for this class.)