Proof. (i) Follows by observing that $|x\log x+(1-x)\log (1-x)|\leq \log 2$ and $|x\log p|+|(1-x)\log p|\leq x| \log \beta |+(1-x)|\log \beta |=-\log \beta$ .

(ii) Follows from uniform continuity of the function $x\mapsto x\log x+(1-x)\log (1-x)$ .

(iii) and (iv) are elementary exercises left to the reader.

Proof. Since $h_0(x) =\infty$ for $x \not =0$ and $h_1(x)=\infty$ for $x \not =1$ , it follows that $I_{W_0}(f)=\infty$ when $f \not \in \mathcal{W}_\Omega$ . To bound $I_{W_0}(f)$ for $f\in \mathcal{W}_\Omega$ , observe that

(11) \begin{equation} I_{W_0}(f) = \frac {1}{2}\int _{\Omega } h_{W_0(x,y)} \left (f(x,y)\right ) dx dy, \end{equation}

since $f$ and $W_0$ agree on $ \Omega ^c$ . The proof is completed by invoking Lemma 33 (i).

Proof. Fix $\varepsilon \gt 0$ . By Lemma 33 (ii) there exists an $\eta \gt 0$ such that $|h_p(u)- h_p(v)| \leq \varepsilon$ whenever $|u-v| \leq \eta$ and $p\in [\beta ,1-\beta ]$ . Inserted into (11), this completes the proof.

Proof. First, we consider the case $f \not \in \mathcal{W}_\Omega$ (in which case $ I_{W_0}(f)=\infty$ by Proposition 34). Then there exists $\Gamma \subseteq [0,1]^2$ with positive measure such that $W_0(x,y)\in \{0,1\}$ and $W_0(x,y) \not = f(x,y)$ for $(x,y) \in \Gamma$ . Choosing

\begin{equation*} a_M(x,y)= \begin{cases} 0 & (x,y) \not \in \Gamma \\[5pt] M & W_0(x,y)= 0\\[5pt] -M & W_0(x,y)= 1. \end{cases} \end{equation*}

and taking $M \to \infty$ , we see that $\sup _{a\in S} K_{W_0}(f,a)=\infty$ in this case.

Next we consider the case $f \in \mathcal{W}_\Omega$ . Recalling the definition of $G_p$ from Lemma 33 and noting that the integrand in (12) is zero if $W_0(x,y)=f(x,y) \in \{0,1\}$ , we then have $K_{W_0}(f,a)=\int _\Omega G_{W_0(x,y)}(a(x,y),f(x,y))dxdy$ . Combined with (11) and Lemma 33 (iii), this shows that

\begin{equation*} I_{W_0}(f)=\frac 12 \int _\Omega h_{W_0(x,y)}(f(x,y))dxdy\geq \frac 12 \sup _{a\in S}\int _\Omega G_{W_0(x,y)}(a(x,y),f(x,y))dxdy =\frac 12 \sup _{a\in S} K_{W_0}(f,a). \end{equation*}

To prove equality, we may w.l.o.g. assume that the right hand side is finite. We may further restrict the integrals on both sides to the subset $\tilde \Omega \subset \Omega$ where $f(x,y)\not \in \{0,1\}$ , since the contributions of both sides to the complement can easily be seen to be equal. Finally, on $\tilde \Omega$ , we may use Lemma 33 (iv) to conclude that

\begin{equation*} \int _{\tilde \Omega } h_{W_0(x,y)}(f(x,y))dxdy=\int _{\tilde \Omega } G_{W_0(x,y)}(a_0(x,y),f(x,y))dxdy \end{equation*}

where $a_0(x,y)=\log \left (\frac {f(x,y)}{1-f(x,y)}\frac {1-W_0(x,y)}{W_0(x,y)}\right )$ . If $a_0\in L^2(\tilde \Omega )$ , the right hand side is bounded by the $\sup$ over all $a\in S$ , giving the desired upper bound. If it is not, we replace $\tilde \Omega$ on both sides by its intersection with the set of points for which $|a_0(x,y)|\leq M$ before bounding the right hand side by a $\sup$ over all square integrable $a$ . The proof is concluded by using the monotone convergence theorem.

Proof. Let $\{f_n\;:\; n \geq 1\} \subseteq \mathcal{W}_\Omega$ be a convergent sequence of graphons satisfying $d_\square (f_n, f) \to 0$ for some $f \in \mathcal{W}$ . Then on each block $I \times J$ of $W_0$ that takes value $0$ or $1$ , $f_n= W_0$ for all $n \geq 1$ . Since $|\int _{I \times J} f_n - f | \leq d_\square (f_n, f)$ and $d_\square (f_n, f) \to 0$ , it follows that $f= W_0$ on $I \times J$ . Thus $f \in \mathcal{W}_\Omega$ .

Proof. We show that $f^*$ is lower semi-continuous on $S$ by demonstrating that for all $\alpha \in \mathbb{R}$ , the set $\{x \in S |f^{*}(x) \gt \alpha \}$ is open. Observe

\begin{equation*} \{x \in S |f^{*}(x) \gt \alpha \}=\{x \in F | f(x) \gt \alpha \} \cup \left ( S \setminus F\right ).\end{equation*}

By lower semi-continuity of $f$ on $F$ , $A=\{x \in F | f(x) \gt \alpha \}$ is open in $F$ , and so $A^c$ is relatively closed with respect to $F$ and therefore closed in $S$ (since $F$ is closed). It follows that

\begin{equation*}\{x \in S | f^*(x) \gt \alpha \}^c= F \cap A^c\end{equation*}

is closed, and so we conclude that $\{x \in S | f^*(x) \gt \alpha \}$ is open.

Proof. First, note that by Propositions 37 and 38, and the observation that $I_{W_0}(f) =\infty$ for all $f \in \mathcal{W} \setminus \mathcal{W}_\Omega$ , it is enough to establish that $I_{W_0}$ is lower semi-continuous on $(\mathcal{W}_\Omega , d_\square )$ . Second, by Proposition 36, $I_{W_0}$ can be written as supremum over the functions $K_{W_0}(\cdot ,a)$ , so it will be enough to show that for all $a\in S$ , the function $K_{W_0}(\cdot ,a)$ is continuous on $(\mathcal{W}_\Omega , d_\square )$ .

Consider two functions $f,g\in \mathcal{W}_\Omega$ , and observe that every $a\in S$ can be approximated by step functions in $L^2$ . Given $\varepsilon$ and $a$ we can therefore find $k\lt \infty$ and a $k$ -step function $a_k$ such that $\|a-a_k\|_2\leq \frac \varepsilon 2$ . As a consequence

\begin{align*} \Big |K_{W_0}(f,a)-K_{W_0}(g,a)\Big| &= \Big |\int a(f-g)\Big |\leq \|a(f-g)\|_1\leq \|a_k(f-g)\|_1+\frac \varepsilon 2 \leq \|a_k\|_\infty k^2 d_{\square }(f,g)\nonumber \\&\quad+ \frac \varepsilon 2. \end{align*}

This is smaller than $\varepsilon$ if $d_{\square }(f,g)\lt \varepsilon /( \|a_k\|_\infty k^2)$ , which proves that $K_{W_0}( \cdot , a)$ is continuous on $(\mathcal{W}_\Omega , d_\square )$ , as required.

Proof. Noting that our definition of $J_{W_0}$ agrees with the definition of $J_{W_0}$ given in [Reference Dhara and Sen20] whenever $f \in \mathcal{W}_\Omega$ , and that $\delta _{\square }(f,W_0)\gt 0$ if $f \notin \mathcal{W}_\Omega$ , the proposition follows from the analogous statement in [Reference Dhara and Sen20, Lemma 2.2].

Proof. Let $s_k$ be such that $\sqrt {{20}/{\log _2s_k}}\leq 1/k$ , let $q_1$ be such that the lengths of the intervals described by $\gamma$ are integer multiples of $1/q_1$ , define $q_k$ inductively by $q_k=s_kq_{k-1}$ , and let $\mathcal P_k$ be the partition of $[0,1]$ into intervals of lengths $1/q_k$ . We will define $f_k$ as $f_k=(g_k)_{\mathcal P_k}$ where $g_k\in \mathcal{W}_\Omega$ will be inductively defined in such a way that (a) $(g_{k})_{\mathcal P_{k-1}}=(g_{k-1})_{\mathcal P_{k-1}}$ for all $k\geq 2$ , (b) $\delta _\square (f,g_k)=0$ for all $k\geq 1$ and (c) $d_\square (g_{k},(g_{k})_{\mathcal P_k})\leq 1/k$ for all $k\geq 1$ . This clearly implies the statement of the lemma, since $g_k\in \mathcal{W}_\Omega$ implies $(g_k)_{\mathcal P_k}\in \mathcal{W}_\Omega$ by the fact that $\mathcal P_k$ is a refinement of $\mathcal P_1$ ,

\begin{equation*} (f_{k+1})_{\mathcal P_k}=((g_{k+1})_{\mathcal P_{k+1}})_{\mathcal P_k}=(g_{k+1})_{\mathcal P_k}=(g_k)_{\mathcal P_k}=f_k \end{equation*}

by (a) and the fact that $\mathcal P_{k+1}$ is a refinement of $\mathcal P_k$ , and the two statements (b) and (c) imply (ii).

We start our inductive construction by setting $g_1=f$ . Noting that $d_\square (h,h')\leq 1$ for all $h,h'\in \mathcal{W}$ , this shows that $g_1$ satisfies the inductive assumptions.

Let $k\geq 2$ and assume that $g_{k-1}$ satisfies the inductive assumption. By Lemma 41, we can find an equipartition $\mathcal Q_{k}$ of $[0,1]$ into $q_k=s_k|\mathcal P_{k-1}|$ classes such that $\mathcal Q_{k}$ refines $\mathcal P_{k-1}$ and $d_\square (g_{k-1},(g_{k-1})_{\mathcal Q_k})\leq 1/k$ . We now define a measure preserving bijection $\phi \;:\;[0,1]\to [0,1]$ as follows: Let $I$ be an interval in $\mathcal P_{k-1}$ , and let $Y_1,\ldots Y_{s_k}$ those elements of $\mathcal Q_k$ subdividing $I$ . By Theorem A.7 in [Reference Janson26], we can find a measure preserving bijection from $I$ to itself such that the image of $Y_1,\ldots Y_{s_k}$ are the $s_k$ intervals in $\mathcal P_k$ that subdivide $I$ . Doing this for all intervals in $\mathcal Q_k$ we obtain a measure preserving bijection $\phi$ such that the images of the partition classes of $\mathcal Q_k$ are the partition classes of $\mathcal P_k$ , and such that $\phi$ maps each interval in $\mathcal P_{k-1}$ onto itself. Applying this bijection to $g_{k-1}$ gives a graphon $g_k\in \mathcal{W}_\Omega$ such that $\delta _\square (g_k,g_{k-1})=0$ and $d_\square (g_{k},(g_{k})_{\mathcal P_k})=d_\square (g_{k-1},(g_{k-1})_{\mathcal Q_k})\leq 1/k$ . By the inductive assumption (b) we have that $\delta _\square (g_k,f)=0$ , and by the fact that $\phi$ maps each interval in $\mathcal P_{k-1}$ onto itself we have that $(g_k)_{\mathcal P_{k-1}}=(g_{k-1})_{\mathcal P_{k-1}}$ . This completes the inductive proof.

Proof of Lemma 31. We establish the lemma by showing that ${\widetilde {\mathcal W}}_\Omega$ contains its limit points. Let $(\widetilde {W}_n)_{n \geq 0}$ be a sequence of graphons in ${\widetilde {\mathcal W}}_\Omega$ that converges to $\widetilde {W}\in {\widetilde {\mathcal W}}$ . Since $\widetilde {W}_n \in {\widetilde {\mathcal W}}_\Omega$ , we may chose a sequence $W_n \in \mathcal{W}_\Omega$ such that $\delta _\square (W_n,\widetilde W)\to 0$ . We claim that $\widetilde {W} \in {\widetilde {\mathcal W}}_\Omega$ .

By Lemma 42, we can find a sequence of refining partitions $\mathcal P_k$ of $[0,1]$ into intervals of length $1/|\mathcal P_k|$ and sequences $W_{n,k}\in \mathcal{W}_\Omega$ such that

1. 1. $\delta _\square ( W_n, W_{n,k}) \leq 1/k$

2. 2. $(W_{n,k+1})_{\mathcal P_k}=W_{n,k}$ .

Next we claim that it is possible to replace $(W_n)$ with a subsequence such that for all $k$ , $W_{n,k}$ converges almost everywhere to a step function $U_k$ with steps made out of the intervals in $\mathcal P_k$ . Indeed, select a subsequence of $(W_n)$ such that the value of $W_{n,1}$ converges on the product of all intervals $I,I'\in \mathcal P_1$ . We obtain $W_{n,1} \to U_1$ almost everywhere for $U_1$ a step function on $s_1$ intervals of $[0,1]$ . Taking further subsequences for $k=2,3 \ldots$ , we obtain a subsequence of $(W_n)$ such that $W_{n,k} \to U_k$ almost everywhere for all $k$ . By the Dominated Convergence Theorem, $\Vert W_{n,k}- U_k \Vert _1 \to 0$ , and so $d_\square ( W_{n,k}, U_k) \to 0$ . Each $U_k$ is a step function on $s_k$ intervals of $[0,1]$ . Note that since $W_{n,k} \in \mathcal{W}_\Omega$ and $d_\square (W_{n,k}, U_k) \to 0$ , Proposition 37 implies that $U_k \in \mathcal{W}_\Omega$ . For the remainder of this proof, we replace $(W_n)$ with this subsequence; doing so does not change the limit of the corresponding sequence in $\widetilde {\mathcal W}$ .

Next we claim that the sequence $(U_k)_{k\geq 1}$ has a limit $U$ in $\mathcal{W}_\Omega$ . It follows from (ii) that $U_k=(U_\ell )_{\mathcal{P}_k}$ for all $\ell \gt k$ . Let $(x,y)$ be a uniform random point in $[0,1]$ . Since $U_k=(U_\ell )_{\mathcal{P}_k}$ , the sequence $(U_1(x,y), U_2(x,y), \ldots )$ is a martingale with respect to the canonical filtration. The random variables $U_i(x,y)$ are bounded, and so the Martingale Convergence Theorem [Reference Durrett21, Theorem 4.2.11] implies that the sequence $(U_1(x,y), U_2(x,y), \ldots )$ converges with probability one. Thus there exists $U \in \mathcal{W}$ such that $U_k \to U$ almost everywhere. By the Dominated Convergence Theorem, $\Vert U_k -U \Vert _1 \to 0$ and therefore $d_\square (U, U_k) \to 0$ . Since $U_k \in \mathcal{W}_\Omega$ for all $k$ , and $\mathcal{W}_\Omega$ is closed, it follows that $U \in \mathcal{W}_\Omega$ . Moreover $\tilde {U} \in {\widetilde {\mathcal W}}_\Omega$ .

It remains to show that $\delta _\square (W_n,U) \to 0$ (as this implies that $\delta _\square ( {\widetilde {W}}_n, \widetilde {U}) \to 0$ , which establishes that the limit of the sequence is in ${\widetilde {\mathcal W}}_\Omega$ ). Let $\varepsilon \gt 0$ . Choose $k \gt 3/\varepsilon$ sufficiently large such that $\Vert U - U_k \Vert _1 \lt \varepsilon /3$ . For this fixed $k$ , there exists $n_0$ such that $\Vert U_k - W_{n,k} \Vert _1 \lt \varepsilon /3$ for all $n \geq n_0$ . Observe that

\begin{align*} \delta _\square (U, W_n) &\leq d_\square (U, U_k) + d_\square (U_k, W_{n,k}) + \delta _\square (W_{n,k}, W_n)\\[5pt] &\leq \Vert U- U_k\Vert _1 + \Vert U_k- W_{n,k}\Vert _1 + \delta _\square (W_{n,k}, W_n) \leq \varepsilon . \end{align*}

Proof of Lemma 32. We modify the proof of [Reference Dhara and Sen20, Lemma 2.1] to allow for $W_0$ with values in $\{0,1\}$ . For $\tilde {f} \in {\widetilde {\mathcal W}}$ , let

\begin{equation*} H(\tilde {f}) = \inf _{g \in \mathcal{W} \;:\; \delta _\square (g, \tilde {f}) =0} I_{W_0}(g). \end{equation*}

If $\tilde f\notin {\widetilde {\mathcal W}}_\Omega$ , then $g\notin \mathcal{W}_\Omega$ for all $g$ contributing to the infimum and by Proposition 34, $H ( \tilde {f})= \infty$ . On the other hand, if $\tilde f\in {\widetilde {\mathcal W}}_\Omega$ , there exists a $g\in \mathcal{W}_\Omega$ contributing to the infimum, so with the help of Proposition 34 we conclude that $H(\cdot )$ is bounded on ${\widetilde {\mathcal W}}_\Omega$ . Combined with the fact that

\begin{equation*} h\in B(\tilde {f}, \delta )\iff \delta _\square (\tilde {g},h)=0 \text{ for some } \tilde {g} \in S(\tilde {f}, \delta ), \end{equation*}

we obtain that for $\tilde {f} \in {\widetilde {\mathcal W}}_\Omega$

\begin{align*} J_{W_0}(\tilde {f}) = \sup _{\delta \gt 0} \inf _{ h \in B( \tilde {f}, \delta )} I_{W_0}(h) = \sup _{\delta \gt 0} \inf _{ \tilde {g} \in S(\tilde {f}, \delta )} H(\tilde {g}) = \sup _{\delta \gt 0} \inf _{ \tilde {h} \in S( \tilde {f}, \delta ) \cap {\widetilde {\mathcal W}}_\Omega } H(\tilde {h}) = \liminf _{\tilde {h} \to \tilde {f}} H(\tilde {h}). \end{align*}

Therefore, $J_{W_0}(\cdot )$ is the pointwise $\liminf$ of a bounded function. This implies that $J_{W_0}(\cdot )$ is lower semi-continuous on ${\widetilde {\mathcal W}}_\Omega$ .

Note that $J_{W_0}(f)=\infty$ for all $f \in {\widetilde {\mathcal W}} \setminus {\widetilde {\mathcal W}}_\Omega$ . Therefore the lower semi-continuity of $J_{W_0}(\cdot )$ on $\widetilde {\mathcal W}$ follows by Proposition 38 and Lemma 31.

Proof. Since $\widetilde {\mathcal W}$ is compact, it suffices to show that $\{\tilde {g} \in \tilde {\mathcal{B}}^\gamma \;:\; \tau (\tilde g) \geq t\}$ is closed. Let $\tilde {f}_n \in \tilde {\mathcal{B}}^\gamma$ be such that $\tau ( \tilde {f}_n) \geq t$ and $\tilde {f_n}$ converges to some graphon $\tilde {f}$ . Since $\tau$ is continuous, $\lim _{n \to \infty } \tau ( \tilde {f}_n) = \tau ( \tilde {f}) \geq t$ .

It remains to show that $\tilde {f} \in \tilde {\mathcal{B}}^\gamma$ . Without loss of generality, we may assume $f_n \in \mathcal{B}^\gamma$ , and write $f_n= (\alpha _{ij}^n)_{i,j \in [m]}$ , where each $\alpha _{ij}^n \in [0,1]$ . By the compactness of $[0,1]^{m^2}$ , there exists a subsequence such that

\begin{equation*}\alpha _{ij}^{n_k} \to \beta _{ij} \text{ for all $i,j \in [m]$}.\end{equation*}

Let $g=(\beta _{ij})_{i,j \in [m]} \in \mathcal{B}^\gamma$ . Since $f_{n_k} \to g$ pointwise and $d_\square (f_{n_k}, g) \leq \Vert f_{n_k}-g\Vert _1$ , the Dominated Convergence Theorem implies that $d_\square (f_{n_k}, g) \to 0$ . Since $\delta _\square (\tilde {f}_n, \tilde {f}) \to 0$ , we have $\delta _\square (\tilde {g}, \tilde {f})=0$ and thus $\tilde {f} \in \tilde {\mathcal{B}}^\gamma$ .

The proof of the second statement is identical, except that it starts from a sequence ${f}_n \in {\mathcal{B}}^\gamma$ such that $\tau ({f}_n) \geq t$ and $f_n$ converges to some ${f}\in \mathcal{W}$ in the metric $d_\square$ .

Proof. If $g$ can be written as $\sum _{i,j\in [k]}\beta _{ij}1_{Y'_i}1_{Y'_j}$ with $\lambda (Y_i)=\lambda (Y_i')$ almost everywhere, then clearly $\delta _{\square }(f,g) = 0$ . To establish the other direction, we will use Theorem 8.6 (vi) from [Reference Janson26]. This will require us to turn $f$ into what is called a twin-free graphon, defined as a graphon $W$ such that there exists no pair $(x,x')\in [0,1]$ such that $W(x,\cdot )=W(x',\cdot )$ almost everywhere. Unfortunately, by their very definition, step functions are not twin-free. To remedy this, we introduce graphons over a general probability space $(\Omega ,\mathcal F,\mu )$ , defined as measurable functions $W:\Omega ^2\to [0,1]$ such that $W(x,y)=W(y,x)$ for all $x,y\in \Omega$ . We also need to define a cut distance between graphons $W_i$ on (potentially) different probability spaces $(\Omega _i,\mathcal F_i,\mu _i)$ , $i=1,2$ . It is defined as

\begin{equation*} \delta _\square (W_1,W_2)=\inf _\mu \sup _{S,T\subset \Omega _1\times \Omega _2}\left |\int (W_1(x,x')-W_2(y,y'))d\mu (x,y)d\mu (x',y')\right | \end{equation*}

where the $\inf$ goes over all couplings of $\mu _1$ and $\mu _2$ . It is easy to see that for graphons defined on $[0,1]$ , this definition agrees with the previous one (see, e.g., Lemma 3.5 in [Reference Borgs, Chayes, Lovász, Sós and Vesztergombi8]). With these new definitions, we define two graphons $W_1$ , $W_2$ over two possibly different probability spaces to be equivalent if $\delta _\square (W_1,W_2)=0$ .

With this definition, the graphon $f$ is equivalent to the ‘discrete’ graphon $f_{ij}'=\beta _{i,j}$ where $i$ and $j$ lie in the probability space $([k],2^{[k]},\mu )$ with $\mu (i)=\lambda (Y_i)$ (use the coupling which pairs $i\in [k]$ with the uniform measure on $Y_i$ ). It is also easy to turn $f'$ into a twin free graphon as follows: if $i$ and $i'$ are twins, i.e., if the $i^{\text{th}}$ and $j^{\text{th}}$ row of $\beta$ are identical, just merge the sets $Y_i$ and $Y_j$ into a new set of measure $\lambda (Y_i)+\lambda (Y_j)$ , reducing $k$ by one. Note that this does not change the function $f$ , just the representation of the form $f=\sum _{i,j\in [k]}\beta _{ij}1_{Y_i}1_{Y_j}$ . Iterating this procedure, we eventually obtain a twin free graphon $f'$ which has cut-distance zero from $f$ , $\delta _\square (f',f)=0$ .

At this point, we use Theorem 8.6 (vi) from [Reference Janson26] which says that $\delta _\square (f',g)=0$ if and only if there exists a measure preserving map $\phi \;:\;[0,1]\to [k]$ such that $g(x,y)=f'_{\phi (x),\phi (y)}$ almost everywhere. Defining $Y'_i=\phi ^{-1}(\{i\})$ proves the lemma, in the case where the rows of $\beta$ are pairwise distinct. Otherwise, the intervals of $g$ may be split in order to match the representation of $f$ .

Proof of Theorem 11, Statement (1). We will prove the bound in the form given in Lemma 30. Let $f^{G_{kn}}$ be the empirical graphon of a graph on $kn$ vertices drawn according to $\mathbb{P}_{kn,W_0}$ . First, we claim that if

(13) \begin{align} \liminf _{n \to \infty } \frac {1}{(kn)^2} \log { \mathbb{P}_{kn, W_0}\left (d_\square (f^{G_{kn}},g) \leq \varepsilon \right )} \geq - I_{W_0}(g) \end{align}

holds for all $g \in \mathcal{W}$ and $\varepsilon \gt 0$ , then the theorem follows.

To see this, we first observe that for $\tilde h\in {\widetilde {\mathcal W}}$ , $0\lt \eta \leq \varepsilon /2$ and $g \in B(\tilde {h}, \eta )$

\begin{equation*} \tilde {\mathbb{P}}_{kn, W_0}(S(\tilde {h}, \varepsilon )) ={\mathbb{P}}_{kn, W_0}(\delta _\square (f^{G_{kn}},\tilde h)\leq \varepsilon ) \geq {\mathbb{P}}_{kn, W_0}(d_\square (f^{G_{kn}},g)\leq \varepsilon /2) \end{equation*}

where the identity follows from the definition of $\tilde {\mathbb{P}}_{kn, W_0}$ and $S(\tilde {h}, \varepsilon )$ , and the lower bound follows upon noting that $\delta _\square (f^{G_{kn}},\tilde h)\leq d_\square (f^{G_{kn}},g)+\delta _\square (g,\tilde h)$ . Therefore, assuming (13) yields

\begin{equation*} \liminf _{n \to \infty } \frac {1}{(kn)^2} \log \tilde {\mathbb{P}}_{kn, W_0}(S(\tilde {h}, \varepsilon )) \geq - I_{W_0}(g) \end{equation*}

for all $0\lt \eta \leq \varepsilon /2$ and all $g\in B(\tilde {h},\varepsilon /2)$ . It follows that

\begin{equation*}\liminf _{n \to \infty } \frac {1}{(kn)^2} \log \tilde {\mathbb{P}}_{kn, W_0}(S(\tilde {h}, \varepsilon )) \geq -\sup _{\eta \in (0,\varepsilon /2]}\inf _{g \in B(\tilde {h}, \eta )} I_{W_0}(g) = -\sup _{\eta \gt 0}\inf _{g \in B(\tilde {h}, \eta )} I_{W_0}(g)=-J_{W_0}(\tilde {h}) \end{equation*}

as required.

We have shown that (13) implies the theorem; we now turn to its proof. By Proposition 34, (13) holds trivially for $g \not \in \mathcal{W}_\Omega$ . We may assume $g \in \mathcal{W}_\Omega$ . Let $\varepsilon \gt 0$ . We define $(g_n)_{n\geq 1}$ , a sequence of $kn \times kn$ block graphons that approximate $g$ . Recall (1). For $i,j \in [kn]$ , let

\begin{equation*}p_{ij}^{(n)}= (kn)^2 \int \int _{[\frac {i-1}{kn},\frac {i}{kn}] \times [\frac {j-1}{kn},\frac {j}{kn}]} g(x,y) dx dy \qquad \text{and}\qquad g_n(x,y)= p_{\vartheta _{kn}(x), \vartheta _{kn}(y)}^{(n)}.\end{equation*}

Since $\|g_n - g\|_{1} \to 0$ , in order to prove (13) it suffices to show that

\begin{equation*}\liminf _{n \to \infty } \frac {1}{(kn)^2} \log { \mathbb{P}_{kn, W_0}\left ( B_{\varepsilon ,n}\right )} \geq - I_{W_0}(g),\end{equation*}

where $B_{\varepsilon ,n}= \{f\;:\; d_\square (f, g_n) \leq \varepsilon /2\}$ . We will apply the following proposition, which is proved as part of Theorem 2.3 in [Reference Chatterjee and Varadhan14]. For completion, we include a proof sketch in the Appendix (Section 8.2).

Proposition 45. Let $f_n$ be a graphon drawn from the measure $\mathbb{P}_{kn, g_n}$ , with $g_n$ as defined above. For any $\varepsilon \gt 0$ , it holds that

\begin{equation*}\lim _{n \to \infty } \mathbb{P}_{kn, g_n} ( d_\square (f_n, g_n) \geq \varepsilon )= 0.\end{equation*}

We now apply a tilting argument to establish the lower bound, following [Reference Chatterjee and Varadhan14]. Note that since $g\in \mathcal{W}_\Omega$ , $g_n \in \mathcal{W}_\Omega$ , and so the support of $\mathbb{P}_{kn, g_n}$ is contained in the support of $\mathbb{P}_{kn, W_0}$ . Therefore we may write

\begin{align*} \mathbb{P}_{kn, W_0}(B_{\varepsilon , n}) &= \int _{B_{\varepsilon , n}} d\mathbb{P}_{kn, W_0}= \int _{B_{\varepsilon , n}} \textsf{exp} \left (- \log \frac {d\mathbb{P}_{kn, g_n}}{d \mathbb{P}_{kn, W_0}}\right ) d\mathbb{P}_{kn, g_n}\\[5pt] &= \mathbb{P}_{kn, g_n}(B_{\varepsilon ,n}) \frac {1}{\mathbb{P}_{kn, g_n} (B_{\varepsilon , n})} \int _{B_{\varepsilon , n}} \textsf{exp} \left (- \log \frac {d\mathbb{P}_{kn, g_n}}{d \mathbb{P}_{kn, W_0}}\right ) d\mathbb{P}_{kn, g_n}. \end{align*}

Proposition 45 implies that for $n$ sufficiently large, $\mathbb{P}_{kn, W_0}(B_{\varepsilon , n})\gt 0$ . Taking the logarithm of both sides and applying Jensen’s inequality, we obtain

\begin{align*} \log \mathbb{P}_{kn, W_0}(B_{\varepsilon , n}) \geq \log \mathbb{P}_{kn, g_n}(B_{\varepsilon , n}) - \frac {1}{\mathbb{P}_{kn, g_n}(B_{\varepsilon , n})} \int _{B_{\varepsilon , n}} \log \left (\frac {d \mathbb{P}_{kn, g_n}}{d \mathbb{P}_{kn, W_0}}\right ) d \mathbb{P}_{kn, g_n}. \end{align*}

By Proposition 45, it holds that $\mathbb{P}_{kn,g_n}(B_{\varepsilon , n}) \to 1$ . Furthermore, letting $p_{\text{min}}$ and $p_{\text{max}}$ be the minimal and maximal values taken on by $W_0$ in $(0,1)$ , we have

\begin{align*}&\frac {1}{(kn)^2}\int _{\mathcal{W}_\Omega \setminus B_{\varepsilon , n}}\log \left (\frac {d \mathbb{P}_{kn, g_n}}{d \mathbb{P}_{kn, W_0}}\right ) d \mathbb{P}_{kn, g_n}\\& \leq \frac {1}{(kn)^2} \int _{\mathcal{W}_\Omega \setminus B_{\varepsilon , n}} \log \left (\left (\frac {1}{\min \{p_{\text{min}}, 1 - p_{\text{max}}\}}\right )^{\binom {kn}{2}}\right ) d \mathbb{P}_{kn, g_n} \to 0. \end{align*}

Therefore,

\begin{align*} \liminf _{n \to \infty } \frac {1}{(kn)^2}\log \mathbb{P}_{kn, W_0}(B_{\varepsilon , n}) &\geq - \limsup _{n \to \infty } \frac {1}{(kn)^2} \int \log \left (\frac {d \mathbb{P}_{kn, g_n}}{d \mathbb{P}_{kn, W_0}}\right ) d \mathbb{P}_{kn, g_n}. \end{align*}

Observe that the probability of sampling a graph $G$ on $kn$ vertices is

\begin{equation*} \mathbb{P}_{kn, g_n}(\{G\})=\prod _{\substack {i,j \in [kn]\\[5pt] i\lt j}} \left ( p_{ij}^{(n)}\unicode {x1D7D9}_{(i,j) \in E(G) } + (1-p_{ij}^{(n)})\unicode {x1D7D9}_{(i,j) \not \in E(G)}\right ). \end{equation*}

By construction if $W_0(i/(kn), j/(kn))=0$ , then $p_{ij}^{(n)}=0$ and if $W_0(i/(kn), j/(kn))=1$ , then $p_{ij}^{(n)}=1$ . Let $V(G)$ denote the vertex set of $G$ . Recalling the convention that $0 \log (0/0)=0$ , we obtain

\begin{align*} & \limsup _{n \to \infty } \frac {1}{(kn)^2} \int \log { \left ( \frac {d\mathbb{P}_{kn, g_n}}{d\mathbb{P}_{kn,W_0}}\right )} d\mathbb{P}_{kn,g_n} \\[5pt] &= \limsup _{n \to \infty } \frac {1}{(kn)^2} \sum _{G: V(G)=[kn]} \mathbb{P}_{kn, g_n}(\{G\})\log \left (\frac { \mathbb{P}_{kn, g_n}(\{G\})}{\mathbb{P}_{kn, W_0}(\{G\})}\right )\\[5pt] &= \limsup _{n \to \infty } \frac {1}{(kn)^2} \sum _{G: V(G)=[kn]} \prod _{\substack {i,j \in [kn]\\[5pt] i\lt j}} \left ( p_{ij}^{(n)}\unicode {x1D7D9}_{(i,j) \in E(G) } + (1-p_{ij}^{(n)})\unicode {x1D7D9}_{(i,j) \not \in E(G)}\right ) \times \\[5pt] &\,\,\,\,\, \left (\sum _{\substack {i,j \in [kn]\\[5pt] i\lt j}} \log { \frac {p_{ij}^{(n)}}{W_0(\frac {i}{kn},\frac {j}{kn})}} \unicode {x1D7D9}\{(i,j) \in E(G)\} +\log { \frac {1-p_{ij}^{(n)}}{1-W_0(\frac {i}{kn},\frac {j}{kn})}} \unicode {x1D7D9}\{(i,j) \not \in E(G)\}\right ) \\[5pt] &=\limsup _{n \to \infty } \frac {1}{(kn)^2} \sum _{\substack {i,j \in [kn]\\[5pt] i\lt j}} p_{ij}^{(n)}\log { \frac {p_{ij}^{(n)}}{W_0(\frac {i}{kn},\frac {j}{kn})}} +(1-p_{ij}^{(n)})\log { \frac {1-p_{ij}^{(n)}}{1-W_0(\frac {i}{kn},\frac {j}{kn})}}\\[5pt] &= \limsup _{n \to \infty }I_{W_0}(g_n) = I_{W_0}(g). \end{align*}

The last equality follows from a straightforward adaptation of an argument from [Reference Chatterjee11, Lemma 5.7]: for any $\varepsilon \gt 0$ , set $A_{\varepsilon }=\{(x,y)\;:\; \|g_n(x,y)-g(x,y)\|_1\gt \varepsilon \}$ . Observe that $\Vert g_n - g\Vert _1 \geq \lambda (A_{\varepsilon }) \varepsilon$ , implying $\lambda (A_{\varepsilon }) \to 0$ for any $\varepsilon \gt 0$ . In addition, note that $Im(W_0)$ is finite and $h_p(\cdot )$ is uniformly continuous for any fixed $p$ . Therefore, for every $\delta \gt 0$ , there exists $\varepsilon \gt 0$ such that $|h_{W_0(x,y)}(g_n(x,y)) - h_{W_0(x,y)}(g(x,y))|\lt \delta$ whenever $|g_n(x,y) - g(x,y)| \lt \varepsilon$ . Consequently,

\begin{align*} |I_{W_0}(g_n) - I_{W_0}(g)| &\leq \frac {1}{2} \int _{A_{\varepsilon }} |h_{W_0(x,y)}(g_n(x,y)) - h_{W_0(x,y)}(g(x,y))| dx dy \\[5pt] &+ \frac {1}{2} \int _{[0,1]^2\backslash A_{\varepsilon }} |h_{W_0(x,y)}(g_n(x,y)) - h_{W_0(x,y)}(g(x,y))| dx dy \\[5pt] &\leq \frac {C}{2} \lambda (A_{\varepsilon }) + \frac {1}{2}\delta \end{align*}

where $C\gt 0$ is such that $h_{W_0(x,y)}(a)\lt C$ for all $a\in [0,1]$ and $(x,y) \in [0,1]^2$ . This completes the proof.

Proof of Theorem 11, Statement 2. We prove the bound in the form given in Lemma 30. Fix $\tilde {g}$ and $\alpha \gt 0$ . Let $\varepsilon , \eta \lt \alpha /2$ , let $H(\varepsilon /2)$ be an $\varepsilon /2$ net as given in Lemma 49, and let $T^*$ be the union of the sets of invertible transformations $T$ given by Lemma 46 for each $h \in H(\varepsilon /2)$ . We index the finite set as $T^*=\{\tau _1, \tau _2, \ldots \tau _{N(\eta , W_0, \varepsilon )}\}$ . Then

\begin{align*} \tilde {\mathbb{P}}_{kn,W_0}\left (S(\tilde {g}, \alpha )\right ) &= \mathbb{P}_{kn,W_0}\left ( \delta _\square (f^{G_{kn}} ,g )\leq \alpha \right ) \\[5pt] &\leq \sum _{h \in H(\varepsilon /2)} \mathbb{P}_{kn,W_0}\left ( \bigcup _{\sigma \in \mathcal{M}_{kn}} \left \{f^{G_{kn}^\sigma } \in \{ f\;:\; \delta _\square ( f, g ) \leq \alpha \} \cap \left \{ f \;:\; d_\square (f,h) \leq \frac \varepsilon 2\right \}\right \}\right ) \\[5pt] &\leq \sum _{h \in H(\varepsilon /2)}\sum _{\sigma \in \mathcal{M}_{kn}} \mathbb{P}_{kn,W_0}\left (\left \{f^{G_{kn}^\sigma } \in \{ f\;:\; \delta _\square ( f, g ) \leq \alpha \} \cap \left \{ f \;:\; d_\square (f,h) \leq \frac \varepsilon 2\right \}\right \}\right ) \\[5pt] &\leq \sum _{\substack {h \in H(\varepsilon /2)\\[5pt] \delta _\square (g,h) \leq \alpha +\varepsilon /2 } }\sum _{\sigma \in \mathcal{M}_{kn} } \mathbb{P}_{kn,W_0}\left ( d_\square (f^{G_{kn}^\sigma },h) \leq \frac \varepsilon 2\right ) \\[5pt] & \leq (kn)!|H(\varepsilon /2)| \max _{\substack {h \in H(\varepsilon /2)\\[5pt] \delta _\square (g,h) \leq \alpha +\varepsilon /2 \\[5pt] i \in [N(\eta , W_0, \varepsilon )]}} \mathbb{P}_{kn,W_0}\left ( d_\square (f^{G_{kn}^{\tau _i}},h) \leq \frac \varepsilon 2 + \eta \right ), \end{align*}

where the last inequality follows from Lemma 46. Lemma 47 implies that

\begin{align*} \limsup _{n \to \infty } \frac {1}{(kn)^2} \log \mathbb{P}_{kn,W_0}\left ( d_\square (f^{G_{kn}^{\tau _i}},h) \leq \frac \varepsilon 2 + \eta \right ) &\leq -\inf _{f: \delta _\square (f,h) \leq \frac \varepsilon 2 +\eta }I_{W_0}(f) \\[5pt] &\leq - \inf _{f: \delta _\square (f,\tilde {g}) \leq \alpha +\varepsilon +\eta } I_{W_0}(f), \end{align*}

when $h$ is such that $\delta _\square (g,h) \leq \alpha +\varepsilon /2$ and $\tau _i$ is invertible.

Let $M \in \mathbb{Z}^+$ , and consider the $M$ sequences $\{y_n^i\}_{n \geq 1}$ where $i \in [M]$ . A basic analysis argument implies that if $\limsup _{n \to \infty } \frac 1{(kn)^2}\log y_n^{i} \leq C$ for all $i \in [M]$ , then $\limsup _{n \to \infty } \frac 1{(kn)^2} \log \left ( \max _{i \in [M]} y^{i}_n\right ) \leq C$ . It follows that

\begin{align*} \limsup _{n \to \infty } &\frac {1}{(kn)^2} \log \tilde {\mathbb{P}}_{kn,W_0}\left (S(\tilde {g}, \alpha )\right ) \\[5pt] &\leq \limsup _{n \to \infty } \frac {1}{(kn)^2} \log \left ( (kn)! |H(\varepsilon /2)| \max _{\substack {h \in H(\varepsilon /2)\\[5pt] \delta _\square (g,h) \leq \alpha +\varepsilon /2 \\[5pt] i \in [N(\eta , W_0, \varepsilon )]}}\mathbb{P}_{kn,W_0}\left ( d_\square (f^{G_{kn}^{\tau _i}},h) \leq \varepsilon /2 + \eta \right )\right )\\[5pt] &= \limsup _{n \to \infty } \frac {1}{(kn)^2} \log \left ( \max _{\substack {h \in H(\varepsilon /2)\\[5pt] \delta _\square (g,h) \leq \alpha +\varepsilon /2 \\[5pt] i \in [N(\eta , W_0, \varepsilon )]}}\mathbb{P}_{kn,W_0}\left ( d_\square (f^{G_{kn}^{\tau _i}},h) \leq \varepsilon /2 + \eta \right )\right )\\[5pt] &\leq - \inf _{f: \delta _\square (f,\tilde {g}) \leq \alpha +\varepsilon +\eta } I_{W_0}(f). \end{align*}

Since $\varepsilon , \eta \lt \alpha /2$ , we obtain

\begin{equation*}\limsup _{n \to \infty } \frac {1}{(kn)^2} \log \tilde {\mathbb{P}}_{kn,W_0}\left (S(\tilde {g}, \alpha )\right )\leq - \inf _{f: \delta _\square (f,\tilde {g}) \leq 2\alpha } I_{W_0}(f).\end{equation*}

Since $(\!-\! \inf _{f: \delta _\square (f,\tilde {g}) \leq 2\alpha } I_{W_0}(f))$ is a non-increasing function as $\alpha \to 0$ ,

\begin{align*} \lim _{\alpha \to 0} \limsup _{n \to \infty } \frac {1}{(kn)^2} \log \tilde {\mathbb{P}}_{kn,W_0}\left (S(\tilde {g}, \alpha )\right ) &\leq \inf _{\alpha \gt 0 } \left (- \inf _{f: \delta _\square (f,\tilde {g}) \leq 2\alpha } I_{W_0}(f)\right )\\[5pt] &= - \sup _{\alpha \gt 0 } \inf _{f: \delta _\square (f,\tilde {g}) \leq 2\alpha } I_{W_0}(f)\\[5pt] &= - J_{W_0} (g), \end{align*}

as required.

Proof. Note that since $h$ is constant on each block $I_i \times I_j$ and $\phi$ respects the interval structure,

\begin{equation*}h^\phi (x,y)= h(\phi (x), \phi (y))= h(x,y).\end{equation*}

It follows that

\begin{equation*}d_\square (g,h)=d_\square (g^\phi , h^\phi )= d_\square (g^\phi , h).\end{equation*}

Proof of Lemma 46. For ease of notation, we denote $f=f^{G_{kn}}$ as the empirical graphon obtained by sampling $W_0$ according to $\mathbb{P}_{kn,W_0}$ . Let $\{H_i\;:\; i \in [s_h]\}$ and $\{W_{0,j}\;:\; j \in [s_w]\}$ denote the intervals of the block structure governed by $\mu$ and $\gamma$ respectively; formally, $H_1 = [0, \mu _1]$ , $W_{0,1} = [0, \gamma _1]$ ,

\begin{equation*}H_i =\left (\sum _{j=1}^{i-1} \mu _j, \sum _{j=1}^{i} \mu _j\right ] \text{ for } 2 \leq i \leq s_h, \quad \text{ and } \quad W_{0,i} =\left (\sum _{j=1}^{i-1} \gamma _j, \sum _{j=1}^{i} \gamma _j\right ] \text{ for } 2 \leq i \leq s_w.\end{equation*}

$\{H_i\}$ are the intervals corresponding to the blocks of $h$ and $\{W_{0,i}\}$ are the intervals corresponding to the blocks of $W_0$ .

We begin with a proof outline. First we construct a finite set of measure preserving transformations $T \subseteq \mathcal{M}$ such that each $\sigma \in \mathcal{M}_{kn}$ is ‘close’ to a transformation $\tau$ in $T$ . Then, in order to compare $f^{\sigma }$ and $f^{\tau }$ , we define $\alpha , \beta$ invertible transformations that respect the intervals $H_1, \ldots H_{s_h}$ . Proposition 51 implies that $d_\square (f^\sigma ,h) = d_\square ((f^{\sigma })^\alpha ,h)$ and $d_\square (f^{\tau },h) = d_\square ((f^{\tau })^\beta ,h)$ . It follows that

(14) \begin{align} \mathbb{P}_{kn,W_0}\left ( d_\square (f^\sigma ,h) \leq \varepsilon \right )&= \mathbb{P}_{kn,W_0}\left ( d_\square (\left (f^\sigma \right )^\alpha ,h) \leq \varepsilon \right ), \end{align}

(15) \begin{align} \mathbb{P}_{kn,W_0}\left ( d_\square (f^{\tau },h) \leq \varepsilon + \eta \right )&=\mathbb{P}_{kn,W_0}\left ( d_\square (\left (f^{\tau }\right )^\beta ,h) \leq \varepsilon + \eta \right ). \end{align}

Finally, we will describe a coupling of $f$ and $g$ , each with marginal distribution $\mathbb{P}_{kn,W_0}$ , that guarantees

(16) \begin{equation} d_\square \left ( \left (f^\sigma \right )^\alpha ,\left (g^{\tau }\right )^\beta \right ) \leq \eta \end{equation}

with probability one. The triangle inequality implies

(17) \begin{align} \mathbb{P}_{kn,W_0}\left ( d_\square (\left (f^\sigma \right )^\alpha ,h) \leq \varepsilon \right )\leq \mathbb{P}_{kn,W_0}\left ( d_\square (\left (f^{\tau }\right )^\beta ,h) \leq \varepsilon + \eta \right ). \end{align}

The statement follows directly from (14), (15), and (17).

To complete the proof according to this outline, we must complete the following tasks:

1. 1. Define a finite net of measure preserving transformations $T \subseteq \mathcal{M}$ with $|T|=N(\eta , s_h, s_w)$ .

2. 2. For each transformation $\sigma \in \mathcal{M}_{kn}$ , define a ‘close’ transformation $\tau \in T$ . Informally, we will say that two transformations are close if they map approximately the same amount of mass from $W_{0,i}$ to $H_j$ for all $i \in [s_w]$ and $j \in [s_h]$ .

3. 3. Define $\alpha$ and $\beta$ , invertible transformations that respect the intervals $H_1 \ldots H_{s_h}$ .

4. 4. Exhibit a coupling of $f$ and $g$ each sampled according to $\mathbb{P}_{kn,W_0}$ that guarantees (16).

We begin with (a). For convenience we index vectors $v \in \mathbb{R} ^{s_w\cdot s_h}$ by pairs $(i,j) \in [s_w] \times [s_h]$ . Let

\begin{equation*}V= \bigg \{ v \in \mathbb{R} _{\geq 0}^{s_w\cdot s_h} \bigg | \sum _{i=1}^{s_w} \sum _{j=1}^{s_h} v_{ij}=1, \sum _{i=1}^{s_w} v_{ij}= \mu _j, \sum _{j=1}^{s_h} v_{ij}= \gamma _i \bigg \}.\end{equation*}

Recall that $\{H_i\}$ are the intervals corresponding to the blocks of $h$ and $\{W_{0,i}\}$ are the intervals corresponding to the blocks of $W_0$ . For each $v \in V$ we associate an invertible measure preserving transformation $\tau _v \in \mathcal{M}$ that maps an interval of length $v_{ij}$ contained in $W_{0,i}$ to an interval that is contained completely in $H_j$ for each $(i,j)$ . To this end, let

\begin{equation*}I_{11} = \left [0, v_{11} \right ] \qquad \text{and}\qquad I_{ij}=\left ( \sum _{a=1}^{i-1} \gamma _a + \sum _{b=1}^{j-1} v_{ib},\sum _{a=1}^{i-1} \gamma _a + \sum _{b=1}^{j} v_{ib} \right ], (i,j) \neq (1,1).\end{equation*}

Note that the intervals $I_{ij}$ are sorted first by the first index, then by the second index. Define $\tau \;:\;[0,1]\to [0,1]$ to be the transformation that translates the intervals so they are first sorted by the second index, then by the first index,