# Large deviation principles for graphon sampling

Jan Grebík  UCLA Mathematics, 520 Portola Plaza, Los Angeles, CA 90095, USA,
and Faculty of Informatics, Masaryk University, Botanická 68A, 602 00 Brno,
Czech Republic Oleg Pikhurko  Mathematics Institute and DIMAP, University of
Warwick, Coventry CV4 7AL, UK

###### Abstract

We investigate possible large deviation principles (LDPs) for the $n$-vertex
sampling from a given graphon with various speeds $s(n)$ and resolve all the
cases except when the speed $s(n)$ is of order $n^{2}$.

For quadratic speed $s=(c+o(1))n^{2}$, we establish an LDP for an arbitrary
$k$-step graphon, which extends a result of Chatterjee and Varadhan [_Europ.
J. Combin._ , 32 (2011) 1000–1017] who did this for $k=1$ (that is, for the
homogeneous binomial random graphs). This is done by reducing the problem to
the LDP for stochastic $k$-block models established recently by Borgs, Chayes,
Gaudio, Petti and Sen [_“A large deviation principle for block models”_ ,
arxiv:2007.14508, 2020] Also, we improve some results by Borgs et al.

##  1 Introduction

###  1.1 Overview of the new results

For the reader’s convenience, this section briefly and informally, summaries
the main new results obtained in this paper. (Their full statements can be
found in Sections 1.2–1.6.)

We study large deviations for the _$n$ -vertex sample_ ${\mathbbm{G}}(n,W)$
from a given _graphon_ $W$, that is, a symmetric measurable function
$W:[0,1]^{2}\to[0,1]$. This is a random graph on vertex set
$[n]:=\\{1,\dots,n\\}$ produced as follows: we pick $n$ random elements
$x_{1},\dots,x_{n}\in[0,1]$ and make each pair $\\{i,j\\}$ an edge with
probability $W(x_{i},x_{j})$, with all choices being mutually independent. We
investigate if a large deviation principle (LDP) holds for a given speed
function $s(n)$, i.e. if there is a rate function $I$ from the appropriately
defined topological space $\widetilde{\mathcal{W}}$ (that includes all finite
graphs, up to isomorphism) to $[0,\infty]$ such that the probability of
${\mathbbm{G}}(n,W)$ hitting a subset $A\subseteq\widetilde{\mathcal{W}}$ can
be related to $\exp(-s(n)\inf_{A}I)$ in the standard LDP sense (made precise
in Definition 1.1 here). The first such LDP result for graphon sampling was
given in the ground-breaking work of Chatterjee and Varadhan
[ChatterjeeVaradhan11] who established an LDP for speed $(c+o(1))n^{2}$ when
$W$ is the constant graphon (and thus ${\mathbbm{G}}(n,W)$ is the standard
binomial random graph).

We show that, for a general graphon $W$, the only “interesting” speeds are
$\Theta(n)$ and $\Theta(n^{2})$; namely for all other speed functions either
an LDP does not hold or it holds with an explicitly described rate function
$I$ that assumes values $0$ and $\infty$ only.

For speed $(c+o(1))n$, we establish an LDP for any graphon $W$, with a key
ingredient of out proof being an extension by Eichelsbacher [Eichelsbacher97]
of the classical Sanov’s LDP result [Sanov57] for empirical measures.

For speed $(c+o(1))n^{2}$, we establish an LDP in the case when $W$ is a _step
graphon_ , that is, the elements of $[0,1]$ are split into $k$ (finitely many)
types and the probability of $\\{i,j\\}$ being an edge of ${\mathbbm{G}}(n,W)$
depends only on the types of $x_{i}$ and $x_{j}$. This case is related to the
so-called _stochastic $k$-block random graph model_ where the difference to
step graphon sampling is that the number of vertices of each type is given.
Our proof uses the LDP for stochastic block models that was recently obtained
by Borgs, Chayes, Gaudio, Petti and Sen [BCGPS]. As a by-product of our line
of research, we also improve some results in [BCGPS].

Finally, we completely resolve the LDP problem (for any given speed) for
_weighted graph sampling_ from $W$, where one takes independent uniform
$x_{1},\dots,x_{n}\in[0,1]$ and output an edge-weighted complete graph on
$[n]$ with the weight of $\\{i,j\\}$ being $W(x_{i},x_{j})$.

###  1.2 Large deviations for general topological spaces

The theory of large deviations (see e.g. the books by Dembo and Zeitouni
[DemboZeitouni10ldta], Rassoul-Agha and Seppäläinen
[RassoulaghaSeppelainen14cldigm], and Varadhan [Varadhan16ld]) studies the
probabilities of rare events on the exponential scale. This is formally
captured by the following definition.

######  Definition 1.1.

A sequence of Borel probability measures $(\mu_{n})_{n\in{\mathbbm{N}}}$ on a
topological space $X$ satisfies a _large deviation principle_ (_LDP_ for
short) with _speed_ $s:{\mathbbm{N}}\to(0,\infty)$ and _rate function_
$I:X\to[0,\infty]$ if

  * •

$s(n)\to\infty$ as $n\to\infty$,

  * •

the function $I$ is _lower semi-continuous_ (_lsc_ for short), that is, for
each $r\in{\mathbbm{R}}$ the level set $\\{I\leqslant r\\}:=\\{x\in
X:I(x)\leqslant r\\}$ is a closed subset of $X$,

  * •

the following _lower bound_ holds:

$\liminf_{n\to\infty}\frac{1}{s(n)}\,{\log\,\mu_{n}(G)}\geqslant-\inf_{x\in
G}I(x),\quad\mbox{for every open $G\subseteq X$,}$ (1)

  * •

the following _upper bound_ holds:

$\limsup_{n\to\infty}\frac{1}{s(n)}\,{\log\,\mu_{n}(F)}\leqslant-\inf_{x\in
F}I(x),\quad\mbox{for every closed $F\subseteq X$.}$ (2)

If $X$ is a compact metric space then there is an equivalent definition
involving only probabilities of balls shrinking to a point, see Lemma 2.8.

Large deviations for various models of random graphs have been receiving much
attention (see e.g. the survey by Chatterjee [Chatterjee16bams]), often
motivated by specific applications, such as tails of subgraph counts in the
binomial random graph (see e.g. [BhattacharyaGangulyLubetzkyZhao17,
ChatterjeeDembo16, HarelMoussetSamotij22, JansonOleszkewiczRucinski04,
JansonRucinski02, JansonRucinski04, LubetzkyZhao15, LubetzkyZhao17rsa]) or in
some of its constrained versions ([DemboLubetzky18ecp,
DionigiGarlaschelliHollanderMandje21, HollanderMandjesRoccaverdeStarreveld18,
HollanderMarkering23]), spectral properties
([ChakrabartyHazraHollanderSfragara22, HazraHollanderMarkering]), algorithms
for clustering in 2-block random graphs ([Massoulie14stoc,
MosselNeemanSly18]), particular fluctuations of subgraph counts in $W$-random
graphs ([BhattacharyaChatterjeeJanson23, DelmasDhersinSciauveau21rsa,
FerayMeliotNikeghbali20, HladkyPelekisSileikis21]), etc. In addition to the
random graph models discussed in this paper, an LDP for growing random graphs
with a given degree distribution was obtained Dhara and Sen [DharaSen22] by
reducing to large deviations for a certain model which gives another
generalisation of the binomial random graph ${\mathbbm{G}}(n,p)$; these
results were strengthened by Markering [Markering23].

###  1.3 Binomial random graph and graphons

A basic but central model is the _binomial random graph_ ${\mathbbm{G}}(n,p)$,
where the vertex set is $[n]$ and each pair of vertices is an edge with
probability $p$, independently of other pairs. A large deviation principle for
${\mathbbm{G}}(n,p)$ for constant $p\in(0,1)$ was established in a ground-
breaking paper of Chatterjee and Varadhan [ChatterjeeVaradhan11] as follows.
(See also the exposition of this proof in Chatterjee’s book
[Chatterjee17ldrg].)

As it turns out, the “right” setting is to consider _graphons_ , that is,
measurable symmetric functions $[0,1]^{2}\to[0,1]$. On the set ${\mathcal{W}}$
of all graphons, one can define the so-called _cut-distance_ $\delta_{\Box}$,
which is a pseudo-metric on ${\mathcal{W}}$. (See Section 2.1 for all missing
definitions related to graphons.) Consider the factor space

$\widetilde{\mathcal{W}}:=\\{\widetilde{U}:U\in{\mathcal{W}}\\},$

where $\widetilde{U}:=\\{V\in{\mathcal{W}}:\delta_{\Box}(U,V)=0\\}$ consists
of all graphons _weakly isomorphic_ to $U$. The space
$(\widetilde{\mathcal{W}},\delta_{\Box})$ naturally appears in the limit
theory of dense graphs, see e.g. the book by Lovász [Lovasz:lngl]. In
particular, a graph $G$ on $[n]$ can be identified with the graphon $f^{G}$
where we partition $[0,1]$ into intervals of length $1/n$ each and let $f^{G}$
be the $\\{0,1\\}$-valued step function that encodes the adjacency relation.
This way, ${\mathbbm{G}}(n,p)$ gives a (discrete) probability measure
$\widetilde{\mathbb{P}}_{n,p}$ on $(\widetilde{\mathcal{W}},\delta_{\Box})$,
where $\widetilde{\mathbb{P}}_{n,p}(A)$ for
$A\subseteq\widetilde{\mathcal{W}}$ is the probability that the sampled graph,
when viewed as a graphon up to weak isomorphism, belongs to the set $A$.

Also, recall that, for $p\in[0,1]$, the _relative entropy_
$h_{p}:[0,1]\to[0,\infty]$ is defined by

$h_{p}(r):=p\ \ell\\!\left(\frac{r}{p}\right)+(1-p)\
\ell\\!\left(\frac{1-r}{p}\right),\quad r\in[0,1],$ (3)

where $\ell:[0,\infty]\to[-1/{\mathrm{e}},\infty]$ is defined by

$\ell\\!\left(x\right):=x\log(x),\quad\mbox{for $x\in[0,\infty]$,}$ (4)

with the agreement that $0\log(0)=0$ and $\infty\log(\infty)=\infty$.

######  Theorem 1.2 (Chatterjee and Varadhan [ChatterjeeVaradhan11]).

Let $p\in[0,1]$. The function $I_{p}:{\mathcal{W}}\to[0,\infty]$ defined by

$I_{p}(U):=\frac{1}{2}\int_{[0,1]^{2}}h_{p}(U(x,y))\,\mathrm{d}x\,\mathrm{d}y,\quad
U\in{\mathcal{W}},$ (5)

gives a well-defined function $\widetilde{\mathcal{W}}\to[0,\infty]$ (that is,
$I_{p}$ assumes the same value at any two graphons at $\delta_{\Box}$-distance
0) which is lower semi-continuous on
$(\widetilde{\mathcal{W}},\delta_{\Box})$. Moreover, the sequence of measures
$(\widetilde{\mathbb{P}}_{n,p})_{n\in{\mathbbm{N}}}$ on
$(\widetilde{\mathcal{W}},\delta_{\Box})$ satisfies an LDP with speed $n^{2}$
and rate function $I_{p}$.∎

###  1.4 Sampling from a graphon

There are various important inhomogeneous random graph models that generalise
the binomial random graph ${\mathbbm{G}}(n,p)$. The main objective of this
paper is to initiate a systematic study of large deviations for the following
model.

For a graphon $W\in{\mathcal{W}}$ and an integer $n\in{\mathbbm{N}}$, the _$n$
-vertex $W$-sample_ ${\mathbbm{G}}(n,W)$ is the random graph on $[n]$
generated by first sampling uniform elements $x_{1},\dots,x_{n}\in[0,1]$ and
then making each pair $\\{i,j\\}$ an edge with probability $W(x_{i},x_{j})$,
where all choices are mutually independent. As it easily follows from standard
results (e.g. [Lovasz:lngl, Lemma 10.23]), the distribution of
${\mathbbm{G}}(n,W)$ will remain the same if we replace $W$ by any weakly
isomorphic graphon, so we could write ${\mathbbm{G}}(n,\widetilde{W})$.
However, here and in many similar situations, we prefer to talk about graphons
rather than equivalence classes of graphons, just for brevity and notational
convenience.

Let $\widetilde{\mathbb{R}}_{n,W}$ be the corresponding (discrete) measure on
$\widetilde{\mathcal{W}}$ where we take the equivalence class
$\widetilde{f^{G}}\in\widetilde{\mathcal{W}}$ of the sampled graph
$G\sim{\mathbbm{G}}(n,W)$. When $W$ is the constant function $p$, we get
exactly the binomial random graph ${\mathbbm{G}}(n,p)$ and
$\widetilde{\mathbb{R}}_{n,W}=\widetilde{\mathbb{P}}_{n,p}$.

Let us give some definitions that are needed to state the first batch of our
LDP results, namely that, informally speaking, the only “interesting” speeds
for the sequence $(\widetilde{\mathbb{R}}_{n,W})_{n\in{\mathbbm{N}}}$ of
measures are $\Theta(n)$ and $\Theta(n^{2})$, as well as a general LDP for
speed $\Theta(n)$. Recall that we work on the graphon space
$\widetilde{\mathcal{W}}$ endowed with the cut-distance $\delta_{\Box}$.

Let $W\in{\mathcal{W}}$ be a graphon. We assign to $W$ two
$\delta_{\Box}$-closed subsets $\mathbf{RN}(W)$ and $\mathbf{FORB}(W)$ of
$\widetilde{\mathcal{W}}$ that satisfy
$W\in\mathbf{RN}(W)\subseteq\mathbf{FORB}(W)$ as follows.

The set $\mathbf{FORB}(W)$ consists by definition of those graphons $U$ such
that $t_{\mathrm{ind}}(F,W)=0$ implies $t_{\mathrm{ind}}(F,U)=0$ for every
graph $F$, where after relabelling $V(F)$ to be $[n]$ we define

$t_{\mathrm{ind}}(F,U):=\int_{[0,1]^{{n}}}\prod_{\\{i,j\\}\in
E(F)}U(x_{i},x_{j})\prod_{\\{i^{\prime},j^{\prime}\\}\in
E(\overline{F})}\left(1-U(x_{i^{\prime}},x_{j^{\prime}})\right)\,\mathrm{d}\lambda^{\oplus
n}(x)$ (6)

to be the _induced (homomorphism) density_ of $F$ in $U$. (Equivalently for
$V(F)=[n]$, we can define $t_{\mathrm{ind}}(F,U)$ as the probability that
${\mathbbm{G}}(n,U)$ is equal to $F$.) In other words, $\mathbf{FORB}(W)$
consists of those graphons that do not contain induced subgraphs not present
in $W$. Since each function $t_{\mathrm{ind}}(F,\\_)$ is well-defined and
continuous on $(\widetilde{\mathcal{W}},\delta_{\Box})$ (see e.g.
[Lovasz:lngl, Lemma 10.23]), the set $\mathbf{FORB}(W)$ is closed and depends
only on the weak isomorphism class $\widetilde{W}$.

The set $\mathbf{RN}(W)$ consists, roughly speaking, of graphons that can be
formed from $W$ by changing the measure on the interval $[0,1]$. Formally,
suppose that $\mu$ is a Borel probability measure on $[0,1]$ with
$\mu\ll\lambda$, that is, $\mu$ is absolutely continuous with respect to the
Lebesgue measure $\lambda$. Let $W_{\mu}$ denote the generalised graphon
$(W,[0,1],\mu)$ in the sense of [Lovasz:lngl, Section 13.1] (see also the
short discussion inside the proof of Lemma 2.3). Even though, $W_{\mu}$ is not
formally an element of ${\mathcal{W}}$, it is known that there is
$U\in{\mathcal{W}}$ that is _weakly isomorphic_ to $W_{\mu}$, meaning that
$\delta_{\Box}(U,W_{\mu})=0$ for the appropriate generalisation of the cut-
distance $\delta_{\Box}$. We define $\mathbf{RN}(W)$ to be the
$\delta_{\Box}$-closure of the set of graphons $U$ for which there is a Borel
probability measure $\mu$ on $[0,1]$ with $\mu\ll\lambda$ such that $U$ is
weakly isomorphic to $W_{\mu}$.

For $Y\subseteq\widetilde{\mathcal{W}}$ we denote as $\chi_{Y}$ the function
that is $0$ on $Y$ and $\infty$ otherwise. In the case when $Y=\\{W\\}$ is a
singleton, we write simply $\chi_{W}$. Note that $\chi_{Y}$ is lsc whenever
$Y$ is $\delta_{\Box}$-closed.

Let us illustrate the above notions on a simple example. Namely, suppose that
$W$ is a _$k$ -step graphon_, meaning that there is a partition
$[0,1]=A_{1}\cup\dots\cup A_{k}$ into measurable sets such that $W$ is a
constant $p_{i,j}$ on each product $A_{i}\times A_{j}$, $i,j\in[k]$. Let us
assume additionally that each $A_{i}$ has positive measure. It is easy to see
that $\mathbf{RN}(W)$ consists exactly of weak equivalence classes of $k$-step
graphons that can be produced from $W$ by stretching or shrinking
$A_{1},\dots,A_{k}$. In other words, every element of $\mathbf{RN}(W)$ comes
from a $k$-step graphon $U$ with parts $B_{1},\dots,B_{k}$ such that the
(constant) value of $U$ on $B_{i}\times B_{j}$ is the same as the value of $W$
on $A_{i}\times A_{j}$ for every $i,j\in[k]$. The structure of the set
$\mathbf{FORB}(W)$ is more complicated. For example, if $p_{i,i}\not=0$ for
some $i\in[k]$, then every graph has positive induced density in $W$ and thus
$\mathbf{FORB}(W)=\widetilde{\mathcal{W}}$ consists of all graphons. If
$p_{i,i}=0$ and $p_{i,j}\in(0,1)$ for every $i\not=j$ then $\mathbf{FORB}(W)$
can be shown to consist of $\widetilde{U}\in\widetilde{\mathcal{W}}$ such that
$U$ has _chromatic number_ at most $k$, that is, $U$ is 0 a.e. on all diagonal
products $B_{i}\times B_{i}$ for some measurable partition $B_{1}\cup\dots\cup
B_{k}$ of $[0,1]$. Suppose that we consider an LDP for
$(\widetilde{\mathbb{R}}_{n,W})_{n\in{\mathbbm{N}}}$ for some speed $s$.
Informally, the price in probability to change substantially the number of
sampled $x_{i}\in[0,1]$ that are in some part $A_{t}$ is
${\mathrm{e}}^{-\Theta(n)}$ while analogous anti-concentration probability for
edge rounding is ${\mathrm{e}}^{-\Theta(n^{2})}$. Thus at speed $s(n)=o(n)$,
we do not see any deviations in the limit and the rate function is $\chi_{W}$.
For speed $s(n)\in\omega(n)\cap o(n^{2})$ (that is, $s(n)/n\to\infty$ and
$s(n)/n^{2}\to 0$ as $n\to\infty$), any vertex distribution per parts $A_{t}$
is “for free” (while edge rounding deviations are still “too expensive”), so
LDP sees exactly $\mathbf{RN}(W)$. Likewise, for speed $\omega(n^{2})$, every
possible sampled graph must admit a vertex partition $V_{1}\cup\dots\cup
V_{k}$ such that for each $(i,j)\in[k]^{2}$ with $p_{i,j}=0$ (resp.
$p_{i,j}=1$) all pairs in $V_{i}\times V_{j}$ are non-edges (resp. edges,
apart the diagonal pairs if $i=j$) and each such graph occurs with probability
at least ${\mathrm{e}}^{-O(n^{2})}$; the corresponding set of graphons in the
limit as $n\to\infty$ is easily seen to be $\mathbf{FORB}(W)$.

Staying with the above $k$-step example $W$, it is not hard to derive from the
classical theorem of Sanov [Sanov57] (see e.g. [DemboZeitouni10ldta, Theorem
2.1.10]) that $(\widetilde{\mathbb{R}}_{n,W})_{n\in{\mathbbm{N}}}$ admits an
LDP for speed $n$ with rate function $I(U)$ which is equal to $\infty$ unless
$U$ is a $k$-step graphon, say with steps $B_{1},\dots,B_{k}$, when

$I(U):=\min_{\sigma}\sum_{i\in[k]}\lambda(B_{\sigma(i)})\log\left(\frac{\lambda(B_{\sigma(i)})}{\lambda(A_{i})}\right),$

with the minimum taken over all permutations $\sigma$ of $[k]$ such that, for
all $i,j\in[k]$, the value of $U$ on $B_{\sigma(i)}\times B_{\sigma(j)}$ is
the same as the value of $W$ on $A_{i}\times A_{j}$ (and $I(U)$ is defined to
be $\infty$ if no such $\sigma$ exists). The natural (and correct) guess of
the rate function for general $W\in\mathcal{W}$ for speed $s(n)=n$ is

$K_{W}(\widetilde{U}):=\inf\left\\{\int_{[0,1]}\ell\\!\left(\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}\right)\,\mathrm{d}\lambda:\delta_{\Box}(\widetilde{U},W_{\mu})=0,\
\mu\ll\lambda\right\\},\quad U\in\mathcal{W},$ (7)

where $\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}$ is the Radon–Nikodym
derivative and $\mu$ is taken over Borel probability measures absolutely
continuous with respect to the Lebesgue measure $\lambda$ (and, as everywhere
in the paper, $\ell\\!\left(s\right):=x\log x$ is the function defined in
(4)). Proposition 3.1e shows that the function $K$ is lsc on
$(\widetilde{\mathcal{W}},\delta_{\Box})$.

Our first result settles LDP for $\widetilde{\mathbb{R}}_{n,W}$ for every
speed other than $\Theta(n^{2})$. We use the standard asymptotic notation
($o$, $O$, $\omega$, and $\Theta$) as $n\to\infty$.

######  Theorem 1.3.

Take any $W\in{\mathcal{W}}$ and any function $s:{\mathbbm{N}}\to(0,\infty)$
with $s(n)\to\infty$ as $n\to\infty$. We consider the existence of an LDP for
the sequence $(\widetilde{\mathbb{R}}_{n,W})_{n\in{\mathbbm{N}}}$ of measures
on the topological space $(\widetilde{\mathcal{W}},\delta_{\Box})$ with speed
$s$.

  1. (a)

If $s(n)=o(n)$, then there is an LDP with rate function $\chi_{W}$.

  2. (b)

If $s(n)=(c+o(1))n$ for some $c\in(0,\infty)$ then there is an LDP with rate
function $\frac{1}{c}\,K_{W}$.

  3. (c)

If $s(n)\in o(n^{2})\cap\omega(n)$, then there is an LDP with rate function
$\chi_{\mathbf{RN}(W)}$.

  4. (d)

If $s(n)=\omega(n^{2})$, then there is an LDP with rate function
$\chi_{\mathbf{FORB}(W)}$.

It is easy to see that Theorem 1.2 implies an LDP with rate function
$\frac{1}{c}h_{p}$ if $W=p$ a.e. and $s(n)=(c+o(1))n^{2}$.

The results of Theorem 1.3 in the cases when $s(n)=o(n^{2})$ are proved by
first establishing an LDP for _weighted graph sampling_ , where we take
independent uniform elements $x_{1},\dots,x_{n}\in[0,1]$ and output the
corresponding edge weighted complete graph $H$ on $[n]$, where
$w_{H}(\\{i,j\\})$, the weight on the edge $\\{i,j\\}$, is equal to
$W(x_{i},x_{j})$. Let $(\widetilde{\mathbb{H}}_{n,W})_{n\in{\mathbbm{N}}}$ be
the corresponding distribution on $\widetilde{\mathcal{W}}$ induced by taking
the equivalence class $\widetilde{f^{H}}\in\widetilde{\mathcal{W}}$ of the
sampled weighted graph $H$, where $f^{H}$ is the $n$-step graphon with parts
of measure $1/n$ whose values are given by the weights of $H$. Our Lemma 5.3
shows that, for speeds $o(n^{2})$, an LDP for
$(\widetilde{\mathbb{H}}_{n,W})_{n\in{\mathbbm{N}}}$ automatically gives an
LDP for $(\widetilde{\mathbb{R}}_{n,W})_{n\in{\mathbbm{N}}}$ with the same
rate function, and vice versa. Working with
$(\widetilde{\mathbb{H}}_{n,W})_{n\in{\mathbbm{N}}}$ is much more convenient
and we completely resolve the LDP problem for this model in Theorem 4.1. In
general, the original sequence
$(\widetilde{\mathbb{R}}_{n,W})_{n\in{\mathbbm{N}}}$ exhibits a different LDP
behaviour than $(\widetilde{\mathbb{H}}_{n,W})_{n\in{\mathbbm{N}}}$ for speeds
$\Omega(n^{2})$ since the second step (edge rounding) may result in
$\Omega(n^{2})$ “atypically” rounded edges with probability
${\mathrm{e}}^{-\Theta(n^{2})}$. In the case when $W$ is $\\{0,1\\}$-valued
(when each edge weight of $H\sim\widetilde{\mathbb{H}}_{n,W}$ is 0 or 1), the
edge rounding step involves no randomness and
$\widetilde{\mathbb{R}}_{n,W}=\widetilde{\mathbb{H}}_{n,W}$. Thus Theorem 4.1
fully resolves the LDP problem for
$(\widetilde{\mathbb{R}}_{n,W})_{n\in{\mathbbm{N}}}$ for such graphons. More
generally, the LDP problem for
$(\widetilde{\mathbb{R}}_{n,W})_{n\in{\mathbbm{N}}}$ is fully resolved for any
$W$ with $\mathbf{RN}(W)=\mathbf{FORB}(W)$, see the discussion in Section 11.

###  1.5 LDP for step graphons for speed $\Theta(n^{2})$

Here (in Theorem 1.4) we prove an LDP for
$(\widetilde{\mathbb{R}}_{n,W})_{n\in{\mathbbm{N}}}$ and speed
$(c+o(1))n^{2}$, when $W$ is a step graphon. Suppose that $W$ has $k$ non-null
parts $A_{1},\dots,A_{k}$ and its values are encoded by a symmetric $k\times
k$-matrix $\mathbold{p}=(p_{i,j})_{i,j=1}^{k}$. It comes as no surprise that
if we consider large deviations for
$(\widetilde{\mathbb{R}}_{n,W})_{n\in{\mathbbm{N}}}$ at speed $\Theta(n^{2})$
then the rate function depends only on $(p_{i,j})_{i,j\in[k]}$ but not on the
(non-zero) measures of the parts $A_{i}$.

We need some preparation to define the rate function for the given matrix
$\mathbold{p}$. For a non-zero real $k$-vector
$\mathbold{\alpha}=(\alpha_{1},\dots,\alpha_{k})\in[0,\infty)^{k}$, let
$(I_{1}^{(\mathbold{\alpha})},\dots,I_{k}^{(\mathbold{\alpha})})$ denote the
partition of $[0,1]$ into consecutive intervals such that each interval
$I_{i}^{(\mathbold{\alpha})}$ has length
$\alpha_{i}/\|\mathbold{\alpha}\|_{1}$. Also, define the function
$J_{\mathbold{\alpha},\mathbold{p}}:\widetilde{\mathcal{W}}\to[0,\infty)$ by

$J_{\mathbold{\alpha},\mathbold{p}}(\widetilde{U}):=\inf_{V\in\widetilde{U}}\,\frac{1}{2}\sum_{i,j\in[k]}\int_{I_{i}^{(\mathbold{\alpha})}\times
I_{j}^{(\mathbold{\alpha})}}h_{p_{i,j}}(V(x,y))\,\mathrm{d}x\,\mathrm{d}y,\quad
U\in{{\mathcal{W}}}.$ (8)

Note that the function $J_{\mathbold{\alpha},\mathbold{p}}$ will not change if
we multiply the vector $\mathbold{\alpha}$ by any positive scalar. Finally,
define

$R_{\mathbold{p}}(\widetilde{U}):=\inf_{\mathbold{\alpha}\in[0,1]^{k}\atop\alpha_{1}+\ldots+\alpha_{k}=1}J_{\mathbold{\alpha},\mathbold{p}}(\widetilde{U}),\quad
U\in{\mathcal{W}}.$ (9)

######  Theorem 1.4.

Let $W$ be a $k$-step graphon with $k$ non-null parts whose values are encoded
by a symmetric $k\times k$ matrix $\mathbold{p}\in[0,1]^{k\times k}$. Let
$s:{\mathbbm{N}}\to(0,\infty)$ be any function such that, for some
$c\in(0,\infty)$, we have $s(n)=(c+o(1))n^{2}$.

Then the function $R_{\mathbold{p}}:\widetilde{\mathcal{W}}\to[0,\infty]$ is
lower semi-continuous with respect to the metric $\delta_{\Box}$. Moreover,
the sequence of measures $(\widetilde{\mathbb{R}}_{n,W})_{n\in{\mathbbm{N}}}$
on $(\widetilde{\mathcal{W}},\delta_{\Box})$ satisfies an LDP with speed
$s(n)$ and rate function $\frac{1}{c}\,R_{\mathbold{p}}$.

For $k=1$, this gives the LDP result of Chatterjee and Varadhan
[ChatterjeeVaradhan11] (that is, Theorem 1.2).

###  1.6 Stochastic block models

Sampling from a step graphon is closely related to a _stochastic block model_
, which provides another important generalisation of the binomial random graph
${\mathbbm{G}}(n,p)$ and which we define now. Here we are given a symmetric
$k\times k$ matrix $\mathbold{p}=(p_{i,j})_{i,j\in[k]}\in[0,1]^{k\times k}$
with entries in $[0,1]$ and an integer vector
$\mathbold{a}=(a_{1},\dots,a_{k})\in{\mathbbm{N}}_{\geqslant 0}^{k}$, where

${\mathbbm{N}}_{\geqslant 0}:=\\{0,1,2,\ldots\\}$

denotes the set of non-negative integers. The corresponding probability
distribution on $\widetilde{\mathcal{W}}$ is defined as follows. Set $n$ to be
$\|\mathbold{a}\|_{1}=a_{1}+\dots+a_{k}$ and let $(A_{1},\dots,A_{k})$ be the
partition of $[n]$ into $k$ consecutive intervals with $A_{i}$ having $a_{i}$
elements. The random graph ${\mathbbm{G}}(\mathbold{a},\mathbold{p})$ on $[n]$
is produced by making each pair $\\{x,y\\}$ of $[n]$ an edge with probability
$p_{i,j}$ where $i,j\in[k]$ are the indices with $x\in A_{i}$ and $y\in
A_{j}$, with all choices made independently of each other. Output the weak
isomorphism class $\widetilde{f^{G}}\in\widetilde{\mathcal{W}}$ of the graphon
$f^{G}$ of the generated graph $G\sim{\mathbbm{G}}(\mathbold{a},\mathbold{p})$
on $[n]$. Let $\widetilde{\mathbb{P}}_{\mathbold{a},\mathbold{p}}$ be the
correponding (discrete) probability measure on $\widetilde{\mathcal{W}}$.

Let us point out the difference between the random graphs
${\mathbbm{G}}((a_{1},\dots,a_{k}),(p_{i,j})_{i,j\in[k]})$ and
${\mathbbm{G}}(a_{1}+\dots+a_{k},W)$ where $W$ is a $k$-step graphon whose
values are encoded by a matrix $(p_{i,j})_{i,j\in[k]}$. In the former model,
we have exactly $a_{i}$ vertices in the $i$-th block for each $i\in[k]$. In
the latter model, each vertex is put into one of the $k$ blocks with the
probabilities given by the measures of $A_{1},\dots,A_{k}$, independently of
the other vertices; thus the number of vertices in each block is binomially
distributed. Of course, if $k=1$, then both models coincide with the binomial
random graph ${\mathbbm{G}}(a_{1},p_{1,1})$.

Recently, Borgs, Chayes, Gaudio, Petti and Sen [BCGPS] extended Theorem 1.2 to
$k$-block stochastic models as follows. For a real-valued function $I$ on a
topological space $X$, let its _lower semi-continuous regularization_ be

$I_{\mathrm{lsc}}(x):=\sup\left\\{\inf_{y\in G}I(y):G\ni x\mbox{ and
$G\subseteq X$ is open}\right\\},\quad x\in X.$ (10)

As it is well-known (see e.g. [RassoulaghaSeppelainen14cldigm, Lemma 2.8]),
$I_{\mathrm{lsc}}$ is lower semi-continuous and, in fact, $I_{\mathrm{lsc}}$
is the largest lsc function with $I_{\mathrm{lsc}}\leqslant I$.

######  Theorem 1.5 (Borgs, Chayes, Gaudio, Petti and Sen [BCGPS]).

Let $\mathbold{\alpha}\in{\mathbbm{N}}_{\geqslant 0}^{k}$ be a non-zero
integer $k$-vector and let $\mathbold{p}\in[0,1]^{k\times k}$ be a symmetric
$k\times k$ matrix. Then the sequence of measures
$(\widetilde{\mathbb{P}}_{n\mathbold{\alpha},\mathbold{p}})_{n\in{\mathbbm{N}}}$
on $(\widetilde{\mathcal{W}},\delta_{\Box})$ satisfies an LDP with speed
$(n\,\|\mathbold{\alpha}\|_{1})^{2}$ and rate function
$(J_{\mathbold{\alpha},\mathbold{p}})_{\mathrm{lsc}}$.∎

Our paper uses Theorem 1.5 to derive Theorem 1.4, even though we initially
proved Theorem 1.4 independently of the work by Borgs et al [BCGPS], by first
proving an LDP for what we call _$k$ -coloured graphons_ (that are defined in
Section 7). Since our original proof of Theorem 1.4 is quite long and shares
many common steps with the proof from [BCGPS] (with both being built upon the
method of Chatterjee and Varadhan [ChatterjeeVaradhan11]), we decided to
derive Theorem 1.4 from the results in [BCGPS] with a rather short proof. An
extra benefit of this approach is that we also improve two aspects of the LDP
of Borgs et al [BCGPS] as follows.

First, we prove that the function
$J_{\mathbold{\alpha},\mathbold{p}}:\widetilde{\mathcal{W}}\to[0,\infty]$ is
lower semi-continuous (so, in particular, there is no need to take the lower
semi-continuous regularization in Theorem 1.5):

######  Theorem 1.6.

For every symmetric matrix ${\mathbold p}\in[0,1]^{k\times k}$ and every non-
zero real $k$-vector $\mathbold{\alpha}\in[0,\infty)^{k}$, the function
$J_{\mathbold{\alpha},\mathbold{p}}:\widetilde{\mathcal{W}}\to[0,\infty]$ is
lower semi-continuous with respect to the metric $\delta_{\Box}$.

Note that if no entry of the fixed matrix $\mathbold{p}$ is 0 or 1 then the
lower semi-continuity of $J_{\mathbold{\alpha},\mathbold{p}}$ follows from a
(more general) result of Markering [Markering23, Theorem 2.3].

Second, we extend Theorem 1.5 by allowing the fraction of vertices assigned to
a part to depend on $n$ as long as it converges to any finite (possibly
irrational) limit.

######  Theorem 1.7.

Fix any symmetric $k\times k$ matrix $\mathbold{p}\in[0,1]^{k\times k}$ and a
non-zero real $k$-vector
$\mathbold{\alpha}=(\alpha_{1},\dots,\alpha_{k})\in[0,\infty)^{k}$. Let

$\mathbold{a}_{n}=(a_{n,1},\dots,a_{n,k})\in{\mathbbm{N}}_{\geqslant
0}^{k},\quad\mbox{for $n\in{\mathbbm{N}}$},$

be arbitrary non-zero integer $k$-vectors such that
$\lim_{n\to\infty}a_{n,i}/n=\alpha_{i}$ for each $i\in[k]$. Then the sequence
of measures
$(\widetilde{\mathbb{P}}_{\mathbold{a}_{n},\mathbold{p}})_{n\in{\mathbbm{N}}}$
on $(\widetilde{\mathcal{W}},\delta_{\Box})$ satisfies an LDP with speed
$\|\mathbold{a}_{n}\|_{1}^{2}$ and rate function
$J_{\mathbold{\alpha},\mathbold{p}}$.

Note that an earlier (unpublished) manuscript by the authors
[GrebikPikhurko:LDPStepW] contained Theorems 1.6 and 1.7, with the same proofs
as are presented here. Thus it is fully superseded by this paper.

###  1.7 Organisation of the paper

This paper is organised as follows.

In Section 2 we give further definitions (repeating some definitions from the
Introduction) and provide some standard or easy results that we will need
later.

In Section 3, we present basic results concerning the function $K_{W}$ that
was defined in (7). In Section 4, we resolve all cases of the LDP problem for
the measures $\widetilde{\mathbb{H}}_{n,W}$ coming from the weighted graph
sampling. In Section 5, we present some basics of exponential equivalence and
show that the sequences $(\widetilde{\mathbb{H}}_{n,W})_{n\in{\mathbbm{N}}}$
and $(\widetilde{\mathbb{R}}_{n,W})_{n\in{\mathbbm{N}}}$ are exponentially
equivalent for any speed $s(n)=o(n^{2})$. This automatically gives LDPs for
$(\widetilde{\mathbb{R}}_{n,W})_{n\in{\mathbbm{N}}}$ in Theorem 1.3 for speeds
$o(n^{2})$. The remaining unproved case of Theorem 1.3, namely when
$s(n)/n^{2}\to\infty$ is done in Section 6.

The rest of the paper deals with speeds in $\Theta(n^{2})$. Section 7
introduces $k$-coloured graphons and proves a compactness result. This result
is used in Section 8 to prove that the functions
$J_{\mathbold{a},\mathbold{p}}$ and $R_{\mathbold{p}}$ are lower semi-
continuous (with this result stated as Theorem 8.4). The large deviation
principles stated in Theorems 1.7 and 1.4 are proved in Section 9 and 10
respectively.

##  2 Preliminaries

Recall that ${\mathbbm{N}}$ (resp. ${\mathbbm{N}}_{\geqslant 0}$) denotes the
set of positive (resp. non-negative) integers. For $n\in{\mathbbm{N}}$, we
write $[n]$ for the set $\\{1,\dots n\\}$. Also, recall that
$\ell\\!\left(x\right):=x\log x$ for $x\in[0,\infty]$ was defined by (4). All
logarithms in this paper are base ${\mathrm{e}}$.

Let $X$ be a set. Its _indicator function_ ${\mathbbm{1}}_{X}$ assumes value
$1$ for every $x\in X$ and 0 otherwise. Recall the related function $\chi_{X}$
which is $0$ on $X$ and $\infty$ elsewhere. The $k$-fold product of $X$ is
denoted by $X^{k}$. Also, ${X\choose k}:=\\{Y\subseteq X:|Y|=k\\}$ denotes the
set of all $k$-subsets of $X$.

A measurable space $(\Omega,{\mathcal{A}})$ is called _standard_ if there is a
Polish topology on $\Omega$ whose Borel $\sigma$-algebra is equal to
${\mathcal{A}}$. Given a measure $\mu$ on $(\Omega,{\mathcal{A}})$, we call a
subset of $\Omega$ _$\mu$ -measurable_ (or just _measurable_ if $\mu$ is
understood) if it belongs to the _completion_ of ${\mathcal{A}}$ by $\mu$,
that is, the $\sigma$-algebra generated by ${\mathcal{A}}$ and $\mu$-null
sets. We will usually omit $\sigma$-algebras from our notation.

Unless specified otherwise, the interval $[0,1]$ of reals is always equipped
with the Lebesgue measure, denoted by $\lambda$. By $\mu^{\oplus k}$ we denote
the completion of the $k$-th power of a measure $\mu$. For example,
$\lambda^{\oplus k}$ is the Lebesgue measure on $[0,1]^{k}$.

Denote as ${\bf A}^{(k)}$ the set of all ordered partitions of $[0,1]$ into
$k$ measurable sets. For a non-zero vector
$\mathbold{\alpha}=(\alpha_{1},\dots,\alpha_{k})\in[0,\infty)^{k}$, we let
${\bf A}^{(\mathbold{\alpha})}\subseteq{\bf A}^{(k)}$ to be the set of all
ordered partitions of $[0,1]$ into $k$ measurable sets such that the $i$-th
set has Lebesgue measure exactly $\alpha_{i}/\|\mathbold{\alpha}\|_{1}$. Also,
$(I_{1}^{(\mathbold{\alpha})},\dots,I_{k}^{(\mathbold{\alpha})})\in{\bf
A}^{(\mathbold{\alpha})}$ denotes the partition of $[0,1]$ into consecutive
intervals whose lengths are given by
$\mathbold{\alpha}/\|\mathbold{\alpha}\|_{1}$ (where each dividing point is
assigned to e.g. its right interval for definiteness). If
$\mathbold{a}\in(0,\infty)^{n}$ consists of $n$ equal entries, then we
abbreviate $I_{j}^{(\mathbold{\alpha})}$ to $I^{n}_{j}$. In other words,
$I^{n}_{j}:=[\frac{j-1}{n},\frac{j}{n})$ for $j\in[n-1]$ and
$I^{n}_{n}:=\left[\frac{n-1}{n},1\right]$.

We will need the following result.

######  Theorem 2.1.

For every two atomless standard measure spaces $(\Omega,\mu)$ and
$(\Omega^{\prime},\mu^{\prime})$, and Borel subsets $A\subseteq\Omega$ and
$A^{\prime}\subseteq\Omega^{\prime}$ with
$0<\mu(A)=\mu^{\prime}(A^{\prime})<\infty$, there is a measure-preserving
Borel isomorphism between $A$ and $A^{\prime}$.

###### Proof.

The case when $A=\Omega$ and $A^{\prime}=\Omega^{\prime}$ amounts to the
Isomorphism Theorem for Measure Spaces, whose proof can be found in e.g.
[Srivastava98cbs, Theorem 3.4.23]. The general case follows by restricting
everything to $A$ and $A^{\prime}$, and noting that the obtained measure
spaces are still standard by e.g. [Srivastava98cbs, Theorem 3.2.4].∎

We write $\mathcal{G}_{n}$ for the set of graphs on the vertex set $[n]$.
Thus, for example, $|\mathcal{G}_{n}|=2^{{n\choose 2}}$. For a graph
$G=(V,E)$, its _complement_ is $\overline{G}:=\left(V,{V\choose 2}\setminus
E\right)$.

Also, let $\mathcal{H}_{n}$ denote the set of all edge-weighted complete
graphs on the vertex set $[n]$ with weights from $[0,1]$. If
$H\in\mathcal{H}_{n}$, then we write $w_{H}:{[n]\choose 2}\to[0,1]$ for the
edge-weight function of $H$, often abbreviating $w_{H}(\\{i,j\\})$ to
$w_{H}(i,j)$.

###  2.1 Graphons

A _graphon_ $U$ is a function $U:[0,1]^{2}\to[0,1]$ which is _symmetric_ (that
is, $U(x,y)=U(y,x)$ for all $x,y\in[0,1]$) and _measurable_ (that is, for
every $a\in{\mathbbm{R}}$, the level set $\\{W\leqslant a\\}$ is a Lebesgue
measurable subset of $[0,1]^{2}$). Recall that we denote the set of all
graphons by $\mathcal{W}$. We call a graphon $W$ _constant_ if there is
$c\in[0,1]$ such that the measure of $W^{-1}(c)\subseteq[0,1]^{2}$ is 1, that
is, if $W$ is a constant function apart from a set of measure 0.

We define the _cut-norm_ $d_{\Box}:{\mathcal{W}}^{2}\to[0,1]$ by

$d_{\Box}(U,V):=\sup_{A,B\subseteq[0,1]}\left|\int_{A\times
B}\left(U-V\right)\,\mathrm{d}\lambda^{\oplus 2}\right|,\quad
U,V\in\mathcal{W},$ (11)

where the supremum is taken over all pairs of measurable subsets of $[0,1]$.
For a function $\phi:[0,1]\to[0,1]$ and a graphon $U$, the _pull-back_
$U^{\phi}$ of $U$ along $\phi$ is defined by

$U^{\phi}(x,y):=U(\phi(x),\phi(y)),\quad x,y\in[0,1].$

The _cut-distance_ $\delta_{\Box}:{\mathcal{W}}^{2}\to[0,1]$ can be defined as

$\delta_{\Box}(U,V):=\inf_{\phi,\psi}d_{\Box}(U^{\phi},V^{\psi}),$ (12)

where the infimum is taken over all measure-preserving maps
$\phi,\psi:[0,1]\to[0,1]$ (then the pull-backs $U^{\phi}$ and $V^{\psi}$ are
necessarily measurable functions, see e.g. Lemma 2.3). We refer the reader to
[Lovasz:lngl, Section 8.2] for more details and, in particular, to
[Lovasz:lngl, Theorem 8.13] for some alternative definitions that give the
same distance. It can be easily verified that $\delta_{\Box}$ is a pseudo-
metric on ${\mathcal{W}}$. Recall that we denote the metric quotient by
$\widetilde{\mathcal{W}}$ and the equivalence class of $U\in\mathcal{W}$ by
$\widetilde{U}$. For brevity, we may write $W$ instead of $\widetilde{W}$,
even if the stated property is clearly independent of the choice of a
representative in $\widetilde{W}$.

Define the _homomorphism density_ of a finite graph $F$ on $[n]$ in a graphon
$W$ by

$t(F,W):=\int_{[0,1]^{n}}\prod_{\\{i,j\\}\in
E(F)}W(x_{i},x_{j})\,\mathrm{d}\lambda^{\oplus n}.$

This can be easily related to the induced homomorphism density defined in (6):
namely, $t(F,W)$ is the sum of $t_{\mathrm{ind}}(F^{\prime},W)$ over all
graphs $F^{\prime}$ on $[n]$ with $E(F^{\prime})\supseteq E(F)$. Also, the
random $n$-vertex sample ${\mathbbm{G}}(n,W)$ (and the corresponding measure
${\mathbbm{R}}_{n,W}$ on $\mathcal{W}$) can be equivalently defined as the
random graph on $[n]$ taking each possible value $F$ with probability
$t_{\mathrm{ind}}(F,W)$.

We will need the following auxiliary results. The first one, due to Lovász and
Szegedy [LovaszSzegedy07gafa]*Theorem 5.1 (see also [Lovasz:lngl, Theorem
9.23]), states that the metric space $(\widetilde{\mathcal{W}},\delta_{\Box})$
is compact. This result is also the special case $k=1$ of our more general
Theorem 7.1 whose proof closely follows that of [LovaszSzegedy07gafa] and is
sketched here.

The next result is a consequence of the Counting Lemma and the Inverse
Counting Lemma in Borgs et al [BCLSV08, Theorem 2.7(a)–(b)] (see also
[Lovasz:lngl, Lemma 10.32 and Theorem 11.3]). It gives that the
$\delta_{\Box}$-topology on $\widetilde{\mathcal{W}}$ is generated by the
homomorphism density maps $W\mapsto t(F,W)$ over all graphs $F$.

######  Theorem 2.2.

A sequence of graphons $(W_{n})_{n\in{\mathbbm{N}}}$ converges to
$W\in\mathcal{W}$ in the cut-distance if and only if
$\lim_{n\to\infty}t(F,W_{n})=t(F,W)$ for every graph $F$.∎

We will also need the following result whose proof we could not find in the
literature.

######  Lemma 2.3.

Let $U$ be a graphon and $\phi:[0,1]\to[0,1]$ be a measurable function such
that the _push-forward measure_ $\phi_{*}\lambda$ (defined by
$(\phi_{*}\lambda)(X):=\lambda(\phi^{-1}(X))$ for measurable
$X\subseteq[0,1]$) satisfies $\phi_{*}\lambda\ll\lambda$, that is,
$\phi_{*}\lambda$ is absolutely continuous with respect to the Lebesgue
measure $\lambda$. Then $U^{\phi}$ is a graphon. Moreover, if the Radon-
Nikodym derivative
$D:=\frac{\,\mathrm{d}(\phi_{*}\lambda)}{\,\mathrm{d}\lambda}$ satisfies
$D(x)\leqslant 1+\epsilon$ for $\lambda$-a.e. $x\in[0,1]$ then

$\delta_{\Box}(U,U^{\phi})\leqslant 2\epsilon.$ (13)

###### Proof.

The function $U^{\phi}:[0,1]^{2}\to[0,1]$ is clearly symmetric so we have to
show that it is measurable. Since the pre-image under $\phi$ of any
$\lambda$-null set is again $\lambda$-null by our assumption
$\phi_{*}\lambda\ll\lambda$, there is a Borel map $\psi:[0,1]\to[0,1]$ such
that the set

$X:=\\{x\in[0,1]:\psi(x)\not=\phi(x)\\}$

is $\lambda$-null. (For a proof, see e.g. [Cohn13mt, Proposition 2.2.5].) Take
any $r\in{\mathbbm{R}}$. The set

$A:=\\{(x,y)\in[0,1]^{2}:U(x,y)\leqslant r\\}$

is measurable so by e.g. [Cohn13mt, Proposition 1.5.2] there are
$B,N\subseteq[0,1]^{2}$ such that $B$ is Borel, $N$ is $\lambda^{\oplus
2}$-null and $A\bigtriangleup B\subseteq N$, where $A\bigtriangleup
B:=(A\setminus B)\cup(B\setminus A)$ denotes the _symmetric difference_ of the
sets $A$ and $B$. The pre-image of $N$ under the Borel map $\psi^{\oplus
2}(x,y):=(\psi(x),\psi(y))$ is also $\lambda^{\oplus 2}$-null for otherwise
this would contradict the absolute continuity $(\phi_{*}\lambda)^{\oplus
2}\ll\lambda^{\oplus 2}$ (which follows from $\phi_{*}\lambda\ll\lambda$ by
the Fubini-Tonelli Theorem for Complete Measures). Thus the level set
$\\{U^{\phi}\leqslant r\\}$ is Lebesgue measurable since its symmetric
difference with the Borel set $(\psi^{\oplus 2})^{-1}(B)$ is a subset of the
null set $(\psi^{\oplus 2})^{-1}(N)\cup(X\times[0,1])\cup([0,1]\times X)$. As
$r\in{\mathbbm{R}}$ was arbitrary, $U^{\phi}$ is a measurable function and
thus a graphon.

For the second part, it will be convenient to use the following generalisation
of a graphon. Namely, by a _generalised graphon_ we mean a triple
$(V,\Omega,\mu)$ where $(\Omega,\mu)$ is an atomless standard probability
space and $V:(\Omega^{2},\mu^{\oplus 2})\to[0,1]$ is a symmetric measurable
function. In the special case $(\Omega,\mu)=([0,1],\lambda)$ we get the
(usual) notion of a graphon. Most definitions and results extend with obvious
modifications from graphons to generalised graphons (see [Lovasz:lngl, Chapter
13.1] for details). For example, the $n$-vertex random sample from
$(V,\Omega,\mu)$ is obtained by taking $\mu$-distributed
$x_{1},\dots,x_{n}\in\Omega$ and making $\\{i,j\\}$ an edge with probability
$V(x_{i},x_{j})$ with all choices being independent. In particular, we will
need the facts that if $(V,\Omega,\mu)$ is a generalised graphon and
$\phi:(\Omega^{\prime},\mu^{\prime})\to(\Omega,\mu)$ is a measure-preserving
map between standard probability spaces, then the function $V^{\phi}$ is
measurable (which can be proved by adapting the proof of the first part of the
lemma) and

$\delta_{\Box}((V,\Omega,\mu),(V^{\phi},\Omega^{\prime},\mu^{\prime}))=0,$
(14)

where we define $V^{\phi}(x,y):=V(\phi(x),\phi(y))$ for
$x,y\in\Omega^{\prime}$ and $\delta_{\Box}$ is the extension of the cut-
distance to generalised graphons via the obvious analogues of (11) and (12).

Let us return to the proof of the second part of the lemma. We can assume that
the set $\\{x\in[0,1]:D(x)\not=1\\}$ has positive measure for otherwise $\phi$
is a measure-preserving map and $\delta_{\Box}(U,U^{\phi})=0$ by (14), as
required. Let $(V,[0,1]^{2},\lambda^{\oplus 2})$ be the generalised graphon
defined by $V((x,y),(x^{\prime},y^{\prime})):=U(x,x^{\prime})$, for
$x,y,x^{\prime},y^{\prime}\in[0,1]$. Thus $V=U^{\pi}$, where
$\pi:[0,1]^{2}\to[0,1]$ is the (measure-preserving) projection on the first
coordinate. By (14), it holds that

$\delta_{\Box}((V,[0,1]^{2},\lambda^{\oplus 2}),U)=0.$

By changing $D$ on a $\lambda$-null set, we can make it a Borel function with
$D(x)\leqslant 1+\epsilon$ for every $x\in[0,1]$. Then

$\Omega:=\\{(x,y)\in[0,1]\times{\mathbbm{R}}:0\leqslant y\leqslant D(x)\\}$

is a Borel subset of $[0,1]\times{\mathbbm{R}}$ (see e.g. [Cohn13mt, Example
5.3.1]) and thus induces a standard measurable space. Let $\mu$ be the
restriction of the Lebesgue measure on ${\mathbbm{R}}^{2}$ to $\Omega$. Define
$W:\Omega^{2}\to[0,1]$ by $W((x,y),(x^{\prime},y^{\prime})):=U(x,x^{\prime})$
for $(x,y),(x^{\prime},y^{\prime})\in\Omega$. Thus $U^{\phi}$ and
$(W,\Omega,\mu)$ are measure-preserving pull-backs of the generalised graphon
$(U,[0,1],\phi_{*}\mu)$ along respectively the map $\phi$ and the projection
$\Omega\to[0,1]$ on the first coordinate. Therefore we have by (14) and the
Triangle Inequality for $\delta_{\Box}$ that

$\delta_{\Box}(U^{\phi},(W,\Omega,\mu))\leqslant\delta_{\Box}(U^{\phi},(U,[0,1],\phi_{*}\mu))+\delta_{\Box}((U,[0,1],\phi_{*}\mu),(W,\Omega,\mu))=0.$

Thus it suffices to show that the cut-distance $\delta_{\Box}$ between
$(V,[0,1]^{2},\lambda^{\oplus 2})$ and $(W,\Omega,\mu)$ is at most
$2\epsilon$. The functions $V$ and $W$ and the measures $\lambda^{\oplus 2}$
and $\mu$ coincide on $X^{2}$, where $X:=[0,1]^{2}\cap\Omega$. Since $D\not=1$
on a set of positive measure, it holds that $\mu(X)<1$. The Borel subsets
$[0,1]^{2}\setminus X$ and $\Omega\setminus X$ of ${\mathbbm{R}}^{2}$ have the
same positive Lebesgue measure and thus, by Theorem 2.1, there is a Borel
measure-preserving bijection $\psi$ between them. By letting $\psi$ be the
identity function on $X$, we get a Borel measure-preserving bijection
$\psi:\Omega\to[0,1]^{2}$. Since $D\leqslant 1+\epsilon$, we have that
$\Omega\setminus X\subseteq[0,1]\times[1,1+\epsilon]$ has measure at most
$\epsilon$. The function $W$ and the pull-back $V^{\psi}$, as maps
$\Omega^{2}\to[0,1]$, coincide on the set $X^{2}$ of measure at least
$(1-\epsilon)^{2}\geqslant 1-2\epsilon$. It follows that the
$d_{\Box}$-distance between them is at most $2\epsilon$. (Indeed, when we
compute it via the analogue of (11), the integrand is bounded by 1 in absolute
value and is non-zero on a set of measure at most $2\epsilon$.) This finishes
the proof of the lemma.∎

Informally speaking, the following result states that if we delete a small
subset of $[0,1]$ and stretch the rest of a graphon uniformly then the new
graphon is close to the original one.

######  Lemma 2.4.

Let $U\in{\mathcal{W}}$ be a graphon, $s\in(0,1]$ be a non-zero real and
$\phi:[0,1]\to[0,1]$ be the map that sends $x$ to $sx$. Then $U^{\phi}$ is a
graphon and $\delta_{\Box}(U,U^{\phi})\leqslant 2(\frac{1}{s}-1)$.

###### Proof.

Clearly, the push-forward $\phi_{*}\lambda$ is the uniform probability measure
on $[0,s]$ so the Radon-Nikodym derivative
$\frac{\,\mathrm{d}(\phi_{*}\lambda)}{\,\mathrm{d}\lambda}$ is a.e. $1/s$ on
$[0,s]$ and $0$ on $[s,1]$. The result now follows from Lemma 2.3. ∎

######  Remark 2.5.

Without affecting $(\widetilde{\mathcal{W}},\delta_{\Box})$, we could have
defined a graphon as a Borel symmetric function $[0,1]^{2}\to[0,1]$ and
required that the measure-preserving maps in the definition of $\delta_{\Box}$
are Borel. Then some parts could be simplified (for example, the first claim
of Lemma 2.3 would not be necessary as the function $U^{\phi}$ would be Borel
for every Borel $\phi$). However, we prefer to use the (now standard)
conventions from Lovász’ book [Lovasz:lngl].

###  2.2 Topology

The (pseudo-)metrics on the graphon space $\mathcal{W}$ that we use are
$d_{\Box}$, $d_{1}$ and $d_{\infty}$ with the last two coming from the $L^{1}$
and $L^{\infty}$ norms respectively, where we view $\mathcal{W}$ as a subset
of the vector space of bounded measurable functions on $[0,1]^{2}$. When we
consider $[0,1]^{n}$, we use the $L^{\infty}$-metric, denoting it also by
$d_{\infty}$. Let

$B_{d}(x,r):=\\{y:d(x,y)<r\\}\quad\mbox{and}\quad\overline{B}_{d}(x,r):=\\{y:d(x,y)\leqslant
r\\}$

denote respectively the open and closed balls of radius $r$ around a point $x$
in a metric $d$. If it is clear from the context we write, e.g.,
$B_{\infty}(x,r)$ instead of $B_{d_{\infty}}(x,r)$, etc.

Let $X$ be a topological space and $\mu$ be a Borel probability measure on
$X$. Recall that $L^{1}(X,\mu)$ is the space of all integrable functions,
$L^{\infty}(X,\mu)$ is the space of all essentially bounded functions, $C(X)$
is the space of all continuous functions and $\mathcal{P}(X)$ is the space of
all Borel probability measures on $X$. Some of the topologies that will
consider on these spaces are as follows:

  * •

the _weak ∗ topology on $\mathcal{P}(X)$_, i.e.,
$\nu_{n}\xrightarrow{weak^{*}}\nu$ if and only if
$\int_{X}f\,\mathrm{d}\nu_{n}\to\int_{X}f\,\mathrm{d}\nu$ for every $f\in
C(X)$,

  * •

the _weak ∗ topology on $L^{1}(X,\mu)$_, i.e., $f_{n}\xrightarrow{weak^{*}}f$
if and only if $\int_{X}f_{n}g\,\mathrm{d}\mu\to\int_{X}fg\,\mathrm{d}\mu$ for
every $g\in C(X)$,

  * •

the _$\tau^{k}$ -topology on $\mathcal{P}(X)$_ for given $k\in{\mathbbm{N}}$,
i.e., the coarsest topology such that, for every bounded Borel function
$a:X^{k}\to\mathbb{R}$, the map
$\mu\mapsto\int_{X^{k}}a\,\mathrm{d}\mu^{\oplus k}$ is continuous,

  * •

the _weak topology on $L^{1}(X,\mu)$_, i.e., $f_{n}\xrightarrow{weak}f$ if and
only if $\int_{X}f_{n}g\,\mathrm{d}\mu\to\int_{X}fg\,\mathrm{d}\mu$ for every
$g\in L^{\infty}(X,\mu)$.

By the _weak_ topology on $\\{\mu\in\mathcal{P}(X):\mu\ll\mu\\}$, we will mean
the topology inherited from the weak topology on $L^{1}(X,\mu)$ via the
natural embedding $\mu\mapsto\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\mu}$. On this
set, the weak topology coincides with the $\tau^{1}$-topology, since every
measurable function can be made Borel by changing it on a null-set. Also, note
that if we view each element $f$ of $L^{1}(X,\mu)$ as a Borel measure
$f\,\mathrm{d}\mu$ defined by
$(f\,\mathrm{d}\mu)(A):=\int_{A}f(x)\,\mathrm{d}\mu(x)$ on $X$, then on the
intersection with $\mathcal{P}(X)$, the corresponding weak∗ topologies
coincide.

Some classical results that we will need are collected in Appendix A.

###  2.3 Some general results on LDP

Here we present some results from the theory of large deviations that we will
need in this paper. Recall that the general definition of a large deviation
principle (LDP) is given in Definition 1.1.

If $X$ is a Hausdorff topological space, then $I:X\to[0,\infty]$ is called a
_good rate function_ if, for every $a\in[0,\infty)$, the level set
$I^{-1}([0,a])$ is compact. (In particular, $I$ is lsc.)

The proof of the following well-known result can be found in e.g.
[DemboZeitouni10ldta]*Theorem 4.2.1.

######  Theorem 2.6 (Contraction Principle).

Let $X$ and $Y$ be Hausdorff topological spaces, $(\mu_{n})_{n\in\mathbb{N}}$
be a sequence of Borel probability measures on $X$, $I:X\to[0,\infty]$ be a
good rate function, $f:X\to Y$ be a continuous function and let
$s(n)\to\infty$ as $n\to\infty$. If $(\mu_{n})_{n\in\mathbb{N}}$ satisfies an
LDP on $X$ with speed $s$ and rate function $I$, then the sequence
$(f_{*}\mu_{n})_{n\in\mathbb{N}}$ of the push-forward measures on $Y$
satisfies an LDP with speed $s$ and rate function $I^{\prime}$, where

$I^{\prime}(y):=\inf\\{I(x):f(x)=y\\}.$

Moreover, $I^{\prime}$ is a good rate function.∎

Let us state a weaker version of a result of Dawson–Gärtner [DawsonGartner87]
(whose proof can be found also in e.g [DemboZeitouni10ldta]*Theorem 4.6.1)
that suffices for our application.

######  Theorem 2.7 (Dawson–Gärtner).

Let $X$ be a set, $(\tau_{k})_{k\in\mathbb{N}}$ be a sequence of increasing
Hausdorff topologies, $I:X\to[0,\infty]$ be a function that is a good rate
function in $\tau_{k}$ for every $k\in\mathbb{N}$,
$(\mu_{n})_{n\in\mathbb{N}}$ be a sequence of Borel probability measures on
the space $(X,\tau)$ where $\tau$ is the topology generated by
$\bigcup_{k\in\mathbb{N}}\tau_{k}$. Let $s(n)\to\infty$ as $n\to\infty$. If,
for every $k\in\mathbb{N}$, $(\mu_{n})_{n\in\mathbb{N}}$ satisfies LDP on
$(X,\tau_{k})$ with speed $s$ and rate $I$, then $(\mu_{n})_{n\in\mathbb{N}}$
satisfies LDP on $(X,\tau)$ with speed $s$ and rate $I$. Moreover,
$I:(X,\tau)\to[0,\infty]$ is a good rate function.∎

When we will be dealing with LDPs on compact metric spaces, we may use the
following alternative characterisation, that involves only the measures of
(small) balls. Its proof can be found in [Varadhan16ld, Lemma 2.3]; also, the
claimed equivalence follows from [DemboZeitouni10ldta, Theorems 4.1.11 and
4.1.18].

######  Lemma 2.8.

Let $(X,d)$ be a compact metric space, $s:{\mathbbm{N}}\to(0,\infty)$ satisfy
$s(n)\to\infty$, and $I:X\to[0,\infty]$ be a lower semi-continuous function on
$(X,d)$. Then a sequence of Borel probability measures
$(\mu_{n})_{n\in{\mathbbm{N}}}$ on $(X,d)$ satisfies an LDP with speed $s$ and
rate function $I$ if and only if

$\displaystyle\lim_{\eta\to
0}\liminf_{n\to\infty}\frac{1}{s(n)}\,{\log\Big{(}\mu_{n}\big{(}B_{d}(x,\eta)\big{)}\Big{)}}$
$\displaystyle\geqslant$ $\displaystyle-I(x),\quad\mbox{for every $x\in X$,}$
(15) $\displaystyle\lim_{\eta\to
0}\limsup_{n\to\infty}\frac{1}{s(n)}\,{\log\Big{(}\mu_{n}\big{(}\overline{B}_{d}(x,\eta)\big{)}\Big{)}}$
$\displaystyle\leqslant$ $\displaystyle-I(x),\quad\mbox{for every $x\in
X$}.\qed$ (16)

Of course, the validity of (15) and (16) does not depend on whether we take
open or closed balls there; our choice above is made merely for uniformity of
notation.

In fact, under the assumptions of Lemma 2.8, the bounds (1) and (15) (resp.
(2) and (16)) are equivalent to each other. So we will also refer to (15) and
(16) as the _(LDP) lower bound_ and the _(LDP) upper bound_ respectively.

##  3 Properties of the function $K_{W}$

We start with some basic observations concerning the function $K_{W}$ that was
defined in (7).

######  Proposition 3.1.

Let $W,U,V\in{\mathcal{W}}$. Then we have the following:

  1. (a)

$K_{W}$ is non-negative,

  2. (b)

$K_{W}(U)=K_{W}(V)$ whenever $\delta_{\Box}(U,V)=0$,

  3. (c)

$K_{W}(U)=0$ if and only if $\delta_{\Box}(W,U)=0$,

  4. (d)

$K_{W}^{-1}([0,\infty))$ is a dense subset of $\mathbf{RN}(W)$ with respect
the $\delta_{\Box}$-metric,

  5. (e)

$K_{W}:(\widetilde{\mathcal{W}},\delta_{\Box})\to[0,\infty]$ is a lower semi-
continuous function,

  6. (f)

if $W$ is not a constant graphon, then $\mathbf{RN}(W)$ contains at least two
(not weakly isomorphic) graphons and there is $U\in{\mathcal{W}}$ such that
$K_{W}(U)\in(0,\infty)$.

###### Proof.

Recall that $\ell\\!\left(x\right):=x\log(x)$ for $x\in[0,\infty]$. Its
restriction to $[0,\infty)$ is a convex continuous function.

Proof of a. Since $\ell$ is a convex function on $[0,\infty)$ and
$\int\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}\,\mathrm{d}\lambda=1$ for
every probability measure $\mu\ll\lambda$, we have by Jensen’s inequality that
$\int\ell\\!\left(\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}\right)\,\mathrm{d}\lambda\geqslant\ell\\!\left(\int\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}\,\mathrm{d}\lambda\right)=\ell\\!\left(1\right)=0$,
giving the required inequality $K_{W}(U)\geqslant 0$ for every $U$.

Proof of b. This is a trivial consequence of the definition of $K_{W}$, since
the infimum in (7) is taken over the same set in both cases.

Before we proceed with the remaining parts of the proposition, we formulate an
auxiliary claim.

######  Claim 3.2.

Let a measure $\mu$ and a sequence $(\mu_{n})_{n\in{\mathbbm{N}}}$ of measures
in $\\{\nu\in\mathcal{P}([0,1]):\nu\ll\lambda\\}$ satisfy
$\mu_{n}\xrightarrow{weak}\mu$ (that is,
$\frac{d\mu_{n}}{d\lambda}\xrightarrow{weak}\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}$).
Then we have

$\liminf_{n\to\infty}\int_{[0,1]}\ell\\!\left(\frac{\,\mathrm{d}\mu_{n}}{\,\mathrm{d}\lambda}\right)\,\mathrm{d}\lambda\geqslant\int_{[0,1]}\ell\\!\left(\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}\right)\,\mathrm{d}\lambda,\quad\mbox{as
$n\to\infty$}.$

###### Proof.

For $a\in[0,\infty)$ define

$Y_{a}:=\left\\{f\in L^{1}([0,1],\lambda):f\geqslant 0\mbox{ $\lambda$-a.e.},\
\|f\|_{1}\leqslant 1,\
\int_{[0,1]}\ell\\!\left(f\right)\,\mathrm{d}\lambda\leqslant a\right\\}.$

Let us show that for every $a\in[0,\infty)$, the subset $Y_{a}\subseteq
L^{1}([0,1],\lambda)$ is closed in the $L^{1}$-topology. Take any functions
$f_{n}$ in $Y_{a}$ that converge in the $L^{1}$-norm to some $f\in
L^{1}([0,1],\lambda)$ as $n\to\infty$. Of course, $f\geqslant 0$
$\lambda$-a.e. and $\|f\|_{1}\leqslant 1$. By passing to a subsequence, we can
assume that $f_{n}(x)\to f(x)$ for $\lambda$-a.e. $x\in[0,1]$. By the
continuity of the function $\ell$, we have that
$\ell\\!\left(f_{n}(x)\right)\to\ell\\!\left(f(x)\right)$ for $\lambda$-a.e.
$x\in[0,1]$. Since $\ell$ is bounded from below by $-1/{\mathrm{e}}$, it holds
by Fatou’s lemma that

$a\geqslant\liminf_{n\to\infty}\int_{[0,1]}\ell\\!\left(f_{n}\right)\,\mathrm{d}\lambda\geqslant\int_{[0,1]}\left(\liminf_{n\to\infty}\ell\\!\left(f_{n}\right)\right)\,\mathrm{d}\lambda=\int_{[0,1]}\ell\\!\left(f\right)\,\mathrm{d}\lambda.$

Thus $f\in Y_{a}$ and we conclude that the set $Y_{a}$ is closed as required.

Since $\ell$ is a convex function, the set $Y_{a}$ is also convex for every
$a$. Thus, by Mazur’s lemma (Theorem A.4), the set $Y_{a}$ is also weakly
closed.

Let
$a:=\liminf_{n\to\infty}\int_{[0,1]}\ell\\!\left(\frac{\,\mathrm{d}\mu_{n}}{\,\mathrm{d}\lambda}\right)\,\mathrm{d}\lambda$.
Suppose that $a<\infty$ as otherwise the claim holds trivially. For any
$\epsilon>0$ there are infinitely many $n$ with
$\frac{\,\mathrm{d}\mu_{n}}{\,\mathrm{d}\lambda}\in Y_{a+\epsilon}$; thus the
weak limit $\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}$ also belongs to the
weakly closed set $Y_{a+\epsilon}$. Since $\epsilon>0$ was arbitrary, it holds
that $\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}\in Y_{a}$, as desired.∎

Proof of c. If $\delta_{\Box}(U,W)=0$ then $K_{W}(U)\leqslant 0$ (since we can
take $\mu:=\lambda$ in the definition of $K_{W}$) while $K_{W}(U)\geqslant 0$
by Part a, as desired.

For the forward implication, suppose that $K_{W}(U)=0$. By the definition of
$K_{W}$, there is a sequence $(\mu_{n})_{n\in{\mathbbm{N}}}$ of elements of
$\mathcal{P}([0,1])$ such that $\mu_{n}\ll\lambda$,
$\delta_{\Box}(W_{\mu_{n}},U)=0$ for every $n\in{\mathbbm{N}}$, and
$\int\ell\\!\left(\frac{\,\mathrm{d}\mu_{n}}{\,\mathrm{d}\lambda}\right)\\!\,\mathrm{d}\lambda\to
0$ as $n\to\infty$.

Let $k\in{\mathbbm{N}}$. It is easy to see that $\mu_{n}^{\oplus
k}\ll\lambda^{\oplus k}$ and that

$\frac{\,\mathrm{d}\mu_{n}^{\oplus k}}{\,\mathrm{d}\lambda^{\oplus
k}}(x)=\prod_{i\in[k]}\frac{\,\mathrm{d}\mu_{n}}{\,\mathrm{d}\lambda}(x_{i})$

holds for $\lambda^{\oplus k}$-almost every
$x=(x_{1},\dots,x_{k})\in[0,1]^{k}$. A direct use of Fubini-Tonelli’s theorem
gives

$\displaystyle\int_{[0,1]^{k}}\ell\\!\left(\frac{\,\mathrm{d}\mu_{n}^{\oplus
k}}{\,\mathrm{d}\lambda^{\oplus k}}\right)\,\mathrm{d}\lambda^{\oplus k}$
$\displaystyle=$
$\displaystyle\int_{[0,1]^{k}}\left(\prod_{i\in[k]}\frac{\,\mathrm{d}\mu_{n}}{\,\mathrm{d}\lambda}(x_{i})\right)\left(\sum_{i\in[k]}\log\left(\frac{\,\mathrm{d}\mu_{n}}{\,\mathrm{d}\lambda}(x_{i})\right)\right)\,\mathrm{d}\lambda^{\oplus
k}(x)$ $\displaystyle=$ $\displaystyle
k\int_{[0,1]}\ell\\!\left(\frac{\,\mathrm{d}\mu_{n}}{\,\mathrm{d}\lambda}\right)\,\mathrm{d}\lambda,\quad\mbox{for
every $n\in{\mathbbm{N}}$.}$

This tends to $0$ as $n\to\infty$ and thus is bounded. Since
$\ell\geqslant-1/{\mathrm{e}}$, the integrals above remain bounded if we
replace $\ell$ by the non-decreasing function
$G(x):=\max\\{\ell\\!\left(x\right),0\\}$, $x\in[0,\infty]$. By the de la
Vallée-Poussin Theorem (Theorem A.2) applied to the function $G$, the set
$\mathcal{F}:=\\{\frac{\,\mathrm{d}\mu_{n}^{\oplus
k}}{\,\mathrm{d}\lambda^{\oplus k}}:n\in{\mathbbm{N}}\\}$ is uniformly
integrable. Thus, by the Dunford–Pettis Theorem (Theorem A.1) its weak closure
is compact in the weak topology. By the Eberlein–Šmulian Theorem (Theorem A.3)
we can pass to a subsequence such that $\frac{\,\mathrm{d}\mu_{n}^{\oplus
k}}{\,\mathrm{d}\lambda^{\oplus k}}$ weakly converges to
$\frac{d\nu_{k}}{\lambda^{\oplus k}}$ for some
$\nu_{k}\in\mathcal{P}([0,1]^{k})$ with $\nu_{k}\ll\lambda^{\oplus k}$.

By iteratively repeating the above step for each $k=1,2,\dots$ and doing
diagonalisation, we can assume that, for every $k$, it holds that
$\frac{\,\mathrm{d}\mu_{n}^{\oplus k}}{\,\mathrm{d}\lambda^{\oplus
k}}\xrightarrow{weak}\frac{d\nu_{k}}{\lambda^{\oplus k}}$ as $n\to\infty$.

Set $\mu:=\nu_{1}$. Let us show that, for each $k\geqslant 2$, the measures
$\nu_{k}$ and $\mu^{\oplus k}$ are the same. By Dynkin’s Theorem (see e.g.
[Cohn13mt, Corollary 1.6.3]), it is enough to show that these two measures
coincide on each product $A_{1}\times\dots\times A_{k}$ of Borel sets since
such products are closed under intersection and generate the Borel
$\sigma$-algebra of $[0,1]^{k}$. By weak convergence, we have

$\int{\mathbbm{1}}_{A_{1}\times\dots\times
A_{k}}d\nu_{k}=\lim_{n\to\infty}\int{\mathbbm{1}}_{A_{1}\times\dots\times
A_{k}}\,\mathrm{d}\mu_{n}^{\oplus
k}=\lim_{n\to\infty}\prod_{i=1}^{k}\int{\mathbbm{1}}_{A_{i}}\,\mathrm{d}\mu_{n}=\prod_{i=1}^{k}\int{\mathbbm{1}}_{A_{i}}d\mu,$

as desired.

Next we exploit the fact that $\delta_{\Box}$-convergence is equivalent to the
homomorphism densities convergence (Theorem 2.2). For every graph
$F=([k],E(F))$, we have by weak convergence that

$\begin{split}t(F,U)=t(F,W_{\mu_{n}})=&\int_{[0,1]^{{k}}}\frac{\,\mathrm{d}\mu_{n}^{\oplus
k}}{\,\mathrm{d}\lambda^{\oplus k}}(x)\prod_{\\{i,j\\}\in
E(F)}W(x_{i},x_{j})\,\mathrm{d}\lambda^{\oplus k}(x)\\\
\xrightarrow{n\to\infty}&\int_{[0,1]^{{k}}}\frac{\,\mathrm{d}\mu^{\oplus
k}}{\,\mathrm{d}\lambda^{\oplus k}}(x)\prod_{\\{i,j\\}\in
E(F)}W(x_{i},x_{j})\,\mathrm{d}\lambda^{\oplus k}(x)=t(F,W_{\mu}).\end{split}$

Thus $\delta_{\Box}(U,W_{\mu})=0$. It remains to show that $\mu=\lambda$,
i.e., $W_{\mu}=W$. Claim 3.2 gives that
$\int_{[0,1]}\ell\\!\left(\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}\right)\,\mathrm{d}\lambda=0$.
Recall that the proof of Part a shows that this integral is non-negative by
applying Jensen’s inequality to the strictly convex function
$\ell\\!\left(x\right)$. Since we have equality, it must be the case that
$\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}$ is constant $\lambda$-a.e. Thus
the probability measures $\mu$ and $\lambda$ coincide, proving c.

Proof of d. It follows from the definition that
$K_{W}^{-1}([0,\infty))\subseteq\mathbf{RN}(W)$. To show that the former set
is dense, it is enough to show that for every $\mu\in\mathcal{P}([0,1])$ such
that $\mu\ll\lambda$ there is a sequence
$(\mu_{n})_{n\in{\mathbbm{N}}}\subseteq\mathcal{P}([0,1])$ such that
$\delta_{\Box}(W_{\mu_{n}},W_{\mu})\to 0$ and, for every $n\in{\mathbbm{N}}$,
we have $\mu_{n}\ll\lambda$ and $K_{W}(W_{\mu_{n}})<\infty$.

Given $n\in{\mathbbm{N}}$, let
$X_{n}:=\\{x\in[0,1]:\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}(x)\geqslant
n\\}$ and $A_{n}:=[0,1]\setminus X_{n}$. If $\lambda(X_{n})=0$, then we let
$\mu_{n}=\mu$. Otherwise let $\,\mathrm{d}\mu_{n}:=g_{n}\,\mathrm{d}\lambda$,
where we define $g_{n}:[0,1]\to{\mathbbm{R}}$ to be the constant
$\frac{1}{\lambda(X_{n})}\,\int_{X_{n}}\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}\,\mathrm{d}\lambda=\mu(X_{n})/\lambda(X_{n})<\infty$
on $X_{n}$ and let $g_{n}$ be $\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}$ on
$A_{n}$. Then we have $\int_{[0,1]}g_{n}\,\mathrm{d}\lambda=1$ and
$\|g_{n}\|_{\infty}\leqslant\max\\{\mu(X_{n})/\lambda(X_{n}),n\\}<\infty$ for
every $n\geqslant 1$. Also, we can take the measure $\mu_{n}\ll\lambda$ in the
definition of $K_{W}(W_{\mu_{n}})$ as an infimum over a set of measures,
obtaining that

$K_{W}(W_{\mu_{n}})\leqslant\int\ell\\!\left(g_{n}\right)\,\mathrm{d}\lambda\leqslant\ell\\!\left(\max\\{\mu(X_{n})/\lambda(X_{n}),n\\}\right)<\infty.$

Moreover, it is easy to see that $\mu^{\oplus k}(A^{k}_{n})=\mu_{n}^{\oplus
k}(A^{k}_{n})$ tends to $1$ as $n\to\infty$ for every fixed
$k\in{\mathbbm{N}}$. For any graph $F=([k],E(F))$, we have

$\begin{split}t(F,W_{\mu_{n}})=&\int_{A_{n}^{k}}\prod_{\\{i,j\\}\in
E(F)}W(x_{i},x_{j})\,\mathrm{d}\mu_{n}^{\oplus k}(x)+\int_{[0,1]^{k}\setminus
A_{n}^{k}}\prod_{\\{i,j\\}\in E(F)}W(x_{i},x_{j})\,\mathrm{d}\mu_{n}^{\oplus
k}(x)\\\ =&\int_{A_{n}^{k}}\prod_{\\{i,j\\}\in
E(F)}W(x_{i},x_{j})\,\mathrm{d}\mu^{\oplus k}(x)+\int_{[0,1]^{k}\setminus
A_{n}^{k}}\prod_{\\{i,j\\}\in E(F)}W(x_{i},x_{j})\,\mathrm{d}\mu_{n}^{\oplus
k}(x)\\\ \xrightarrow{n\to\infty}&\int_{[0,1]^{k}}\prod_{\\{i,j\\}\in
E(F)}W(x_{i},x_{j})\,\mathrm{d}\mu^{\oplus k}(x)+0\ =\
t(F,W_{\mu})\end{split}$

and the claim follows.

Proof of e. We have to show that the function
$K_{W}:\widetilde{\mathcal{W}}\to[0,\infty]$ is lsc. Take an arbitrary
sequence $(U_{n})_{n\in{\mathbbm{N}}}$ of graphons convergent to a graphon $U$
in the $\delta_{\Box}$-distance. We need to show that
$K_{W}(U)\leqslant\liminf_{n\to\infty}K_{W}(U_{n})$. Assume that
$\liminf_{n\to\infty}K_{W}(U_{n})<\infty$ as otherwise there is nothing to do.
By passing to a subsequence we can in fact assume that
$\sup_{n\in{\mathbbm{N}}}K_{W}(U_{n})<\infty$. After passing to a further
subsequence, we can pick a sequence $(\mu_{n})_{n\in{\mathbbm{N}}}$ in
$\mathcal{P}([0,1])$ such that $\delta_{\Box}(U_{n},W_{\mu_{n}})=0$,
$\mu_{n}\ll\lambda$ and

$\liminf_{n\to\infty}\int_{[0,1]}\ell\\!\left(\frac{\,\mathrm{d}\mu_{n}}{\,\mathrm{d}\lambda}\right)\,\mathrm{d}\lambda=\liminf_{n\to\infty}K_{W}(U_{n}).$

By using Theorems A.1, A.2 and A.3 similarly as above and passing to a
subsequence, we find $\mu\in\mathcal{P}([0,1])$ such that $\mu\ll\lambda$ and
$\frac{\,\mathrm{d}\mu_{n}^{\oplus k}}{\,\mathrm{d}\lambda^{\oplus
k}}\xrightarrow{weak}\frac{\,\mathrm{d}\mu^{\oplus
k}}{\,\mathrm{d}\lambda^{\oplus k}}$ for every $k\in{\mathbbm{N}}$. Similarly
as in the proof of Part c, one gets

$t(F,U_{n})=t(F,W_{\mu_{n}})\to t(F,W_{\mu}).$

This implies $\delta_{\Box}(U,W_{\mu})=0$ and
$K_{W}(U)\leqslant\int_{[0,1]}\ell\\!\left(\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}\right)\,\mathrm{d}\lambda$.
Another use of Claim 3.2 implies
$K_{W}(U)\leqslant\liminf_{n\to\infty}K_{W}(U_{n})$ because
$\frac{\,\mathrm{d}\mu_{n}}{\,\mathrm{d}\lambda}\xrightarrow{weak}\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}$.
This finishes the proof.

Proof of f. Suppose that $W$ is not a constant graphon. First, we find
$U,V\in\mathbf{RN}(W)$ such that $\delta_{\Box}(U,V)>0$.

Since $W$ is not constant there are $a<b\in[0,1]$ such that $A:=W^{-1}([0,a])$
and $B:=W^{-1}([b,1])$ both have non-zero measure. Let
$\epsilon:=\frac{(b-a)}{9}>0$. Using Lebesgue’s density theorem, we can find
pairwise disjoint intervals $X_{A},Y_{A},X_{B},Y_{B}$ of the same positive
measure such that

$\lambda^{\oplus 2}\left(\,(X_{A}\times Y_{A})\cap
A\,\right)\geqslant(1-\epsilon)\,\lambda^{\oplus 2}(X_{A}\times Y_{A})$
$\lambda^{\oplus 2}\left(\,(X_{B}\times Y_{B})\cap
B\right)\geqslant(1-\epsilon)\,\lambda^{\oplus 2}(X_{B}\times Y_{B}).$

We use these intervals to define distinct $U,V\in\mathbf{RN}(W)$.

######  Definition 3.3.

For disjoint intervals $D_{0},D_{1}\subseteq[0,1]$, we define the graphon
$W_{(D_{0},D_{1})}$ as follows. For $(x,y)\in[0,1]^{2}$, let $i,j\in\\{0,1\\}$
be the indices satisfying $x\in I^{2}_{i}$ and $y\in I^{2}_{j}$, and define

$W_{(D_{0},D_{1})}(x,y):=W(\psi^{-1}_{D_{i}}(x)+i/2,\psi^{-1}_{D_{j}}(y)+j/2),$

where, for an interval $D$ with end-points $c<d$,
$\psi_{D}(z):=\frac{z-c}{2(d-c)}$ is the linear maps that bijectively maps $D$
to $[0,1/2]$.

Informally speaking, $W_{(D_{0},D_{1})}$ is obtained from $W$ by putting half
of the whole mass uniformly on $D_{0}$ and half on $D_{1}$.

Set $U:=W_{(X_{A},Y_{A})}$ and $V:=W_{(X_{B},Y_{B})}$. Clearly,
$\widetilde{U},\widetilde{V}\in\mathbf{RN}(W)$. Thus $U$ is at most $a$ (resp.
$V$ is at least $b$) on $(0,1/2)\times(1/2,1)$ apart a subset of measure at
most $\epsilon$. Let us show that $\delta_{\Box}(U,V)>0$. Let
$\varphi:[0,1]\to[0,1]$ be an arbitrary measure preserving bijection. We can
assume that at least half measure of the pre-image
$\varphi^{-1}(\,(0,\frac{1}{2})\,)$ lies in the first half of $[0,1]$ by the
symmetry between $X_{A}$ and $Y_{A}$. Thus
$C:=\varphi^{-1}(\,(0,\frac{1}{2})\,)\cap(0,\frac{1}{2})$ has measure at least
$1/4$. By the measure preservation of $\varphi$, we have that the measure of
$D:=\varphi^{-1}(\,(\frac{1}{2},1)\,)\cap(\frac{1}{2},1)$ is

$\textstyle\lambda(D)=\frac{1}{2}-\lambda\left(\varphi^{-1}(\,(\frac{1}{2},1)\,)\cap(0,\frac{1}{2})\right)=\frac{1}{2}-\lambda\left((0,\frac{1}{2})\setminus
C\right)=\lambda(C).$

Then we have

$\begin{split}\int_{C\times D}V^{\varphi}(x,y)\,\mathrm{d}\lambda^{\oplus 2}\
&=\ \int_{\varphi(C)\times\varphi(D)}V(x,y)\,\mathrm{d}\lambda^{\oplus 2}\
\geqslant\ b\lambda^{\oplus 2}(C\times D)-\frac{\epsilon}{4}\\\ \int_{C\times
D}U(x,y)\,\mathrm{d}\lambda^{\oplus 2}\ &\leqslant\ a\lambda^{\oplus
2}(C\times D)+\frac{\epsilon}{4}.\end{split}$

and thus

$d_{\Box}(U,V^{\varphi})\geqslant(b-a)\lambda(C_{i}\times
D_{i})-\frac{\epsilon}{2}\geqslant\frac{(b-a)-8\epsilon}{16}>\frac{(b-a)}{144}.$

Since $\varphi$ was an arbitrary measure preserving function, we have
$d_{\Box}(U,V)>0$, as desired.

Finally, take any $\widetilde{V}\in\mathbf{RN}(W)$ not weakly isomorphic to
$W$, which exists by above. By Part d, there is
$\widetilde{U}\in\mathbf{RN}(W)$ such that $K_{W}(U)<\infty$ and
$\delta_{\Box}(U,V)<\delta_{\Box}(W,V)$. Then $\delta_{\Box}(U,W)>0$ and, by
Parts a and c, we have $K_{W}(U)>0$. Thus $K_{W}(U)\in(0,\infty)$, finishing
the proof.∎

##  4 LDPs for $(\widetilde{\mathbb{H}}_{n,W})_{n\in{\mathbbm{N}}}$

In this section, we completely resolve the LDP problem for the measures
$\widetilde{\mathbb{H}}_{n,W}$, which come from sampling uniform
$x\in[0,1]^{n}$ and taking the graphon of the edge-weighted graph $H$ on $[n]$
with $w_{H}(i,j):=W(x_{i},x_{j})$.

######  Theorem 4.1.

Take any graphon $W\in{\mathcal{W}}$ and any function
$s:{\mathbbm{N}}\to(0,\infty)$ with $s(n)\to\infty$ as $n\to\infty$. We
consider the existence of an LDP for the sequence
$(\widetilde{\mathbb{H}}_{n,W})_{n\in{\mathbbm{N}}}$ of probability measures
on the metric space $(\widetilde{\mathcal{W}},\delta_{\Box})$ with speed $s$.

  1. (a)

If $s(n)=o(n)$ then there is an LDP with rate function $\chi_{W}$.

  2. (b)

If $s(n)=(c+o(1))n$ for some $c\in(0,\infty)$ then there is an LDP with rate
function $\frac{1}{c}\,K_{W}$.

  3. (c)

If $s(n)=\omega(n)$, then there is an LDP with rate function
$\chi_{\mathbf{RN}(W)}$.

  4. (d)

If $W$ is a constant graphon, then LDP holds (regardless of the speed $s$)
with rate function $\chi_{W}=K_{W}=\chi_{\mathbf{RN}(W)}$.

  5. (e)

If $W$ is not a constant graphon and $s(n)$ does not satisfy any of the
assumptions a–c, then there is no LDP.

Before we prove Theorem 4.1, let us show that the measures
$(\widetilde{\mathbb{H}}_{n,W})_{n\in{\mathbbm{N}}}$ are supported around
$\mathbf{RN}(W)$ in the metric $\delta_{\Box}$ (which implies that any rate
function for any speed must be $\infty$ outside of the closed set
$\mathbf{RN}(W)$).

######  Proposition 4.2.

Let $W\in{\mathcal{W}}$ and $n\in{\mathbbm{N}}$. Then

$\widetilde{\mathbb{H}}_{n,W}\left(\left\\{\widetilde{U}\in\widetilde{\mathcal{W}}:\delta_{\Box}(\widetilde{U},\mathbf{RN}(W))\leqslant\frac{1}{n}\right\\}\right)=1.$

###### Proof.

The proof consists of two steps. In the first step we show that the claim
holds whenever $W$ attains only finitely many values. In the second step we
use the fact that such graphons are dense in $\mathcal{W}$ in the
$L^{\infty}$-norm to extend the claim to any $W$. It will be convenient in the
proof to use also the measures $(\mathbb{H}_{n,W})_{n\in{\mathbbm{N}}}$ on the
space $\mathcal{W}$. Recall that this is the version of
$(\widetilde{\mathbb{H}}_{n,W})_{n\in{\mathbbm{N}}}$, where we do not take the
equivalence class $\widetilde{f^{H}}$ of the sampled weighted graph $H$ but
simply output $f^{H}$.

Step (I). Suppose first that $W$ attains only finitely many values, i.e., the
set $W\\!\left([0,1]^{2}\right)$ is finite. Then the measures
$\mathbb{H}_{n,W}$ are atomic for every $n\in{\mathbbm{N}}$. Let
$U\in\mathcal{W}$ be such that $\mathbb{H}_{n,W}(\\{U\\})>0$. Note that by the
definition of $\mathbb{H}_{n,W}$ there is $H\in\mathcal{H}_{n}$ such that
$U=f^{H}$ and if we put

$X_{H}:=\left\\{x\in[0,1]^{{n}}:\mbox{for all }i<j\mbox{ in }[n]\ \
W(x_{i},x_{j})=w_{H}(i,j)\right\\},$

then we have $\lambda^{\oplus n}\left(X_{H}\right)>0$. By $d_{1}\geqslant
d_{\Box}$, it is enough to find a sequence $(V_{k})_{k\in{\mathbbm{N}}}$ in
$\mathcal{W}$ such that
$\lim_{k\to\infty}d_{1}\left(V_{k},U\right)\leqslant\frac{1}{n}$ and
$\widetilde{V}_{k}\in\mathbf{RN}(W)$ for each $k$.

Recall that $B_{\infty}(x,r)$ denotes the (open) radius-$r$ ball around
$x\in[0,1]^{{n}}$ in the $L^{\infty}$-metric. By the Lebesgue Density Theorem
(for the $L^{\infty}$-metric on $[0,1]^{{n}}$), the set of density points of
$X_{H}$ has measure $\lambda^{\oplus n}(X_{H})>0$ so it contains a point
${{x}}\in(0,1)^{{n}}$ such that ${{x}}_{i}\not={{x}}_{j}$ for every $i<j$ in
$[n]$. Recall that ${x}$ being a density point of $X_{H}$ means that

$\lim_{\epsilon\to 0}\frac{\lambda^{\oplus n}(X_{H}\cap
B_{\infty}\left({{x}},\epsilon\right))}{\lambda^{\oplus
n}(B_{\infty}\left({{x}},\epsilon\right))}=1.$

Let $k\in{\mathbbm{N}}$ be large enough. Then the intervals
$J_{i,k}:=\left[{{x}}_{i}-\frac{1}{k},{{x}}_{i}+\frac{1}{k}\right]$, for
$i\in[n]$, are pairwise disjoint. Similarly to Definition 3.3, let

$V_{k}:=W_{(J_{1,k},\dots,J_{n,k})}$

be obtained from $W$ by putting mass $1/n$ uniformly into each of the
intervals $J_{1,k},\dots,J_{n,k}$. By definition, $V_{k}\in\mathbf{RN}(W)$.
Let $i<j$ in $[n]$ and define

$A_{i,j,k}:=\left\\{(a,b)\in I^{n}_{i}\times
I^{n}_{j}:V_{k}(a,b)\not=w_{H}(i,j)\right\\}.$

Since the intervals $I_{1}^{n},\ldots,I_{n}^{n}$ in $V_{k}$ correspond to the
invervals $J_{1,k},\ldots,J_{n,k}$ in $W$, we have by Fubini-Tonelli’s Theorem
that

$\begin{split}\lambda^{\oplus
2}\left(A_{i,j,k}\right)\,=\,&\textstyle\frac{(2k)^{2}}{n^{2}}\,\lambda^{\oplus
2}\left(\left\\{(a,b)\in
B_{\infty}\\!\left(({{x}}_{i},{{x}}_{j}),\frac{1}{k}\right):W(a,b)\not=w_{H}(i,j)\right\\}\right)\\\
\,=\,&\textstyle\frac{(2k)^{n}}{n^{2}}\,\lambda^{\oplus
n}\left(\left\\{{{z}}\in
B_{\infty}\left({{x}},\frac{1}{k}\right):W({{z}}_{i},{{z}}_{j})\not=w_{H}(i,j)\right\\}\right)\\\
\,\leqslant\,&\textstyle\frac{(2k)^{n}}{n^{2}}\,\lambda^{\oplus
n}(B_{\infty}\\!\left({{x}},\frac{1}{k}\right)\setminus
X_{H})\,=\,\frac{\lambda^{\oplus
n}(B_{\infty}\left({{x}},\frac{1}{k}\right)\setminus
X_{H})}{n^{2}\,\lambda^{\oplus
n}(B_{\infty}\\!\left({{x}},\frac{1}{k}\right))},\end{split}$

which tends to $0$ as $k\to\infty$ since ${x}$ is a density point for $X_{H}$.

Noticing that, for $1\leqslant i<j\leqslant k$, $A_{i,j,k}$ is exactly the
subset of $I^{n}_{i}\times I^{n}_{j}$ where $U$ and $V_{k}$ differ we have

$\begin{split}d_{1}\left(V_{k},U\right)\ =\
&\int_{[0,1]^{2}}\left|V_{k}-U\right|\,\mathrm{d}\lambda^{\oplus 2}\\\ \
\leqslant\ &\sum_{i\in[n]}\lambda^{\oplus 2}\left(I^{n}_{i}\times
I^{n}_{i}\right)+2\sum_{1\leqslant i<j\leqslant n}\lambda^{\oplus
2}\left(A_{i,j,k}\right)\ \xrightarrow{k\to\infty}\ \frac{1}{n}.\end{split}$

This finishes the first step of the proof.

Step (II). Let $W$ be an arbitrary graphon and let $n\in{\mathbbm{N}}$. For
$k\in{\mathbbm{N}}$, let $W_{k}\in\mathcal{W}$ be such that
$d_{\infty}(W,W_{k})\leqslant\frac{1}{k}$ and $W_{k}$ attains only finitely
many values. Note that for every Borel probability measure
$\mu\in\mathcal{P}([0,1])$ that is absolutely continuous with respect to
$\lambda$, we have

$d_{\infty}\left(W_{\mu},(W_{k})_{\mu}\right)\leqslant\frac{1}{k}.$ (17)

Indeed, this distance is equal to the integral over the probability measure
$\mu^{\oplus 2}$ of the function $|W-W_{k}|$, which is at most $\frac{1}{k}$
except on a set which is null in $\lambda^{\oplus 2}$ and thus also in
$\mu^{\oplus 2}\ll\lambda^{\oplus 2}$.

It follows by $\delta_{\Box}\leqslant d_{\Box}\leqslant d_{\infty}$ that

$\begin{split}\left\\{\widetilde{U}\in\widetilde{\mathcal{W}}:\delta_{\Box}\left(\widetilde{U},\mathbf{RN}(W_{k})\right)\leqslant\frac{1}{n}\right\\}\subseteq\left\\{\widetilde{V}\in\widetilde{\mathcal{W}}:\delta_{\Box}\left(\widetilde{V},\mathbf{RN}(W)\right)\leqslant\frac{1}{n}+\frac{1}{k}\right\\}.\end{split}$
(18)

In the natural coupling between $\mathbb{H}_{n,W}$ and $\mathbb{H}_{n,W_{k}}$
where we use the same ${{x}}\in[0,1]^{n}$, the edge weights on each pair
differ at most by $\frac{1}{k}$ and thus the $d_{\infty}$-distance between the
sampled graphons is at most $\frac{1}{k}$ with probability 1. Since the left-
hand side of (18) has the $\widetilde{\mathbb{H}}_{n,W_{k}}$-measure $1$ by
Step (I), we conclude that the $\widetilde{\mathbb{H}}_{n,W}$-measure of the
$(\frac{1}{n}+\frac{2}{k})$-neighbourhood of $\mathbf{RN}(W)$ in
$\delta_{\Box}$ is also 1. Now the proposition follows by the
$\sigma$-additivity of $\widetilde{\mathbb{H}}_{n,W}$ since
$k\in{\mathbbm{N}}$ was arbitrary. ∎

Now we can now resolve the LDP problem for $\widetilde{\mathbb{H}}_{n,W}$ for
every speed.

###### Proof of Theorem 4.1.

It is more convenient to prove its parts in a different order than stated.

Proof of b. Recall that we are given $W\in{\mathcal{W}}$ and have to show that
$(\widetilde{\mathbb{H}}_{n,W})_{n\in{\mathbbm{N}}}$ satisfies the LDP on
$\left(\widetilde{\mathcal{W}},\delta_{\Box}\right)$ with speed
$s(n)=(c+o(1))n$ and rate function $\frac{1}{c}\,K_{W}$. It is enough to do
the case when $c=1$ and $s(n)=n$.

Recall that $\mathcal{P}([0,1])$ is the space of all Borel probability
measures on $[0,1]$ and, for $k\in{\mathbbm{N}}$, $\tau^{k}$ is the coarsest
topology on $\mathcal{P}([0,1])$ such that, for every bounded Borel function
$a:[0,1]^{k}\to\mathbb{R}$, the map

$\mu\mapsto\int_{[0,1]^{k}}a\,\mathrm{d}\mu^{\oplus
k},\quad\mu\in\mathcal{P}([0,1]),$ (19)

is continuous. Let $\tau^{\infty}$ be the topology generated by
$\bigcup_{k\in\mathbb{N}}\tau^{k}$, that is, the coarsest topology on
$\mathcal{P}([0,1])$ such that the map in (19) is continuous for all
$k\in{\mathbbm{N}}$ and all Borel functions $a$.

The topology $\tau^{k}$ will be useful to us since it makes various maps
involving $k$-fold integrals continuous. However, one has to be careful as
some natural properties fail. For example, [DemboZeitouni10ldta, Exercise
7.3.18] shows that the map $\mathcal{P}([0,1])\to\mathcal{P}([0,1]^{k})$ that
sends a measure $\mu$ to its $k$-th power $\mu^{\oplus k}$ for $k\geqslant 2$
is not continuous with respect the $\tau^{1}$-topologies on these two spaces.

Let $q_{n}:[0,1]^{{n}}\to\mathcal{P}([0,1])$ be the map that assigns to
$x\in[0,1]^{{n}}$ the measure

$L(x):=\frac{1}{n}\sum_{i\in[n]}\delta_{x_{i}}.$

######  Claim 4.3.

The map $q_{n}:[0,1]^{{n}}\to(\mathcal{P}([0,1]),\tau^{\infty})$ is Borel.

###### Proof of Claim.

It is enough to show that, for every $k\in{\mathbbm{N}}$, $t\in{\mathbbm{R}}$,
and every Borel function $a:[0,1]^{k}\to{\mathbbm{R}}$, the pre-image under
$q_{n}$ of the set $\\{\mu\in\mathcal{P}([0,1]):\int a\mu^{\oplus k}<t\\}$ is
Borel since these sets generate the topology $\tau^{\infty}$. The pre-image is
exactly the set $\\{x\in[0,1]^{{n}}:\phi(x)<t\\}$, where $\phi(x)$ is the
integral of $a$ under the $k$-th power of
$q_{n}(x)=\frac{1}{n}\sum_{i\in[n]}\delta_{x_{i}}$. Note that $\phi$ is the
sum of $n^{-k}a(x_{i_{1}},\dots,x_{i_{k}})$ over all $n^{k}$ possible choices
of $i_{1},\dots,i_{k}\in[n]$. This is a Borel function of $x$. Thus its level
set $\\{\phi<t\\}\subseteq[0,1]^{{n}}$ is also Borel, as desired. ∎

Recall that $\lambda$ is the Lebesgues measure on $[0,1]$. Define
$\Lambda_{n}$ to be the push forward of $\lambda^{\oplus n}$ via $q_{n}$. By
Claim 4.3, $\Lambda_{n}$ is a well-defined Borel probability measure on the
topological space $(\mathcal{P}([0,1]),\tau^{\infty})$.

Let $\mu\in\mathcal{P}([0,1])$. Define the _Kullback–Leibler divergence_ (or
_relative entropy_) of $\mu$ with respect to the Lebesgue measure $\lambda$ by

$H(\mu|\lambda):=\left\\{\begin{array}[]{ll}\int_{[0,1]}\ell\\!\left(\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}\right)\,\mathrm{d}\lambda,&\mbox{if
$\mu\ll\lambda$,}\\\ \infty,&\mbox{otherwise.}\end{array}\right.$ (20)

The following result for $m=2$ was proved by Eichelsbacher [Eichelsbacher97,
Theorem 1] who remarked ([Eichelsbacher97, Page 911]) that his result can be
generalised to arbitrary $m$. (A more general result can be found in
Eichelsbacher and Schmock [EichelsbacherSchmock02, Theorems 1.7(c) and 1.10]:
namely Theorem 4.4 follows from the special case when the family $\Phi$ in
[EichelsbacherSchmock02] is taken to be the set of all bounded measurable
functions $[0,1]^{m}\to{\mathbbm{R}}$.)

######  Theorem 4.4 (Eichelsbacher [Eichelsbacher97]).

Let $m\in{\mathbbm{N}}$ and let $L^{\oplus m}_{n}$ be the law of the $m$-th
power $(L(x_{n}))^{\oplus m}\in\mathcal{P}([0,1]^{m})$ where $x_{n}$ is a
uniform element of $[0,1]^{{n}}$. For $\nu\in\mathcal{P}([0,1]^{m})$, if $\nu$
is the $m$-th power $\eta^{\oplus m}$ of some measure
$\eta\in\mathcal{P}([0,1])$, then define

$I(\nu):=H(\eta|\lambda);$

otherwise we define $I(\nu):=\infty$.

Then for every $t\in[0,\infty)$ the level set $\\{I\leqslant t\\}$ is
$\tau^{1}$-compact and the sequence of measures $(L^{\oplus
m}_{n})_{n\in{\mathbbm{N}}}$ on the topological space
$(\mathcal{P}([0,1]^{m}),\tau^{1})$ satisfies an LDP with speed $n$ and rate
function $I$.∎

Let us show that, for every $m\in{\mathbbm{N}}$, the set
$\mathcal{P}_{\mathrm{power}}([0,1]^{m})$ of measures
$\mu\in\mathcal{P}([0,1]^{m})$ such that $\mu=\nu^{\oplus m}$ for some
$\nu\in\mathcal{P}([0,1])$ is closed in the $\tau^{1}$-topology. By Dynkin’s
theorem (e.g. [Cohn13mt, Corollary 1.6.3]), this set can be equivalently
described as the set of those $\mu\in\mathcal{P}([0,1]^{m})$ such that for all
measurable sets $A_{1},\dots,A_{m}\subseteq[0,1]$ it holds that

$\mu(A_{1}\times\dots\times A_{m})=\prod_{i=1}^{m}\mu\left([0,1]^{i-1}\times
A_{i}\times[0,1]^{m-i}\right).$ (21)

So take any measure $\mu$ which is not in this set and fix some
$A_{1},\dots,A_{m}\subseteq[0,1]$ violating (21). Then there is $\epsilon>0$
such that (21) is still violated if we modify each value of $\mu$ by less than
$\epsilon$. Thus if we take the indicator functions of the $m+1$ sets
appearing in (21) and require that the $\nu$-integral of each differs from the
corresponding value of $\mu^{\oplus m}$ by less than $\epsilon$, then we
obtain a $\tau^{1}$-open set of measures $\nu$, which contains $\mu$ and is
disjoint from $\mathcal{P}_{\mathrm{power}}([0,1]^{m})$. Hence, the latter set
is indeed a $\tau^{1}$-closed.

Since for each integer $n\in{\mathbbm{N}}$ the support of the measure
$L^{\oplus m}_{n}$ lies inside the closed set
$\mathcal{P}_{\mathrm{power}}([0,1]^{m})$, the LDP of Theorem 4.4 can be
restricted to this set, with each level set of the rate function $I$ still
being compact. On the the other hand, the map $\nu\mapsto\nu^{\oplus m}$ gives
a homeomorphism between the topological spaces $(\mathcal{P}([0,1]),\tau^{m})$
and $(\mathcal{P}_{\mathrm{power}}([0,1]^{m}),\tau^{1})$. Also, under this
map, the push-forward of $\Lambda_{n}$ is precisely $L^{\oplus m}_{n}$ while
$I$ corresponds to $H(\\_|\lambda)$. Thus, for every $m\in{\mathbbm{N}}$, the
sequence $(\Lambda_{n})_{n\in\mathbb{N}}$ on
$\left(\mathcal{P}([0,1]),\tau^{m}\right)$ satisfies an LDP with speed $n$ and
rate function $H(\\_|\lambda)$. Since $\tau^{\infty}$ is the coarsest topology
generated by all $\tau^{m}$, we obtain the following claim by the
Dawson–Gärtner theorem (Theorem 2.7).

######  Claim 4.5.

The sequence $(\Lambda_{n})_{n\in\mathbb{N}}$ satisfies an LDP on
$\left(\mathcal{P}([0,1]),\tau^{\infty}\right)$ with speed $n$ and rate
function $H(\\_|\lambda)$.∎

Fix a representation of $W:[0,1]^{2}\to[0,1]$ as a symmetric Borel function
that satisfies $W(x,x)=0$ for all $x\in[0,1]$. We remark that the requirement
to have a value 0 on the diagonal corresponds to the fact that weighted graphs
in our definition do not have loops. For any $\mu\in\mathcal{P}([0,1])$ we
define $W_{\mu}:[0,1]^{2}\to[0,1]$ to be the generalised graphon on the
measure space $([0,1],\mu)$ that attains the same values as $W$. Note that
since $\mu$ can have atoms we need to have $W$ fixed as an everywhere defined
Borel function (and not as a measurable function defined a.e.). Also, if
$\mu\ll\lambda$, then the new definition of $W_{\mu}$ is the same as the old
one (up to weak isomorphism of graphons).

Write $\widetilde{W}_{\mu}$ for the equivalence class of $W_{\mu}$ in
$\widetilde{\mathcal{W}}$. Define a map
$\Delta_{W}:\mathcal{P}([0,1])\to\widetilde{\mathcal{W}}$ by
$\mu\mapsto\widetilde{W}_{\mu}$. Even though the definition of $\Delta_{W}$
depends on the fixed representative of $W$ as a Borel function, it can be
easily verified that, irrespective of this representation, the push-forwards
of the Lebesgue measure $\lambda^{\oplus n}$ to the space
$\widetilde{\mathcal{W}}$ along the maps in the diagram below are the same.

######  Claim 4.6.

The map $\Delta_{W}$ is $(\tau^{\infty},\delta_{\Box})$-continuous.

###### Proof.

By Theorem 2.2, it is enough to show that, for any fixed graph $F=([k],E(F))$,
the real-valued function
$t(F,\Delta_{W}(\\_)):\mathcal{P}([0,1])\to{\mathbbm{R}}$ is
$\tau^{\infty}$-continuous. This function sends a measure
$\mu\in\mathcal{P}([0,1])$ to
$t(F,W_{\mu})=\int_{[0,1]^{k}}a(x)\,\mathrm{d}\mu^{\oplus k}(x)$, where
$a(x):=\prod_{\\{i,j\\}\in E(F)}W(x_{i},x_{j})$ for $x\in[0,1]^{k}$. It is, in
fact, $\tau^{k}$-continuous by definition, since $a$ is a Borel function. The
claim is proved. ∎

For $n\in{\mathbbm{N}}$, consider now the map
$q_{n,W}:[0,1]^{n}\to\mathcal{W}$ that is defined by

$q_{n,W}(x):=f^{x,W},\quad\mbox{$x\in[0,1]^{n}$},$

where $f^{x,W}$ is the step graphon that is obtained from the weighted graph
$H$ on $[n]$ that corresponds to the $x$-sample from $W$, i.e.,
$w_{H}(i,j)=W(x_{i},x_{j})$. Note that since $W$ is a fixed Borel function the
map $q_{n,W}$ is well-defined.

It follows easily from the definitions that the diagram

${\left[0,1\right]^{{n}}}$${\mathcal{W}}$${\mathcal{P}([0,1])}$${\widetilde{\mathcal{W}}}$$\scriptstyle{q_{n,W}}$$\scriptstyle{q_{n}}$$\scriptstyle{\Delta_{W}}$

is commutative. In particular, for every $n\in{\mathbbm{N}}$, the measure
$\widetilde{\mathbb{H}}_{n,W}$ is the push-forward of $\Lambda_{n}$ via
$\Delta_{W}$. (Recall that $\Lambda_{n}$ is the push-forward of
$\lambda^{\oplus n}$ via $q_{n}$.)

By Claim 4.5, the sequence $(\Lambda_{n})_{n\in{\mathbbm{N}}}$ satisfies LDP
on $(\mathcal{P}([0,1]),\tau^{\infty})$ with speed $n$ and good rate function
$H(\\_|\lambda)$. By the Contraction Principle (Theorem 2.6), the sequence
$(\widetilde{\mathbb{H}}_{n,W})_{n\in{\mathbbm{N}}}$ of measures on
$(\widetilde{\mathcal{W}},\delta_{\Box})$ satisfies an LPD with speed $n$ and
rate $K_{W}$, finishing the proof of Part b

Let us turn to the remaining parts of Theorem 4.1.

Proof of a. Recall that the claimed rate function is $\chi_{W}$. Let
$\mathcal{O}\subseteq\widetilde{\mathcal{W}}$ be an open set. Suppose that the
equivalence class $\widetilde{W}$ of $W$ belongs to $\mathcal{O}$ for
otherwise $\inf_{\mathcal{O}}\chi_{W}=\infty$ and the LDP lower bound (1)
vacuously holds. Since the cut-distance between the graphon $W$ and its
$n$-vertex sample $G\sim\widetilde{\mathbb{H}}_{n,W}$ tends to 0 with
probability $1-o(1)$ as $n\to\infty$ (by, for example, [Lovasz:lngl, Lemma
10.16]), the probability that $f^{H}\in\mathcal{O}$ tends to 1 and the LDP
lower bound (1) trivially holds. (Recall that we assume that $s(n)\to\infty$
as $n\to\infty$.)

Next, let $F\subseteq\widetilde{\mathcal{W}}$ be a closed set. Suppose that
$\widetilde{W}\not\in F$ for otherwise the LDP upper bound is vacuously true.
By Part b applied to the closed set $F$ with speed $n$, we have that

$\limsup_{n\to\infty}\frac{1}{n}\log\left(\widetilde{\mathbb{H}}_{n,W}(F)\right)\leqslant-\inf_{\widetilde{U}\in
F}K_{W}(U).$

Observe that the right-hand side is strictly less than $0$. Indeed, since the
function $K_{W}$ is lower semi-continuous by Proposition 3.1e, it attains its
infimum over the compact set $F$ at some $\widetilde{V}\in F$. By Proposition
3.1c, we have $K_{W}(V)>0$. Thus $\inf_{\widetilde{U}\in
F}K_{W}(U)=K_{W}(V)>0$.

Consequently, by $s(n)=o(n)$, we have

$\begin{split}\limsup_{n\to\infty}\frac{1}{s(n)}\log\left(\widetilde{\mathbb{H}}_{n,W}(F)\right)=-\infty=-\inf_{\widetilde{U}\in
F}\chi_{W}(U)\end{split}$

and that shows that the LDP upper bound (2) holds as well.

Proof of c. Here $s(n)/n\to\infty$ and the stated rate is
$\chi_{\mathbf{RN}(W)}$. Let $\mathcal{O}\subseteq\widetilde{\mathcal{W}}$ be
an open set. Suppose that $\mathcal{O}\cap\mathbf{RN}(W)\not=\emptyset$ as
otherwise the LDP lower bound (1) vacuously holds. By the already proved Part
b (for speed $n$) we have

$\begin{split}\liminf_{n\to\infty}\frac{1}{n}\log\left(\widetilde{\mathbb{H}}_{n,W}(\mathcal{O})\right)\geqslant-\inf_{\widetilde{U}\in\mathcal{O}}K_{W}(U).\end{split}$

Recall that $\mathbf{RN}(W)$ is the closure of the set of graphons $W_{\mu}$
over all Borel probability measures $\mu\ll\lambda$; thus we can find such
$\mu$ so that $\widetilde{W_{\mu}}$ belongs to the open set $\mathcal{O}$.
Pick $r>0$ such that the $\delta_{\Box}$-ball of radius $r$ around
$\widetilde{W_{\mu}}$ lies entirely inside $\mathcal{O}$. By the integrability
of $\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}$ with respect to $\lambda$,
there is finite $R$ such that the $\lambda$-measure of the level set
$X:=\\{\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\lambda}\leqslant R\\}$ is at least
$1-r/2$. Let the probability measure $\nu$ be zero on $[0,1]\setminus X$ and
be the restriction of $\mu$ to $X$ scaled up by factor $1/\mu(X)$. Since the
measures $\mu^{\oplus 2}$ and $(\frac{1}{\mu(X)}\,\nu)^{\oplus 2}$ coincide on
a set $X^{2}$ of measure at least $(1-r/2)^{2}>1-r$, we have
$\delta_{\Box}(W_{\mu},W_{\nu})<r$. Thus $W_{\nu}$ still belongs to the open
set $\mathcal{O}$. Thus $\inf_{\mathcal{O}}K_{W}\leqslant
K_{W}(W_{\nu})\leqslant\ell\\!\left(R\right)<\infty$. Consequently, since
$s(n)/n\to\infty$, we have

$\begin{split}\liminf_{n\to\infty}\frac{1}{s(n)}\log\left(\widetilde{\mathbb{H}}_{n,W}(\mathcal{O})\right)=0=-\inf_{\widetilde{U}\in\mathcal{O}}\chi_{\mathbf{RN}(W)}(U).\end{split}$

This establishes the LDP lower bound (1).

Suppose now that $F\subseteq\widetilde{\mathcal{W}}$ is a closed set. Assume
that $F\cap\mathbf{RN}(W)=\emptyset$ as otherwise the LDP upper bound (2)
vacuously holds. Thus we can find $n_{0}\in{\mathbbm{N}}$ such that

$F\cap\left\\{\widetilde{V}\in\widetilde{\mathcal{W}}:\delta_{\Box}(\widetilde{V},\mathbf{RN}(W))\leqslant\frac{1}{n_{0}}\right\\}=\emptyset$

by the compactness of $\widetilde{\mathcal{W}}$. Consequently,
$\widetilde{\mathbb{H}}_{n,W}(F)=0$ holds for every $n\geqslant n_{0}$ by
Proposition 4.2, and the upper LDP bound (2) follows.

Proof of d. Here $W$ is a constant graphon, say of value $p$. Trivially,
$\mathbf{RN}(W)=\\{W\\}$, $K_{W}=\chi_{W}=\chi_{\mathbf{RN}(W)}$, and
$\widetilde{\mathbb{H}}_{n,W}$ is the Dirac point mass on $\widetilde{W}_{n}$,
where the graphon $W_{n}$ is $p$ everywhere, except it is $0$ on
$\cup_{i=1}^{n}(I_{n}^{i}\times I_{n}^{i})$. (Recall that weighted graphs do
not have loops.) Since the graphons $W_{n}$ converge to $W$, the LPD claimed
in Part d holds.

Proof of e. It remains to show that there is no LDP if $W$ is not constant and
$s(n)$ does not satisfy any of the assumptions in Parts a–c of Theorem 4.1.
Pick two subsequences of $n$ such that the speeds $s(n)$ satisfy two different
assumptions from a–c. These two subsequences satisfy the corresponding LDPs by
what we have just proved. It is enough to show that the two corresponding rate
functions differ since the (lower semi-continuous) LDP rate function on a
regular topological space is unique (see e.g.,
[RassoulaghaSeppelainen14cldigm, Theorem 2.13]).

If at least one of the occurring cases is from Part b then, by Proposition
3.1f, the rate function assumes a finite positive value and thus determines
$\lim_{n\to\infty}s(n)/n$ (and is also different from the
$\\{0,\infty\\}$-valued functions $\chi_{W}$ and $\chi_{\mathbf{RN}(W)}$),
giving the required. Otherwise, we have exactly the two cases of Parts a and c
occurring, one rate function $\chi_{W}$ is $0$ on a single point
$\widetilde{W}$ while the other rate function vanishes on at least two
different points by Proposition 3.1f. ∎

##  5 Exponential equivalence

The following notion of _exponential equivalence_ is useful for transferring
an LDP proved for one sequence of measures to another (via Theorem 5.2) We use
the standard definition (as in [DemboZeitouni10ldta, Definition 4.2.10]),
which simplifies slightly when restricted to the case of separable metric
spaces.

######  Definition 5.1 (Exponential equivalence).

Let $(\mu_{n})_{n\in{\mathbbm{N}}}$ and $(\nu_{n})_{n\in{\mathbbm{N}}}$ be
sequences of Borel probability measures on a separable metric space $(X,d)$.
Let $s:{\mathbbm{N}}\to(0,\infty)$ satisfy $s(n)\to\infty$ as $n\to\infty$. We
say that $(\mu_{n})_{n\in{\mathbbm{N}}}$ and $(\nu_{n})_{n\in{\mathbbm{N}}}$
are _exponentially equivalent for speed $s$_ if there is a sequence of Borel
probability measure $(\Theta_{n})_{n\in{\mathbbm{N}}}$ on $X\times X$ such
that for every $n\in{\mathbbm{N}}$ the marginals of $\Theta_{n}$ are $\mu_{n}$
and $\nu_{n}$, and for every $\alpha>0$ it holds that

$\limsup_{n\to\infty}\frac{1}{s(n)}\log\left(\Theta_{n}\left(\\{(x,y)\in
X\times X:d(x,y)>\alpha\\}\right)\right)=-\infty.$

Informally speaking, the definition states that there is a coupling such that
the probability of seeing a pair of outcomes at distance bounded from 0 decays
faster than ${\mathrm{e}}^{-O(s)}$. This notion is useful because of the
following result.

######  Theorem 5.2 (See e.g. [DemboZeitouni10ldta]*Theorem 4.2.13).

Let $(\mu_{n})_{n\in{\mathbbm{N}}}$ and $(\nu_{n})_{n\in{\mathbbm{N}}}$ be two
sequences of Borel probability measures on a separable metric space $(X,d)$
that are exponentially equivalent for some speed $s(n)\to\infty$. Let
$I:X\to[0,\infty]$ be a good rate function. Then $(\mu_{n})_{n\in\mathbb{N}}$
satisfies an LDP on $X$ with speed $s$ and rate $I$ if and only if
$(\nu_{n})_{n\in\mathbb{N}}$ satisfies an LDP on $X$ with speed $s$ and rate
$I$.∎

Next, let us show that, for any speed $o(n^{2})$, the $n$-vertex samples from
a graphon, with or without edge rounding, are exponentially equivalent.

######  Lemma 5.3.

Let $W\in{\mathcal{W}}$. Take any function $s:{\mathbbm{N}}\to(0,\infty)$ such
that $s(n)\to\infty$ and $s(n)/n^{2}\to 0$ as $n\to\infty$. Then the sequences
$(\widetilde{\mathbb{R}}_{n,W})_{n\in{\mathbbm{N}}}$ and
$(\widetilde{\mathbb{H}}_{n,W})_{n\in{\mathbbm{N}}}$ are exponentially
equivalent for speed $s$.

###### Proof.

Let $n\in{\mathbbm{N}}$ and $H\in\mathcal{H}_{n}$. Recall that $w_{H}$ denotes
the edge-weight function of $H$. Let $\Lambda_{n,H}$ be the atomic probability
measure on $\mathcal{W}$ which, for every graph $G$ on $[n]$, gives mass

$\Lambda_{n,H}(\\{f^{G}\\}):=\prod_{\\{i,j\\}\in
E(G)}w_{H}(i,j)\prod_{\\{i^{\prime},j^{\prime}\\}\in
E(\overline{G})}\left(1-w_{H}(i^{\prime},j^{\prime})\right)$ (22)

to $f^{G}$. This is exactly the distribution after edge-rounding the weighted
graph $H$ (and taking the corresponding graphon in $\mathcal{W}$). It is easy
to see that, for every $n\in{\mathbbm{N}}$, the assignment
$(H,G)\mapsto\Lambda_{n,H}\left(\left\\{f^{G}\right\\}\right)$ is Borel
measurable. This allows us to define a Borel probability measure
$\Lambda_{n,W}$ on $\mathcal{W}\times\mathcal{W}$ by

$\Lambda_{n,W}(A):=\int\Lambda_{n,H}\left(\left\\{f^{G}:G\in\mathcal{G}_{n},\
\left(f^{H},f^{G}\right)\in
A\right\\}\right)\,\mathrm{d}\mathbb{H}_{n,W}(f^{H}),$

where $A\subseteq\mathcal{W}\times\mathcal{W}$ is a Borel set. Informally
speaking, the first component is the weighted $n$-vertex sample $H$ from $W$
while the second component is a rounding of $H$ (or, more precisely, we take
the graphons corresponding to these graphs). Define the probability measure
$\Theta_{n,W}$ as the push-forward of $\Lambda_{n,W}$ via
$\mathcal{W}\times\mathcal{W}\twoheadrightarrow\widetilde{\mathcal{W}}\times\widetilde{\mathcal{W}}$,
the product of the quotient maps. One can easily verify that the marginals of
$\Theta_{n,W}$ are $\widetilde{\mathbb{H}}_{n,W}$ and
$\widetilde{\mathbb{R}}_{n,W}$.

Let us show that the coupling given by $\Theta_{n,W}$ satisfies Definition
5.1. Take any $\alpha>0$. We set

$\mathcal{O}_{\alpha}:=\\{(\widetilde{U},\widetilde{V})\in\widetilde{\mathcal{W}}\times\widetilde{\mathcal{W}}:\delta_{\Box}(\widetilde{U},\widetilde{V})>\alpha\\}$

and

$\mathcal{Q}_{\alpha}:=\\{(U,V)\in\mathcal{W}\times\mathcal{W}:\delta_{\Box}(U,V)>\alpha\\}.$

Clearly, we have
$\Theta_{n,W}(\mathcal{O}_{\alpha})=\Lambda_{n,W}(\mathcal{Q}_{\alpha})$. Our
aim is to show that this is ${\mathrm{e}}^{-\omega(s(n))}$ as $n\to\infty$.

We need the following result. Recall that the measure $\Lambda_{n,H}$ was
defined in (22).

######  Claim 5.4.

For every $k\in{\mathbbm{N}}$ there is $C>0$ such that for every
$F\in\mathcal{G}_{k}$, $\beta>0$, $n\in{\mathbbm{N}}$ and
$H\in\mathcal{H}_{n}$ it holds that

$\Lambda_{n,H}\left(\left\\{f^{G}:G\in\mathcal{G}_{n},\
\left|t(F,f^{H})-t(F,f^{G})\right|>\beta\right\\}\right)\leqslant{\mathrm{e}}^{-C\beta^{2}n^{2}}.$
(23)

###### Proof.

Let $F\in\mathcal{G}_{k}$, $n\in{\mathbbm{N}}$ and $H\in\mathcal{H}_{n}$. Let
$\hom(F,G)$ denote the number of _homomorphisms_ from $F$ to $G$, that is,
functions $V(F)\to V(G)$ that send edges to edges. Note that
$\hom(F,G)=t(F,f^{G})\,n^{k}$. With this notation we have that the left-hand
side of (23) is equal to

$\Lambda_{n,H}\left(\left\\{f^{G}:G\in\mathcal{G}_{n},\
\left|\hom(F,G)-t(F,f^{H})n^{k}\right|>\beta n^{k}\right\\}\right).$

Enumerate the set $\binom{[n]}{2}$ as $\left\\{e_{1},\dots,e_{m}\right\\}$,
$m:={n\choose 2}$. Consider the corresponding edge-exposure martingale for
$t(F,\\_)$ in the edge rounding process for $H$. Formally, for
$s\in\\{0,\dots,m\\}$ we define a random variable
$X_{s}:\mathcal{G}_{n}\to\mathbb{R}$ as

$X_{s}(G):=\sum_{f\in[n]^{[k]}}\prod_{\begin{subarray}{c}\\{i,j\\}\in E(F)\\\
a(f(i),f(j))>s\end{subarray}}w_{H}(f(i),f(j))\prod_{\begin{subarray}{c}\\{i,j\\}\in
E(F)\\\ a(f(i),f(j))\leqslant
s\end{subarray}}{\mathbbm{1}}_{\\{f(i),f(j)\\}\in E(G)},\quad
G\in\mathcal{G}_{n},$

where $a(i,j)$ for $ij\in{[n]\choose 2}$ is the unique index in
$\left[m\right]$ with $e_{a(i,j)}=\\{i,j\\}$. Consider the ($\sigma$-)algebra
filtration $\left(\mathcal{B}_{s}\right)_{s=0}^{m}$ on $\mathcal{G}_{n}$ that
is generated by the functions $\left({\mathbbm{1}}_{e_{i}\in
E(G)}\right)_{i=1}^{s}$, i.e., revealing edges one-by-one according to the
enumeration. It is easy to see that the sequence
$\left(X_{s}\right)_{s=0}^{m}$ forms a martingale with respect to the
filtration $\left(\mathcal{B}_{s}\right)_{s=0}^{m}$. Moreover
$\mathbb{E}(X_{0})=t(F,f^{H})n^{k}$ and $X_{m}(G)=\hom(F,G)$ for every
$G\in\mathcal{G}_{n}$. Let $s\in[m]$. Then we have

$\begin{split}\left|X_{s}-X_{s-1}\right|\leqslant&\
\left|\left\\{f:\in[n]^{[k]}:e_{s}\subseteq
f(\,[k]\,)\right\\}\right|\leqslant k^{2}n^{k-2}.\end{split}$

By Azuma’s inequality (see e.g. [AlonSpencer16pm, Theorem 7.2.1]), we have
that, for some $C=C(k)>0$,

$\displaystyle\Lambda_{n,H}\left(\left\\{f^{G}:G\in{\mathcal{G}}_{n},\
\left|\hom(F,G)-t(F,f^{H})n^{k}\right|>\beta n^{k}\right\\}\right)$
$\displaystyle=$
$\displaystyle\Lambda_{n,H}\left(\left\\{f^{G}:G\in{\mathcal{G}}_{n},\
\left|X_{m}-\mathbb{E}\left(X_{0}\right)\right|>\beta n^{k}\right\\}\right)$
$\displaystyle\leqslant$ $\displaystyle\
2{\mathrm{e}}^{-\frac{\beta^{2}n^{2k}}{2mk^{4}n^{2(k-2)}}}\leqslant{\mathrm{e}}^{-C\beta^{2}n^{2}}.$

This finishes the proof of the claim. ∎

We are now ready to verify Definition 5.1 for any given $\alpha>0$. The
Inverse Counting Lemma of Borgs et al [BCLSV08, Theorem 2.7(b)] (see also
[Lovasz:lngl, Lemma 10.32]) implies that (depending on $\alpha>0$) there are
$k\in{\mathbbm{N}}$ and $\beta>0$ such that

$\mathcal{Q}_{\alpha}\subseteq\\{(U,V)\in\mathcal{W}\times\mathcal{W}:\exists
F\in{\mathcal{G}}_{k}\ \left|t(F,U)-t(F,V)\right|>\beta\\}.$

We have

$\begin{split}\Lambda_{n,W}\left(\mathcal{Q}_{\alpha}\right)=&\int\Lambda_{n,H}\left(\left\\{f^{G}:G\in\mathcal{G}_{n},\
\left(f^{H},f^{G}\right)\in\mathcal{Q}_{\alpha}\right\\}\right)\,\mathrm{d}\mathbb{H}_{n,W}(f^{H})\\\
\leqslant&\int\Lambda_{n,H}\left(\left\\{f^{G}:G\in\mathcal{G}_{n},\ \exists
F\in{\mathcal{G}}_{k}\
\left|t(F,f^{H})-t(F,f^{G})\right|>\beta\right\\}\right)\,\mathrm{d}\mathbb{H}_{n,W}(f^{H})\\\
\leqslant&\sum_{F\in{\mathcal{G}}_{k}}\int\Lambda_{n,H}\left(\left\\{f^{G}:G\in\mathcal{G}_{n},\
\left|t(F,f^{H})-t(F,f^{G})\right|>\beta\\}\right\\}\right)\,\mathrm{d}\mathbb{H}_{n,W}(f^{H})\\\
\leqslant&\ 2^{{k\choose 2}}{\mathrm{e}}^{-C\beta^{2}n^{2}}\end{split}$

where $C>0$ depends only on $k\in{\mathbbm{N}}$ and the last inequality
follows from Claim 5.4. Putting all together, we obtain

$\limsup_{n\to\infty}\frac{1}{s(n)}\log\left(\Theta_{n,W}\left(\mathcal{O}_{\alpha}\right)\right)\leqslant\limsup_{n\to\infty}-\frac{1}{s(n)}C\beta^{2}n^{2}=-\infty$

by the assumption that $s(n)=o(n^{2})$.

This verifies all requirements of Definition 5.1 and finishes the proof. ∎

##  6 LDPs for the measures $\widetilde{\mathbb{R}}_{n,W}$

Now we are ready to establish Theorem 1.3 that deals with LDPs for the random
(edge rounded) graph ${\mathbbm{G}}(n,W)$.

###### Proof of Theorem 1.3.

Recall that, by Theorem 5.2, if two sequences of probability measures on the
same space are exponentially equivalent then one sequence satisfies an LDP if
and only if the other satisfies the same LDP. Thus the combination of Lemma
5.3 and Theorem 4.1 easily implies all claims of Theorem 1.3, apart from Part
d.

Let us prove Part d. Here the speed is $s(n)=\omega(n^{2})$ and the stated
rate function is $\chi_{\mathbf{FORB}(W)}$. There are two steps in the proof.

  1. (I)

If $\widetilde{U}\not\in\mathbf{FORB}(W)$, then there are $\alpha>0$ and
$n_{0}\in{\mathbbm{N}}$ such that
$\widetilde{\mathbb{R}}_{n,W}\left(B_{\delta_{\Box}}(\widetilde{U},\alpha)\right)=0$
for every $n\geqslant n_{0}$.

  2. (II)

If $\alpha>0$ and $G\in\mathcal{G}_{k}$ are such that
$t_{\mathrm{ind}}(G,W)\not=0$, then

$\lim_{n\to\infty}\frac{1}{s(n)}\log\left(\widetilde{\mathbb{R}}_{n,W}\left(B_{\delta_{\Box}}\left(\widetilde{f^{G}},\frac{1}{k}+\alpha\right)\right)\right)=0.$
(24)

First we show how (I) and (II) imply Part d of the theorem.

Let $F\subseteq\widetilde{\mathcal{W}}$ be a $\delta_{\Box}$-closed set. If
$F\cap\mathbf{FORB}(W)\not=\emptyset$, then the LDP upper bound (2) is
vacuously satisfied. Otherwise for some $\alpha>0$ we have
$\delta_{\Box}(F,\mathbf{FORB}(W))\geqslant\alpha$ because we take the
distance between two disjoint closed sets in a compact metric space. For each
$\widetilde{U}\in F$ we pick $\alpha_{U}\in(0,\alpha)$ and
$n_{U}\in{\mathbbm{N}}$ that satisfy (I). Of course, the open balls centred at
$\widetilde{U}$ of radius $\alpha_{U}$ over all $\widetilde{U}\in F$ cover
$F$. By the compactness of $F$ there is a finite subcover; let it be given by
$\widetilde{U}_{1},\dots,\widetilde{U}_{l}\in F$. Then, for every
$n\geqslant\max_{i\in[l]}n_{U_{i}}$, we have

$\widetilde{\mathbb{R}}_{n,W}(F)\leqslant\widetilde{\mathbb{R}}_{n,W}\left(\bigcup_{i\in[l]}B_{\delta_{\Box}}\left(\widetilde{U}_{i},\alpha_{U_{i}}\right)\right)=0.$

Thus the LDP upper bound (2) vacuously holds.

Let $\mathcal{O}\subseteq\widetilde{\mathcal{W}}$ be a $\delta_{\Box}$-open
set. If $\mathcal{O}\cap\mathbf{FORB}(W)=\emptyset$, then the LDP lower bound
(1) is vacuously satisfied. Otherwise there are
$\widetilde{U}\in\mathbf{FORB}(W)$ and $\alpha>0$ such that
$B_{\delta_{\Box}}(\widetilde{U},3\alpha)\subseteq\mathcal{O}$. It is known
that the cut-distance between any graphon $U$ and its typical $n$-vertex
sample tends to 0 as $n\to\infty$ (see e.g. [Lovasz:lngl, Lemma 10.16]). Thus
there is a graph $G\in\mathcal{G}_{k}$, where we can additionally assume that
$k>1/\alpha$, such that $t_{\mathrm{ind}}(G,U)>0$ and
$\delta_{\Box}(f^{G},U)<\alpha$. It follows that

$B_{\delta_{\Box}}\left(\widetilde{f^{G}},\frac{1}{k}+\alpha\right)\subseteq
B_{\delta_{\Box}}\left(\widetilde{U},\frac{1}{k}+\alpha+\delta_{\Box}(f^{G},U)\right)\subseteq
B_{\delta_{\Box}}(\widetilde{U},3\alpha)\subseteq\mathcal{O}.$

Since $\widetilde{U}\in\mathbf{FORB}(W)$, we must have
$t_{\mathrm{ind}}(G,W)>0$. Thus we have by (II) that

$\liminf_{n\to\infty}\frac{1}{s(n)}\log\left(\widetilde{\mathbb{R}}_{n,W}\left(\mathcal{O}\right)\right)\geqslant\liminf_{n\to\infty}\frac{1}{s(n)}\log\left(\widetilde{\mathbb{R}}_{n,W}\left(B_{\delta_{\Box}}\left(\widetilde{f^{G}},\frac{1}{k}+\alpha\right)\right)\right)=0,$

and the LDP lower bound (1) vacuously holds.

It remains to establish each of Steps (I) and (II).

Step (I). Let $\widetilde{U}\not\in\mathbf{FORB}(W)$. By definition there are
$k\in{\mathbbm{N}}$ and $H\in\mathcal{G}_{k}$ such that
$t_{\mathrm{ind}}(H,W)=0$ and $t_{\mathrm{ind}}(H,U)>0$. Since the map
$t_{\mathrm{ind}}(H,\\_)$ is $\delta_{\Box}$-continuous by Theorem 2.2, we can
find $\alpha>0$ such that

$B_{\delta_{\Box}}(\widetilde{U},\alpha)\subseteq\left\\{\widetilde{V}\in\mathcal{W}:t_{\mathrm{ind}}(H,V)>\frac{1}{2}\,t_{\mathrm{ind}}(H,U)\right\\}.$

We show that this $\alpha$ works as required with
$n_{0}:=\lceil{k^{2}}/t_{\mathrm{ind}}(H,U)\rceil$.

Let $n\geqslant n_{0}$ and $G\in\mathcal{G}_{n}$ be any graph such that
$\delta_{\Box}(f^{G},U)<\alpha$. In particular, we have

$t_{\mathrm{ind}}(H,f^{G})-\binom{k}{2}\frac{1}{n}>\frac{1}{2}\left(t_{\mathrm{ind}}(H,U)-\frac{k^{2}}{n}\right)>0$
(25)

Note that

$\lambda^{\oplus k}\left(\left\\{x\in[0,1]^{k}:\exists\,l\in[n]\
\exists\,i\not=j\in[k]\ x_{i},x_{j}\in
I^{n}_{l}\right\\}\right)\leqslant\binom{k}{2}\frac{1}{n}.$

Thus, by (25) we can find an injective embedding of $H$ into $G$. It follows
by Fubini-Tonelli’s theorem that $t_{\mathrm{ind}}(G,W)\leqslant
t_{\mathrm{ind}}(H,W)$. Since $t_{\mathrm{ind}}(H,W)=0$, we have
$t_{\mathrm{ind}}(G,W)=0$. This implies that
$\widetilde{\mathbb{R}}_{n,W}(\\{\widetilde{f^{G}}\\})\leqslant
n!\,t_{\mathrm{ind}}(G,W)$ is zero. Since the discrete measure
$\widetilde{\mathbb{R}}_{n,W}$ is supported on
$\\{\widetilde{f^{G}}:G\in{\mathcal{G}}_{n}\\}$, we conclude that
$\widetilde{\mathbb{R}}_{n,W}\left(B_{\delta_{\Box}}\left(\widetilde{U},\alpha\right)\right)=0$,
as desired.

Step (II). Let $\alpha>0$ and let $G\in\mathcal{G}_{k}$ be such that
$t_{\mathrm{ind}}(G,W)>0$. Let $H\sim{\mathbbm{G}}(n,W)$ be the random
$n$-vertex sample from $W$. For $\gamma\in(0,1)$ define

$X_{\gamma}:=\\{x\in[0,1]^{{k}}:\forall\\{i,j\\}\in E(G)\
W(x_{i},x_{j})\geqslant\gamma,\ \forall\\{i,j\\}\in E(\overline{G})\
W(x_{i},x_{j})\leqslant 1-\gamma\\}.$

It follows from $t_{\mathrm{ind}}(G,W)>0$ and the $\sigma$-additivity of
$\lambda^{\oplus k}$ that there is $\gamma>0$ such that $\lambda^{\oplus
k}\left(X_{\gamma}\right)>0$. By the Lebesgue Density Theorem, we can find
${{x}}\in X_{\gamma}$ such that ${{x}}_{i}\not={{x}}_{j}$ whenever $i\not=j$
in $[k]$ and

$\lim_{l\to\infty}\frac{\lambda^{\oplus k}\left(X_{\gamma}\cap
B_{\infty}\left({{x}},\frac{1}{l}\right)\right)}{\lambda^{\oplus
k}\left(B_{\infty}\left({{x}},\frac{1}{l}\right)\right)}=1.$

Fix $l\in{\mathbbm{N}}$ large enough so that

$\frac{\lambda^{\oplus k}\left(X_{\gamma}\cap
B_{\infty}\left({{x}},\frac{1}{l}\right)\right)}{\lambda^{\oplus
k}\left(B_{\infty}\left({{x}},\frac{1}{l}\right)\right)}>1-\frac{\alpha}{2},$
(26)

and the intervals
$J_{i}:=\left[{{x}}_{i}-\frac{1}{l},{{x}}_{i}+\frac{1}{l}\right]$, $i\in[k]$,
are pairwise disjoint.

First, we prove (24) in the case when $n$ is taken only over integers
divisible by $k$. Informally, the main idea is that if an $n$-vertex graph $H$
is a uniform blow-up of $G$ then $\delta_{\Box}(f^{G},f^{H})=0$; furthermore,
by adding any edges inside the $k$ parts of $H$ we increase the cut-distance
by at most $1/k$ and thus we can afford any further $\alpha{n\choose 2}$
rounding errors without the cut-distance going over $1/k+\alpha$,

Let $n\in{\mathbbm{N}}$ be such that $m:=n/k$ is an integer. For
$i\in{\mathbbm{N}}$, let $i\mathrm{\,mod\,}k$ denote the (unique) integer in
$[k]$ congruent to $i$ modulo $k$. Define

$\mathcal{X}:=\left\\{x\in[0,1]^{{n}}:\forall i\in[n]\ x_{i}\in
J_{i\mathrm{\,mod\,}k}\right\\}$

and note that $\lambda^{\oplus
k}\left(\mathcal{X}\right)=\left(\frac{2}{l}\right)^{n}$.

Let $x$ be a random $n$-vector, chosen uniformly from $\mathcal{X}$. Thus we
put exactly $m$ of the coordinates $x_{i}$ into each interval $J_{j}$. Call a
pair $ij\in{[n]\choose 2}$ _crossing_ if
$i\mathrm{\,mod\,}k\not=j\mathrm{\,mod\,}k$. Clearly, there are
$m^{2}{k\choose 2}$ crossing pairs. Let $B(x)$ be the set of crossing pairs
$ij\in{[n]\choose 2}$ such that either
$\\{i\mathrm{\,mod\,}k,j\mathrm{\,mod\,}k\\}\in E(G)$ and
$W(x_{i},x_{j})<\gamma$ or $\\{i\mathrm{\,mod\,}k,j\mathrm{\,mod\,}k\\}\in
E(\overline{G})$ and $W(x_{i},x_{j})>1-\gamma$. We call the pairs in $B(x)$
_$x$ -bad_ and call all other crossing pairs _$x$ -good_.

Take any $i_{1},\dots,i_{k}\in[n]$ which are congruent modulo $k$ to
respectively $1,2,\dots,k$. Then $(x_{i_{1}},\dots,x_{i_{k}})$ is a uniform
element of $\prod_{i=1}^{k}J_{i}$ and by Fubini-Tonelli’s theorem, the
probability of seeing at least one $x$-bad pair in
${\\{i_{1},\dots,i_{k}\\}\choose 2}$ is the probability that a uniform element
of $\prod_{i=1}^{k}J_{i}$ ends in the complement of $X_{\gamma}$. This is at
most $\alpha/2$ by (26). Thus the expected fraction (for uniform
$x\in{\mathcal{X}}$) of $x$-bad pairs inside $\\{i_{1},\dots,i_{k}\\}$ is at
most $\alpha/2$. Since every crossing pair participates in the same number of
$k$-tuples in ${[n]\choose k}$ with distinct residues modulo $k$, if we take a
uniform such $k$-tuple and a uniform pair $ij$ inside it (which is necessarily
crossing), then we get a uniformly distributed crossing pair. Moreover, we
have already shown that, regardless of the chosen $k$-tuple, the probability
(over the random choices of $ij$ and $x$) that $ij$ is $x$-bad is at most
$\alpha/2$. Thus the expected value of $|B(x)|$ is at most
$\frac{\alpha}{2}\cdot m^{2}{k\choose 2}$. Let

${\mathcal{Y}}:=\left\\{x\in{\mathcal{X}}:|B(x)|\leqslant\alpha m^{2}{k\choose
2}\right\\}.$

By Markov’s inequality, the probability that $x\in{\mathcal{Y}}$ is at least
$1/2$.

Note that if $ij\in{[n]\choose 2}$ is an $x$-good pair then the probability of
$ij$ being rounded _correctly_ (meaning that $ij$ is an edge if and only if
$\\{i\mathrm{\,mod\,}k,j\mathrm{\,mod\,}k\\}\in E(G)$) is at least $\gamma$.
Thus if $x\in{\mathcal{Y}}$ then the rounding produces at least
$t:=\big{\lceil}(1-\alpha)m^{2}{k\choose 2}\big{\rceil}$ correct crossing
pairs with probability at least $\gamma^{t}$. If this happens and we overlay
all vertices in the $i$-th part of $H$ (namely those $j\in[n]$ with
$j\mathrm{\,mod\,}k=i$) with the $i$-th vertex of $G$ then the
$L^{1}$-distance between the corresponding graphons $f^{H}$ and $f^{G}$ is at
most

$\frac{2}{(km)^{2}}\left(k{m\choose 2}+\alpha m^{2}{k\choose
2}\right)<\frac{1}{k}+\alpha,$

where the first and second terms assume the worst-case scenario that all non-
crossing and all bad pairs respectively were rounded the “wrong” way.

Thus the probability that
$\delta_{\Box}(f^{G},f^{H})\leqslant\frac{1}{k}+\alpha$ for
$H\sim{\mathbbm{G}}(n,W)$ is at least the product of the following terms:

  * •

$(2/l)^{n}$: the probability that the uniform $x\in[0,1]^{n}$ is in
${\mathcal{X}}$,

  * •

$1/2$: the probability that a uniform $x\in{\mathcal{X}}$ hits ${\mathcal{Y}}$
(i.e., that there are at least $t$ $x$-good pairs),

  * •

$\gamma^{t}$: the probability that some $t$ of the $x$-good pairs, say the
first $t$ of them in the lexicographic order on ${[n]\choose 2}$, are rounded
correctly.

Altogether we have

$\log\left(\widetilde{\mathbb{R}}_{n,W}\left(B_{\delta_{\Box}}\left(\widetilde{f^{G}},\frac{1}{k}+\alpha\right)\right)\right)\geqslant
n\log\left(\frac{2}{l}\right)+\log\left(\frac{1}{2}\right)+t\log(\gamma),$
(27)

which in absolute value is clearly in $O(n^{2})\subseteq o(s(n))$ as
$n\to\infty$ (over the multiples of $k$), as desired.

Consider the case of general $n$. Assume that $n\geqslant 4k/\alpha$. Let
$n^{\prime}$ be the (unique) multiple of $k$ between $n-k+1$ and $n$. Let
$H^{\prime}$ be the subgraph of $H\sim{\mathbbm{G}}(n,W)$ induced by
$[n^{\prime}]$. By Lemma 2.4 applied with $s:=n^{\prime}/n$ we have
$\delta_{\Box}(f^{H},f^{H^{\prime}})\leqslant
2(n/n^{\prime}-1)<2k/n\leqslant\alpha/2$. Clearly, the random graph
$H^{\prime}$ is distributed as ${\mathbbm{G}}(n^{\prime},W)$. Thus

$\widetilde{\mathbb{R}}_{n,W}\left(B_{\delta_{\Box}}\left(\widetilde{f^{G}},\frac{1}{k}+\alpha\right)\right)\geqslant\widetilde{\mathbb{R}}_{n^{\prime},W}\left(B_{\delta_{\Box}}\left(\widetilde{f^{G}},\frac{1}{k}+\frac{\alpha}{2}\right)\right).$

If $n\to\infty$, then $n^{\prime}\to\infty$ over multiples of $k$ and the
right-hand side is ${\mathrm{e}}^{-o(s(n))}$ by the inequality in (24) for
$\alpha/2$, which was already established in this case, giving the required.

This finishes the proof of Theorem 1.3.∎

##  7 Coloured graphons

The definitions and results of this section are needed in order to establish
the lower semi-continuity of the functions
$J_{\mathbold{\alpha},\mathbold{p}}$ and $R_{\mathbold{p}}$ that were defined
in Section 1.5.

Fix $k\in\mathbb{N}$. By a _$k$ -coloured graphon_ we mean a pair
$(W,\mathcal{A})$ where $W\in\mathcal{W}$ and $\mathcal{A}\in{\bf A}^{(k)}$,
that is, $\mathcal{A}$ is a partition of $[0,1]$ into $k$ measurable parts.
One can view the partition $\mathcal{A}$ as a $k$-colouring of $[0,1]$. Write
$\mathcal{W}^{(k)}:={\mathcal{W}}\times{\bf A}^{(k)}$ for the space of all
$k$-coloured graphons. We define the pseudo-metric $d^{(k)}_{\Box}$ (the
analogue of the cut-norm $d_{\Box}$) on $\mathcal{W}^{(k)}$ as

$d^{(k)}_{\Box}((U,\mathcal{A}),(V,\mathcal{B})):=\sup_{C,D\subseteq[0,1]}\sum_{i,j\in[k]}\left|\int_{C\times
D}({{\mathbbm{1}}}_{A_{i}\times A_{j}}U-{{\mathbbm{1}}}_{B_{i}\times
B_{j}}V)\,\mathrm{d}\lambda^{\oplus
2}\right|+\sum_{i\in[k]}\lambda(A_{i}\triangle B_{i}),$

for $(U,\mathcal{A}),(V,\mathcal{B})\in\mathcal{W}^{(k)}$, where
${\mathcal{A}}=(A_{1},\dots,A_{k})$ and ${\mathcal{B}}=(B_{1},\dots,B_{k})$.
Informally speaking, two $k$-coloured graphons are close to each other in
$d^{(k)}$ if they have similar distributions of coloured edges across cuts,
where an edge is coloured by the colours of its endpoints. The second term is
added so that e.g. we can distinguish two constant-0 graphons with different
part measures.

The _cut-distance_ for coloured graphons is then defined as

$\delta^{(k)}_{\Box}((U,\mathcal{A}),(V,\mathcal{B})):=\inf_{\phi,\psi}d^{(k)}_{\Box}((U,\mathcal{A})^{\phi},(V,\mathcal{B})^{\psi}),$
(28)

where the infimum is taken over measure-preserving maps
$\phi,\psi:[0,1]\to[0,1]$ and we denote
$(U,\mathcal{A})^{\phi}:=(U^{\phi},{\mathcal{A}}^{\phi})$ and
${\mathcal{A}}^{\phi}:=(\phi^{-1}(A_{1}),\dots,\phi^{-1}(A_{k}))$ with
$(A_{1},\dots,A_{k})$ being the parts of ${\mathcal{A}}$. As in the graphon
case (compare with e.g. [Lovasz:lngl, Theorem 8.13]), some other definitions
give the same distance (e.g. it is enough to take the identity function for
$\psi$). We chose this definition as it is immediately clear from it that the
function $\delta^{(k)}_{\Box}$ is symmetric and defines a pseudo-metric. We
write $\widetilde{\mathcal{W}}^{(k)}$ for the corresponding quotient, where we
identify two $k$-coloured graphons at $\delta^{(k)}_{\Box}$-distance 0.

######  Theorem 7.1.

The metric space $(\widetilde{\mathcal{W}}^{(k)},\delta^{(k)}_{\Box})$ is
compact.

###### Proof.

The proof is obtained by the obvious adaptation of the proof of Lovász and
Szegedy [LovaszSzegedy07gafa, Theorem 5.1] (see also [Lovasz:lngl, Theorem
9.23]) that the space $(\widetilde{\mathcal{W}},\delta_{\Box})$ is compact.

Let $(W_{n},\mathcal{A}_{n})_{n\in\mathbb{N}}$ be an arbitrary sequence of
elements of $\mathcal{W}^{(k)}$. We have to find a subsequence that converges
to some element of $\mathcal{W}^{(k)}$ with respect to $\delta_{\Box}^{(k)}$.

When dealing with the elements of $\mathcal{W}^{(k)}$, we can ignore null
subsets of $[0,1]$; thus all relevant statements, e.g. that one partition
refines another, are meant to hold almost everywhere.

For $n\in\mathbb{N}$, let the parts of $\mathcal{A}_{n}$ be
$(A_{n,1},\dots,A_{n,k})$ and, by applying a measure-preserving bijection to
$(W_{n},\mathcal{A}_{n})$, assume by Theorem 2.1 that the colour classes
$A_{n,1},\dots,A_{n,k}\subseteq[0,1]$ are all intervals, coming in this order.
By passing to a subsequence, assume that, for each $i\in[k]$, the length of
$A_{n,i}$ converges to some $\alpha_{i}\in[0,1]$ as $n\to\infty$. With
$\mathbold{\alpha}:=(\alpha_{1},\dots,\alpha_{k})$, this gives rise to the
“limiting” partition

$\mathcal{A}:=(I_{1}^{(\mathbold{\alpha})},\dots,I_{k}^{(\mathbold{\alpha})})\in{\bf
A}^{(\mathbold{\alpha})}$

of $[0,1]$ into intervals.

Let $m_{1}:=k$ and inductively for $q=2,3,\ldots$ let $m_{q}$ be sufficiently
large such that for every graphon $W$ and a measurable partition
$\mathcal{A}^{\prime}$ of $[0,1]$ with $|\mathcal{A}^{\prime}|\leqslant
m_{q-1}$ there is a measurable partition $\mathcal{P}=(P_{1},\dots,P_{m})$ of
$[0,1]$ refining $\mathcal{A}^{\prime}$ such that $m\leqslant m_{q}$ and
$d_{\Box}(W,W_{\mathcal{P}})\leqslant 1/q$. Here $W_{\mathcal{P}}$ denotes the
projection of $W$ to the space of ${\mathcal{P}}$-step graphons; namely, for
every $i,j\in[m]$ with $P_{i}\times P_{j}$ non-null in $\lambda^{\oplus 2}$,
$W_{{\mathcal{P}}}$ assumes the constant value
$\frac{1}{\lambda(P_{i})\lambda(P_{j})}\int_{P_{i}\times
P_{j}}W\,\mathrm{d}\lambda^{\oplus 2}$ on $P_{i}\times P_{j}$ (and, say,
$W_{{\mathcal{P}}}$ is defined to be 0 on all $\lambda^{\oplus 2}$-null
products $P_{i}\times P_{j}$). Such a number $m_{q}$ exists by [Lovasz:lngl,
Lemma 9.15], a version of the Weak Regularity Lemma for graphons.

For each $n\in\mathbb{N}$, we do the following. Let
$\mathcal{P}_{n,1}:=\mathcal{A}_{n}$ and, inductively on $q=2,3,\dots$, let
$\mathcal{P}_{n,q}$ be the partition with at most $m_{q}$ parts obtained by
applying the above Weak Regularity Lemma to $(W_{n},\mathcal{P}_{n,q-1})$. By
adding empty parts to $\mathcal{P}_{n,q}$, for each $q\geqslant 1$, we can
assume that it has the same number of parts (namely, $m_{q}$) of each colour,
that is, we can denote its parts as $(P_{n,q,i,j})_{i\in[k],j\in[m_{q}]}$, so
that $P_{n,q,i,j}\subseteq A_{n,i}$ for all $(i,j)\in[k]\times[m_{q}]$. Also,
define $W_{n,q}:=(W_{n})_{\mathcal{P}_{n,q}}$ to be the projection of the
graphon $W_{n}$ on the space of $\mathcal{P}_{n,q}$-step graphons.

Then, iteratively for $q=2,3,\dots$, repeat the following. Find a measure-
preserving bijection $\phi:[0,1]\to[0,1]$ such that
$(\mathcal{P}_{n,q})^{\phi}$ is a partition into intervals and $\phi$
preserves the previous partitions
$\mathcal{P}_{n,1},\dots,\mathcal{P}_{n,q-1}$ (each of which is a partition
into intervals by induction on $q$). Then, for each $m\geqslant q$, replace
$(W_{n,m},\mathcal{P}_{n,m})$ by $(W_{n,m},\mathcal{P}_{n,m})^{\phi}$. When we
are done with this step, the following properties hold for each integer
$q\geqslant 2$:

  * •

$\delta_{\Box}^{(k)}((W_{n,q},\mathcal{A}_{n}),(W_{n},\mathcal{A}_{n}))\leqslant
k^{2}/q$;

  * •

The partition $\mathcal{P}_{n,q}$ refines $\mathcal{P}_{n,q-1}$ (and,
inductively, also refines $\mathcal{A}_{n}=\mathcal{P}_{n,1}$);

  * •

$|\mathcal{P}_{n,q}|=km_{q}$ with exactly $m_{q}$ parts assigned to each
colour class of $\mathcal{A}_{n}$.

Next, iteratively for $q=1,2,\dots$, we pass to a subsequence of $n$ so that
for every $(i,j)\in[k]\times[m_{q}]$, the length of the interval $P_{n,q,i,j}$
converges, and for every pair
$(i,j),(i^{\prime},j^{\prime})\in[k]\times[m_{q}]$, the common value of the
step-graphon $W_{n,q}$ on $P_{n,q,i,j}\times P_{n,q,i^{\prime},j^{\prime}}$
converges. It follows that the sequence $W_{n,q}$ converges pointwise to some
graphon $U_{q}$ which is itself a step-function with $km_{q}$ parts that are
intervals. We use diagonalisation to find a subsequence of $n$ so that, for
each $q\in\mathbb{N}$, $W_{n,q}$ converges to some step-graphon $U_{q}$ a.e.
as $n\to\infty$, with the step partition $\mathcal{P}_{q}$ of $U_{q}$
consisting of $km_{q}$ intervals and refining the partition ${\mathcal{A}}$.

It follows that, for all $s<t$ in ${\mathbbm{N}}$, the partition
$\mathcal{P}_{t}$ is a refinement of $\mathcal{P}_{s}$ and, moreover, $U_{s}$
is the conditional expectation $\mathbb{E}[U_{t}|\mathcal{P}_{s}]$ a.e. As
observed in the proof of Lovász and Szegedy [LovaszSzegedy07gafa, Theorem
5.1], this (and $0\leqslant U_{t}\leqslant 1$ a.e.) implies by the Martingale
Convergence Theorem that $U_{q}$ converge a.e. to some graphon $U$ as
$q\to\infty$. By the Dominated Convergence Theorem, $U_{q}\to U$ also in the
$L^{1}$-distance.

We claim that $\delta_{\Box}((W_{n},\mathcal{A}_{n}),(U,\mathcal{A}))\to 0$ as
$n\to\infty$ (after we passed to the subsequence defined as above). Take any
$\epsilon>0$. Fix an integer $q>4/\epsilon$ such that
$\|U-U_{q}\|_{1}\leqslant\epsilon/(4k^{2})$. Given $q$, fix $n_{0}$ such that
for all $n\geqslant n_{0}$ we have
$\|U_{q}-W_{n,q}\|_{1}\leqslant\epsilon/(4k^{2})$ and
$\sum_{i=1}^{k}\lambda(I_{i}^{(\mathbold{\alpha})}\bigtriangleup
A_{n,i})\leqslant\epsilon/4$. Then, for every $n\geqslant n_{0}$ we have

$\displaystyle\delta_{\Box}^{(k)}((U,\mathcal{A}),(W_{n},\mathcal{A}_{n}))$
$\displaystyle\leqslant$ $\displaystyle
d_{\Box}^{(k)}((U,\mathcal{A}),(U_{q},\mathcal{A}))+d_{\Box}^{(k)}((U_{q},\mathcal{A}),(W_{n,q},\mathcal{A}_{n}))$
$\displaystyle+$
$\displaystyle\delta_{\Box}^{(k)}((W_{n,q},\mathcal{A}_{n}),(W_{n},\mathcal{A}_{n}))$
$\displaystyle\leqslant$ $\displaystyle
k^{2}\|U-U_{q}\|_{1}+k^{2}\|U_{q}-W_{n,q}\|_{1}+\sum_{i=1}^{k}\lambda(I_{i}^{(\mathbold{\alpha})}\bigtriangleup
A_{n,i})+1/q$ $\displaystyle\leqslant$
$\displaystyle\epsilon/4+\epsilon/4+\epsilon/4+\epsilon/4\ =\ \epsilon.$

Since $\epsilon>0$ was arbitrary, the claim is proved. Thus the metric space
$(\widetilde{\mathcal{W}}^{(k)},\delta^{(k)}_{\Box})$ is indeed compact. ∎

##  8 The lower semi-continuity of $J_{\mathbold{\alpha},\mathbold{p}}$ and
$R_{\mathbold{p}}$

For this section we fix an integer $k\geqslant 1$, a symmetric $k\times k$
matrix $\mathbold{p}=(p_{i,j})_{i,j\in[k]}\in[0,1]^{k\times k}$ and a non-zero
real vector $\mathbold{\alpha}\in[0,\infty)^{k}$. We show that the functions
$J_{\mathbold{\alpha},\mathbold{p}}$ and $R_{\mathbold{p}}$, that were defined
in (8) and (9) respectively, are lower semi-continuous functions on
$(\widetilde{\mathcal{W}},\delta_{\Box})$.

Let $\Gamma:\mathcal{W}^{(k)}\to{\mathcal{W}}$ be the map that forgets the
colouring, i.e., $\Gamma(U,\mathcal{A}):=U$ for
$(U,{\mathcal{A}})\in\mathcal{W}^{(k)}$. For $i,j\in[k]$, let the map
$\Gamma_{i,j}:\mathcal{W}^{(k)}\to{\mathcal{W}}$ send
$(U,(A_{1},\dots,A_{k}))\in\mathcal{W}^{(k)}$ to the graphon $V$ defined as

$V(x,y):=\left\\{\begin{array}[]{ll}U(x,y),&(x,y)\in(A_{i}\times
A_{j})\cup(A_{j}\times A_{i}),\\\
p_{i,j},&\mbox{otherwise,}\end{array}\right.\quad\mbox{for $x,y\in[0,1]$.}$

######  Lemma 8.1.

The maps $\Gamma$ and $\Gamma_{i,j}$, for ${i,j\in[k]}$, are $1$-Lipschitz
maps from $(\mathcal{W}^{(k)},d_{\Box}^{(k)})$ to $({\mathcal{W}},d_{\Box})$.

###### Proof.

First, consider $\Gamma:\mathcal{W}^{(k)}\to\mathcal{W}$. Take arbitrary
$(U,\mathcal{A}),(V,\mathcal{B})\in\mathcal{W}^{(k)}$. Let
${\mathcal{A}}=(A_{1},\dots,A_{k})$ and $\mathcal{B}=(B_{1},\dots,B_{k})$.
Clearly, the pairwise products $A_{i}\times A_{j}$ (resp. $B_{i}\times B_{j}$)
for $i,j\in[k]$ partition $[0,1]^{2}$. Thus we have

$\displaystyle d_{\Box}(\Gamma(U,\mathcal{A}),\Gamma(V,\mathcal{B}))$
$\displaystyle=$ $\displaystyle d_{\Box}(U,V)\ =\
\sup_{C,D\subseteq[0,1]}\left|\int_{C\times D}(U-V)\,\mathrm{d}\lambda^{\oplus
2}\right|$ (29) $\displaystyle\leqslant$
$\displaystyle\sup_{C,D\subseteq[0,1]}\sum_{i,j\in[k]}\left|\int_{C\times
D}(U\,{{\mathbbm{1}}}_{A_{i}\times A_{j}}-V\,{\mathbbm{1}}_{B_{i}\times
B_{j}})\,\mathrm{d}\lambda^{\oplus 2}\right|$ $\displaystyle\leqslant$
$\displaystyle d_{\Box}^{(k)}((U,\mathcal{A}),(V,\mathcal{B})).$

Thus the function $\Gamma$ is indeed $1$-Lipschitz.

The claim about $\Gamma_{i,j}$ follows by observing that

$d_{\Box}(\Gamma_{i,j}(U,\mathcal{A}),\Gamma_{i,j}(V,\mathcal{B}))\leqslant
d_{\Box}(\Gamma(U,\mathcal{A}),\Gamma(V,\mathcal{B}))$

for every $(U,\mathcal{A}),(V,\mathcal{B})\in\mathcal{W}^{(k)}$.∎

######  Lemma 8.2.

Let $F$ be $\Gamma$ or $\Gamma_{i,j}$ for some $i,j\in[k]$. Then $F$ gives
rise to a well-defined function
$\widetilde{\mathcal{W}}^{(k)}\to\widetilde{\mathcal{W}}$ which, moreover, is
$1$-Lipschitz as a function from
$(\widetilde{\mathcal{W}}^{(k)},\delta_{\Box}^{(k)})$ to
$(\widetilde{\mathcal{W}},\delta_{\Box})$.

###### Proof.

Take any $(U,{\mathcal{A}}),(V,{\mathcal{B}})\in\mathcal{W}^{(k)}$. Let
$\epsilon>0$ be arbitrary. Fix measure-preserving maps
$\phi,\psi:[0,1]\to[0,1]$ with
$d_{\Box}^{(k)}((U,{\mathcal{A}})^{\psi},(V,{\mathcal{B}})^{\phi})<\delta_{\Box}^{(k)}((U,{\mathcal{A}}),(V,{\mathcal{B}}))+\epsilon$.
By Lemma 8.1, we have

$\displaystyle\delta_{\Box}\left(F(U,{\mathcal{A}}),F(V,{\mathcal{B}})\right)$
$\displaystyle\leqslant$ $\displaystyle
d_{\Box}\left((F(U,{\mathcal{A}}))^{\psi},(F(V,{\mathcal{B}}))^{\phi}\right)\
=\
d_{\Box}\left(F(U^{\psi},{\mathcal{A}}^{\psi}),F(V^{\phi},{\mathcal{B}}^{\phi})\right)$
$\displaystyle\leqslant$ $\displaystyle
d_{\Box}^{(k)}((U^{\psi},{\mathcal{A}}^{\psi}),(V^{\phi},{\mathcal{B}}^{\phi}))\
<\
\delta_{\Box}^{(k)}\left((U,{\mathcal{A}}),(V,{\mathcal{B}})\right)+\epsilon.$

This implies both claims about $F$ as $\epsilon>0$ was arbitrary. ∎

For $(U,(A_{1},\dots,A_{k}))\in\mathcal{W}^{(k)}$, define

$I^{(k)}_{\mathbold{p}}(U,(A_{1},\dots,A_{k})):=\frac{1}{2}\sum_{i,j\in[k]}\int_{A_{i}\times
A_{j}}I_{p_{i,j}}(U)\,\mathrm{d}\lambda^{\oplus 2}.$ (30)

In the special case of (30) when $k=1$ and $p_{1,1}=p$ (and we ignore the
second component since ${\bf A}^{(1)}$ consists of just the trivial partition
of $[0,1]$ into one part), we get the function
$I_{p}:{\mathcal{W}}\to[0,\infty]$ of Chatterjee and Varadhan defined in (5).

######  Lemma 8.3.

The function $I^{(k)}_{\mathbold{p}}$ gives a well-defined function
$\widetilde{\mathcal{W}}^{(k)}\to[0,\infty]$ which, moreover, is lower semi-
continuous as a function on
$(\widetilde{\mathcal{W}}^{(k)},\delta^{(k)}_{\Box})$.

###### Proof.

Note that we can write

$I^{(k)}_{\mathbold{p}}(U,\mathcal{A})=\sum_{1\leqslant i\leqslant j\leqslant
k}I_{p_{i,j}}(\Gamma_{i,j}(U,\mathcal{A})),\quad(U,{\mathcal{A}})\in\mathcal{W}^{(k)},$
(31)

because $\Gamma_{i,j}(U,{\mathcal{A}})$ assumes value $p_{i,j}$ outside of
$(A_{i}\times A_{j})\cup(A_{j}\times A_{i})$ while $I_{p}(p)=0$ for any
$p\in[0,1]$. Recall that, by Theorem 1.2, $I_{p}$ gives a well-defined
function $\widetilde{\mathcal{W}}\to[0,\infty]$ for every $p\in[0,1]$. Thus,
by Lemma 8.2, the right-hand side of (31) does not change if we replace
$(U,{\mathcal{A}})$ by any other element of $\mathcal{W}^{(k)}$ at
$\delta_{\Box}^{(k)}$-distance 0. We conclude that $I_{\mathbold{p}}^{(k)}$
gives a well-defined function on $\widetilde{\mathcal{W}}^{(k)}$.

Each composition $I_{p}\circ\Gamma_{i,j}$ is lsc as a function
$(\widetilde{\mathcal{W}}^{(k)},\delta_{\Box}^{(k)})\to[0,\infty]$ because,
for every $r\in{\mathbbm{R}}$, the level set
$\\{I_{p}\circ\Gamma_{ij}\leqslant r\\}$ is closed as the pre-image under the
continuous function
$\Gamma_{i,j}:\widetilde{\mathcal{W}}^{(k)}\to\widetilde{\mathcal{W}}$ of the
closed set $\\{I_{p}\leqslant r\\}$. (Recall that the function
$I_{p}:\widetilde{\mathcal{W}}\to[0,\infty]$ is lsc by Theorem 1.2.) Thus
$I^{(k)}_{\mathbold{p}}:\widetilde{\mathcal{W}}^{(k)}\to[0,\infty]$ is lsc by
(31), as a finite sum of lsc functions. ∎

Now we are ready to show that the functions
$J_{\mathbold{\alpha},\mathbold{p}}$ and $R_{\mathbold{p}}$ are lsc (thus
proving Theorem 1.6 and the first part of Theorem 1.4). The argument showing
the lower semi-continuity of these functions is motivated by the proof of the
Contraction Principle (Theorem 2.6)

######  Theorem 8.4.

For every symmetric matrix $\mathbold{p}\in[0,1]^{k\times k}$ and every non-
zero real vector $\mathbold{\alpha}\in[0,\infty)^{k}$, the functions
$J_{\mathbold{\alpha},\mathbold{p}}$ and $R_{\mathbold{p}}$ are lower semi-
continuous on $(\widetilde{\mathcal{W}},\delta_{\Box})$.

###### Proof.

Note that $J_{\mathbold{\alpha},\mathbold{p}}(\widetilde{U})$ for any
$U\in{\mathcal{W}}$ is equal to the infimum of
$I_{\mathbold{p}}^{(k)}(V,{\mathcal{A}})$ over all
$(V,{\mathcal{A}})\in\mathcal{W}\times{\bf A}^{(\mathbold{\alpha})}$ such that
$\Gamma(V,{\mathcal{A}})=V$ belongs to $\widetilde{U}$. Indeed, for any
partition ${\mathcal{A}}\in{\bf A}^{(\mathbold{\alpha})}$ of $[0,1]$, one can