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

[[concept]]

Theorem

Let $\{G_n\}$ be a convergent graph sequence with limit graphon $W$. Then ${\lim }_{n\to \infty }\frac{{\lambda }_j(A_n)}{n}={\lambda }_j(W)={\lim }_{n\to \infty }{\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$

Proof

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

T_{W_{n}} \varphi(v) &= \int _{0}^1 W_{n}(u,v) \varphi(u)\, du &= \lambda \varphi(v) \\ &= \int _{0}^1 \sum_{i,j=1}^n [A_{n}]_{ij} \mathbb{1}(u \in I_{i}) \mathbb{1}(v \in I_{j}) \varphi(u)\, du &= \lambda \varphi(v) \\ &= \mathbb{1}(v \in I_{j}) \int _{0}^1 \sum_{i,j=1}^n [A_{n}]_{ij} \mathbb{1}(u \in I_{i}) \varphi(u) \, du &= \lambda \varphi(v) \\ \implies &= \sum_{i,j=1}^n [A_{n}]_{ij} \int _{0}^1 \mathbb{1}(u \in I_{i}) \varphi(u) \, du &=\lambda \varphi(v \in I_{j}) \end{aligned} $$ LHS is a constant for each $v \in I_{j}$. This means that $\varphi$ is a step function $\varphi(v \in I_{j}) = x_{j}$. Thus, we can rewrite the last line as $$\begin{aligned} \lambda x_{j} &= \sum_{i=1}^n [A_{n}]_{ij} x_{i} \frac{1}{n} \end{aligned}$$ since for each $i$ we have $\varphi(u) = \begin{cases} x_{i},\,\,x_{i} \in I_{i}\\0, \,\,\,\text{otherwise}\end{cases}$ . The above is just a matrix multiplication, so we get $$\begin{align} \implies \lambda x &= \frac{1}{n} A_{n}x \\ \implies \lambda_{j} (T_{W_{n}}) &= \frac{\lambda_{j}(A_{n})}{n} \;\;\;\forall j \end{align}$$ For convergence, this means that $$\begin{align} (\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{align}$$ where - $c_{k}$ is the $k$-cycle graph - $t$ is the graph [[Concept Wiki/homomorphism density]] - $\tilde{t}$ is the [[Concept Wiki/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.)

Mentions

Mentions

TABLE
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link), 1, "") + choice(contains(author, this.file.link), 1, "") + choice(contains(director, this.file.link), 1, "") + choice(contains(source, this.file.link), 1, "") as direct_source
 
WHERE !direct_source
SORT file.name ASC

const { dateTime } = await cJS()
 
return function View() {
	const file = dc.useCurrentFile();
	return <p class="dv-modified">Created {dateTime.getCreated(file)}     ֍     Last Modified {dateTime.getLastMod(file)}</p>
}