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.

Mentions

File
2025-03-26 lecture 15

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