cycle homomorphism density is given by the trace of the adjacency matrix

[[concept]]

claim

Let $C_k$ be the $k$-cycle. Let $G$ be a graph with adjacency matrix eigenvalues ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$

For $k\ge 4$, we have $t(C_k,G)=\frac{\left({\sum }_i{\lambda }_i^k\right)}{n^k}$

Proof

Note that $\text{hom}(C_k,G)={\sum }_{i,j,k,\ell ,\dots }(A_{ij}{A}_{jk})A_{k\ell }{A}_{\ell m}\dots A_{\zeta i}$ $={\sum }_{i,k,\ell }{\sum }_j(A_{ij}{A}_{jk})A_{k\ell }{A}_{\ell m}\dots A_{\zeta i}$ $={\sum }_{i,k,\ell }[A^2{]}_{ik}{A}_{kl}{A}_{\ell m}\dots A_{\zeta i}$ $=⋮$ $={\sum }_i[A^k{]}_{ii}=\mathrm{Tr}(A^k)={\sum }_i{\lambda }^k$

Thus $t(c_k,G)=\frac{{\sum }_i{\lambda }_i^k}{n^k}$

Note

This implies that cycles can be counted using a convolutional GNN with white input (see Lecture 9) with graph shift operator $S=\frac{A}{n}$.

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