# Finitely Forcible Graphons with an Almost Arbitrary Structure††thanks: The
work of the first and third authors has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme (grant agreement No 648509). This publication reflects
only its authors’ view; the European Research Council Executive Agency is not
responsible for any use that may be made of the information it contains. The
first author was also supported by the Engineering and Physical Sciences
Research Council Standard Grant number EP/M025365/1. The work of the second
author was supported by NSF Postdoctoral Fellowship Award DMS-1705204. The
work of the fourth author was supported by the Leverhulme Trust 2014 Philip
Leverhulme Prize of the first author and partially by the project 17-09142S of
GAČR.

Daniel Král’  László M. Lovász  Jonathan A. Noel  Jakub Sosnovec

###### Abstract

Graphons are analytic objects representing convergent sequences of large
graphs. A graphon is said to be finitely forcible if it is determined by
finitely many subgraph densities, i.e., if the asymptotic structure of graphs
represented by such a graphon depends only on finitely many density
constraints. Such graphons appear in various scenarios, particularly in
extremal combinatorics.

Lovász and Szegedy conjectured that all finitely forcible graphons possess a
simple structure. This was disproved in a strong sense by Cooper, Král’ and
Martins, who showed that any graphon is a subgraphon of a finitely forcible
graphon. We strengthen this result by showing for every $\varepsilon>0$ that
any graphon spans a $1-\varepsilon$ proportion of a finitely forcible graphon.

title = Finitely Forcible Graphons with an Almost Arbitrary Structure, author
= Daniel Král’, László M. Lovász, Jonathan A. Noel, and Jakub Sosnovec,
plaintextauthor = Daniel Kral, Laszlo M. Lovasz, Jonathan A. Noel, Jakub
Sosnovec, year=2020, number=9, received=25 September 2019, published=31 July
2020, doi=10.19086/da.12058,

[classification=text]

##  1 Introduction

The theory of graph limits is an emerging area of combinatorics, which offers
analytic tools to study large graphs. The range of applications of analytic
methods offered by the theory of graph limits has been constantly expanding.
The most prominent examples of such applications come from the closely related
flag algebra method of Razborov [32], which changed the landscape of extremal
graph combinatorics by providing progress on numerous important problems in
the area, e.g. [1, 2, 3, 4, 5, 17, 19, 20, 21, 22, 30, 31, 32, 33, 34]. Among
other applications of the methods provided by the theory, we would like to
highlight those from computer science related to property and parameter
testing algorithms [29]. We refer the reader to the recent monograph by Lovász
[25] for further results.

In this paper, we are interested in limits of sequences of dense graphs. An
analytic object representing a sequence of dense graphs is called a graphon.
Formally, a _graphon_ is a measurable function $W$ from the unit square
$[0,1]^{2}$ to the unit interval $[0,1]$ that is symmetric; i.e.,
$W(x,y)=W(y,x)$ for every $(x,y)\in[0,1]^{2}$. Given a graphon $W$, we can
define the density $d(H,W)$ of a graph $H$ in $W$ (we give the definition in
Section 2). Every graphon is uniquely determined, up to weak isomorphism, by
the densities of all graphs. The main objects of our study are _finitely
forcible_ graphons, which are graphons that are uniquely determined by the
densities of finitely many graphs. We refer the reader to Section 2 for a
detailed presentation of these concepts.

Results on finitely forcible graphons can be found in disguise in various
settings in graph theory. For example, a classical result of Thomason [35],
also see Chung, Graham and Wilson [7], on quasirandom graphs is equivalent to
saying that the constant graphon is finitely forcible by the densities of
$4$-vertex graphs. Another source of motivation for studying finitely forcible
graphons comes from extremal graph theory. For example, Proposition 3, given
in Section 2, states that a graphon $W$ is finitely forcible if and only if
there exists some linear combination of subgraph densities such that $W$ is
its unique minimizer.

Lovász and Szegedy [27] initiated a systematic study of properties of finitely
forcible graphons and conjectured, based on examples of finitely forcible
graphons known at that time, that all finitely forcible graphons must posses a
simple structure. In particular, a graphon $W$ can be associated with a
topological space whose points correspond to types of vertices that appear in
any sequence of graphs converging to $W$ (so-called typical vertices); the
following conjectures assert that this space cannot be complex for finitely
forcible graphons.

######  Conjecture 1 (Lovász and Szegedy, [27, Conjecture 9]).

The space of typical vertices of every finitely forcible graphon is compact.

######  Conjecture 2 (Lovász and Szegedy, [27, Conjecture 10]).

The space of typical vertices of every finitely forcible graphon has finite
dimension.

Conjectures 1 and 2 were disproved by counterexample constructions in [16] and
[15], respectively. A stronger counterexample to Conjecture 2 was given in
[9]: if true, Conjecture 2 would imply that the minimum number of parts of a
weak $\varepsilon$-regular partition of a finitely forcible graphon is bounded
by a power of $\varepsilon^{-1}$. For the finitely forcible graphon
constructed in [9], any weak $\varepsilon$-regular partition must have a
number of parts almost exponential in $\varepsilon^{-2}$ for infinitely many
$\varepsilon>0$, which is close to the general lower bound from [8]. This line
of research culminated with the following general result of Cooper, Martins
and the first author [10].

######  Theorem 1.

For every graphon $W_{F}$, there exists a finitely forcible graphon $W_{0}$
such that $W_{F}$ is a subgraphon of $W_{0}$ induced by a $1/14$ fraction of
the vertices of $W_{0}$.

Theorem 1 yields counterexamples to Conjectures 1 and 2 and provides a
universal framework for constructing finitely forcible graphons with very
complex structure. In view of Proposition 3, Theorem 1 says that problems on
minimizing a linear combination of subgraph densities, which are among the
problems of the simplest kind in extremal graph theory, may have unique
optimal solutions with highly complex structure. Furthermore, given the
general nature of Theorem 1, it is surprising [10] that the family of graphs
whose densities force $W_{0}$ in Theorem 1 can be chosen to be independent of
$W_{F}$.

It is natural to ask whether the fraction $1/14$ in Theorem 1 can be replaced
by a larger quantity. The proof techniques from [10] allows replacing the
fraction by any number smaller than $1/2$. The purpose of this paper is to
show that the fraction can be replaced by any number smaller than $1$.

######  Theorem 2.

For every $\varepsilon>0$ and every graphon $W_{F}$, there exists a finitely
forcible graphon $W_{0}$ such that $W_{F}$ is a subgraphon of $W_{0}$ induced
by a $1-\varepsilon$ fraction of the vertices of $W_{0}$.

The proof of Theorem 2 is based on the method of decorated constraints, which
was introduced in [16, 15], and uses Theorem 1 as one of the main tools.
Informally speaking, Theorem 1 is used to embed the graphon $W_{F}$ on a small
part of $W_{0}$ and other auxiliary structure of $W_{0}$ is then used to
magnify the graphon $W_{F}$ to the $1-\varepsilon$ fraction of the vertices of
$W_{0}$. We remark that, in contrast to the proof of Theorem 1, the family of
graphs used to force $W_{0}$ in Theorem 2 depends on $\varepsilon$, and we
show in Section 4 that this dependence is necessary.

##  2 Preliminaries

We now introduce the notation and terminology used in the paper. We start with
some general notation. For $k\in\mathbb{N}$, $[k]$ denotes the set of integers
$\\{1,2,\ldots,k\\}$. If $\mathcal{F}$ is a family of sets, we use
$\bigcup\mathcal{F}$ to denote the union of all sets $F\in\mathcal{F}$. Unless
stated otherwise, we work with the Lebesgue measure on $[0,1]^{d}$ throughout
the paper. If $X\subseteq\mathbb{R}^{d}$ is a measurable set, we write $|X|$
for its measure and for two measurable sets $X,Y\subset\mathbb{R}^{d}$, and we
write $X\sqsubseteq Y$ to mean $|X\setminus Y|=0$.

###  2.1 Graphs and graphons

The _order_ of a graph $G$, which is denoted by $|G|$, is its number of
vertices. The _density_ of a graph $H$ in $G$, which is denoted $d(H,G)$, is
the probability that a uniformly randomly chosen set of $|H|$ vertices of $G$
induces a graph isomorphic to $H$. If $|H|>|G|$, then we set $d(H,G)$ to zero

Our notation mostly follows that used in [10] in relation to graph limits. As
defined earlier, a _graphon_ is a measurable function $W$ from the unit square
$[0,1]^{2}$ to the unit interval $[0,1]$ that is _symmetric_ ; i.e.,
$W(x,y)=W(y,x)$ for every $(x,y)\in[0,1]^{2}$. Conceptually, a graphon $W$ can
be thought of as an infinite weighted graph on the vertex set $[0,1]$ with the
edge $(x,y)\in[0,1]^{2}$ having weight $W(x,y)$. Following this intuition, we
refer to the points of $[0,1]$ as _vertices_. To visualize the structure of a
graphon, we shall use a figure that may be seen as a continuous version of the
adjacency matrix. More precisely, in a figure depicting $W$, the domain of
$W$ is represented by the unit square $[0,1]^{2}$ with the origin in the top
left corner. The values of $W$ are represented by appropriate shades of gray
($0$ corresponds to white and $1$ to black). See the left side of Figure 2 for
an example.

A graphon can be associated with a probability distribution on graphs of a
fixed order. Formally, for a graphon $W$ and an integer $k\in\mathbb{N}$, a
$W$-_random graph_ of order $k$ is a graph $G$ obtained by the following two
step procedure. Let $x_{1},\ldots,x_{k}\in[0,1]$ be $k$ points chosen
uniformly and independently at random. Form a graph $G$ with the vertex set
$[k]$ such that the edge $ij$ is present with probability $W(x_{i},x_{j})$ for
every pair of distinct vertices $i,j\in[k]$. The _density_ of a graph $H$ in
the graphon $W$ is the probability that a $W$-random graph of order $|H|$ is
isomorphic to $H$; we denote the density of $H$ in $W$ by $d(H,W)$. Note that
$d(H,W)$ is also the expected density of $H$ in a $W$-random graph $G$ of
order $k$ for every $k\geq|H|$.

Consider a sequence of graphs $\left(G_{n}\right)_{n\in\mathbb{N}}$ such that
the orders $\left|G_{n}\right|$ tend to infinity. We say that the sequence
$\left(G_{n}\right)_{n\in\mathbb{N}}$ is _convergent_ if for every graph $H$,
the sequence of the densities of $H$ in $G_{n}$, i.e., the sequence
$\left(d\left(H,G_{n}\right)\right)_{n\in\mathbb{N}}$, is convergent. We say
that the sequence $\left(G_{n}\right)_{n\in\mathbb{N}}$ converges to a graphon
$W$ if

$\lim_{n\to\infty}d\left(H,G_{n}\right)=d(H,W)$

for every graph $H$. Lovász and Szegedy [28] showed that every convergent
sequence of graphs converges to a graphon. Conversely, they showed that for
every graphon, there exists a sequence of graphs converging to it. In
particular, the sequence of $W$-random graphs of increasing orders converges
to $W$ with probability one.

For a graphon $W$ and a vertex $x\in[0,1]$, we define the _degree_ of $x$ in
$W$ as

$\deg_{W}(x)=\int_{[0,1]}W(x,y)\mathop{}\\!\mathrm{d}y.$

Note that the degree is well-defined for almost every vertex $x\in[0,1]$. We
also define the _neighbourhood_ of a vertex $x\in[0,1]$ as the set
$\\{y\in[0,1]:W(x,y)>0\\}$ and denote it $N_{W}(x)$. Note that the set
$N_{W}(x)$ is measurable for almost every $x\in[0,1]$. The _density_ of a
graphon $W$ between two measurable subsets $A$ and $B$ of $[0,1]$ is defined
to be

$d_{W}(A,B)=\int_{A\times
B}W(x,y)\mathop{}\\!\mathrm{d}{x}\mathop{}\\!\mathrm{d}{y}.$

When the graphon $W$ is clear from context, we omit the subscripts. Finally,
we define a graphon parameter $t(C_{4},W)$ as follows:

$t(C_{4},W)=\int_{[0,1]^{4}}W(x_{1},x_{2})W(x_{2},x_{3})W(x_{3},x_{4})W(x_{4},x_{1})\mathop{}\\!\mathrm{d}{x_{1}}\mathop{}\\!\mathrm{d}{x_{2}}\mathop{}\\!\mathrm{d}{x_{3}}\mathop{}\\!\mathrm{d}{x_{4}},$

which is equal to the probability that a randomly chosen cyclic $4$-tuple in a
$W$-random graph forms a (not necessarily induced) cycle of length four.
Observe that $t(C_{4},W)=d(C_{4},W)/3+d(K_{4}^{-},W)/3+d(K_{4},W)$, where
$K_{4}^{-}$ is the graph obtained from $K_{4}$ by removing an edge.

We say that two graphons $W_{1}$ and $W_{2}$ are _weakly isomorphic_ if
$d\left(H,W_{1}\right)=d\left(H,W_{2}\right)$ for every graph $H$. Clearly,
weakly isomorphic graphons are limits of the same sequences of graphs. It is
natural to ask how weakly isomorphic graphons can differ in their structure;
this was answered in [6]. Recall that a function $\varphi\colon[0,1]\to[0,1]$
is _measure-preserving_ if it is measurable and $|\varphi^{-1}(X)|=|X|$ for
every measurable subset $X\subseteq[0,1]$. It is easy to check that if
$\varphi\colon[0,1]\to[0,1]$ is a measure-preserving map, then the graphon
$W^{\varphi}$ defined as $W^{\varphi}(x,y)=W(\varphi(x),\varphi(y))$ is weakly
isomorphic to $W$. In [6], it was shown in particular that two graphons
$W_{1}$ and $W_{2}$ are weakly isomorphic if and only if there exist measure-
preserving maps $\varphi_{1},\varphi_{2}\colon[0,1]\to[0,1]$ such that
$W_{1}^{\varphi_{1}}=W_{2}^{\varphi_{2}}$ almost everywhere.

Let $W_{1}$ and $W_{2}$ be two graphons and $X\subseteq[0,1]$ a non-null
measurable set. We say that $W_{1}$ is a _subgraphon_ of $W_{2}$ induced by
$X$ if there exist measure-preserving maps $\varphi_{1}\colon X\to[0,|X|)$ and
$\varphi_{2}\colon X\to X$ such that

$W_{1}\left(|X|^{-1}\cdot\varphi_{1}(x),|X|^{-1}\cdot\varphi_{1}(y)\right)=W_{2}\left(\varphi_{2}(x),\varphi_{2}(y)\right)$

for almost every $(x,y)\in X\times X$.

A graphon $W$ is _finitely forcible_ if there exist graphs
$H_{1},\ldots,H_{m}$ such that any graphon $W^{\prime}$ satisfying that
$d\left(H_{i},W^{\prime}\right)=d\left(H_{i},W\right)$ for every $i\in[m]$ is
weakly isomorphic to $W$. A family of graphs $H_{1},\ldots,H_{m}$ whose
densities determine the graphon $W$ up to weak isomorphism is called a
_forcing family_. Examples of finitely forcible graphons include constant
graphons, step graphons [26] and the half-graphon [11, 27]. We remind the
reader that a _step graphon_ is a graphon $W$ such that there exists a
partition of $[0,1]$ into intervals $U_{1},\ldots,U_{k}$ such that $W$ is
constant on $U_{i}\times U_{j}$ for every $i,j\in[k]$, and the _half-graphon_
is the graphon $W_{\Delta}$ such that $W_{\Delta}(x,y)=1$ if $x+y\geq 1$ and
$W_{\Delta}(x,y)=0$ otherwise.

The following proposition provides a link between finitely forcible graphons
and extremal graph theory.

######  Proposition 3.

A graphon $W$ is finitely forcible if and only if there exist graphs
$H_{1},\ldots,H_{m}$ and reals $\alpha_{1},\ldots,\alpha_{m}$ such that for
every graphon $W^{\prime}$,

$\sum_{i=1}^{m}\alpha_{i}d\left(H_{i},W\right)\leq\sum_{i=1}^{m}\alpha_{i}d\left(H_{i},W^{\prime}\right),$

and equality holds if and only if $W$ and $W^{\prime}$ are weakly isomorphic.

In the opposite direction, it is not the case that every linear combination of
subgraph densities has a unique minimizer (e.g. $d(K_{3},W)$ is minimized by
any triangle-free graphon $W$). However, Lovász [23, 24, 25, 27] conjectured
that one can always add further density constraints to make the solution
unique. Specifically, he conjectured the following. Let
$H_{1},\ldots,H_{\ell}$ be graphs and $d_{1},\ldots,d_{\ell}$ reals. If there
exists a graphon $W$ such that $d(H_{i},W)=d_{i}$, $i=1,\ldots,\ell$, then
there exists a finitely forcible such graphon. This statement turned out to be
false and the conjecture was recently disproved by Grzesik and two of the
authors [18].

We next give two statements about graphons that are needed in our arguments.
We start with a lemma, which is a special case of [12, Proof of Theorem 3.12]
given by Doležal et al. We include a short proof of the lemma for the
completeness. We remark that the lemma can also be proven following the lines
of [10, Section 5.4]. We also remark that it is necessary to require that
$t(C_{4},W_{1})=t(C_{4},W_{2})$ as can be seen by the following example. Let
$W_{1}$ be the graphon that is equal to zero on $[0,1/2]^{2}\cup[1/2,1]^{2}$
and equal to one elsewhere, and let $W_{2}$ be the graphon equal to $1/2$
everywhere (see Figure 1). Further, let $\varphi(x)=2x\mod 1$. It is easy to
check that
$d_{W_{1}}(\varphi^{-1}(J),\varphi^{-1}(J^{\prime}))=d_{W_{2}}(J,J^{\prime})=\frac{|J|\cdot|J^{\prime}|}{2}$
for all measurable subsets $J,J^{\prime}\subseteq[0,1]$, however, the graphons
$W_{1}$ and $W_{2}$ are not weakly isomorphic.

Figure 1: The graphons $W_{1}$ and $W_{2}$ from the example given before Lemma
4.

######  Lemma 4.

Let $W_{1}$ and $W_{2}$ be two graphons. Suppose that there exists a measure
preserving map $\varphi:[0,1]\to[0,1]$ such that

$d_{W_{1}}(\varphi^{-1}(J),\varphi^{-1}(J^{\prime}))=d_{W_{2}}(J,J^{\prime})$
(1)

for all measurable subsets $J,J^{\prime}\subseteq[0,1]$. If
$t(C_{4},W_{1})=t(C_{4},W_{2})$, then for almost all $(x,y)\in[0,1]^{2}$, it
holds that $W_{1}(x,y)=W_{2}(\varphi(x),\varphi(y))$.

###### Proof.

A graphon $W$ can be viewed as an operator $T_{W}$ on $L^{2}([0,1])$, the
$L^{2}$-space of functions from $[0,1]$, defined as

$T_{W}(h)(x)=\int_{[0,1]}W(x,y)h(y)\mathop{}\\!\mathrm{d}y$

for $h\in L^{2}([0,1])$. The operator $T_{W}$ is self-adjoint and compact for
any graphon $W$ [25, Section 7.5]. Moreover, it has a discrete spectrum, all
its eigenvalues $(\lambda_{i})_{i\in\mathbb{N}}$ are real and it holds [25,
Section 7.5] that

$t(C_{4},W)=\sum_{i=1}^{\infty}\lambda_{i}^{4}.$ (2)

The map $\varphi:[0,1]\to[0,1]$ naturally yields a pullback embedding
$\varphi^{*}:L^{2}([0,1])\to L^{2}([0,1])$, where
$\varphi^{*}(h)(x):=h(\varphi(x))$ for $h\in L^{2}([0,1])$. Similarly, we
define $\varphi^{*}(W)(x,y):=W(\varphi(x),\varphi(y))$ for a graphon $W$. Let
$K$ be the image of $L^{2}([0,1])$ under $\varphi^{*}$; $K$ is a subspace of
$L^{2}([0,1])$, and a standard argument shows that it is closed. Equation (1)
implies that for any $h_{1},h_{2}\in K$, we have $\langle
T_{\varphi^{*}(W_{2})}h_{1},h_{2}\rangle=\langle T_{W_{1}}h_{1},h_{2}\rangle$.
Furthermore, if $h$ is orthogonal to $K$, then $T_{\varphi^{*}(W_{2})}h=0$.
Let $\Pi_{K}$ be the orthogonal projection onto $K$. We then have that

$T_{\varphi^{*}(W_{2})}=\Pi_{K}T_{W_{1}}\Pi_{K}.$

This implies that if $(\lambda_{i})_{i\in\mathbb{N}}$ are the eigenvalues of
$T_{W_{1}}$ and $(\mu_{i})_{i\in\mathbb{N}}$ the eigenvalues of
$T_{\varphi^{*}(W_{2})}$, listed in non-increasing order according to their
absolute values, then $|\mu_{i}|\leq|\lambda_{i}|$ for every $i\in\mathbb{N}$,
and equality holds for every $i$ if and only if
$T_{\varphi^{*}(W_{2})}=T_{W_{1}}$. In particular,

$\sum_{i\in\mathbb{N}}\mu_{i}^{4}\leq\sum_{i\in\mathbb{N}}\lambda_{i}^{4},$

and equality holds if and only if $T_{\varphi^{*}(W_{2})}=T_{W_{1}}$. By
equation (2), we do indeed have equality, so
$T_{\varphi^{*}(W_{2})}=T_{W_{1}}$, and therefore $\varphi^{*}(W_{2})=W_{1}$
almost everywhere. ∎

We next state a property of weakly isomorphic graphons that we will need in
our arguments presented further in the paper. For a graphon $W$, let
$\omega(W)$ be the supremum of $|A|$ taken over all measurable sets
$A\subseteq[0,1]$ such that $W$ is equal to $1$ almost everywhere on $A\times
A$.

######  Lemma 5.

If $W$ and $W^{\prime}$ are two weakly isomorphic graphons, then
$\omega(W)=\omega(W^{\prime})$.

###### Proof.

By the results from [6] on weakly isomorphic graphons, it suffices to show
that if $W$ is a graphon and $\varphi:[0,1]\to[0,1]$ is a measure-preserving
map, then $\omega(W)=\omega(W^{\varphi})$. To show this, we use that

$\omega(W)=\sup\left\\{\|f\|_{1}\bigg{|}f\in L^{1}([0,1]),0\leq f\leq
1,\int_{[0,1]^{2}}f(x)\left(1-W(x,y)\right)f(y)\,\mbox{d}x\,\mbox{d}y=0\right\\}.$

Every function $f$ satisfying that

$\int_{[0,1]^{2}}f(x)\left(1-W(x,y)\right)f(y)\,\mbox{d}x\,\mbox{d}y=0$

also satisfies that

$\int_{[0,1]^{2}}f(\varphi(x))\left(1-W^{\varphi}(x,y)\right)f(\varphi(y))\,\mbox{d}x\,\mbox{d}y=0.$

Since it holds that $\|f(\varphi(\cdot))\|_{1}=\|f\|_{1}$, we obtain that
$\omega(W^{\varphi})\geq\omega(W)$. Conversely, if $g:[0,1]\to[0,1]$ is a
measurable function, there exists a measurable function $f:[0,1]\to[0,1]$ such
that

$\int_{A}f(x)\,\mbox{d}x=\int_{\varphi^{-1}(A)}g(x)\,\mbox{d}x$

for any measurable set $A$. Indeed, the function $f$ is the Radon-Nikodym
derivative of the pushforward measure $\varphi_{*}(\nu)$ according to the
Lebesgue measure, where the measure $\nu$ is defined as $\nu(X)=\int_{X}g$.
Note that $\|g\|_{1}=\|f\|_{1}$. Furthermore, if a function $g$ satisfies

$\int_{[0,1]^{2}}g(x)\left(1-W^{\varphi}(x,y)\right)g(y)\,\mbox{d}x\,\mbox{d}y=0,$

then the corresponding function $f$ satisfies that

$\int_{[0,1]^{2}}f(x)\left(1-W(x,y)\right)f(y)\,\mbox{d}x\,\mbox{d}y=0.$

This implies $\omega(W)\geq\omega(W^{\varphi})$, and we can conclude that
$\omega(W)=\omega(W^{\varphi})$ as desired. ∎

We close this subsection with two propositions that we need in our exposition.

######  Proposition 6.

Let $H$ be a graph on $n$ vertices. There exist connected graphs
$H_{1},\ldots,H_{k}$ with at most $n$ vertices each and a polynomial $p$ in
$k$ variables such that the following holds for every graphon $W$:

$d(H,W)=p\left(d(H_{1},W),\ldots,d(H_{k},W)\right).$

###### Proof.

We proceed by induction on the number of connected components of $H$. The base
of induction is the case that $H$ is connected, in which case we set $k=1$,
$H_{1}=H$ and $p$ to be the identity. Suppose that $H$ is not connected; let
$H^{\prime}$ be one of its components and let $H^{\prime\prime}$ be the
subgraph of $H$ induced by the vertices not in $H^{\prime}$. Further, let
$n^{\prime}$ be the number of vertices of $H^{\prime}$. Observe that

$d(H^{\prime},W)\cdot
d(H^{\prime\prime},W)=\sum_{G}\sum_{\begin{subarray}{c}A\subseteq
V(G),|A|=n^{\prime}\\\ G[A]\approx H^{\prime}\\\ G[V(G)\setminus A]\approx
H^{\prime\prime}\end{subarray}}\binom{n}{n^{\prime}}^{-1}d(G,W),$

where the sum is taken over all graphs $G$ on $n$ vertices, $G[A]\approx
H^{\prime}$ represents that the subgraph of $G$ induced by $A$ is isomorphic
to $H^{\prime}$, and $G[V(G)\setminus A]\approx H^{\prime\prime}$ represents
that the subgraph of $G$ induced by $V(G)\setminus A$ is isomorphic to
$H^{\prime\prime}$. Note that an $n$-vertex graph $G$ has a subset $A$ of
$n^{\prime}$ vertices such that $G[A]\approx H^{\prime}$ and $G[V(G)\setminus
A]\approx H^{\prime\prime}$ only if $G$ is $H$ or $G$ has fewer components
than $H$. It follows that $d(H,W)$ can be expressed as a linear combination of
$d(G,W)$, where $G$ ranges through $n$-vertex graphs with fewer components
than $H$, and $d(H^{\prime},W)\cdot d(H^{\prime\prime},W)$; the coefficients
of this linear combination do not depend on $W$. The proposition now follows.
∎

The second proposition is a well-known measure-theoretic result which we will
apply throughout the paper. It follows from the Monotone Reordering Theorem
[25, Proposition A.19] and the fact that any standard probability space is
isomorphic to the unit interval.

######  Proposition 7.

Let $X$ be a non-null measurable subset of $[0,1)$ and $h:X\to\mathbb{R}$ a
measurable function. There exists a measure-preserving map
$\varphi:X\to[0,|X|)$ and a non-decreasing function $f:[0,|X|)\to\mathbb{R}$
such that $h(x)=f(\varphi(x))$ for almost every $x\in X$.

###  2.2 Partitioned graphons and decorated constraints

The most direct way of showing that a graphon $W$ is finitely forcible is by
explicitly providing the forcing family of graphs $H_{1},\ldots,H_{m}$ and
their densities $d_{1},\ldots,d_{m}$ and analyzing all graphons $W^{\prime}$
such that $d\left(H_{i},W^{\prime}\right)=d_{i}$. However, this approach often
becomes impractical when $m$ is very large and, even more so, when
$H_{1},\dots,H_{m}$ depend on $\varepsilon$, as is required to prove Theorem
2. We now introduce the method of decorated constraints that was developed in
[15, 16], which allows us to use more advanced constraints to establish that a
graphon is finitely forcible.

A _density expression_ is a formal polynomial in graphs; i.e., graphs and real
numbers are density expressions, and if $D_{1}$ and $D_{2}$ are density
expressions, then so are $D_{1}+D_{2}$ and $D_{1}\cdot D_{2}$. A density
expression $D$ can be _evaluated_ with respect to a graphon $W$ by replacing
every graph $H$ in $D$ with $d(H,W)$. A _constraint_ is an equality between
two density expressions. A constraint is _satisfied_ by a graphon $W$ if both
density expressions evaluated with respect to $W$ are equal. A simple example
of a constraint is the equality $H=d$, which is satisfied by a graphon $W$ if
and only if $d(H,W)=d$.

If $\mathcal{C}$ is a finite set of constraints and $W$ is the unique graphon,
up to weak isomorphism, that satisfies all of the constraints in
$\mathcal{C}$, then $W$ is finitely forcible. Indeed, $W$ is the unique
graphon, up to weak isomorphism, with the density of $H$ equal to $d(H,W)$ for
all graphs $H$ appearing in a constraint in $\mathcal{C}$. We will often say
that the constraints contained in $\mathcal{C}$ _force_ the graphon $W$.

A graphon $W$ is _partitioned_ if there exist positive reals
$a_{1},\ldots,a_{k}$ summing to one and distinct reals
$d_{1},\ldots,d_{k}\in[0,1]$ such that the set $A_{i}$ of vertices of $W$ with
degree $d_{i}$ has measure $a_{i}$ for all $i\in[k]$. The sets $A_{i}$ are
called _parts_ and the _degree_ of a part $A_{i}$ is $d_{i}$. We will abuse
the notation here and if $W$ and $W^{\prime}$ are two partitioned graphons
with parts of measures $a_{i}$ and degrees $d_{i}$, we will use the same
letters to denote the corresponding parts of $W$ and $W^{\prime}$. This is
technically incorrect since the part $A_{i}$ can be a different subset of
$[0,1]$ in $W$ and $W^{\prime}$ but we will make sure that the graphon that we
have in mind is always clear from the context. The property of being a
partitioned graphon can be forced in the following sense; see [16, Lemma 2]
for a proof.

######  Lemma 8.

Let $a_{1},\ldots,a_{k}$ be positive reals summing to one and
$d_{1},\ldots,d_{k}$ distinct reals from $[0,1]$. There exists a finite set of
constraints $\mathcal{C}$ such that a graphon $W$ satisfies all constraints in
$\mathcal{C}$ if and only if $W$ is a partitioned graphon with parts of
measures $a_{1},\ldots,a_{k}$ and degrees $d_{1},\ldots,d_{k}$.

Consider a partitioned graphon $W$ and let $\mathcal{P}$ be the set of its
parts. The _relative degree_ of a vertex $x\in[0,1]$ in $W$ with respect to a
non-empty set $\mathcal{X}\subseteq\mathcal{P}$ of parts is defined as

$\deg_{W}^{\mathcal{X}}(x)=\left|\bigcup\mathcal{X}\right|^{-1}\cdot\int_{\bigcup\mathcal{X}}W(x,y)\mathop{}\\!\mathrm{d}y.$

Similarly, the _relative neighbourhood_ of $x\in[0,1]$ with respect to
$\mathcal{X}$, which is denoted by $N_{W}^{\mathcal{X}}(x)$, is the set
$N_{W}(x)\cap\bigcup\mathcal{X}$. If $\mathcal{X}=\\{X\\}$ for some part $A$,
then we simply write $\deg_{W}^{X}(x)$ and $N_{W}^{X}(x)$. As before, if the
graphon $W$ is clear from context, then we omit the subscripts. For two non-
empty subsets $\mathcal{X}_{1},\mathcal{X}_{2}\subseteq\mathcal{P}$, the
restriction of the graphon $W$ to
$\bigcup\mathcal{X}_{1}\times\bigcup\mathcal{X}_{2}$ will be referred to as
the _tile_ $\mathcal{X}_{1}\times\mathcal{X}_{2}$. If both $\mathcal{X}_{1}$
and $\mathcal{X}_{2}$ are singletons, we call the tile _simple_ ; otherwise,
it is _composite_.

We now introduce a formally stronger (but technically equivalent) version of
constraints, which we call decorated constraints. These are similar to
decorated constraints used in [9, 10, 15, 16] except that we will allow
vertices of graphs appearing in constraints to be assigned to multiple parts,
as opposed to just a single part. We discuss the difference in more detail
further. We will always have a particular set $\mathcal{P}$ of parts in mind
when working with decorated constraints. A _decorated_ graph $G$ is a graph
with $0\leq m\leq|G|$ distinguished vertices labelled from $1$ to $m$, which
are called _roots_ , and with every vertex $v$ (including the roots) assigned
a non-empty subset of $\mathcal{P}$, which is called the _decoration_ of $v$.
If the decoration of a vertex is a single element set, e.g., $\\{A\\}$, we
just write $A$ as the decoration to simplify our notation. Two decorated
graphs $G_{1}$ and $G_{2}$ are _compatible_ if the subgraphs induced by their
roots are isomorphic, respecting both the labels of roots and the decorations
assigned to them. A _decorated density expression_ is a formal polynomial in
decorated graphs such that all graphs in the expression are mutually
compatible, and a _decorated constraint_ is an equality between two decorated
density expressions such that all graphs in the expression are mutually
compatible.

Let $W$ be a partitioned graphon with parts $\mathcal{P}$ and $C$ a decorated
constraint of the form $D=0$ where $D$ is a decorated density expression. We
now describe what we mean when we say that the graphon $W$ satisfies $C$. Let
$H_{0}$ be the decorated graph induced by the roots $v_{1},\ldots,v_{m}$ of
the decorated graphs in $C$. Call an $m$-tuple
$\left(x_{1},\ldots,x_{m}\right)\in[0,1]^{m}$ _feasible_ if each $x_{i}$
belongs to one of the parts that $v_{i}$ is decorated with,
$W\left(x_{i},x_{j}\right)>0$ for every edge $v_{i}v_{j}\in
E\left(H_{0}\right)$ and $W\left(x_{i},x_{j}\right)<1$ for every non-edge
$v_{i}v_{j}\notin E\left(H_{0}\right)$. Given a feasible $m$-tuple
$\left(x_{1},\ldots,x_{m}\right)\in[0,1]^{m}$, the evaluation of $D$ at the
$m$-tuple is obtained by replacing each decorated graph $H$ with the
probability that a $W$-random graph of order $|H|$ is the graph $H$,
conditioned on the event that the roots are chosen as the vertices
$x_{1},\ldots,x_{m}$, that they induce the graph $H_{0}$, and that each non-
root vertex is chosen from the union of the parts in its decoration. The
graphon $W$ _satisfies_ the constraint $C$ if for almost every feasible
$m$-tuple, the evaluation of $D$ is equal to zero. We say that $W$ satisfies a
decorated constraint of the form $D=D^{\prime}$ if it satisfies
$D-D^{\prime}=0$.

We next describe a convention of depicting decorated constraints that we use
in this paper, which is analogous to that used in [9, 10]. The roots of
decorated graphs will be represented by squares and the non-root vertices by
circles. The decoration of every vertex will be depicted as a label inside the
square or circle. If $X$ is any letter such that $X_{1},X_{2},\ldots$ are
parts, then $X_{*}$ will denote the label $\\{X_{1},X_{2},\ldots\\}$. For
example, if $B_{1},B_{2}$ are all the parts with the letter $B$, then $B_{*}$
will refer to the label $\\{B_{1},B_{2}\\}$. The roots in all decorated graphs
appearing in a constraint will be placed on the same mutual positions; i.e.,
the corresponding roots of different graphs in the constraint are on the same
respective positions. Edges are represented as solid lines between vertices
and non-edges are represented as dashed lines. The absence of any line between
two root vertices indicates that the constraint should hold for both cases
when the edge between the root vertices is present and when it is not present.
Finally, the absence of a line between a non-root vertex and another vertex
represent the sum of decorated graphs with this edge present and without this
edge. Thus, if $k$ such lines are absent in a decorated graph, the figure
represents the sum of $2^{k}$ decorated graphs.

We now give an example of evaluating decorated constraints, which is
illustrated in Figure 2. We consider the graphon $W$ depicted in the left part
of the figure: the graphon $W$ has three parts $A$, $B_{1}$ and $B_{2}$, each
of measure $1/3$. The densities between the parts are as given in the figure.
In particular, the degree of $A$ is $2/3$, the degree of $B_{1}$ is $11/18$
and the degree of $B_{2}$ is $1$. We next consider the decorated graph $H$
depicted in the right part of Figure 2. The graph $H$ has two roots $v_{1}$
and $v_{2}$ that are adjacent and decorated with $B_{1}$ and $A$,
respectively, and it has two non-root vertices $v_{3}$ and $v_{4}$ that are
also adjacent and decorated with $\\{B_{1},B_{2}\\}$ (denoted $B_{*}$) and
$A$, respectively. The vertex $v_{3}$ is adjacent to both roots and $v_{4}$ is
adjacent only to $v_{1}$. The probability described in the previous paragraph
is independent of the choice of $x_{1}$ and $x_{2}$ in $B_{1}$ and $A$ and is
equal to $13/96$. In particular, the graphon $W$ satisfies the decorated
constraint $H=13/96$ depicted in Figure 2.

Figure 2: An example of evaluating a decorated constraint.

In [16, Lemma 3], it was shown that decorated constraints where each vertex is
decorated with a single element set are equivalent to (ordinary) constraints.
Let us call such decorated constraints _simple_ ; i.e., a decorated constraint
is simple if all decorations appearing in it are single element sets. We now
argue that each decorated constraint is equivalent to a set of simple
decorated constraints. If a decorated graph $H$ contains a non-root vertex $v$
decorated by a set of parts $\mathcal{X}$, we may replace $H$ with a convex
combination of graphs $H$ decorated by elements of $\mathcal{X}$, where the
coefficients are proportional to the measures of the parts from $\mathcal{X}$.
If one of the roots, say $v$, appearing in a decorated constraint is decorated
by a set $\mathcal{X}$, we consider all decorated constraints with $v$
labelled by elements of $\mathcal{X}$. In this way, we can convert any
decorated constraint to an equivalent set of simple decorated constraints.
Hence, we can conclude, using [16, Lemma 3], that the following holds.

######  Proposition 9.

Fix the number of parts and their sizes and degrees. For every decorated
constraint $C$, there exists a finite collection of constraints
$\mathcal{C}^{\prime}$ such that a partitioned graphon $W$ satisfies $C$ if
and only if it satisfies $\mathcal{C}^{\prime}$.

We next describe how decorated constraints can be used to embed a finitely
forcible graphon inside another graphon. Suppose that $W_{0}$ is a finitely
forcible graphon that is forced by constraints $H_{i}=d_{i}$ for $i\in[k]$,
where $H_{1},\ldots,H_{k}$ are graphs and $d_{1},\ldots,d_{k}$ are their
densities. If $W$ is a partitioned graphon and $A$ one of its parts, replacing
each $H_{i}$ with the decorated graph where each vertex is decorated with $A$
results in a set of constraints that are satisfied if and only if the
subgraphon of $W$ induced by $A$ is weakly isomorphic to $W_{0}$. The same
holds if instead of a single part $A$ we consider a set of parts. We state
this observation as a separate lemma.

######  Lemma 10.

Let $W_{0}$ be a finitely forcible graphon, $\mathcal{P}$ a set of parts and
$\mathcal{X}$ a non-empty subset of $\mathcal{P}$. There exists a finite set
$\mathcal{C}$ of decorated constraints such that every partitioned graphon $W$
with parts $\mathcal{P}$ satisfies $\mathcal{C}$ if and only if the subgraphon
of $W$ induced by $\bigcup\mathcal{X}$ is weakly isomorphic to $W_{0}$.

We conclude this subsection by stating a lemma, which appeared implicitly in
[27, proof of Lemma 2.7 or Lemma 3.3] and was explicitly stated in [9, Lemma
8].

######  Lemma 11.

Let $X,Z\subseteq\mathbb{R}$ be measurable non-null sets and let $F\colon
X\times Z\to[0,1]$ be a measurable function. If there exists a constant
$C\in\mathbb{R}$ such that

$\int_{Z}F(x,z)F(x^{\prime},z)\mathop{}\\!\mathrm{d}{z}=C$

for almost every $(x,x^{\prime})\in X^{2}$, then it holds that

$\int_{Z}F(x,z)^{2}\mathop{}\\!\mathrm{d}{z}=C$

for almost every $x\in X$.

##  3 Main Proof

In this section, we prove Theorem 2. For technical reasons, it is easier to
consider graphons as functions from $[0,1)^{2}$ rather than $[0,1]^{2}$, and
we do so throughout the section. Note that this change affects a graphon on a
set of measure zero only. In general, we refer to intervals of the type
$[a,b)$ as _half-open_ , however, we do not refer to intervals of the type
$(a,b]$ as _half-open_.

For the proof of Theorem 2, fix a graphon $W_{F}$ and $\varepsilon>0$. We can
assume that $\frac{1}{\varepsilon}-1$ is a power of two, i.e.,
$\varepsilon=\frac{1}{2^{r}+1}$ for an integer $r$, and that almost every
vertex of $W_{F}$ has degree less than one. If either assumption does not
hold, choose $\varepsilon^{\prime}<\varepsilon$ such that
$\frac{1}{\varepsilon^{\prime}}-1$ is a power of two and apply the theorem
with the graphon $W^{\prime}_{F}$ such that
$W^{\prime}_{F}(x,y)=W_{F}(\frac{1-\varepsilon^{\prime}}{1-\varepsilon}\cdot
x,\frac{1-\varepsilon^{\prime}}{1-\varepsilon}\cdot y)$ for
$(x,y)\in[0,\frac{1-\varepsilon}{1-\varepsilon^{\prime}})^{2}$ and
$W^{\prime}_{F}(x,y)=0$ elsewhere.

Set $M=4\left(\frac{1}{\varepsilon}-1\right)$ and $m=\log_{2}M$. By applying
the Monotone Reordering Theorem and, if needed, changing the graphon $W_{F}$
on a set of measure zero, we can assume that there exists a partition of
$[0,1)$ into half open intervals $Q_{1},\ldots,Q_{M}$ such that the degree of
every vertex $x$ of $W_{F}$ contained in $Q_{k}$, $k\in[M]$, belongs to the
interval $[(k-1)/M,k/M)$ and the subinterval $Q_{k}$ precedes
$Q_{k+1},\ldots,Q_{M}$ for every $k\in[M]$. Note that some of the subintervals
$Q_{k}$ can be empty.

###  3.1 Overview of $\boldsymbol{W_{0}}$W0

We next provide a description of the general structure of the graphon $W_{0}$
and present the detailed definition of individual tiles throughout this
section together with the decorated constraints enforcing its structure. We
also refer the reader to Figure 3, where the graphon $W_{0}$ is visualized,
and to Table 1, which provides references to subsections where individual
tiles are forced. The graphon $W_{0}$ is a partitioned graphon with

  * •

$M$ parts $A_{1},\ldots,A_{M}$,

  * •

$M+9$ parts $B_{A},\ldots,B_{F},B_{G_{1}},\ldots,B_{G_{M}},B_{P},B_{Q},B_{R}$,

  * •

$m+1$ parts $C_{1},\ldots,C_{m}$ and $C_{\infty}$,

  * •

$m+1$ parts $D_{1},\ldots,D_{m}$ and $D_{\infty}$,

  * •

$m$ parts $E_{1},\ldots,E_{m-1}$ and $E_{\infty}$,

  * •

$M$ parts $F_{1},\ldots,F_{M}$, and

  * •

two parts $G_{1}$ and $G_{2}$.

In total, $W_{0}$ has $3M+3m+13$ parts, and the set of the parts contained in
each of the seven groups above is denoted $A_{*},B_{*},\ldots,G_{*}$,
respectively; this notation is in line with the notation that we have
introduced for visualizing decorated constraints. The set of all $3M+3m+13$
parts of $W_{0}$ is denoted by $\mathcal{P}$, i.e., $\mathcal{P}=A_{*}\cup
B_{*}\cup\cdots\cup G_{*}$. We will also use $B_{G_{*}}$ to denote the set
containing the parts $B_{G_{1}},\ldots,B_{G_{M}}$, and $|X_{*}|$ to denote the
measure of the union of the parts contained in $X_{*}$ for
$X\in\\{A,B,\ldots,G\\}$. For some arguments that we present, it may be
convenient to think of parts contained in each of the groups as a single part.
Indeed, the parts contained in the same group serve a similar purpose.

Figure 3: A sketch of the graphon $W_{0}$. The composite tile $A_{*}\times A_{*}$ contains the graphon $W_{F}$ and the composite tile $B_{*}\times B_{*}$ contains the graphon ${\widetilde{W}}_{0}$ from Theorem 12. An enhanced sketch of the structure between the parts contained in $A_{*}$ and $B_{G*}$ and the parts contained in $C_{*}$, $D_{*}$, $E_{*}$ and $F_{*}$ is given in Figure 4.  Figure 4: A sketch of the structure of the graphon $W_{0}$ between the parts contained in $A_{*}$ and $B_{G*}$ and the parts contained in $C_{*}$, $D_{*}$, $E_{*}$ and $F_{*}$. | $A_{*}$ | $B_{*}$ | $C_{*}$ | $D_{*}$ | $E_{*}$ | $F_{*}$ | $G_{1}$ | $G_{2}$
---|---|---|---|---|---|---|---|---
$A_{*}$ | 3.8 | 3.9 | 3.7 | 3.7 | 3.5 | 3.4 | 3.9 | 3.10
$B_{*}$ | 3.9 | 3.3 | 3.7 | 3.7 | 3.5 | 3.4 | 3.9 | 3.10
$C_{*}$ | 3.7 | 3.7 | 3.6 | 3.6 | 3.5 | 3.4 | 3.9 | 3.10
$D_{*}$ | 3.7 | 3.7 | 3.6 | 3.6 | 3.5 | 3.4 | 3.9 | 3.10
$E_{*}$ | 3.5 | 3.5 | 3.5 | 3.5 | 3.5 | 3.4 | 3.9 | 3.10
$F_{*}$ | 3.4 | 3.4 | 3.4 | 3.4 | 3.4 | 3.4 | 3.9 | 3.10
$G_{1}$ | 3.9 | 3.9 | 3.9 | 3.9 | 3.9 | 3.9 | 3.9 | 3.10
$G_{2}$ | 3.10 | 3.10 | 3.10 | 3.10 | 3.10 | 3.10 | 3.10 | 3.10
Table 1: References to the subsections where the corresponding tiles are
analyzed.

We now describe the structure of the graphon $W_{0}$. Each part
$X\in\mathcal{P}$ of the graphon is a half-open subinterval of $[0,1)$ with
measure given in Table 2, and these subintervals follow the order in which
they were listed when we introduced the parts of $W_{0}$. For the rest of this
section, the subinterval of $[0,1)$ forming a part $X\in\mathcal{P}$ of
$W_{0}$ is denoted by $X^{0}$; we use $X^{0}$ solely to denote the subinterval
while we still use $X$ for the part of $W_{0}$. This allows us to clearly
distinguish the subintervals of $[0,1)$ forming the parts of $W_{0}$ from the
subsets of $[0,1)$ corresponding to the parts with the same name in other
graphons that we will consider. We will also use $A_{*}^{0},\ldots,G_{*}^{0}$
to denote the unions of the subintervals associated with the parts contained
in $A_{*},\ldots,G_{*}$, respectively.

Part | Measure | Pre-Degree
---|---|---
$A_{k}$ | $(1-\varepsilon)|Q_{k}|$ | $\frac{\varepsilon(k+1)}{4}$
$B_{G_{k}}$ | $\frac{\varepsilon}{20}\cdot\frac{1}{14}\cdot|Q_{k}|$ | $\frac{\varepsilon}{4}$
$B_{A},\ldots,B_{F},B_{P},B_{R}$ | $\frac{\varepsilon}{20}\cdot\frac{1}{14}$ | $\frac{\varepsilon}{4}$
$B_{Q}$ | $\frac{\varepsilon}{20}\cdot\frac{5}{14}$ | $\frac{\varepsilon}{4}$
$C_{k},D_{k}$ | $\frac{\varepsilon}{20}\cdot\frac{1}{2^{k}}$ | $\frac{1-\varepsilon}{2^{k-1}}+\frac{\varepsilon}{4}$
$C_{\infty},D_{\infty}$ | $\frac{\varepsilon}{20}\cdot\frac{1}{2^{m}}$ | $\frac{1-\varepsilon}{2^{m}}+\frac{\varepsilon}{4}=\frac{\varepsilon}{2}$
$E_{k}$ | $\frac{\varepsilon}{20}\cdot\frac{1}{2^{k}}$ | $\frac{1-\varepsilon}{2^{k}}+\frac{\varepsilon}{4}$
$E_{\infty}$ | $\frac{\varepsilon}{20}\cdot\frac{1}{2^{m-1}}$ | $\frac{1-\varepsilon}{2^{m}}+\frac{\varepsilon}{4}=\frac{\varepsilon}{2}$
$F_{k}$ | $\frac{\varepsilon}{20}\cdot\frac{1}{M}$ | $\frac{\varepsilon(k+1)}{4}$
$G_{1}$ | $\frac{\varepsilon}{2}$ |
$G_{2}$ | $\frac{\varepsilon}{4}$ |
Table 2: The sizes and the pre-degrees of the parts of the graphon $W_{0}$.

The graphon $W_{F}$ is contained on the composite tile $A_{*}\times A_{*}$ and
we set $W_{0}((1-\varepsilon)x,(1-\varepsilon)y)=W_{F}(x,y)$ for every
$(x,y)\in[0,1)^{2}$. In this way, the part $Q_{k}$ of the graphon $W_{F}$
corresponds to the part $A_{k}$ of the graphon $W_{0}$ for every $k\in[M]$.
The graphon $W_{0}$ outside the composite tile $A_{*}\times A_{*}$ will be
defined in the following subsections, and we use the convention that when the
value $W_{0}(x,y)$ is defined, the definition also sets the value
$W_{0}(y,x)$.

The parts contained in $B_{*}\cup\cdots\cup F_{*}$ of the graphon $W_{0}$ are
used to enforce its structure, and the parts $G_{1}$ and $G_{2}$ are used to
balance the degrees inside the parts. For each part $X\in\mathcal{P}$ except
for $G_{1}$ and $G_{2}$, we define a real number $\operatorname{pre-deg}(X)$,
which we call the _pre-degree_ of $X$. These numbers are given in Table 2. The
definition of the graphon $W_{0}$ will ensure that

$\int_{[0,1)\setminus
G_{2}^{0}}W_{0}(x,z)\mathop{}\\!\mathrm{d}{z}=\operatorname{pre-deg}(X)$ (3)

for every $x\in X^{0}$; further details are given in Subsection 3.9. We next
fix an irrational number $\delta_{X}\in(0,\varepsilon/4)$ for each part
$X\in\mathcal{P}$ such that the numbers $\delta_{X}$, $X\in\mathcal{P}$, are
rationally independent; in particular, all the numbers $\delta_{X}$,
$X\in\mathcal{P}$, are mutually distinct. The part $G_{2}$ will be used to
distinguish different parts of the graphons by guaranteeing that the degree of
each part $X\in\mathcal{P}\setminus\\{G_{1},G_{2}\\}$ is $\operatorname{pre-
deg}(X)+\delta_{X}$. The graphon $W_{0}$ is constant on each tile $X\times
G_{2}$, $X\in\mathcal{P}$, and the sole purpose of these tiles is to guarantee
that different parts have distinct degrees.

We conclude this subsection by defining a notation that will be convenient in
our exposition. Let $\mathcal{X}$ be a non-empty set of parts of $W_{0}$ and
$\mathcal{X}^{0}$ the set of corresponding half-intervals. If
$\bigcup\mathcal{X}^{0}$ is a half-open interval, we define a mapping
$\gamma_{\mathcal{X}}:[0,1)\to\bigcup\mathcal{X}^{0}$ as

$\gamma_{\mathcal{X}}(x)=x\cdot\left|\bigcup\mathcal{X}^{0}\right|+\min\bigcup\mathcal{X}^{0}\;.$
(4)

Informally speaking, $\gamma_{\mathcal{X}}$ maps the half-interval $[0,1)$ to
the half-interval $\bigcup\mathcal{X}^{0}$ linearly. For example,
$W_{0}(\gamma_{A_{*}}(x),\gamma_{A_{*}}(y))=W_{F}(x,y)$ for every
$x,y\in[0,1)$. If $\mathcal{X}=\\{X\\}$, we will just write $\gamma_{X}$
instead of $\gamma_{\\{X\\}}$.

###  3.2 Universal graphon

In this subsection, we revisit the construction of the graphon $W_{0}$ from
Theorem 1 given in [10]. In the proof of Theorem 2, we apply Theorem 1 with
the same graphon $W_{F}$ for which we are proving Theorem 2. To distinguish
the graphons $W_{0}$ from Theorems 1 and 2, we will be using
${\widetilde{W}}_{0}$ for the graphon from Theorem 1. The graphon
${\widetilde{W}}_{0}$ obtained in this way is visualized in Figure 5, and we
now review some of the properties of the graphon ${\widetilde{W}}_{0}$ and the
proof of its finite forcibility given in [10].

Figure 5: The graphon ${\widetilde{W}}_{0}$ constructed in [10].

######  Theorem 12.

The graphon ${\widetilde{W}}_{0}$ is a partitioned graphon with $10$ parts
${\widetilde{A}},\ldots,{\widetilde{G}}$, ${\widetilde{P}}$, ${\widetilde{Q}}$
and ${\widetilde{R}}$ that has the following properties in particular.

  1. (a)

The parts ${\widetilde{A}},\ldots,{\widetilde{G}}$, ${\widetilde{P}}$ and
${\widetilde{R}}$ are half-open intervals $[0/14,1/14)$, $\ldots$,
$[6/14,7/14)$, $[7/14,8/14)$ and $[13/14,14/14)$, respectively. In particular,
each of these parts has measure $1/14$.

  2. (b)

The part ${\widetilde{Q}}$ is $[8/14,13/14)$, i.e., its measure is $5/14$.

  3. (c)

It holds that

${\widetilde{W}}_{0}\left(\frac{6+x}{14},\frac{6+y}{14}\right)=W_{F}(x,y)$

for every $(x,y)\in[0,1)^{2}$, i.e., the subgraphon induced by
${\widetilde{G}}$ is $W_{F}$.

  4. (d)

It holds that

${\widetilde{W}}_{0}\left(\frac{6+x}{14},\frac{7+y}{14}\right)=W_{\Delta}(x,y)$

for every $(x,y)\in[0,1)^{2}$, where $W_{\Delta}$ is the half-graphon defined
in Section 2, i.e., the tile ${\widetilde{G}}\times{\widetilde{P}}$ is the
half-graphon.

  5. (e)

For every graphon $W$ that is weakly isomorphic to ${\widetilde{W}}_{0}$,
there exists a measure-preserving map ${\widetilde{g}}:[0,1)\to[0,1)$ such
that

$W(x,y)={\widetilde{W}}_{0}\left({\widetilde{g}}(x),{\widetilde{g}}(y)\right)$

for almost every $(x,y)\in[0,1)^{2}$.

We use the graphon ${\widetilde{W}}_{0}$ to define $W_{0}$ on the composite
tile $B_{*}\times B_{*}$ by setting

$W_{0}(\gamma_{B_{*}}(x),\gamma_{B_{*}}(y))={\widetilde{W}}_{0}(x,y)$

for every $[0,1)^{2}$. In this way, the parts
$\widetilde{A},\ldots,\widetilde{F}$, $\widetilde{P}$, $\widetilde{Q}$ and
$\widetilde{R}$ of the graphon ${\widetilde{W}}_{0}$ correspond to the parts
$B_{A},\ldots,B_{F}$, $B_{P}$, $B_{Q}$ and $B_{R}$ of the graphon $W_{0}$,
respectively, and the part $\widetilde{G}$ to the union
$B_{G_{1}}\cup\cdots\cup B_{G_{M}}$.

###  3.3 General structure of $\boldsymbol{W_{0}}$W0

In this subsection, we provide an overview of the constraints that witness the
finite forcibility of $W_{0}$, and use some of them to establish the general
structure of any graphon satisfying them. The constraints that we use are the
following:

  * •

the constraints given in Lemma 8 such that any graphon satisfying them is
partitioned graphon with parts $\mathcal{P}$ that have the same degrees and
measures as those of $W_{0}$,

  * •

the decorated constraints from Lemma 10 applied to the graphon
${\widetilde{W}}_{0}$ and with $\mathcal{X}=B_{*}$, and

  * •

the decorated constraints that we present in the current and subsequent
subsections of this section.

Suppose that $W$ is a graphon satisfying all these constraints. We will
construct a particular measure-preserving map $g:[0,1)\to[0,1)$ and prove that
$W(x,y)=W_{0}(g(x),g(y))$ for almost every $(x,y)\in[0,1)^{2}$.

We now present the construction of the map $g$. By Lemma 8, the graphon $W$ is
a partitioned graphon with parts $\mathcal{P}$ that have the same measures and
degrees as those in $W_{0}$. In the rest of the section, the subset of $[0,1)$
forming a part $X\in\mathcal{P}$ of $W$ is denoted by $X$; recall that the
half-interval forming the corresponding part in $W_{0}$ is denoted by $X^{0}$.
The Monotone Reordering Theorem implies that for each part $X\in\mathcal{P}$
there exists a measure-preserving map $\varphi_{X}:X\to[0,|X^{0}|)$ and a non-
decreasing function $f_{X}:[0,|X^{0}|)\to\mathbb{R}$ such that

$f_{X}(\varphi_{X}(x))=\deg_{W}^{F_{*}}(x)$

for almost every $x\in X$. Theorem 12 implies that there exists a measure-
preserving map ${\widetilde{g}}:B_{*}\to[0,|B_{*}|)$ such that

$W(x,y)=\widetilde{W}_{0}\left(\frac{\widetilde{g}(x)}{|B_{*}|},\frac{\widetilde{g}(y)}{|B_{*}|}\right)$

for almost every $(x,y)\in B_{*}\times B_{*}$. We next define the mapping
$g:[0,1)\to[0,1)$ as follows.

$g(x)=\left\\{\begin{array}[]{cl}\gamma_{B_{*}}({\widetilde{g}}(x)/|B_{*}|)&\mbox{if
$x$ belongs to a part contained in $B_{*}$, and}\\\
\gamma_{X}(\varphi_{X}(x)/|X|)&\mbox{if $x$ belongs to a part $X\not\in
B_{*}$}.\end{array}\right.$

Recall that our goal is to show that $W(x,y)=W_{0}(g(x),g(y))$ for almost
every $(x,y)\in[0,1)^{2}$. Note that the definition of $g$ directly implies
that $W(x,y)=W_{0}(g(x),g(y))$ for almost every $(x,y)\in B_{*}\times B_{*}$.

Figure 6: Set-decorated constraints aligning the parts contained in $B_{*}$.
The value of $X$ ranges among $A,\ldots,F,P,Q,R$, and the value of $d_{Z}$ is
equal to the degree of the part $\widetilde{Z}$ in the graphon
${\widetilde{W}}_{0}$ where $Z\in\\{A,\ldots,G,P,Q,R\\}$.

The definition of the function $g$ implies that each part $X\not\in B_{*}$ of
$W$ is mapped to the part $X^{0}$ of $W_{0}$ by $g$, however, this property is
not implied by the definition of $g$ for the parts $X\in B_{*}$. The decorated
constraints presented in Figure 6 guarantee this as we will now argue. Recall
that for almost every $x,y\in B_{*}\times B_{*}$, we have
$W(x,y)=\widetilde{W}_{0}\left(\frac{\widetilde{g}(x)}{|B_{*}|},\frac{\widetilde{g}(y)}{|B_{*}|}\right)$.
The first constraint in the figure implies that for every
$X\in\\{A,\ldots,F,P,Q,R\\}$, each vertex of the part $B_{X}$ of the graphon
$W$ belongs to the part ${\widetilde{X}}$ of the graphon
${\widetilde{W}}_{0}$, which is embedded in the composite tile $B_{*}\times
B_{*}$. Likewise, the second constraint implies that each vertex of one of the
parts of $B_{G*}$ belongs to the part ${\widetilde{G}}$ of the graphon
${\widetilde{W}}_{0}$. It follows that for each $X\in\\{A,\ldots,F,P,Q,R\\}$,
the part $B_{X}$ of $W$ is mapped by $g$ to the part $B_{X}^{0}$ of $W_{0}$,
and that $B_{G_{*}}$ is mapped to $B_{G_{*}}^{0}$. Note that we have not yet
proven that each $B_{G_{i}}$ is mapped to $B_{G_{i}}^{0}$; we will do so in
the next section.

###  3.4 Coordinate system

In this subsection, we introduce some structure of the graphon $W_{0}$ that
allows us to define a coordinate system inside most of its parts. The
arguments follow lines similar to those in [9, 10, 16, 15]. By Lemma 10, there
exist decorated constraints such that the composite tile $F_{*}\times F_{*}$
is weakly isomorphic to the half-graphon. These constraints guarantee that the
subgraphon induced by $F_{*}$ is the half-graphon, however, they do not fix
the order of the parts $F_{1},\ldots,F_{M}$ inside it. So, in addition to the
constraints given by Lemma 10, we also include the constraints depicted in
Figure 7.

Figure 7: Decorated constraints forcing the structure of some of the tiles
involving parts from $F_{*}$. The first constraint should hold for all
$i,j\in[M]$ such that $i+j\leq M$, the second for all $i,j\in[M]$ such that
$i+j\geq M+2$, and the last for all
$X\in\\{B_{A},\ldots,B_{F},B_{P},B_{Q},B_{R}\\}$.  Figure 8: Decorated
constraints forcing the structure of the rest of the tiles involving parts
from $F_{*}$. The constraints should hold for $X\in\\{A,B_{G},C,D,E\\}$. The
last constraint should hold for all $i<j$ with $i,j\in[M]$ if
$X\in\\{A,B_{G}\\}$, with $i,j\in[m]\cup\\{\infty\\}$ if $X\in\\{C,D\\}$ and
with $i,j\in[m-1]\cup\\{\infty\\}$ if $X=E$ (using the convention that
$i<\infty$ for every $i\in\mathbb{N}$).

The first constraint in Figure 7 implies that each of the tiles $F_{i}\times
F_{j}$ with $i,j\in[M]$ and $i+j\leq M$ is equal to zero almost everywhere and
the second constraint implies that each of the tiles $F_{i}\times F_{j}$ with
$i,j\in[M]$ and $i+j\geq M+2$ is equal to one almost everywhere. Since the
graphon on the composite tile $F_{*}\times F_{*}$ is weakly isomorphic to the
half-graphon by Lemma 10, the choice of $\varphi_{X}$ for $X\in F_{*}$ yields
that $W(x,y)=W_{0}(g(x),g(y))$ for almost every $(x,y)\in F_{*}\times F_{*}$.

The composite tiles $X\times F_{*}$ of $W_{0}$ are equal to zero for
$X\in\\{B_{A},\ldots,B_{F},B_{P},B_{Q},B_{R}\\}$ and this is enforced by the
last constraint Figure 7. Therefore, it holds that $W(x,y)=0=W_{0}(g(x),g(y))$
for almost every $(x,y)\in X\times F_{*}$ for
$X\in\\{B_{A},\ldots,B_{F},B_{P},B_{Q},B_{R}\\}$.

Next fix $X\in\\{A,B_{G},C,D,E\\}$. For $(x,y)\in X^{0}_{*}\times F^{0}_{*}$,
we define $W_{0}(x,y)=1$ for
$\gamma_{X_{*}}^{-1}(x)/|X_{*}|+\gamma_{F_{*}}^{-1}(y)/|F_{*}|\geq 1$, and
$W_{0}(x,y)=0$ otherwise. The first constraint in Figure 8 implies that for
almost every pair $y,y^{\prime}\in F_{*}$, either $N_{X_{*}}(y)\sqsubseteq
N_{X_{*}}(y^{\prime})$ or $N_{X_{*}}(y^{\prime})\sqsubseteq N_{X_{*}}(y)$. The
second constraint implies that $\deg^{F_{*}}(y)=\deg^{X_{*}}(y)$ for almost
every $y\in F_{*}$. It follows that the composite tile $X_{*}\times F_{*}$ is
a scaled half-graphon. The last constraint guarantees that the degrees
relative to $F_{*}$ of almost all the vertices contained in $X_{i}$ are
smaller than those in $X_{j}$ for $i<j$, i.e., the parts of $X_{*}$ are
ordered in the same way in $W$ as in $W_{0}$ according to the degrees relative
to $F_{*}$. In particular, this implies that $g$ maps the part $B_{G_{i}}$ to
the part $B^{0}_{G_{i}}$ for every $i\in[M]$. The choice of $\varphi_{X}$ for
$X\in A_{*}\cup C_{*}\cup D_{*}\cup E_{*}$ according to the Monotone
Reordering Theorem yields that $W(x,y)=W_{0}(g(x),g(y))$ for almost every
$(x,y)\in X\times F_{*}$. Finally, since $g$ maps the part $B_{G_{i}}$ to the
part $B^{0}_{G_{i}}$ for every $i\in[M]$, we also obtain that
$W(x,y)=W_{0}(g(x),g(y)))$ for almost every $(x,y)\in B_{G_{*}}\times F_{*}$.

###  3.5 Checker tiles

The _checker graphon_ $W_{C}$ is the graphon defined as follows; the graphon
is also depicted in Figure 9. Let $I_{k}$ denote the half-open interval
$\left[1-2^{-k+1},1-2^{-k}\right)$ for $k\in\mathbb{N}$. Set $W_{C}(x,y)=0$ if
$x$ and $y$ belongs to the same interval $I_{k}$ for some $k\in\mathbb{N}$,
and $W_{C}(x,y)=0$ otherwise.

Figure 9: The checker graphon $W_{C}$.

We now define the graphon $W_{0}$ on the tiles involving the parts from
$E_{*}$. Given a part $X$ in
$\\{A_{1},\ldots,A_{M},B_{G_{1}},\ldots,B_{G_{M}},C_{*},D_{*},E_{*}\\}$, set
$W_{0}(\gamma_{E_{*}}(x),\gamma_{X}(y))=W_{C}(x,y)$ for all
$(x,y)\in[0,1)^{2}$. We also set $W(x,y)=0$ for all $(x,y)\in E_{*}\times X$
where $X\in B_{*}\setminus B_{G_{*}}$.

Figure 10: The decorated constraints forcing the structure of the composite
tile $E_{*}\times E_{*}$.

We next consider the constraints depicted in Figures 10 and 11. Since the
arguments follow the lines of those presented in [10], we present them here on
a general level and refer the reader for further details to [10, Section 3.2].
The first constraint on the first line in Figure 10 implies that there exists
a collection $\mathcal{E}$ of disjoint measurable subsets of $E_{*}$ such that
the following holds for almost every $(x,y)\in E_{*}\times E_{*}$: $W(x,y)=1$
if and only if $x$ and $y$ belong to the same set of $\mathcal{E}$. The second
constraint on the first line implies that the sets in $\mathcal{E}$ are
intervals with respect to the relative degrees to $F_{*}$ of vertices in
$E_{*}$, i.e., there exists a collection $\mathcal{J}$ of disjoint
subintervals of $[0,1)$ such that the following holds for almost every
$(x,y)\in E_{*}\times E_{*}$: $W(x,y)=1$ if and only if
$\gamma_{E_{*}}^{-1}(g(x))$ and $\gamma_{E_{*}}^{-1}(g(y))$ belong to the same
$J\in\mathcal{J}$. The first constraint on the second line yields that the
length $|J|$ of each interval $J\in\mathcal{J}$, which is the value of the
left side of the expression, is equal to $1-\sup J$, which is the value of the
right side of the expression (when the two $E_{*}$-roots are mapped by
$\gamma_{E_{*}}^{-1}(g(\cdot))$ to $J$). Finally, the remaining constraint is
equivalent to saying that

$\sum_{J\in\mathcal{J}}|J|^{2}=\frac{1}{3}.$

Together with the fact that $|J|=1-\sup J$, this implies that, up to changing
each contained in $\mathcal{J}$ on a set of measure zero, $\mathcal{J}$
contains exactly the sets $I_{k}$, $k\in\mathbb{N}$, which were defined at the
beginning of this subsection. It follows that $W(x,y)=W_{0}(g(x),g(y))$ for
almost every $(x,y)\in E_{*}\times E_{*}$.

Figure 11: The decorated constraints forcing the structure of the composite
tiles $E_{*}\times X$ for
$X\in\\{A_{1},\ldots,A_{M},B_{G_{1}},\ldots,B_{G_{M}},C_{*},D_{*},E_{*}\\}$,
and $E_{*}\times Z$ for $Z\in B_{*}\setminus B_{G*}$.

Finally, we consider the constraints depicted in Figure 11. Fix $X$ to be one
of $A_{1},\ldots,A_{M}$, $B_{G_{1}},\ldots,B_{G_{M}}$, $C_{*}$, $D_{*}$ and
$E_{*}$. The first two constraints on the first line imply that there exist
disjoint measurable subsets $K_{J}\subseteq X$ such that the following holds
for almost every $(x,y)\in E_{*}\times X$: $W(x,y)=1$ if and only if there
exists $J\in\mathcal{J}$ such that $\gamma_{E*}^{-1}(g(x))\in J$ and $y\in
K_{J}$. The third constraint yields that each of these sets is an interval
with respect to the relative degrees to $F_{*}$, i.e., there exist disjoint
subintervals $L_{J}\subseteq[0,1)$ such that the following holds for almost
every $(x,y)\in E_{*}\times X$: $W(x,y)=1$ if and only if there exists
$J\in\mathcal{J}$ such that $\gamma_{E*}^{-1}(g(x))\in J$ and
$\gamma_{X}^{-1}(g(y))\in L_{J}$. Furthermore, the last constraint on the
first line implies that $|J|=|L_{J}|$ for every $J\in\mathcal{J}$.

The first constraint on the second line implies that if $J\in\mathcal{J}$
precedes $J^{\prime}\in\mathcal{J}$, then $L_{J}$ precedes $L_{J^{\prime}}$.
Hence, we conclude that $J$ and $L_{J}$ differ on a set of measure zero for
every $J\in\mathcal{J}$. It follows that $W(x,y)=W_{0}(g(x),g(y))$ for almost
every $(x,y)\in E_{*}\times X$. The last constraint in Figure 11 implies that
$W(x,y)=0=W_{0}(g(x),g(y))$ for almost every $(x,y)\in E_{*}\times Z$, $Z\in
B_{*}\setminus B_{G_{*}}$.

###  3.6 Exponential checker tiles

Figure 12: The graphons $W_{C}^{2}$ and $W_{C}^{3}$.

We next define a refined version $W_{C}^{r}$, $r\in\mathbb{N}$, of the checker
graphon. Informally speaking, we form $W_{C}^{r}$ by splitting the parts of
the checker graphon into $1,2^{r-1},2^{2(r-1)},2^{3(r-1)}$, etc. parts. So,
fix $r\in\mathbb{N}$ and define the graphon $W_{C}^{r}$ as follows:
$W_{C}^{r}(x,y)=1$ if and only if $x$ and $y$ belongs to the same interval
$I_{k}$, $k\in\mathbb{N}$, and

$\left\lfloor\frac{x-\min I_{k}}{|I_{k}|}\cdot
2^{(k-1)(r-1)}\right\rfloor=\left\lfloor\frac{y-\min I_{k}}{|I_{k}|}\cdot
2^{(k-1)(r-1)}\right\rfloor,$

and $W_{C}^{r}(x,y)=0$ otherwise. The graphons $W_{C}^{2}$ and $W_{C}^{3}$ are
depicted in Figure 12. Also note that the graphon $W_{C}^{1}$ is the checker
graphon itself. Finally, we define
$W_{0}(\gamma_{C_{*}}(x),\gamma_{C_{*}}(y))=W_{0}(\gamma_{C_{*}}(x),\gamma_{D_{*}}(y))=W_{C}^{2}(x,y)$
and $W_{0}(\gamma_{D_{*}}(x),\gamma_{D_{*}}(y))=W_{C}^{3}(x,y)$ for
$(x,y)\in[0,1)^{2}$.

Figure 13: The decorated constraints forcing the tiles $C_{*}\times C_{*}$ and
$D_{*}\times D_{*}$. The constraints on the first line should hold for
$X=C_{*}$ and $X=D_{*}$.

Consider now the decorated constraints given in Figure 13. The arguments are
similar to those presented in Subsection 3.5, so we present them briefly. Fix
$X$ to be $C_{*}$ or $D_{*}$. The constraints on the first line in Figure 13
imply that there exists a family $\mathcal{J}_{X}$ of disjoint subintervals
$[0,1)$ such that the following holds for almost every $(x,y)\in X\times X$:
$W(x,y)=1$ if $\gamma_{X}^{-1}(g(x))$ and $\gamma_{X}^{-1}(g(y))$ belong to
the same interval $J\in\mathcal{J}_{X}$, and $W(x,y)=0$ otherwise. Without
loss of generality, we can assume that all intervals in $\mathcal{J}_{X}$ are
half-open. The first constraint on the second line implies that the following
holds for almost every $x\in C_{*}$: if $\gamma_{C_{*}}^{-1}(g(x))\in I_{k}$,
$k\in\mathbb{N}$, and $\gamma_{C_{*}}^{-1}(g(x))\in J$,
$J\in\mathcal{J}_{C_{*}}$, then $|J|=2|I_{k}|^{2}=2^{-2k+1}$. It follows that
$W(x,y)=W_{0}(g(x),g(y))$ for almost every $(x,y)\in C_{*}\times C_{*}$.
Similarly, the second constraints implies that the following holds for almost
every $x\in D_{*}$: if $\gamma_{D_{*}}^{-1}(g(x))\in I_{k}$, $k\in\mathbb{N}$,
and $\gamma_{D_{*}}^{-1}(g(x))\in J$, $J\in\mathcal{J}_{D_{*}}$, then
$|J|=4|I_{k}|^{3}=2^{-3k+2}$. This yields that $W(x,y)=W_{0}(g(x),g(y))$ for
almost every $(x,y)\in D_{*}\times D_{*}$.

Figure 14: The decorated constraints forcing the structure of the composite
tile $C_{*}\times D_{*}$.

We next consider the constraints depicted in Figure 14. The two constraints on
the first line imply that there exist disjoint measurable sets $K_{J}\subseteq
D_{*}$, $J\in\mathcal{J}_{C*}$, such that the following holds for almost every
$(x,y)\in C_{*}\times D_{*}$: $W(x,y)=1$ if and only if there exists
$J\in\mathcal{J}_{C_{*}}$ such that $\gamma_{C_{*}}^{-1}(g(x))\in J$ and $y\in
K_{J}$. The first constraint on the second line implies that each $K_{J}$ is
an interval with respect to the degrees relative to $F_{*}$, i.e., there exist
disjoint subintervals $L_{J}$ of $[0,1)$, $J\in\mathcal{J}_{C_{*}}$, such that
the following holds for almost every $(x,y)\in C_{*}\times D_{*}$: $W(x,y)=1$
if there exists $J\in\mathcal{J}_{C_{*}}$ such that
$\gamma_{C_{*}}^{-1}(g(x))\in J$ and $\gamma_{D_{*}}^{-1}(g(y))\in L_{J}$, and
$W(x,y)=0$ otherwise. The second constraint on the second line yields that
$|J|=|L_{J}|$. Finally, the last constraint on the second line implies that if
$J$ precedes $J^{\prime}$, $J,J^{\prime}\in\mathcal{J}_{C_{*}}$, then $L_{J}$
precedes $L_{J^{\prime}}$. We conclude that $W(x,y)=W_{0}(g(x),g(y))$ for
almost every $(x,y)\in C_{*}\times D_{*}$.

###  3.7 Referencing dyadic squares

In this subsection, we introduce an auxiliary structure that allows us to copy
a tile $B_{G_{i}}\times B_{G_{j}}$ to a tile $A_{i}\times A_{j}$, $i,j\in[M]$.
Define $I_{s,t}$ for $s\in\mathbb{N}$ and $t\in[2^{s-1}]$ to be the half-open
interval $\left[\frac{t-1}{2^{s-1}},\frac{t}{2^{s-1}}\right)$. A half-open
interval $I_{s,t}$ for $s\in\mathbb{N}$ and $t\in[2^{s-1}]$ is a _dyadic
interval of order $s$_, and $I_{s,t}\times I_{s,t^{\prime}}$ for
$s\in\mathbb{N}$ and $t,t^{\prime}\in[2^{s-1}]$ is a _dyadic square of order
$s$_. Note that dyadic squares of order $s$ partition $[0,1)^{2}$ for every
$s\in\mathbb{N}$; see Figure 15. A tile $B_{G_{i}}\times B_{G_{j}}$ is copied
to a tile $A_{i}\times A_{j}$, $i,j\in[M]$, by ensuring that the density of
every dyadic square of the tile $A_{i}\times A_{j}$ is the same as the density
of the corresponding dyadic square of the tile $B_{G_{i}}\times B_{G_{j}}$.
The auxiliary structure that is used to achieve this is embedded in the
composite tiles $X\times C_{*}$ and $X\times D_{*}$, $X\in A_{*}\cup
B_{G_{*}}$.

Figure 15: Partitions of the square $[0,1)^{2}$ into dyadic squares of orders
$2$, $3$ and $4$.

Fix $X\in A_{*}\cup B_{G_{*}}$. Informally speaking, the structure between $X$
and $\gamma_{C_{*}}(I_{s})$ and the structure between $X$ and
$\gamma_{D_{*}}(I_{s})$ partitions $X$ into dyadic intervals of order $s$;
here, the interval $I_{s}$ is as defined in Subsection 3.5. The structure of
the tiles is illustrated in Figure 16. For every $s\in\mathbb{N}$, each dyadic
interval of order $s$ appears once between $X$ and $\gamma_{C_{*}}(I_{s})$ in
the tile $X\times C_{*}$, while it appears $2^{s-1}$ times between $X$ and
$\gamma_{D_{*}}(I_{s})$ in the tile $X\times D_{*}$. In particular,
$\gamma_{C_{*}}(I_{s})$ is split into $2^{s-1}$ parts in the same way as in
the tile $C_{*}\times C_{*}$ and $\gamma_{D_{*}}(I_{s})$ is split into
$2^{2(s-1)}$ parts in the same way as in the tile $D_{*}\times D_{*}$.
Formally, we define the tile $X\times C_{*}$ as follows. For $(x,y)\in X\times
C_{*}$, we define $W_{0}(x,y)=1$ if there exist $s\in\mathbb{N}$ and
$t\in[2^{s-1}]$ such that $\gamma^{-1}_{C_{*}}(y)\in I_{s}$,

$\frac{\gamma^{-1}_{C_{*}}(y)-\min I_{s}}{|I_{s}|}\in
I_{s,t}\quad\mbox{and}\quad\gamma^{-1}_{X}(x)\in I_{s,t}\;,$

and $W_{0}(x,y)=0$ otherwise. Similarly, for $(x,y)\in X\times D_{*}$, we
define $W_{0}(x,y)=1$ if there exist $s\in\mathbb{N}$ and $t\in[2^{s-1}]$ such
that $\gamma^{-1}_{D_{*}}(y)\in I_{s}$,

$\left(\frac{\gamma^{-1}_{D_{*}}(y)-\min I_{s}}{|I_{s}|}\cdot 2^{s-1}\mod
1\right)\in I_{s,t}\quad\mbox{and}\quad\gamma^{-1}_{X}(x)\in I_{s,t}\;,$

and $W_{0}(x,y)=0$ otherwise (in the displayed expression, $x\mod 1$ stands
for $x-\lfloor x\rfloor$). Finally, we set $W_{0}(x,y)=0$ for all $(x,y)\in
X\times(C_{*}\cup D_{*})$ where $X\in B_{*}\setminus B_{G_{*}}$.

Figure 16: The composite tiles $X\times C_{*}$ (in the left) and $X\times
D_{*}$ (in the right) for $X\in A_{*}\cup B_{G_{*}}$.
Figure 17: The decorated constraints forcing the structure of the tiles
$X\times C_{*}$ and $X\times D_{*}$ for $X\in A_{*}\cup B_{G_{*}}$. The
constraints should hold for every such $X$ and for both $(Y,Z)=(C_{*},E_{*})$
and $(Y,Z)=(D_{*},C_{*})$.

We now establish that the constraints depicted in Figure 17 force the
structure of the tiles defined in the previous paragraph. Fix $X\in A_{*}\cup
B_{G_{*}}$ and fix $(Y,Z)$ to be either $(C_{*},E_{*})$ or $(D_{*},C_{*})$.
Recall the definition of $\mathcal{J}_{C_{*}}$ and $\mathcal{J}_{D_{*}}$ from
Subsection 3.6 and, for completeness, define $\mathcal{J}_{E_{*}}$ to be
$\\{I_{s},s\in\mathbb{N}\\}$. Note that each of $\mathcal{J}_{C_{*}}$,
$\mathcal{J}_{D_{*}}$ and $\mathcal{J}_{E_{*}}$ is a partition of $[0,1)$ into
half-open intervals, $\mathcal{J}_{C_{*}}$ refines $\mathcal{J}_{E_{*}}$, and
$\mathcal{J}_{D_{*}}$ refines $\mathcal{J}_{C_{*}}$. In particular, the
partition given by $\mathcal{J}_{Y}$ refines the partition given by
$\mathcal{J}_{Z}$. The first two constraints on the first line imply that
there exists a collection of subintervals $K_{J}$ of $[0,1)$,
$J\in\mathcal{J}_{Y}$, such that the following holds for almost every
$(x,y)\in X\times Y$: $W(x,y)=1$ if there exists $J\in\mathcal{J}_{Y}$ such
that $\gamma_{Y}^{-1}(g(y))\in J$ and $\gamma_{X}^{-1}(g(x))\in K_{J}$ (note
that the interval $J$ is uniquely determined by $y$), and $W(x,y)=0$
otherwise. Also note that these two constraints do not imply that the
intervals $K_{J}$ are disjoint, and indeed, we will see further that they are
not. Suppose that $J,J^{\prime}\in\mathcal{J}_{Y}$, $J\not=J^{\prime}$, are
subintervals of the same interval contained in $\mathcal{J}_{Z}$. The third
constraint on the first line implies that $K_{J}$ and $K_{J^{\prime}}$ are
disjoint (possibly after removing a set of measure zero from each of them),
and the first constraint on the second line implies that if $J$ precedes
$J^{\prime}$, then $K_{J}$ precedes $K_{J^{\prime}}$. The final constraint
yields that $|K_{J}|=2^{-s+1}$ for every interval $J\in\mathcal{J}_{Y}$ such
that $J\sqsubseteq I_{s}$, $s\in\mathbb{N}$. However, this can only be
possible if for every interval $J_{0}\in\mathcal{J}_{Z}$, the intervals
$K_{J}$ for $J\sqsubseteq J_{0}$, $J\in\mathcal{J}_{Y}$, partition the
interval $[0,1)$ up to a set of measure zero. We conclude that
$W(x,y)=W_{0}(g(x),g(y))$ for almost every $(x,y)\in X\times Y$.

Figure 18: The decorated constraints forcing the structure of the tiles
$X\times C_{*}$ and $X\times D_{*}$ for $X\in B_{*}\setminus B_{G_{*}}$.

Finally, the two constraints depicted in Figure 18 imply that
$W(x,y)=0=W_{0}(g(x),g(y))$ for almost every $(x,y)\in X\times(C_{*}\cup
D_{*})$ where $X\in B_{*}\setminus B_{G*}$.

###  3.8 Forcing the graphon $\boldsymbol{W_{F}}$WF

In this subsection, we force that the subgraphon of $W$ induced by $A_{*}$ is
weakly isomorphic to $W_{F}$. In particular, we define
$W_{0}(\gamma_{A*}(x),\gamma_{A*}(y))=W_{F}(x,y)$ for every
$(x,y)\in[0,1)^{2}$, and argue that the constraints presented in this
subsection imply that $W(x,y)=W_{0}(g(x),g(y))$ for almost every $(x,y)\in
A_{*}\times A_{*}$.

The argument is split into two steps. First, we establish that the density of
every dyadic square of each tile $A_{i}\times A_{j}$ is the same as the
density of the corresponding dyadic square of the tile $B_{G_{i}}\times
B_{G_{j}}$, $i,j\in[M]$. This is achieved using the auxiliary structure of the
tiles involving $C_{*}$, $D_{*}$ and $E_{*}$. Recall the partitions
$\mathcal{J}_{C_{*}}$, $\mathcal{J}_{D_{*}}$ and $\mathcal{J}_{E_{*}}$ of
$[0,1)$ used earlier. Informally speaking, we use the partition given by
$\mathcal{J}_{E_{*}}$ to determine the order of the dyadic square that we are
concerned with, the partition given by $\mathcal{J}_{C_{*}}$ to determine the
row index of the dyadic square and the partition given by
$\mathcal{J}_{D_{*}}$ to determine the column index of the dyadic square.
However, even if the densities of all dyadic squares of tiles $A_{i}\times
A_{j}$ and $B_{G_{i}}\times B_{G_{j}}$ agree, it does not follow that
subgraphons induced by $A_{*}$ and $B_{G_{*}}$ are weakly isomorphic. The
partition into dyadic squares could average (hide) a finer internal structure
of the tile $A_{i}\times A_{j}$. By Lemma 4, if this were the case, then the
parameter $t(C_{4},\cdot)$, which corresponds to the non-induced density of
$C_{4}$, would be higher for the subgraphon induced by $A_{*}$ than for the
subgraphon induced by $B_{G_{*}}$, Hence, fixing the parameter
$t(C_{4},\cdot)$ together with fixing the densities of all dyadic squares
forces the subgraphons induced by $A_{*}$ and $B_{G_{*}}$ to be weakly
isomorphic. We present these arguments formally in the rest of the subsection.

Figure 19: The decorated constraints forcing the structure of the tile
$A_{*}\times A_{*}$. The first constraint should hold for all $i\in[M]$ and
$j\in[M]$.

Fix $i,j\in[M]$ and consider the first constraint in Figure 19. The constraint
implies that the following holds for almost every $x\in C_{*}$ and $y\in
D_{*}$ with $W(x,y)>0$. Let $s\in\mathbb{N}$ be the unique integer such that
$\gamma_{D_{*}}^{-1}(g(y))\in I_{s}$, and let $t,t^{\prime}\in[2^{s-1}]$ be
the unique integers such that

$\frac{\gamma_{D_{*}}^{-1}(g(y))-\min I_{s}}{|I_{s}|}\in
I_{s,t}\qquad\mbox{and}\qquad\left(\frac{\gamma_{D_{*}}^{-1}(g(y))-\min
I_{s}}{|I_{s}|}\cdot 2^{s-1}\mod 1\right)\in I_{s,t^{\prime}}\;.$

Because of the structure of the tile $C_{*}\times D_{*}$ and $W(x,y)>0$, it
follows (with the exceptions forming a set of measure zero) that

$\gamma_{C_{*}}^{-1}(g(x))\in
I_{s}\qquad\mbox{and}\qquad\frac{\gamma_{C_{*}}^{-1}(g(x))-\min
I_{s}}{|I_{s}|}\in I_{s,t}\;,$

i.e., the part of $\mathcal{J}_{C_{*}}$ that $\gamma_{C_{*}}^{-1}(g(x))$
belongs to is determined by $y$. The indices $s$, $t$ and $t^{\prime}$, which
are determined by the choice of the $C_{*}$-root and the $D_{*}$-root,
describe a dyadic square of $A_{i}\times A_{j}$. For the particular choice of
the roots $x\in C_{*}$ and $y\in D_{*}$, the left side of the constraint is
equal to

$\frac{d_{W}(g^{-1}(\gamma_{A_{i}}(I_{s,t})),g^{-1}(\gamma_{A_{j}}(I_{s,t^{\prime}})))}{|A_{i}||A_{j}|}\;,$

which corresponds to the density of the dyadic square $I_{s,t}\times
I_{s,t^{\prime}}$ inside the tile $A_{i}\times A_{j}$ ($d_{W}(\cdot,\cdot)$
was defined in Section 2). Similarly, the right side is equal to

$\frac{d_{W}(g^{-1}(\gamma_{B_{G_{i}}}(I_{s,t})),g^{-1}(\gamma_{B_{G_{j}}}(I_{s,t^{\prime}})))}{|B_{G_{i}}||B_{G_{j}}|}\;,$

which corresponds to the density of the dyadic square $I_{s,t}\times
I_{s,t^{\prime}}$ inside the tile $B_{G_{i}}\times B_{G_{j}}$. Considering all
possible choices of the roots $x\in C_{*}$ and $y\in D_{*}$, we conclude that
the following holds for all $s\in\mathbb{N}$ and $t,t^{\prime}\in[2^{s-1}]$:

$\frac{d_{W}(g^{-1}(\gamma_{A_{i}}(I_{s,t})),g^{-1}(\gamma_{A_{j}}(I_{s,t^{\prime}})))}{|A_{*}||A_{*}|}=\int_{\gamma^{-1}_{A_{*}}(\gamma_{A_{i}}(I_{s,t}))\times\gamma^{-1}_{A_{*}}(\gamma_{A_{j}}(I_{s,t^{\prime}}))}W_{F}(x,y)\mathop{}\\!\mathrm{d}{x}\mathop{}\\!\mathrm{d}{y},$

i.e., the density of any dyadic square inside the tile $A_{i}\times A_{j}$ is
equal to the desired density. Since $\gamma_{A_{*}}$ is a linear function and
any half-open subinterval of $[0,1)$ can be expressed as a countable union of
half-open intervals of the form
$\gamma^{-1}_{A_{*}}(\gamma_{A_{i}}(I_{s,t}))$, $i\in[M]$, $s\in\mathbb{N}$
and $t\in[2^{s-1}]$, we obtain that the following holds

$\frac{d_{W}(g^{-1}(\gamma_{A_{*}}(J)),g^{-1}(\gamma_{A_{*}}(J^{\prime})))}{|A_{*}||A_{*}|}=\int_{J\times
J^{\prime}}W_{F}(x,y)\mathop{}\\!\mathrm{d}{x}\mathop{}\\!\mathrm{d}{y}$ (5)

for any two two measurable subsets $J$ and $J^{\prime}$ of $[0,1)$.

Next, fix any measurable bijection $\psi:[0,1)\to A_{*}$ such that
$\psi^{-1}(X)=|X|/|A_{*}|$ for every measurable subset of $A_{*}$. Define a
graphon $W_{A}$ as $W_{A}(x,y)=W(\psi(x),\psi(y))$, i.e., $W_{A}$ is the
subgraphon of $W$ induced by $A_{*}$. Further, let
${\widetilde{g}}:[0,1)\to[0,1)$ be the map defined as
${\widetilde{g}}(x)=\gamma_{A_{*}}^{-1}(g(\psi(x)))$. Note that
${\widetilde{g}}$ is a measure-preserving map from $[0,1)$ to $[0,1)$. Using
(5), we obtain that

$d_{W_{A}}\left({\widetilde{g}}^{-1}(J),{\widetilde{g}}^{-1}(J^{\prime})\right)=d_{W_{F}}\left(J,J^{\prime}\right)$
(6)

for any two measurable subsets $J$ and $J^{\prime}$ of $[0,1)$. In addition,
the second constraint in Figure 19 yields that

$t(C_{4},W_{A})=t(C_{4},W_{F}).$ (7)

Lemma 4 now implies that
$W_{A}(x,y)=W_{F}({\widetilde{g}}(x),{\widetilde{g}}(y))$ for almost every
$(x,y)\in[0,1)^{2}$. Since it holds that
$W_{0}(\gamma_{A_{*}}(x),\gamma_{A_{*}}(y))=W_{F}(x,y)$ for every
$(x,y)\in[0,1)^{2}$, we conclude that

$W(x,y)=W_{F}(\gamma_{A_{*}}^{-1}(g(x)),\gamma_{A_{*}}^{-1}(g(y)))=W_{0}(g(x),g(y))$

for almost every $(x,y)\in A_{*}\times A_{*}$.

###  3.9 Degree balancing

We now define the graphon $W_{0}$ on the remaining tiles except for those
involving the part $G_{2}$. First, set $W_{0}(x,y)=0$ for all $(x,y)\in
A_{*}\times B_{*}$. The graphon $W_{0}$ is now defined on all tiles except for
those involving the part $G_{1}$ or $G_{2}$. Recall the definition of pre-
degrees given in Table 2. For $x\in[0,1)\setminus(G_{1}\cup G_{2})$, we define

$h(x)=\int_{[0,1)\setminus(G_{1}\cup
G_{2})}W_{0}(x,y)\mathop{}\\!\mathrm{d}y,$

and set

$W_{0}(x,y)=\frac{2}{\varepsilon}\left(\operatorname{pre-deg}(X)-h(x)\right)$

for every $(x,y)\in X^{0}\times G_{1}^{0}$,
$X\in\mathcal{P}\setminus\\{G_{1},G_{2}\\}$; we will show that
$W_{0}(x,y)\in[0,1]$ in what follows. Finally, let $\rho\in[0,1]$ be such that

$\frac{\rho\varepsilon}{2}+\sum_{X\in\mathcal{P}\setminus\\{G_{1},G_{2}\\}}\frac{2}{\varepsilon}\int_{X}\left(\operatorname{pre-
deg}(X)-h(x)\right)\mathop{}\\!\mathrm{d}x$

is a rational number, and set $W_{0}(x,y)=\rho$ for every $(x,y)\in
G_{1}^{0}\times G_{1}^{0}$. Note that the sum in the displayed expression
corresponds to the density between $G_{1}$ and all other parts except for
$G_{1}$ and $G_{2}$.

We now establish that all the values of $W_{0}$ defined in this subsection
belong to $[0,1]$ by showing that $\operatorname{pre-
deg}(X)-h(x)\in[0,\varepsilon/2]$ for every $x\in X^{0}$,
$X\in\mathcal{P}\setminus\\{G_{1},G_{2}\\}$. Since the total measure of the
parts $B_{*}$, $C_{*}$, $D_{*}$, $E_{*}$ and $F_{*}$ is $\varepsilon/4$, it is
enough to show that

$\int_{A^{0}}W_{0}(x,y)\mathop{}\\!\mathrm{d}y\in\left[\operatorname{pre-
deg}(X)-\varepsilon/2,\operatorname{pre-deg}(X)-\varepsilon/4\right]$ (8)

for every $x\in X^{0}$, $X\in\mathcal{P}\setminus\\{G_{1},G_{2}\\}$.

If $X=A^{0}_{k}$, $k\in[M]$, the value of the integral in (8) belongs to
$\left[(1-\varepsilon)\frac{k-1}{M},(1-\varepsilon)\frac{k}{M}\right]$ for
every $x\in X^{0}$ by the definition of $Q_{k}$, which was given at the
beginning of this section. Since $M=4\cdot\frac{1-\varepsilon}{\varepsilon}$,
it follows that the value of the integral belongs to the interval
$\left[\frac{(k-1)\varepsilon}{4},\frac{k\varepsilon}{4}\right]$, which
coincides with the interval on the right side of (8). Similarly, if
$X=F^{0}_{k}$, the value of the integral in (8) belongs to
$\left[(1-\varepsilon)\frac{k-1}{M},(1-\varepsilon)\frac{k}{M}\right]$ for
every $x\in X^{0}$ by the definition of $W_{0}$, and this interval again
coincides with that on the right side of (8).

If $X\in B_{*}$, then the integral in (8) is zero and (8) is also satisfied.
If $X=C^{0}_{k}$ or $X=D^{0}_{k}$, $k\in[m]$, then the integral in (8) is
equal to $\frac{1-\varepsilon}{2^{k-1}}$ for every $x\in X^{0}$ and (8) is
satisfied. If $X=E^{0}_{k}$, $k\in[m-1]$, then the integral in (8) is equal to
$\frac{1-\varepsilon}{2^{k}}$ for every $x\in X^{0}$ and (8) is again
satisfied. Finally, if
$X\in\\{C^{0}_{\infty},D^{0}_{\infty},E^{0}_{\infty}\\}$, then the integral in
(8) is at most $\frac{1-\varepsilon}{2^{m}}$, and so its value belongs to the
interval on the right side of (8).

Figure 20: The decorated constraint forcing the structure of the tile
$A_{*}\times B_{*}$.
Figure 21: The decorated constraints forcing the structure of the tiles
involving the part $G_{1}$. The first constraint should hold for every
$X\in\mathcal{P}\setminus\\{G_{1},G_{2}\\}$ and the last constraint for every
$X\in\mathcal{P}\setminus\\{G_{2}\\}$.

We now force the structure of the tiles that we have just defined. First, the
constraint in Figure 20 implies that $W(x,y)=W_{0}(g(x),g(y))=0$ for almost
every $(x,y)\in A\times B$. We now analyze the constraints depicted in Figure
21. The two constraints on the first line imply that, for every
$X\in\mathcal{P}\setminus\\{G_{2}\\}$, the integral

$\int_{X}W(x,y)W(x,y^{\prime})\mathop{}\\!\mathrm{d}x$ (9)

is the same for almost every $y,y^{\prime}\in G_{1}$ (and is equal to the
value of the corresponding integral in $W_{0}$). By Lemma 11, the integral

$\int_{X}W(x,y)^{2}\mathop{}\\!\mathrm{d}x$

is the same for almost every $y\in G_{1}$ and its value is equal to (9).
Therefore, for almost every $(y,y^{\prime})\in G_{1}^{2}$, we have that

$\int_{X}\left(W(x,y)-W(x,y^{\prime})\right)^{2}\mathop{}\\!\mathrm{d}{x}=0.$

In particular, there exists a $y^{\prime}\in G_{1}$ such that for almost every
$y\in G_{1}$,

$\int_{X}\left(W(x,y)-W(x,y^{\prime})\right)^{2}\mathop{}\\!\mathrm{d}{x}=0.$

This is equivalent to saying that $W(x,y)=W(x,y^{\prime})$ for almost all
$(x,y)\in X\times G_{1}$. Thus, there exists a function
${\widetilde{h}}:[0,1)\setminus G_{2}\to\mathbb{R}$ such that
$W(x,y)={\widetilde{h}}(x)$ for almost every $(x,y)\in([0,1)\setminus
G_{2})\times G_{1}$. The two constraints on the second line in the figure
imply that

$\int_{G_{1}}W(x,y)\mathop{}\\!\mathrm{d}y=\int_{G_{1}^{0}}W_{0}(x,g(y))\mathop{}\\!\mathrm{d}y$

for almost every $x\in[0,1)\setminus G_{2}$. We conclude that
$W(x,y)=W_{0}(g(x),g(y))$ for almost every $(x,y)\in([0,1)\setminus
G_{2})\times G_{1}$.

###  3.10 Degree distinguishing

We now finish the definition and forcing of the graphon $W_{0}$. Recall that
we fixed irrational numbers $\delta_{X}\in(0,\varepsilon/4)$ for each part
$X\in\mathcal{P}$ such that the numbers $\delta_{X}$, $X\in\mathcal{P}$, are
rationally independent. For each $X\in\mathcal{P}$, we set
$W_{0}(x,y)=\delta_{X}/|G_{2}|=4\delta_{X}/\varepsilon$ for all $(x,y)\in
X^{0}\times G^{0}_{2}$. Observe that the degree of each part
$X\in\mathcal{P}\setminus\\{G_{1},G_{2}\\}$ is equal to $\operatorname{pre-
deg}(X)+\delta_{X}$, the degree of $G_{1}$ is $r+\delta_{G_{1}}$ where $r$ is
a rational number (this follows from the choice of $\rho$), and the degree of
$G_{2}$ is a rational combination of the values $\delta_{X}$,
$X\in\mathcal{P}$ (recall that $\varepsilon$ is rational). Since the values
$\delta_{X}$, $X\in\mathcal{P}$, are rationally independent, the degrees of
all the parts are distinct.

Figure 22: The decorated constraints forcing the structure of the tiles
involving the part $G_{2}$. The constraints should hold for every
$X\in\mathcal{P}$.

Fix $X\in\mathcal{P}$ and consider the constraints depicted in Figure 22. The
first constraint yields that

$\frac{1}{|G_{2}|}\int_{G_{2}}W(x,y)\mathop{}\\!\mathrm{d}y=\delta_{X}$

for almost every $x\in X$, and the second constraint yields that

$\frac{1}{|G_{2}|}\int_{G_{2}}W(x,y)W(x^{\prime},y)\mathop{}\\!\mathrm{d}y=\delta_{X}^{2}$

for almost every $x,x^{\prime}\in X$. The latter implies by Lemma 11 that

$\frac{1}{|G_{2}|}\int_{G_{2}}W(x,y)^{2}\mathop{}\\!\mathrm{d}y=\delta_{X}^{2}$

for almost every $x\in X$. Hence, for almost every $x\in X$,

$\frac{1}{|G_{2}|}\int_{G_{2}}\left(W(x,y)-\delta_{X}\right)^{2}\mathop{}\\!\mathrm{d}y=\frac{1}{|G_{2}|}\int_{G_{2}}W(x,y)^{2}\mathop{}\\!\mathrm{d}y-\frac{2\delta_{X}}{|G_{2}|}\int_{G_{2}}W(x,y)\mathop{}\\!\mathrm{d}y+\delta_{X}^{2}=0,$

which implies that $W(x,y)=\delta_{X}=W_{0}(g(x),g(y))$ for almost every
$(x,y)\in X\times G_{2}$. This concludes the argument that
$W(x,y)=W_{0}(g(x),g(y))$ for almost every $(x,y)\in[0,1)^{2}$ and the proof
of Theorem 2 is now finished.

##  4 Sizes of Forcing Families

In this section, we show that there is no finite family $\mathcal{G}$ of
graphs such that Theorem 2 would hold for all graphons $W_{F}$ and
$\varepsilon>0$ with $\mathcal{G}$ being the forcing family. In particular,
the main result of this section is the following theorem.

######  Theorem 13.

For every positive integer $n$, there exists a graphon $W_{F}$ and a real
number $\varepsilon>0$ such that if $W$ is a finitely forcible graphon
containing $W_{F}$ as a subgraphon on at least $1-\varepsilon$ fraction of its
vertices, then every forcing family for $W$ contains a graph of order greater
than $n$.

To prove Theorem 13, we need a modification of a result of Erdős, Lovász and
Spencer [13, Lemma 5]. The proof follows the lines of the proof in [13] but we
include its sketch for completeness.

######  Lemma 14.

Let $n$ be a positive integer and let $H_{1},\ldots,H_{m}$ be all connected
graphs on at most $n$ vertices. There exist graphons $W_{1},\dots,W_{m}$ such
that the vectors

$(d(H_{1},W_{i}),\ldots,d(H_{m},W_{i})),\;i\in[m],$

are linearly independent in $\mathbb{R}^{m}$, and there is no index $i\in[m]$
and non-null set $A\subseteq[0,1]$ such that $W_{i}$ is positive almost
everywhere on $A\times A$.

###### Proof.

Fix an integer $n$ and the graphs $H_{1},\ldots,H_{m}$. Let $k_{i}$ be the
number of vertices of $H_{i}$, $i\in[m]$. For $i\in[m]$ and
$\vec{s}_{i}\in[0,1]^{k_{i}}$ such that
$\vec{s}_{i,1}+\cdots+\vec{s}_{i,k_{i}}\leq 1$, define $W_{i,\vec{s}_{i}}$ to
be the following step graphon with $k_{i}+1$ parts $S_{1},\ldots,S_{k_{i}+1}$.
The measure of the part $S_{j}$, $j\in[k_{i}]$, is $\vec{s}_{i,j}$, and the
measure of the remaining part $S_{k_{i}+1}$ is
$1-(\vec{s}_{i,1}+\cdots+\vec{s}_{i,k_{i}})$. The value of
$W_{i,\vec{s}_{i}}(x,y)$ is equal to $1$ for $(x,y)\in[0,1]^{2}$ such that
$x\in S_{j}$, $y\in S_{j^{\prime}}$ and the $j$-th and $j^{\prime}$-th
vertices of $H_{i}$ are adjacent, and it is equal to $0$ elsewhere. Note that
there does not exist a non-null set $A\subseteq[0,1]$ such that
$W_{i,\vec{s}_{i}}$ is positive almost everywhere on $A\times A$.

Let $\mathcal{S}\subseteq\mathbb{R}^{m}$ be the set of vectors that arise as
$(d(H_{j},W_{i,\vec{s}_{i}}))_{j\in[m]}$ over all choices of $i$ and
$\vec{s}_{i}$. We claim that the span of $\mathcal{S}$ is $\mathbb{R}^{m}$.
Suppose not. Then we may choose $(c_{1},\dots,c_{m})$ to be a non-zero vector
in the orthogonal complement of the span of $\mathcal{S}$. That is,
$c_{1},\dots,c_{m}$ are real numbers, not all zero, such that

$c_{1}\cdot d(H_{1},W_{i,\vec{s}_{i}})+\cdots+c_{m}\cdot
d(H_{m},W_{i,\vec{s}_{i}})=0$ (10)

for every $i\in[m]$ and $\vec{s}_{i}\in[0,1]^{k_{i}}$ such that
$\vec{s}_{i,1}+\cdots+\vec{s}_{i,k_{i}}\leq 1$. Take $i$ such that $c_{i}\neq
0$. The left side of (10) is a polynomial in
$\vec{s}_{i,1},\ldots,\vec{s}_{i,k_{i}}$. Observe that the only term that
contributes to the coefficient of the monomial
$\vec{s}_{i,1}\cdots\vec{s}_{i,k_{i}}$ is the term
$c_{i}d(H_{i},W_{i,\vec{s}_{i}})$. It follows that the left side of (10) is
polynomial that is not identically zero, which implies that the equality (10)
cannot hold for all choices of $\vec{s}_{i}\in[0,1]^{k_{i}}$. Thus, the span
of $\mathcal{S}$ is $\mathbb{R}^{m}$, and so we can choose $m$ linearly
independent vectors from $\mathcal{S}$. The corresponding graphons can be
taken as $W_{i}$. ∎

We are now ready to prove Theorem 13.

###### Proof of Theorem 13.

Fix an integer $n$. Note that Proposition 6 yields that the densities of all
subgraphs on at most $n$ vertices are determined by the densities of connected
subgraphs on at most $n$ vertices. Therefore, to prove the theorem, it is
enough to show the following: there exists a graphon $W_{F}$ and a real number
$\varepsilon>0$ such that no graphon $W$ that contains $W_{F}$ as a subgraphon
on at least $1-\varepsilon$ fraction of its vertices is a finitely forcible
graphon such that the set of all _connected_ graphs with at most $n$ vertices
is a forcing family. Let $H_{1},\ldots,H_{m}$ be all connected graphs with the
number of vertices between two and $n$, and let $k_{i}$ be the number of
vertices of $H_{i}$, $i\in[m]$.

Let $W_{1},\dots,W_{m}$ be the graphons from Lemma 14. In addition, let
$W_{m+1}$ be the graphon equal to one everywhere. We define $W_{F}(x,y)$ to be
equal to

$W_{i}((m+2)x-(i-1),(m+2)y-(i-1))\qquad\mbox{if
$(x,y)\in\left[\frac{i-1}{m+2},\frac{i}{m+2}\right)^{2}$ for $i\in[m+1]$,
and}$

equal to $0$ otherwise. In other words, $W_{F}$ contains each of the graphons
$W_{1},\ldots,W_{m+1}$ on a $\frac{1}{m+2}$ fraction of its vertices, and it
is zero elsewhere.

We next define a $m\times m$ square matrix $A^{\delta}$ for $\delta\in(0,1)$
as

$A^{\delta}_{ij}=(1-\delta)^{k_{i}}k_{i}\left(\frac{1}{m+2}\right)^{\;k_{i}-1}d(H_{i},W_{j})\mbox{
for }i,j\in[m].$

The matrix $A^{\delta}$ is invertible since multiplying each row by
$(1-\delta)^{-k_{i}}k_{i}^{-1}\left(\frac{1}{m+2}\right)^{-(k_{i}-1)}$ results
in the matrix that has $d(H_{i},W_{j})$ as the entry in the $i$-th row and
$j$-th column. Hence, there exists $\varepsilon_{0}$ such that any matrix
obtained from $A^{\delta}$ for $\delta\in(0,\varepsilon_{0})$ by perturbing
each of its entries by at most $\varepsilon_{0}$ is invertible. We now set
$\varepsilon=\min\left\\{\frac{\varepsilon_{0}}{(m+3)^{n}n},\frac{1}{m+4}\right\\}$.

Suppose that $W$ is a graphon that contains $W_{F}$ on a
$1-\varepsilon^{\prime}$ fraction of its vertices for some
$\varepsilon^{\prime}\leq\varepsilon$. By applying a suitable measure
preserving transformation, we can assume that the subgraphon of $W$ on
$\left[\frac{i-1}{m+2}(1-\varepsilon^{\prime}),\frac{i}{m+2}(1-\varepsilon^{\prime})\right)^{2}$
is weakly isomorphic to $W_{i}$ for every $i\in[m+1]$, and the graphon $W$ is
zero almost everywhere else on $[0,1-\varepsilon^{\prime})^{2}$. Consider a
vector $\vec{s}\in\left[0,\frac{1}{m+1}\right)^{m+1}$, and let
$t_{0},\ldots,t_{m+2}\in[0,1]$ be such that $t_{0}=0$,
$t_{i}=t_{i-1}+\vec{s}_{i}$ for $i\in[m+1]$, and $t_{m+2}=1$. Define a
function $\varphi_{\vec{s}}:[0,1]\to[0,1]$ as follows:

$\varphi_{\vec{s}}(x)=\begin{cases}\frac{(i-1)(1-\varepsilon^{\prime})}{m+2}+\frac{x-t_{i-1}(1-\varepsilon^{\prime})}{(m+2)(t_{i}-t_{i-1})}&\mbox{if
$x\in[t_{i-1}(1-\varepsilon^{\prime}),t_{i}(1-\varepsilon^{\prime}))$ for
$i\in[m+2]$, and}\\\ x&\mbox{otherwise.}\end{cases}$

Finally, define the graphon $W_{\vec{s}}$ as
$W_{\vec{s}}(x,y)=W(\varphi_{\vec{s}}(x),\varphi_{\vec{s}}(y))$. Informally
speaking, the part of $W$ containing $W_{i}$ is stretched to size
$\vec{s}_{i}(1-\varepsilon^{\prime})$ for every $i\in[m+1]$. In particular,
the graphons $W$ and $W_{\frac{1}{m+2},\ldots,\frac{1}{m+2}}$ are the same.

We now analyze $d(H_{i},W_{\vec{s}})$ as a function of
$\vec{s}_{1},\ldots,\vec{s}_{m+1}$. Each of the $k_{i}$ vertices of $H_{i}$
can be chosen either from one of the $m+2$ intervals
$[t_{i-1}(1-\varepsilon^{\prime}),t_{i}(1-\varepsilon^{\prime}))$,
$i\in[m+2]$, or from the interval $[1-\varepsilon^{\prime},1]$, i.e., there
are $(m+3)^{k_{i}}$ ways how individual vertices of $H_{i}$ can be chosen from
these $m+3$ intervals. Since $H_{i}$ is connected, the choices where no vertex
of $H_{i}$ is chosen to be in the interval $[1-\varepsilon^{\prime},1]$
contribute to $d(H_{i},W_{\vec{s}})$ by a total of

$\sum_{j=1}^{m+1}((1-\varepsilon^{\prime})\vec{s}_{j})^{\;k_{i}}d(H_{i},W_{j}).$

We next analyze contributions of the choices where at least one of the
vertices of $H_{i}$ is chosen from the interval $[1-\varepsilon^{\prime},1]$.
Consider a choice where $\ell\geq 1$ vertices are mapped to the interval
$[1-\varepsilon^{\prime},1]$. For this choice, the contribution is a product
of a constant between $0$ and $1$, the $\ell$-th power of
$\varepsilon^{\prime}$ and $k_{i}-\ell$ factors of the form
$\vec{s}_{1},\vec{s}_{2},\ldots,\vec{s}_{m+1}$, and
$(1-\vec{s}_{1}-\vec{s}_{2}-\ldots-\vec{s}_{m+1})$; the constant is the
probability that a $W$-random graph is $H_{i}$ conditioned on the vertices
being sampled from the chosen intervals. Since the absolute value of the
derivative of the product of the $k_{i}-\ell$ factors with respect to
$\vec{s}_{j}$ is at most $k_{i}-\ell$ and the product of the remaining factors
is a constant, which is at most $\varepsilon^{\prime}$, the contribution to
the derivative of $d(H_{i},W)$ with respect to $\vec{s}_{j}$ is at most
$k_{i}\varepsilon^{\prime}$. This holds for each such choice of intervals for
the vertices of $H_{i}$. It follows that the derivative of $d(H_{i},W)$ with
respect to $\vec{s}_{j}$ is between

$(1-\varepsilon^{\prime})^{k_{i}}k_{i}\vec{s}_{j}^{\;k_{i}-1}d(H_{i},W_{j})-(m+3)^{k_{i}}k_{i}\varepsilon^{\prime}\mbox{
and
}(1-\varepsilon^{\prime})^{k_{i}}k_{i}\vec{s}_{j}^{\;k_{i}-1}d(H_{i},W_{j})+(m+3)^{k_{i}}k_{i}\varepsilon^{\prime}\mbox{.}$

Observe that there is an open ball contained in
$\left(0,\frac{1}{m+1}\right)^{m+1}$ that contains the point
$\vec{s}=\left(\frac{1}{m+2},\ldots,\frac{1}{m+2}\right)$ such that each
$d(H_{i},W_{\vec{s}})$, $i\in[m]$, is well-defined on this ball. Also observe
that the entries of the Jacobian matrix $\left(\frac{\partial
d(H_{i},W_{\vec{s}})}{\partial\vec{s}_{j}}\right)_{i,j\in[m]}$ for
$\vec{s}=\left(\frac{1}{m+2},\ldots,\frac{1}{m+2}\right)$ differ from the
entries of $A^{\varepsilon^{\prime}}$ by at most
$(m+3)^{k_{i}}k_{i}\varepsilon^{\prime}\leq(m+3)^{n}n\varepsilon\leq\varepsilon_{0}$.
In particular, the Jacobian matrix is invertible. Hence, the Implicit Function
Theorem implies that there exist
$\delta\in\left(0,\frac{1}{m+1}-\frac{1}{m+2}\right)$ and a continuous
function
$g\colon\left(\frac{1}{m+2}-\delta,\frac{1}{m+2}+\delta\right)\to\left(0,\frac{1}{m+1}\right)^{m}$
such that
$g\left(\frac{1}{m+2}\right)=\left(\frac{1}{m+2},\ldots,\frac{1}{m+2}\right)$
and

$d(H_{i},W)=d(H_{i},W_{(g(z)_{1},\ldots,g(z)_{m},z)})$

for every $z\in\left(\frac{1}{m+2}-\delta,\frac{1}{m+2}+\delta\right)$. Fix
$z\in\left(\frac{1}{m+2},\frac{1}{m+2}+\delta\right)\subseteq\left(0,\frac{1}{m+1}\right)$.
We set $W^{\prime}=W_{(g(z)_{1},\ldots,g(z)_{m},z)}$. Observe that the
densities of all graphs $H_{1},\ldots,H_{m}$ are the same in $W$ and
$W^{\prime}$ by the choice of $g$ and $z$.

We finish the proof by establishing that the graphons $W$ and $W^{\prime}$ are
not weakly isomorphic. By Lemma 5, it suffices to show that
$\omega(W)<\omega(W^{\prime})$. Note that
$\omega(W)\geq\frac{1-\varepsilon^{\prime}}{m+2}$, which can be seen by
considering the interval
$[\frac{m}{m+2}(1-\varepsilon^{\prime}),\frac{m+1}{m+2}(1-\varepsilon^{\prime}))$.
Let $X$ be any measurable set $X\subseteq[0,1]$ such that $W$ is equal to $1$
almost everywhere on $X\times X$ and
$|X|\geq\frac{1-\varepsilon^{\prime}}{m+2}$. We construct a measurable set
$X^{\prime}\subseteq[0,1]$ such that $|X^{\prime}|>|X|$ and $W^{\prime}$ is
equal to $1$ almost everywhere on $X^{\prime}\times X^{\prime}$.

Define $X_{1}=X\cap[0,1-\varepsilon^{\prime})$ and
$X_{2}=X\cap[1-\varepsilon^{\prime},1]$. Observe that
$X_{1}\sqsubseteq\left[\frac{m}{m+2}(1-\varepsilon^{\prime}),\frac{m+1}{m+2}(1-\varepsilon^{\prime})\right)$
by the second assertion of Lemma 14 and that
$|X_{2}|\leq\varepsilon^{\prime}\leq\varepsilon\leq\frac{1}{m+4}$. This
implies that

$|X_{1}|\geq\frac{1-\varepsilon^{\prime}}{m+2}-\varepsilon^{\prime}=\frac{1-(m+3)\varepsilon^{\prime}}{(m+2)}\geq\frac{1}{(m+2)(m+4)}.$

Since the interval
$\left[\frac{m}{m+2}(1-\varepsilon^{\prime}),\frac{m+1}{m+2}(1-\varepsilon^{\prime})\right)$
is stretched to an interval of size
$z(1-\varepsilon^{\prime})>\frac{1}{m+2}(1-\varepsilon^{\prime})$ in
$W^{\prime}$, we obtain that

$\omega(W^{\prime})\geq
z(m+2)|X_{1}|+|X_{2}|=|X|+(z(m+2)-1)|X_{1}|\geq|X|+\frac{z(m+2)-1}{(m+2)(m+4)}.$

Since the choice of $X$ was arbitrary, it follows that

$\omega(W^{\prime})\geq\omega(W)+\frac{z(m+2)-1}{(m+2)(m+4)}>\omega(W)$

and we conclude that the graphons $W$ and $W^{\prime}$ are not weakly
isomorphic. ∎

We would like to remark that Theorem 13 excludes the existence of a finite
family $\mathcal{G}$ of graphs such that for every graphon $W_{F}$ and every
$\varepsilon>0$, there exists a finitely forcible graphon $W_{0}$ that
contains $W_{F}$ as subgraphon on a $1-\varepsilon$ fraction of its vertices,
and $\mathcal{G}$ is a forcing family for $W_{0}$. In other words, Theorem 2
cannot be proven with a universal forcing family (unlike Theorem 1). However,
we were not able to show that the number of graphs needed to force the
structure of graphons containing $W_{F}$ must grow with $\varepsilon^{-1}$,
i.e., we do not know whether the following stronger statement is true: for
every $K\in\mathbb{N}$, there exist a graphon $W_{F}$ and $\varepsilon>0$ such
that if $W_{0}$ is a finitely forcible graphon that contains $W_{F}$ as a
subgraphon on a $1-\varepsilon$ fraction of its vertices, then every forcing
family of $W_{0}$ contains at least $K$ graphs.

## Acknowledgment

We would like to thank Jan Hladký for useful discussions on the step forcing
property of $C_{4}$, in particular, the arguments used at the end of
Subsection 3.8. We would also like to thank the authors of [12] for sharing an
early version of their manuscript.

## References

  * [1] R. Baber: Turán densities of hypercubes, available as arXiv:1201.3587.
  * [2] R. Baber and J. Talbot: A solution to the $2/3$ conjecture, SIAM J. Discrete Math. 28 (2014), 756–766.
  * [3] R. Baber and J. Talbot: Hypergraphs do jump, Combin. Probab. Comput. 20 (2011), 161–171.
  * [4] J. Balogh, P. Hu, B. Lidický and H. Liu: Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube, European J. Combin. 35 (2014), 75–85.
  * [5] J. Balogh, P. Hu, B. Lidický and F. Pfender: Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle, European J. Combin. 52 (2016), 47–58.
  * [6] C. Borgs, J.T. Chayes and L. Lovász: Moments of two-variable functions and the uniqueness of graph limits, Geom. Funct. Anal. 19 (2010), 1597–1619.
  * [7] F.R.K. Chung, R.L. Graham and R.M. Wilson: Quasi-random graphs, Combinatorica 9 (1989), 345–362.
  * [8] D. Conlon and J. Fox: Bounds for graph regularity and removal lemmas, Geom. Funct. Anal. 22 (2012), 1191–1256.
  * [9] J. W. Cooper, T. Kaiser, D. Král’ and J. A. Noel: Weak regularity and finitely forcible graph limits, Trans. Amer. Math. Soc. 370 (2018), 3833–3864.
  * [10] J. W. Cooper, D. Král’, T. L. Martins: Finitely forcible graph limits are universal, Adv. Math. 340 (2018), 819–854.
  * [11] P. Diaconis, S. Holmes and S. Janson: Threshold graph limits and random threshold graphs, Internet Math. 5 (2009), 267–318.
  * [12] M. Doležal, J. Grebík, J. Hladký, I. Rocha and V. Rozhoň: Cut distance identifying graphon parameters over weak* limits, available as arXiv:1809.03797.
  * [13] P. Erdős, L. Lovász and J. Spencer: Strong independence of graphcopy functions, In Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977), Academic Press, New York-London (1979), 165–172.
  * [14] A. Frieze and R. Kannan: Quick approximation to matrices and applications, Combinatorica 19 (1999), 175–220.
  * [15] R. Glebov, T. Klimošová and D. Král’: Infinite dimensional finitely forcible graphon, P. Lond. Math. Soc. 118 (2019), 826–856.
  * [16] R. Glebov, D. Král’ and J. Volec: Compactness and finite forcibility of graphons, J. Eur. Math. Soc. 21 (2019), 3199–3223.
  * [17] A. Grzesik: On the maximum number of five-cycles in a triangle-free graph, J. Combin. Theory Ser. B 102 (2012), 1061–1066.
  * [18] A. Grzesik, D. Král and L. M. Lovász: Elusive extremal graphs, available as arXiv:1807.01141.
  * [19] H. Hatami, J. Hladký, D. Král’, S. Norine and A. Razborov: Non-three-colorable common graphs exist, Combin. Probab. Comput. 21 (2012), 734–742.
  * [20] H. Hatami, J. Hladký, D. Král’, S. Norine and A. Razborov: On the number of pentagons in triangle-free graphs, J. Combin. Theory Ser. A 120 (2013), 722–732.
  * [21] D. Král’, C.-H. Liu, J.-S. Sereni, P. Whalen and Z. Yilma: A new bound for the 2/3 conjecture, Combin. Probab. Comput. 22 (2013), 384–393.
  * [22] D. Král’, L. Mach and J.-S. Sereni: A new lower bound based on Gromov’s method of selecting heavily covered points, Discrete Comput. Geom. 48 (2012), 487–498.
  * [23] L. Lovász: Graph homomorphisms: Open problems, unpublished manuscript, 2008, available as http://www.cs.elte.hu/~lovasz/problems.pdf.
  * [24] L. Lovász: Very large graphs, Curr. Dev. Math. 2008 (2009), 67–128.
  * [25] L. Lovász: Large networks and graph limits, AMS, Providence, RI, 2012.
  * [26] L. Lovász and V.T. Sós: Generalized quasirandom graphs, J. Combin. Theory Ser. B 98 (2008), 146–163.
  * [27] L. Lovász and B. Szegedy: Finitely forcible graphons, J. Combin. Theory Ser. B 101 (2011), 269–301.
  * [28] L. Lovász and B. Szegedy: Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), 933–957.
  * [29] L. Lovász and B. Szegedy: Testing properties of graphs and functions, Israel J. Math. 178 (2010), 113–156.
  * [30] O. Pikhurko and A. Razborov: Asymptotic structure of graphs with the minimum number of triangles, Combin. Probab. Comput. 26 (2017), 138–160.
  * [31] O. Pikhurko and E.R. Vaughan: Minimum number of k-cliques in graphs with bounded independence number, Combin. Probab. Comput. 22 (2013), 910–934.
  * [32] A. Razborov: Flag algebras, J. Symbolic Logic 72 (2007), 1239–1282.
  * [33] A. Razborov: On 3-hypergraphs with forbidden 4-vertex configurations, SIAM J. Discrete Math. 24 (2010), 946–963.
  * [34] A. Razborov: On the minimal density of triangles in graphs, Combin. Probab. Comput. 17 (2008), 603–618.
  * [35] A. Thomason: Pseudo-random graphs, Ann. Discrete Math. 33 (1987), 307–331.

[dan] Daniel Král’
Faculty of Informatics
Masaryk University
Brno, Czech Republic
dkralfimunicz
http://fi.muni.cz/ dkral [laci] László M. Lovász
Department of Mathematics
Massachusetts Institute of Technology
Cambridge, MA, USA
lmlovaszmitedu
http://math.mit.edu/ lmlovasz/ [jon] Jonathan A. Noel
Mathematics Institute
University of Warwick
Coventry, UK
jnoelwarwickacuk
http://homepages.warwick.ac.uk/staff/J.Noel [kuba] Jakub Sosnovec
NXP semiconductors
Brno, Czech Republic
jsosnovecemailcz
http://sites.google.com/site/jsosnovec1