convergence in L-p implies convergence in cut norm

[[concept]]

Theorem

Let $W : [0, 1]^{2} \to [- 1, 1]$ . Then

| | W | |_{◻} \overset{(1)}{\leq} | | W | |_{1} \overset{(2)}{\leq} | | W | |_{2} \overset{(3)}{\leq} | | W | |_{\infty} \overset{(4)}{\leq} 1

And convergence $L_{p}$ for $p \geq 1$ implies convergence in the cut norm

Proof

Easy to see (1) from the definition of the cut norm:

cut norm (kernels)

Let $W$ be a kernel in $[0, 1]^{2}$ . Its cut norm is defined as
$| | W | |_{◻} = sup_{S, T \subseteq [0, 1]} | \int \int_{S \times T} W (u, v) d u d v |$

This is computing the L-1 norm restricted to a subset of the nodes, so $| | W | |_{◻} \leq | | W | |_{1}$ .

(2) and (3) are a common result from functional analysis, and (4) is because of the selected codomain for $W$ .

Convergence in the cut norm follows immediately from this hierarchy.

Mentions

File
template graphs converge to the graphon
2025-03-26 lecture 15

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