Skip to main content
added some top-level tags
Link
Yemon Choi
  • 25.8k
  • 9
  • 69
  • 156
Source Link
abcd
  • 367
  • 1
  • 6

A Question on Graph Limits

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!