fully random graphs converge to the graphon in probability

[[concept]]

Theorem

Let ${G_{n}}$ be a sequence of "fully random" graphs sampled from graphon $W$ . With probability at least $1 - \exp (- \frac{n}{2 \log n})$ ,

δ_{◻} (G_{n}, W) \leq \frac{22}{\sqrt{\log n}}

Where $δ_{◻}$ is the cut metric. ie, $G_{n} \to W$ in probability.

File
2025-03-26 lecture 15

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