graph sequence converges if and only if the induced graphon sequence converges

[[concept]]

Theorem

Sequences of graphs ${G_{n}}$ converging to graphon $W$ also converge in the cut norm:

G_{n} \to W ⟺ | | W_{n} - W | |_{◻} \to 0 as n \to \infty

Where $W_{n}$ is the induced graphon of $G_{n}$ .

In fact, to show that left and right convergence with the homomorphism density are equivalent is via convergence wrt the cut metric/cut norm as above.

Proofs are in the book Large networks and convergent graph sequences by Lavàsz (online). For the equivalence in homomorphism density, see section counting and inverse counting lemmas.

Mentions

File
convergence bound for graph convolutions
2025-03-26 lecture 15
2025-04-07 lecture 18

Created 2025-03-26 Last Modified 2025-05-13