Moments of Two-Variable Functions and the Uniqueness of Graph Limits

Introduction

Our interest in these integrals stems from graph theory (see next paragraph), but such integrals appear in physics, statistics, and other areas. In many respects, these integrals can be thought of as 2-variable analogues of moments of 1-variable functions, so instead of moment sequences, such $2$-variable functions have a ”moment graph parameter” (function defined on graphs). Just like moments of a 1-variable function determine the function up to measure preserving transformations, these “moments” determine the 2-variable function up to measure preserving transformations. The exact formulation and proof of this fact is the main goal of this paper.

Our main motivation for this study comes from the theory of convergent graph sequences. Let $F$ and $G$ be two simple graphs (graphs without loops and multiple edges). Let us map the nodes of $F$ randomly into $V(G)$, and let $t(F,G)$ denote the probability that this map preserves adjacency. For example, $t(K_{2},G)$ denotes the edge density of $G$. In general, we call $t(F,G)$ the homomorphism density or simply the density of $F$ in $G$.

We call a sequence of simple graphs $(G_{n})$ convergent, if $t(F,G_{n})$ has a limit for every simple graph $F$. The notion of convergent graph sequences was introduced by Borgs, Chayes, Lovász, Sós and Vesztergombi , see also , and further studied in and . Lovász and Szegedy proved that every convergent graph sequence has a “limit object” in the form of a function $W\in{\cal W}_{0}$ in the sense that

for every simple graph $F$. In this case we say that $G_{n}$ converges to $W$. It was also shown in that for every function $W\in{\cal W}_{0}$ there is a convergent sequence $(G_{n})$ of simple graphs converging to $W$. To complete the picture, the results in this paper imply that the limit object is unique up to measure preserving transformations.

Results

For the precise statement of our results, we need some definitions. Instead of the interval $$, we consider two-variable functions on an arbitrary probability space; while this does not add real generality it leads to a cleaner picture. We need a few definitions.

We start by recalling some basic notions from probability theory. Let $(\Omega,{\cal A},\pi)$ be a probability space (where $\Omega$ is the underlying set, ${\cal A}$ is a $\sigma$-algebra on $\Omega$, and $\pi$ is a probability measure on ${\cal A}$). As usual, $(\Omega,{\cal A},\pi)$ is called complete if ${\cal A}$ contains all sets of external measure $0$, and the completion of $(\Omega,{\cal A},\pi)$ is obtained by replacing ${\cal A}$ with the $\sigma$-algebra generated by ${\cal A}$ and all subsets $N\subset\Omega$ of external measure $0$.

Let $(\Omega,{\cal A},\pi)$ and $(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime})$ be probability spaces, and let $\phi$ be a measure preserving map from $\Omega$ to $\Omega^{\prime}$. The map $\phi$ is called an isomorphism if it is a bijection between $\Omega$ and $\Omega^{\prime}$ and both $\phi$ and $\phi^{-1}$ are measure preserving, and it is called an isomorphism mod $0$ if there are null sets $N\in{\cal A}$ and $N^{\prime}\in{\cal A}^{\prime}$ such that the restriction of $\phi$ to $\Omega\setminus N$ is an isomorphism between $\Omega\setminus N$ and $\Omega^{\prime}\setminus N^{\prime}$ (equipped with the suitable restrictions of $({\cal A},\pi)$ and $({\cal A}^{\prime},\pi^{\prime})$, respectively). In the last case $(\Omega,{\cal A},\pi)$ and $(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime})$ are called isomorphic mod $0$.

It turns out that several of our results require a little bit more structure than that of an arbitrary probability space. In particular, we will consider Lebesgue spaces, i.e., complete probability spaces that are isomorphic mod $0$ to the disjoint union of a closed interval (equipped with the standard Lebesgue sets and Lebesgue measure) and a countable set of atoms. See , Section 2.2 for an axiomatic definition of Lebesgue spaces, and Section 2.4 for the proof that a probability space is Lebesgue if and only if it is isomorphic mod 0 to the disjoint union of a closed interval and a countable set of atoms.

We are now ready to introduce the main objects studied in this paper.

From our point of view, graphons obtained by changing $W$ on a set of measure $0$, or changing the $\sigma$-algebra ${\cal A}$ so that $W$ remains measurable, do not differ essentially from the original. However, for technical reasons we have to distinguish them. We say that a graphon is strong, if $W$ is measurable with respect to ${\cal A}\times{\cal A}$ (not just the completion of it). We can always change $W$ on a set of measure $0$ to make the graphon strong (Theorem 3.2(i)).

We say that $H$ is complete, if the underlying probability space is complete, and we say that it is Lebesguian, if the underlying probability space is a Lebesgue space. The completion, $\overline{H}$, of $H$ is obtained by completing the underlying probability space, i.e., by replacing ${\cal A}$ by its completion $\overline{{\cal A}}$.

Let $H=(\Omega,{\cal A},\pi,W)$ be a graphon, and let $F$ be a finite graph with $V(F)=\{1,\dots,k\}$. The definition (1) then can be extended as

Let $H=(\Omega,{\cal A},\pi,W)$ and $H^{\prime}=(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime},W^{\prime})$ be two graphons. The goal of this paper is to determine necessary and sufficient conditions under which

To this end, we will introduce two different notions of isomorphism. Both will be expressed in terms of the following operation: given a graphon $H^{\prime}=(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime},W^{\prime})$ and a measure preserving map $\phi$ from a probability space $(\Omega,{\cal A},W)$ into $(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime})$, let $(W^{\prime})^{\phi}$ be “pull-back” of $W^{\prime}$, defined by $(W^{\prime})^{\phi}(x,y)=W(\phi(x),\phi(y))$. If $H=(\Omega,{\cal A},\pi,W)$ and $G=(\Gamma,{\cal B},\rho,U)$ are two graphons and $\phi:~\Omega\to Gamma$ is measure preserving from the completion $\overline{{\cal A}}$ into ${\cal B}$ such that $W=U^{\phi}$ almost everywhere, then we call $\phi$ a weak isomorphism from $H$ to $G$. Note that a weak isomorphism is not necessarily invertible.

We say that $H$ and $H^{\prime}$ are isomorphic mod 0 (in notation $H^{\prime}\cong H^{\prime}$), if there exists a map $\phi:~\Omega\to\Omega^{\prime}$ such that $\phi$ is an isomorphism mod 0 and $(W^{\prime})^{\phi}=W$ almost everywhere in $\Omega\times\Omega$. For simplicity, we often drop the qualifier mod 0.

We call $H$ and $H^{\prime}$ weakly isomorphic if there is a third graphon $G$ and weak isomorphisms from $H$ and $H^{\prime}$ into $G$. It will follow from Theorems 3.2 and 2.1 that we could require here that $G$ is a strong Lebesguian graphon.

The isomorphism relation $\cong$ is clearly an equivalence relation, and it will follow from Theorem 2.1 (ii) below that weak isomorphism is an equivalence relation as well. Every graphon is weakly isomorphic with its completion, and every pair of isomorphic graphons is weakly isomorphic. It is clear that if two graphons $H$ and $H^{\prime}$ are weakly isomorphic then (4) holds for every graph $H$. Theorem 2.1 (ii) below will show that the converse also holds.

To state our results, we need one more notion, the notion of twins. Let $H=(\Omega,{\cal A},\pi,W)$ be a graphon. Two points $x_{1},x_{2}\in\Omega$ are called twins if $W(x_{1},y)=W(x_{2},y)$ for almost all $y\in\Omega$. Note that relation of being twins is an equivalence relation. We call the graphon $H$ almost twin-free if all there exists a set $N$ of measure zero such that no two points in $\Omega\setminus N$ are twins.

2 Main results

With these definitions, we can state our main result:

(i) If $H$ and $H^{\prime}$ are almost twin-free Lebesguian graphons, then (4) holds for every simple graph $F$ if and only if $H\cong H^{\prime}$.

(ii) If $H$ and $H^{\prime}$ are general graphons, then (4) holds for every simple graph $F$ if and only if $H$ and $H^{\prime}$ are weakly isomorphic.

A natural idea of the proof of Theorem 2.1 is the following: can we bring a graphon $(\Omega,{\cal A},\pi,W)$ to a “canonical form”, so that isomorphic or weakly isomorphic graphons would have identical canonical forms? In the case of functions in a single variable, this is possible, through “monotonization”: for every bounded real function on $$there is an unique monotone increasing left-continuous function on$$ that has the same moments.

In Section 4 we’ll construct not quite a canonical form, but a “canonical ensemble”, a probability distribution $(H_{\alpha})$ of graphons on the same $\sigma$-algebra such that $H\cong H_{\alpha}$ for almost all $\alpha$, and two graphons are isomorphic if and only if their ensembles can be coupled so that corresponding graphons are identical (up to sets of measure $0$).

An important element of the proof is a curious measure-theoretic fact. Consider a 2-variable function for which all 1-variable functions obtained by fixing one of the variables are measurable. This of course does not in general imply that the 2-variable function is measurable, but it does imply it in some circumstances (see e.g. Corollary 4.2).

As we will see, the second statement of Theorem 2.1 can easily be deduced from the first. In fact, we’ll show that every graphon is weakly isomorphic to a twin-free Lebesguian graphon. (See Theorem 3.2 for more details of this isomorphism.)

We can also transform a Lebesguian graphon into a graphon whose underlying probability space is the unit interval with the Lebesgue measure, by “resolving” the atoms into intervals of the appropriate length. This form is the most elementary and therefore useful in applications; however, it is not so convenient for the purposes of this paper because we loose twin-freeness.

It is easy to see that if $H$ and $H^{\prime}$ are weakly isomorphic, then (4) holds not only for simple graphs $F$ but also for graphs with multiple edges (which we’ll call multigraphs if we want to emphasize that multiple edges are allowed; but we don’t allow loops). Thus (4) for simple graphs implies this equation for multigraphs. (This fact will be an important step in the proof, see Section 5.2.)

We can formulate our results in a probabilistic way. Recall that a coupling between two probability spaces $(\Omega,{\cal A},\pi)$ and $(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime})$ is a probability distribution on ${\cal A}\times{\cal A}^{\prime}$ whose marginals are $\pi$ and $\pi^{\prime}$, respectively. A coupling between two graphons means a coupling between their underlying probability spaces. Let $H=(\Omega,{\cal A},\pi,W)$ be a graphon, and let $X_{1},\dots,X_{n}$ be independent random samples from $\pi$. Then we have

Let $H=(\Omega,{\cal A},\pi,W)$ and $H^{\prime}=(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime},W^{\prime})$ two graphons, and suppose that there exists a coupling $\gamma$ between them such that $W(X_{1},Y_{1})=W^{\prime}(X_{2},Y_{2})$ holds with probability $1$ for two independent samples $(X_{1},X_{2})$ and $(Y_{1},Y_{2})$ from $\gamma$. In this case clearly (4) holds for every graph $F$. As we will see, Theorem 2.1 implies that in the Lebesguian case the converse also holds.

For two functions $W,W^{\prime}\in{\cal W}$ the following are equivalent.

(a) For every simple graph $F$, $t(F,W^{\prime})=t(F,W)$.

(b) For every multigraph $F$, $t(F,W^{\prime})=t(F,W)$.

(c) There exists a function $U\in{\cal W}$ and two measure preserving maps $\varphi,\psi:~\to$ such that $W=U^{\varphi}$ and $W^{\prime}=U^{\psi}$ almost everywhere.

(d) There exist two measure preserving maps $\varphi,\psi:~\to$ such that $(W^{\prime})^{\varphi}=W^{\psi}$ almost everywhere.

(e) There exists a probability measure $\gamma$ on $\times$ such that each marginal of $\gamma$ is the Lebesgue measure, and if $(X,X^{\prime})$ and $(Y,Y^{\prime})$ are two independent samples from $\gamma$, then $W(X,Y)=W^{\prime}(X^{\prime},Y^{\prime}))$ with probability $1$.

3 Examples

The property of being twin-free is crucial for Theorem 2.1 (i).

Let $\phi_{k}:~\to$ be the map $\phi_{k}(x)=kx\pmod{1}$. For any function $W\in{\cal W}$, the functions $W^{\phi_{2}}$ and $W^{\phi_{3}}$ define graphons that are weakly isomorphic but in general not isomorphic. Indeed, for a “generic” $W$ (say $W=xy$), every point has two twins in $W^{\phi_{2}}$ and three twins in $W^{\phi_{3}}$. The pair of maps in Corollary 2.2 (c) go from $W$, while in (d), they go into $(W^{\phi_{3}})^{\phi_{2}}=(W^{\phi_{2}})^{\phi_{3}}=W^{\phi_{6}}$.

Our next example shows that the Lebesgue property is also needed.

Let $\Omega$ be a subset of $$with inner Lebesgue measure$0$and outer Lebesgue measure$1$, and let$\Omega^{\prime}$be its complement. Let${\cal A}$and${\cal A}^{\prime}$consist of the traces of Lebesgue measurable sets on$\Omega$and$\Omega^{\prime}$, respectively. Let$W$and$W^{\prime}$be the restrictions of the function$xy$to$\Omega\times\Omega$and$\Omega^{\prime}\times\Omega^{\prime}$, respectively. The identical embeddings$\varphi:~\Omega\to$and$\varphi^{\prime}:~\Omega^{\prime}\to$are measure preserving, and hence$H=(\Omega,{\cal A},\pi,W)$and$H^{\prime}=(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime},W^{\prime})$are weakly isomorphic. But for every$x\in\Omega$, we have

which shows that there is no way to “match up” the points in $\Omega$ and $\Omega^{\prime}$ to get an isomorphism mod $0$. The same example shows that conclusions (d), (e) in Corollary 2.2 could not be extended to the non-Lebesgue case either.

Isomorphism

The main goal of this section is to describe how a general graphon can be transformed into a twin-free Lebesguian graphon. To this end, we have to recall some basic notions from measure theory (mostly because their usage does not seem standard), and then discuss different “isomorphism-like” mappings between graphons.

For a set ${\cal S}$ of subsets of a set $\Omega$, we denote by $\sigma({\cal S})$ the $\sigma$-algebra generated by ${\cal S}$. We call a $\sigma$-algebra ${\cal A}$ countably generated if there is countable set $S\subseteq{\cal A}$ such that $\sigma({\cal S})={\cal A}$. This is equivalent to the existence of a sequence ${\cal A}_{1}\subseteq{\cal A}_{2}\subseteq\dots$ of finite $\sigma$-algebras whose union generates ${\cal A}$.

We say that a set ${\cal S}\subseteq{\cal A}$ is a basis for the probability space $(\Omega,{\cal A},\pi)$, if $\sigma(S)$ is dense in ${\cal A}$, i.e., for every $X\in{\cal A}$ there is a $Y\in\sigma({\cal S})$ such that $\pi(X\triangle Y)=0$.

Given sets $A\subset\Omega$ and two points $x,y\in\Omega$, we say that $A$ separates $x$ and $y$ if $|\{x,y\}\cap A|=1$. We say that a set ${\cal S}$ of subsets of $\Omega$ separates $x$ and $y$ if there exists a set $A\in{\cal S}$ that separates $x$ and $y$. This leads to a partition ${\cal P}[{\cal S}]$ of $\Omega$ by placing two points in the same class if and only if they are not separated by ${\cal S}$. We say that ${\cal S}$ is separating if it separates any two points in $\Omega$. We’ll say that a graphon is separating if its underlying $\sigma$-algebra is separating.

A probability space $(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime})$ is called a full subspace of $(\Omega,{\cal A},\pi)$ if $\Omega^{\prime}$ is a (not necessarily measurable) subset of $\Omega$ of external measure $1$, ${\cal A}^{\prime}=\{A\cap\Omega^{\prime}\mid A\in{\cal A}\}$, and $\pi^{\prime}(A\cap\Omega^{\prime}))=\pi(A)$ for all $A\in{\cal A}$.

Consider two probability spaces $(\Omega,{\cal A},\pi)$ and $(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime})$ and a measure preserving map $\phi:\Omega\to\Omega^{\prime}$. The map $\phi$ is called an embedding of the first space into the second if $\phi$ is an isomorphism between $(\Omega,{\cal A},\pi)$ and a full subspace of $(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime})$. We call $\phi$ an embedding of a graphon $H=(\Omega,{\cal A},\pi,W)$ into a graphon $H^{\prime}=(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime},W^{\prime})$ if $\phi$ is an embedding of $(\Omega,{\cal A},\pi)$ into $(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime})$ and $(W^{\prime})^{\phi}=W$ almost everywhere.

2 Push-Forward and Quotients

Let $(\Omega,{\cal A},\pi)$ and $(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime})$ be probability spaces and let $\phi:~\Omega\to\Omega^{\prime}$ be a measure preserving map. We have described how to “pull back” a graphon on $(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime})$ to a (weakly isomorphic) graphon on $(\Omega,{\cal A},\pi)$. It is also possible to “push-forward” a graphon $H=(\Omega,{\cal A},\pi,W)$ to a graphon $(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime},W_{\phi})$. This is defined by the requirement that

for all $A_{1}^{\prime},A_{2}^{\prime}\in{\cal A}^{\prime}$. The next lemma states that the “push-forward” $W_{\phi}$ is well defined, and that $(W_{\phi})^{\phi}$ is a certain conditional expectation of $W$.

Let $(\Omega,{\cal A},\pi)$ and $(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime})$ be probability spaces, let $\phi:\Omega\to\Omega^{\prime}$ be a measure preserving map, and let $W$ be a graphon on $(\Omega,{\cal A},\pi)$.

(ii) Let ${\cal A}_{\phi}=\phi^{-1}({\cal A}^{\prime})$. Then $(W_{\phi})^{\phi}={\sf E}(W\mid{\cal A}_{\phi}\times{\cal A}_{\phi})$ almost everywhere.

(iii) If $\phi$ is an embedding of $(\Omega,{\cal A},\pi)$ into $(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime})$, then $(W_{\phi})^{\phi}=W$ almost everywhere.

(i) By linearity, it is easy to see that we can restrict ourselves to the case where $W$ takes values in $$. Define a measure$\mu$on${\cal A}^{\prime}\times{\cal A}^{\prime}$ by

for $A_{1}^{\prime},A_{2}^{\prime}\in{\cal A}$. With this definition, we have that

implying in particular that $\mu$ is absolutely continuous with respect to $\pi^{\prime}\times\pi^{\prime}$. Hence the Radon-Nikodym derivative,

is well defined. Using the above bound once more, together with the fact that $\mu(A_{1}\times A_{2})=\mu(A_{2}\times A_{1})$, we furthermore have that

almost everywhere. Changing $W_{\phi}$ on a set of measure zero, we may assume that these relations hold everywhere. To define $W_{\phi}$ for a general bounded function $W$, we use linearity.

(ii) Let $A_{1},A_{2}\in{\cal A}_{\phi}$, i.e., let $A_{1}=\phi^{-1}(A_{1}^{\prime})$ and $A_{2}=\phi^{-1}(A_{2}^{\prime})$ for some $A_{1}^{\prime},A_{2}^{\prime}\in{\cal A}^{\prime}$. By the definition of $W_{\phi}$, the fact that $\phi$ is measure preserving, and the definition of $(W_{\phi})^{\phi}$, we have that

This implies that $(W_{\phi})^{\phi}={\sf E}(W\mid{\cal A}_{\phi}\times{\cal A}_{\phi})$ almost everywhere.

(iii) Since $\phi$ is an isomorphism between $(\Omega,{\cal A},\pi)$ and a subspace of $(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime})$, we know that given any $A\in{\cal A}$, we can find an $A^{\prime}\in{\cal A}^{\prime}$ such that $\phi(A)=A^{\prime}\cap\phi(\Omega)$. But then $\phi^{-1}(A^{\prime})=\phi^{-1}(\phi(A))=A$, proving that $A\in{\cal A}_{\phi}$. Thus ${\cal A}_{\phi}={\cal A}$, which implies that $(W_{\phi})^{\phi}=W$ almost everywhere. ∎

We can use the “push-forward” construction to define quotients of graphons. Let $H=(\Omega,{\cal A},\pi,W)$ be a graphon, let ${\cal P}$ be an arbitrary partition of $\Omega$ into disjoint sets, and for $x\in\Omega$, let $[x]$ denote the class in ${\cal P}$ that contains the point $x$. We then define a graphon $H/{\cal P}=(\Omega/{\cal P},{\cal A}/{\cal P},\pi/{\cal P},W/{\cal P})$ and a measure preserving map $\phi:\Omega\to\Omega/{\cal P}$ as follows: the points in $\Omega/{\cal P}$ are the classes of the partition ${\cal P}$, $\phi$ is the map $\phi:x\mapsto[x]$, ${\cal A}/{\cal P}$ is the $\sigma$-algebra consisting of the sets $A^{\prime}\subset\Omega/{\cal P}$ such that $\phi^{-1}(A^{\prime})\in{\cal A}$, and $(\pi/{\cal P})(A^{\prime}):=\pi(\phi^{-1}(A^{\prime}))$. Then $\phi$ is measure preserving, and the function $W/{\cal P}=W_{\phi}$ is defined by (5).

3 Reductions

Now we are able to state the theorem that allows us to reduce every graphon to a twin-free Lebesguian graphon.

(i) Let $H=(\Omega,{\cal A},\pi,W)$ be a graphon. Then one can change the value of $W$ on a set of $\pi\times\pi$-measure $0$ to get a strong graphon.

(ii) Let $H=(\Omega,{\cal A},\pi,W)$ be a graphon. Then there exists a countably generated $\sigma$-algebra ${\cal A}_{0}\subset{\cal A}$ such that $W$ is $({\cal A}_{0}\times{\cal A}_{0})$-measurable.

(iii) Let $H=(\Omega,{\cal A},\pi,W)$ be a graphon. Then the graphon $H/{\cal P}[{\cal A}]$ is separating. If $H$ is countably generated, then so is $H/{\cal P}[{\cal A}]$.

(iv) Let $H=(\Omega,{\cal A},\pi,W)$ be a separating graphon on a probability space with a countable basis. Then the completion of $H$ can be embedded into a Lebesguian graphon.

(v) Let $H=(\Omega,{\cal A},\pi,W)$ be a graphon, and let ${\cal P}$ be the partition into the twin-classes of $H$. Then $H/{\cal P}$ is almost twin-free. If $H$ is Lebesguian, then $H/{\cal P}$ is Lebesguian as well. Furthermore, the projection $H\to H/{\cal P}$ is a weak isomorphism.

Every graphon has a weak isomorphism into a strong Lebesguian graphon.

The proof of this theorem (which is not hard, but technical) will be given in the rest of this section.

Let $H=(\Omega,{\cal A},\pi,W)$ be a graphon, and let $W^{\prime}={\sf E}(W\mid{\cal A}\times{\cal A})$. Then $W^{\prime}$ is ${\cal A}\times{\cal A}$-measurable, and changing $W^{\prime}$ on a set of measure $0$, we may assume that $W^{\prime}$ is symmetric and bounded. Moreover, $\int_{A\times A^{\prime}}(W^{\prime}-W)=0$ for all $A,A^{\prime}\in{\cal A}$, which implies that $\int_{S}(W^{\prime}-W)=0$ for all sets $S$ in the completion of ${\cal A}\times{\cal A}$, so $W=W^{\prime}$ almost everywhere. These observations prove part (i) of the Theorem.

3.2 Countable generation

We prove a simple lemma, which implies Theorem 3.2(ii), and will also be used at several other places (Sections 4.1 and 5.2).

Let ${\cal C}$ be the set of bounded, $({\cal A}\times{\cal A}^{\prime})$-measurable functions $W$ for which the statement of the lemma is true. The set ${\cal C}$ is clearly a vector space that contains the constant function $1$ as well as the indicator functions of all rectangles $A\times B$ with $A\in{\cal A}$ and $B\in{\cal A}^{\prime}$. If is further not hard to show that if $(W_{k})$ is a sequence of non-negative functions in ${\cal C}$ and $W_{k}\uparrow W$ for a bounded function $W$, then the limiting function $W$ is in ${\cal C}$ as well. By the monotone class theorem (see, e.g., Theorem 3.14 in ), we conclude that ${\cal C}$ contains all bounded functions which are measurable with respect to the $\sigma$-algebra generated by the rectangles $A\times B$, i.e., the $\sigma$-algebra ${\cal A}\times{\cal A}^{\prime}$. ∎

3.3 Merging inseparable elements

If we identify elements in the same class of the partition ${\cal P}[{\cal A}]$, we get a $\sigma$-algebra which is isomorphic under the obvious map. This implies (iii) of Theorem 3.2.

3.4 Lebesgue property

Consider a separating graphon $H=(\Omega,{\cal A},\pi,W)$, and assume that ${\cal A}$ is generated by the countable set ${\cal S}$. Then ${\cal S}$ is a basis for the completion of $(\Omega,{\cal A},\pi)$. We invoke the fact (see e.g. , Section 2.2) that any separating complete probability space with a countable basis can be embedded into a Lebesgue space. Thus there exists an embedding $\psi$ of the completion of $(\Omega,{\cal A},\pi)$ into a Lebesgue space $(\Omega^{\prime},{\cal L}^{\prime},\lambda^{\prime})$. Let $W^{\prime}$ be the push-forward of $W$, $W^{\prime}=W_{\psi}$. By Lemma 3.1, we have that $(W^{\prime})^{\psi}=W$ almost everywhere, which shows that $\psi$ is an embedding of the completion of $H$ into $(\Omega^{\prime},{\cal L}^{\prime},\lambda^{\prime},W^{\prime})$. This proves part (iv) of Theorem 3.2.

3.5 Partitions into Twin-Classes

We prove (v) in Theorem 3.2. We may assume that ${\cal A}$ is countably generated. Indeed, by Lemma 3.4, we can replace ${\cal A}$ by a countably generated $\sigma$-algebra ${\cal A}_{0}$. This does not change the relation of being twins: Two points $x,x^{\prime}\in\Omega$ are twins if and only if the set $A_{x,x^{\prime}}=\{y\in\Omega:W(x,y)=W(x,y^{\prime})\}$ has measure $1$. Since $W$ is measurable with respect to ${\cal A}_{0}\times{\cal A}_{0}$, the set $A_{x,x^{\prime}}$ lies in ${\cal A}_{0}\subset{\cal A}$, implying that $x$ and $x^{\prime}$ are twins with respect to $H$ if and only if they are twins with respect to $H_{0}$.

Let ${\cal A}_{\cal P}$ consists of those sets in ${\cal A}$ that do not separate any pair of twin points. Clearly ${\cal A}_{\cal P}$ is a $\sigma$-algebra.

$W$ is almost ${\cal A}_{\cal P}\times{\cal A}_{\cal P}$-measurable.

Let $\widetilde{W}={\sf E}(W\mid{\cal A}_{\cal P}\times{\cal A}_{\cal P})$. We want to prove that

for all $A,B\in{\cal A}$. Define the functions

Since $U_{A}(y)=U_{A}(z)$ if $y,z$ are twins, the function $U_{A}$ is ${\cal A}_{\cal P}$-measurable, similarly for $V_{A}$, and obviously for $g_{A}$. Repeatedly using the fact that $\int fg=\int f{\sf E}(g\mid{\cal A}_{0})$ if $f$ is ${\cal A}_{0}$-measurable, this implies

(where the last equality follows since $\widetilde{W}$ is ${\cal A}_{\cal P}\times{\cal A}_{\cal P}$-measurable). This implies (8) and completes the proof of Claim 1.

Let $\widetilde{W}={\sf E}(W\mid{\cal A}_{\cal P}\times{\cal A}_{\cal P})$ as before, then $H_{\cal P}=(\Omega,{\cal A}_{\cal P},\pi,\widetilde{W})$ is a graphon, which is clearly weakly isomorphic to $(\Omega,{\cal A},\pi,W)$. Let $N$ be the set of points $x\in\Omega$ for which $\{y\in\Omega:~\widetilde{W}(x,y)\not=W(x,y)\}$ has positive measure. Then clearly $N$ is a null set, and two points $x,x^{\prime}\in\Omega\setminus N$ are twins in $H$ if and only if they are twins in $H_{\cal P}$. The graphon $H/{\cal P}$ is obtained from $H_{\cal P}$ by identifying indistinguishable elements, which implies that $H/{\cal P}$ is twin-free.

To prove that $H/{\cal P}$ is Lebesguian if $H$ is Lebesguian, we invoke the fact (established in Section 3.2 of ) that $(\Omega/{\cal P},{\cal A}/{\cal P},\pi/{\cal P})$ is a Lebesgue space provided $(\Omega,{\cal A},\pi)$ is a Lebesgue space and there exists a countable set ${\cal S}\subseteq{\cal A}$ that separates two points if and only they are in different partition classes.

To construct such a set ${\cal S}$, let ${\cal T}$ be a countable set generating ${\cal A}$, closed under finite intersections. For $A\in{\cal A}$ and $x\in\Omega$, let

Since $W$ is a bounded ${\cal A}\times{\cal A}$-measurable function, the function $A\mapsto\mu_{x}(A)$ is a finite measure for all $x\in\Omega$, while the function $x\mapsto\mu_{x}(A)$ is a ${\cal A}$-measurable function on $\Omega$ for all $A\in{\cal A}$.

By definition, $x,x^{\prime}\in\Omega$ are twins iff the set $\{y\in\Omega:W(x,y)=W(x,y^{\prime})\}$ has measure zero. This is equivalent to the condition that $\mu_{x}(A)=\mu_{x^{\prime}}(A)$ for all $A\in{\cal A}$. Since the measure $\mu_{x}(\cdot)$ on ${\cal A}$ is uniquely determined by the sets in ${\cal T}$, we have that $x$ and $x^{\prime}$ are twins if and only if $\mu_{x}(T)=\mu_{x^{\prime}}(T)$ for all $T\in{\cal T}$.

For every $T\in{\cal T}$ and rational number $r$, consider the sets $S_{T,r}=\{x\in\Omega:~\mu_{x}(T)\geq r\}$. There is a countable number of these. Furthermore, if $x$ and $x^{\prime}$ are twins, then they belong to exactly the same sets $S_{T,r}$; if they are not twins, then there is a $T\in{\cal T}$ such that $\mu_{x}(T)\not=\mu_{x^{\prime}}(T)$, and for any rational number between $\mu_{x}(T)$ and $\mu_{x^{\prime}}(T)$, the set $S_{T,r}$ separates $x$ and $x^{\prime}$.

4 Isomorphism and Weak Isomorphism

We conclude this section with relating isomorphism and weak isomorphism.

Let $H_{i}=(\Omega_{i},{\cal A}_{i},\pi_{i},W_{i})$ be graphons with the Lebesgue property ($i=1,2$), and let $\phi:~\Omega_{1}\to\Omega_{2}$ be measure-preserving. If $H_{1}$ is almost twin-free, and $W_{1}=W_{2}^{\phi}$ almost everywhere, then $\phi$ is an isomorphism mod $0$, so in particular $H_{1}\cong H_{2}$.

and let $N_{1}=\Omega_{1}\setminus\Omega_{1}^{\prime}$. Then $\pi_{1}(N_{1})=0$ by Fubini and our assumption that $W_{1}=W_{2}^{\phi}$ almost everywhere.

Let $N_{1}^{\prime}$ be a nullset such that all twin-classes of $H_{1}$ have at most one point in $\Omega_{1}\setminus N_{1}^{\prime}$, and let $\phi^{\prime}$ to be the restriction of $\phi$ to $\Omega_{1}^{\prime}\setminus N_{1}^{\prime}$. Then $\phi^{\prime}$ is injective: indeed, if $x_{1},x_{2}\in\Omega_{1}^{\prime}\setminus N_{1}^{\prime}$ and $\phi(x_{1})=\phi(x_{2})$, then $W_{1}(x_{1},y)=W_{2}(\phi(x_{1}),\phi(y))=W_{2}(\phi(x_{2}),\phi(y))=W_{1}(x_{2},y)$ for almost all $y$ by the definition of $\Omega_{1}^{\prime}$, hence $x_{1}$ and $x_{2}$ are twins, a contradiction. As shown in , Section 2.5, an injective measure preserving map between Lebesgue spaces has a measurable inverse defined almost everywhere. This implies that $\phi^{\prime}:\Omega_{1}^{\prime}\setminus N_{1}^{\prime}\to\Omega_{2}$ is an isomorphism mod $0$, which shows that $\phi$ is an isomorphism mod $0$ as well. ∎

If two twin-free graphons with the Lebesgue property are weakly isomorphic, then they are isomorphic.

Canonical Ensembles

We could try to construct a “canonical form” of a graphon by assigning “tags” to the points in $\Omega$. For example, we could tag a point $x$ with its marginal $d(x)=\int W(x,y)\,d\pi(y)$, or by the sequence of marginals of higher powers of $W$. This, however, would not work: for example, there could be a transitive group of measure-preserving permutations of $\Omega$ leaving $W$ invariant, and then all points would still have the same tag.

To break the symmetry, we select an infinite sequence $\alpha=(a_{1},a_{2},\dots)$ of points in $\Omega$, which we call anchor points. Now we can tag each point $x\in\Omega$ with the sequence

We will show that if $\alpha_{1},\alpha_{2},\dots$ are taken i.i.d. at random with distribution $\pi$ then with probability one, then $H_{\alpha}$ is isomorphic mod $0$ to the original graphon $H$ (see Section 4.2 for details). So using an infinite sequence of independent random points as anchor points, the tags of the points contain all information about the points.

These tags are almost canonical, except for the choice of the sequence $\alpha$. So instead of a canonical form, we get a “canonical ensemble”, a probability distribution $(H_{\alpha})$ of graphons such that $H\cong H_{\alpha}$ for almost all $\alpha$, and two graphons are isomorphic if and only if their ensembles can be coupled so that corresponding graphons are isomorphic.

To prove Theorem 2.1 (i), we will therefore have to show that if $H$ and $H^{\prime}$ satisfy (4), then we can “couple” the choice of anchor points $\alpha$ in $H$ and $\beta$ in $H^{\prime}$ so that $H_{\alpha}\cong H^{\prime}_{\beta}$, thus yielding an isomorphism of $H$ and $H^{\prime}$. This second step in the proof will be carried out in Section 5.3.

The next technical lemma will be important in the construction of “canonical ensembles”.

By Lemma 3.4, we may assume that ${\cal A}$ and ${\cal A}^{\prime}$ are countably generated. Let ${\cal A}^{\prime}_{1}\subset{\cal A}^{\prime}_{2}\subset\dots$ and ${\cal A}^{\prime}_{1}\subset{\cal A}^{\prime}_{2}\subset\dots$ be a sequence of finite $\sigma$-algebras with $\sigma(\cup_{n}{\cal A}_{n})={\cal A}$ and $\sigma(\cup_{n}{\cal A}^{\prime}_{n})={\cal A}^{\prime}$, and let $P_{n}^{\prime}$ denote the partition of $\Omega^{\prime}$ into the atoms of ${\cal A}^{\prime}_{n}$. For $y\in S\in P_{n}^{\prime}$ with $\pi^{\prime}(S)>0$, define

We define $U_{n,m}(x,y)=0$ if $y\in S\in P_{n}^{\prime}$ with $\pi^{\prime}(S)=0$.

First we prove that for every $n\geq 1$, every $A\in{\cal A}$ and $A^{\prime}\in{\cal A}^{\prime}_{n}$, we have with probability $1$

It suffices to prove this in the case when $A^{\prime}=S\in P_{n}^{\prime}$ and $\pi^{\prime}(S)>0$. Then for every $y_{0}\in A^{\prime}$, we have

Since both sides are independent of $y_{0}\in S$, integrating over $y_{0}\in S$ equation (11) follows.

The number of choices of $n$, $A\in\cup_{k}{\cal A}_{k}$ and $A^{\prime}\in{\cal A}^{\prime}_{n}$ is countable, and hence it follows that with probability 1, (11) holds for all $n\geq 1$, every $A\in\cup_{k}{\cal A}_{k}$ and $A^{\prime}\in{\cal A}^{\prime}_{n}$. Since $\cup_{k}{\cal A}_{k}$ is dense in ${\cal A}$, this implies that (11) holds for all $n\geq 1$, every $A\in{\cal A}$ and $A^{\prime}\in{\cal A}^{\prime}_{n}$.

From now on, we suppose that the choice of the $Y_{i}$ is such that this holds.

For a fixed $n$, the indices $m$ have a subsequence $m_{1}<m_{2}<\dots$ such that $U_{n,m_{j}}$ converges to some function $U_{n}$ in the weak-$*$-topology of $L_{\infty}({\cal A}_{0}\times{\cal A}^{\prime}_{n})$. Hence by (11),

for all $n\geq 1$, every $A\in{\cal A}$ and $A^{\prime}\in{\cal A}^{\prime}_{n}$. Thus $U_{n}$ is a representative of ${\sf E}(W\mid{\cal A}\times{\cal A}^{\prime}_{n})$. Since $U_{n}$ is ${\cal A}_{0}\times{\cal A}^{\prime}_{n}$ measurable, it is also a representative of ${\sf E}(W\mid{\cal A}_{0}\times{\cal A}^{\prime}_{n})$. This shows that for every $n\geq 1$ we have

By Levy’s Upward Theorem, the left hand side of (12) tends to ${\sf E}(W\mid{\cal A}\times{\cal A}^{\prime})=W$ almost everywhere. The right hand side of (12) tends to ${\sf E}(W\mid{\cal A}_{0}\times{\cal A}^{\prime})$ almost everywhere, so $W={\sf E}(W\mid{\cal A}_{0}\times{\cal A}^{\prime})$ almost everywhere, which proves the Lemma. ∎

We formulate a couple of corollaries, the first of which is immediate:

Let $(\Omega,{\cal A},\pi,W)$ be a graphon, and let $X_{1},X_{2},\dots$ be independent random points from $\Omega$. Let ${\cal A}_{0}\subseteq{\cal A}$ be the (random) $\sigma$-algebra generated by the functions $W(\cdot,X_{k})$. Then with probability $1$, $W$ is almost ${\cal A}_{0}\times{\cal A}_{0}$-measurable.

Let ${\cal A}_{1}$ denote the $\sigma$-algebras generated by the functions $W(\cdot,X_{2k})$. Clearly ${\cal A}_{1}\subseteq{\cal A}_{0}$. By Lemma 4.1, $W$ is almost ${\cal A}_{1}\times{\cal A}$ measurable with probability $1$, so we can change it on a set of measure $0$ to get an ${\cal A}_{1}\times{\cal A}$ measurable function $W^{\prime}$. Let ${\cal A}_{2}^{\prime}$ be the $\sigma$-algebras generated by the functions $W^{\prime}(X_{2k+1},\cdot)$. Applying the lemma again, we get that $W^{\prime}$ is almost ${\cal A}_{1}\times{\cal A}_{2}^{\prime}$ measurable. With probability $1$, each function $W(X_{2k+1},\cdot)$ differs from $W^{\prime}(X_{2k+1},\cdot)$ on a set of measure $0$ only (since the $X_{2k+1}$ are independent of ${\cal A}_{1}$), and so ${\cal A}_{2}^{\prime}\subseteq\sigma({\cal A}_{0})$. So $W^{\prime}$ is ${\cal A}_{0}\times\sigma({\cal A}_{0})$ measurable, which implies that $W^{\prime}$, and hence $W$, are almost ${\cal A}_{0}\times{\cal A}_{0}$ measurable. ∎

2 Anchor Sequences

Let ${\cal A}_{\alpha}$ denote the $\sigma$-algebra of subsets of $\Omega$ of the form $\Phi_{\alpha}^{-1}(A)$, where $A\in{\cal L}$. Note that ${\cal A}_{\alpha}\subseteq{\cal A}$ by the fact that $\Phi_{\alpha}$ is measurable. Further, almost by definition, ${\cal A}_{\alpha}$ is the smallest sub-$\sigma$-algebra of ${\cal A}$ such that all the functions $W(\cdot,\alpha_{i})$ are measurable. As a consequence, we may apply Lemma 4.3 to conclude that for almost all $\alpha$, $W$ is almost ${\cal A}_{\alpha}\times{\cal A}_{\alpha})$-measurable, which by Lemma 3.1 gives that $W=W_{\alpha}^{\Phi_{\alpha}}$ almost everywhere. ∎

Let $H$ be a twin free graphon with the Lebesgue property. If $\alpha$ is regular, then $\Phi_{\alpha}$ is an isomorphism mod $0$ and $H_{\alpha}\cong H$.

Coupling

We recall some notions from . A partially labeled graph is a finite graph in which some of the nodes are labeled by different nonnegative integers. Two partially labeled graphs are isomorphic, if there is a label-preserving isomorphism between them. A $k$-labeled graph is a partially labeled graph with labels $1,\dots,k$.

Let $F_{1}$ and $F_{2}$ be two partially labeled graphs. Their product $F_{1}F_{2}$ is defined as follows: we take their disjoint union, and then identify nodes with the same label (retaining the labels, and any multiple edges which this might create). For two unlabeled graphs, $F_{1}F_{2}$ is their disjoint union. Clearly this multiplication is associative and commutative.

It is easy to see that if $F_{1}$ and $F_{2}$ are two $k$-labeled graphs, then

2 Multiple Edges

Let $H=(\Omega,{\cal A},\pi,W)$ and $H^{\prime}=(\Omega^{\prime},{\cal A}^{\prime},\pi^{\prime},W^{\prime})$ be two graphons, and assume that $t(F,H)=t(F,H^{\prime})$ for every simple graph $F$. Then $t(F,H)=t(F,H^{\prime})$ for every multigraph $F$.