A Question on Graph Limits

Question

I have a somewhat technical question about the concept of graph limits:

Suppose that $G_n$ is a sequence of labelled, simple, unweighted graphs, and let $W_n$ denote the graphon of $G_n$ (i.e. $W_n(x,y) = 1$ for all $\frac{i-1}{n}<x\leq \frac{i}{n}$ and $\frac{j-1}{n} < y \leq \frac{j}{n}$, whenever $(i,j)$ or $(j,i)$ forms an edge of $G_n$). Now, suppose that $W_n$ converges in cut distance to a graphon $W$ (see page $17 - 18$ of https://arxiv.org/pdf/math/0702004.pdf for the definition of cut distance). Then, does it follow that there exists a sequence $\pi_n$ of permutations of $\{1,...,n\}$, such that the graphons corresponding to the permuted graphs $G_n^{\pi_n}$ converges in cut norm to $W$? By a permuted graph $G^\pi$, I mean that the nodes of $G$ are relabelled by the permutation $\pi$ in $G^\pi$, i.e. the $i^{th}$ vertex of $G^\pi$ is $\pi(i)$, if the ith vertex of $G$ is $i$.

Any help will be greatly appreciated!

Answer 1

It looks so. $W$ may be approximated with prescribed accuracy $\varepsilon$ in a cut-norm (and even in $L^1$) by a graphon $W_\varepsilon$ which corresponds to a certain finite graph (that is, the function $W_\varepsilon(x,y)$ depends only on integer parts of $Nx,Ny$ for certain large $N$.) And for large $n$ the distance from $W_n^\varphi$ (where $\varphi$ runs over measure-preserving transforms of $[0,1]$) to $W^\varepsilon$ is almost realized on the map corresponding to some permutation $\pi_n$.