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 $λ_{1}, λ_{2}, \dots, λ_{n}$

For $k \geq 4$ , we have

t (C_{k}, G) = \frac{(\sum_{i} λ_{i}^{k})}{n^{k}}

Proof

Note that

hom (C_{k}, G) = \sum_{i, j, k, ℓ, \dots} (A_{i j} A_{j k}) A_{k ℓ} A_{ℓ m} \dots A_{ζ i}

= \sum_{i, k, ℓ} \sum_{j} (A_{i j} A_{j k}) A_{k ℓ} A_{ℓ m} \dots A_{ζ i}

= \sum_{i, k, ℓ} [A^{2}]_{i k} A_{k l} A_{ℓ m} \dots A_{ζ i}

= ⋮

= \sum_{i} [A^{k}]_{i i} = Tr (A^{k}) = \sum_{i} λ^{k}

Thus $t (c_{k}, G) = \frac{\sum_{i} λ_{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}$ .

File
2025-03-03 graphs lecture 11