A Partial Characterization of Robinsonian $L^p$ Graphons

Abstract

We present a characterization of Robinsonian $L^p$ graphons for $p>5$. Each $L^p$ graphon $w$ is the limit object of a sequence of edge density-normalized simple graphs $\{G_n/\Vert G_n{\Vert }_1\}$ under the cut distance $\hat{I}{´}_{\square }$. A graphon $w$ is Robinson if it satisfies the Robinson property: if $x\le y\le z$, then $w(x,z)\le \min \{w(x,y),w(y,z)\}$, and it is Robinsonian if $\hat{I}{´}_{\square }(w,u)=0$ for some Robinson $u$. In previous work, the author and collaborators introduced a graphon parameter $\hat{I}›$ that recognizes the Robinson property, where $\hat{I}›(w)=0$ precisely when $w$ is Robinson. Using functional analytic arguments, we show here that for $p>5$, the Robinsonian $L^p$ graphons $w$ are precisely those that are the cut distance limit object of graphs $G_n$ such that $\hat{I}›(G_n/\Vert G_n{\Vert }_1)\to 0$.

9 pages, 1 figure