convergent graph sequence

[[concept]]

Sequence of Convergent Graphs

Let ${G_{n}}_{n}$ be a graph sequence such that $lim_{n \to \infty} t (F, G_{n}) = \tilde{t} (F, W)$ for all motifs $F$ where

$t (\cdot)$ is the graph homomorphism density
$\tilde{t} (\cdot)$ is the graphon homomorphism density and
$W$ is a graphon

Then ${G_{n}}$ is a convergent graph sequence with limit $W$ .

Note on Initial Idea of Convergent Graph Sequence

This is a {“local”} idea of convergence since it checks to see if {sampled subgraphs converge "in distribution" up to the limiting object}. This is called {left convergence since it deals with left homomorphism densities} $t (F, G_{n})$ and $\tilde{t} (F, W)$ .

(we count the occurrences of the motif within the graph/graphon)
^note-1

Note

This is not the only way to identify a (dense) convergent graph sequence. Another definition is based on the convergence of {min-cuts or right homomorphisms} $t (G_{n}, F)$ and $\tilde{t} (W, F)$ .

This is a {more “global”} notion of convergence that is used sometimes by graph theorists or in physics (micro-canonical ground state energy)
^note-2

Note

For dense graphs, left and right convergence are equivalent (for the metric we like) without proof.
^note-3

Review

#flashcards/math/dsg

Mentions

File
Davis-Kahan Theorem
eigenvalues of the induced graphon converge pointwise to the eigenvalues of the limit
graph sequence converges if and only if the induced graphon sequence converges
graph shift operators converge to graphon shift operators
lipschitz graph convolutions of graph signals converge to lipschitz graphon filters
the graph convolution converges to the graphon convolution in the spectral domain for a convergent sequence of graph signals
2025-03-24 graphs lecture 14
2025-03-26 lecture 15
2025-03-31 lecture 16
2025-04-02 lecture 17
2025-04-07 lecture 18

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>
}