# Prominent examples of flip processes

Pedro Araújo  ,  Jan Hladký  ,  Eng Keat Hng  and  Matas Šileikis
<EMAIL_ADDRESS>Institute of Computer Science of the Czech
Academy of Sciences, Pod Vodárenskou věží 2, 182 07, Praha 8, Czechia.

###### Abstract.

Flip processes, introduced in [_Garbe, Hladký, Šileikis, Skerman: From flip
processes to dynamical systems on graphons_], are a class of random graph
processes defined using a _rule_ which is just a function
$\mathcal{R}:\mathcal{H}_{k}\rightarrow\mathcal{H}_{k}$ from all labelled
graphs of a fixed order $k$ into itself. The process starts with an arbitrary
given $n$-vertex graph $G_{0}$. In each step, the graph $G_{i}$ is obtained by
sampling $k$ random vertices $v_{1},\ldots,v_{k}$ of $G_{i-1}$ and replacing
the induced graph $G_{i-1}[v_{1},\ldots,v_{k}]$ by
$\mathcal{R}(G_{i-1}[v_{1},\ldots,v_{k}])$.

Using the formalism of dynamical systems on graphons associated to each such
flip process from _ibid._ we study several specific flip processes, including
the triangle removal flip process and its generalizations, ‘extremist flip
processes’ (in which $\mathcal{R}(H)$ is either a clique or an independent
set, depending on whether $e(H)$ has less or more than half of all potential
edges), and ‘ignorant flip processes’ in which the output $\mathcal{R}(H)$
does not depend on $H$.

With institutional support RVO:67985807. JH and EKH were supported by the
Czech Science Foundation, grant number 21-21762X; PA and MŠ were supported by
the Czech Science Foundation, grant number 20-27757Y

###### Contents

  1. 1 Introduction
    1. 1.1 Random graph processes
    2. 1.2 Flip processes, basics
    3. 1.3 Flip processes, going back in time
    4. 1.4 Flip processes, destinations
    5. 1.5 Our results
      1. 1.5.1 Ignorant flip processes (Section 4)
      2. 1.5.2 Stirring flip processes (Section 5)
      3. 1.5.3 Complementing flip processes (Section 6)
      4. 1.5.4 Extremist flip processes (Section 7)
      5. 1.5.5 Monotone flip processes (Section 8)
      6. 1.5.6 Component completion flip processes (Section 9)
      7. 1.5.7 Removal flip processes (Section 10)
      8. 1.5.8 Quadratically many steps and beyond
  2. 2 Definitions and basics
    1. 2.1 Differential equations
      1. 2.1.1 Grönwall’s inequality
      2. 2.1.2 On notation of integrals
      3. 2.1.3 Differential equations in Banach spaces
    2. 2.2 Graphons
      1. 2.2.1 Densities and degrees
      2. 2.2.2 Sampling
      3. 2.2.3 Regularity lemma
      4. 2.2.4 Inequality between clique densities
    3. 2.3 Probability
  3. 3 Flip processes as dynamical systems on graphons: a recap
    1. 3.1 The velocity operator
    2. 3.2 Trajectories
    3. 3.3 Continuity properties of trajectories
    4. 3.4 Destinations and speed of convergence
  4. 4 Ignorant flip processes
  5. 5 Stirring flip processes
    1. 5.1 Age of a balanced stirring process
  6. 6 Complementing flip processes
  7. 7 Extremist flip processes
    1. 7.1 Behaviour on constants
    2. 7.2 Density thresholds
    3. 7.3 Trajectory rescaling for large $k$
    4. 7.4 Stabilization in an extremist flip process
  8. 8 Monotone flip processes
  9. 9 Component completion flip processes
  10. 10 Removal flip processes
    1. 10.1 Destination of a limit
    2. 10.2 Speed of removal flip processes
    3. 10.3 Graphons with the same destination
    4. 10.4 Stabilization in a removal flip process

##  1\. Introduction

###  1.1. Random graph processes

Graphs are among the most universal structures, and they have therefore served
as mathematical models in many settings. It is often the case that these
settings evolve in time according to a stochastic rule. A variety of random
graph processes have been introduced and studied extensively to this end. Most
of these processes are defined so that they start with a specific initial
graph on vertex set $[n]$ (for each $n\in\mathbb{N}$), and this vertex set
remains unchanged. Further, it is usually asymptotic properties as $n$ tends
to infinity which are investigated. Let us give some examples. The simplest
such process is the _Erdős–Rényi graph process_ , introduced in the seminal
paper [8] of Erdős and Rényi in 1960. The process starts with the edgeless
graph $G_{0}$ on $[n]$. In each step $t=1,\ldots,\binom{n}{2}$, the graph
$G_{t}$ is obtained by taking $G_{t-1}$ and turning a uniformly random non-
edge into an edge. Obviously, the graph $G_{\binom{n}{2}}$ is complete.
Another process introduced by Bollobás and Erdős at a “conference in
Fairbanks, Alaska, in 1990, while admiring the playful bears” [6], is the
_triangle removal process_. The process starts with the complete graph $G_{0}$
on $[n]$. In each step $t=1,2,\ldots$, the graph $G_{t}$ is obtained by taking
$G_{t-1}$, choosing a randomly selected triangle (uniformly among the set of
all triangles in $G_{t-1}$), and erasing its three edges. The process stops at
the (random) time when $G_{t}$ is triangle free. A major question raised
already by Bollobás and Erdős in 1990 was what the number of edges of the
final graph $G_{t}$ is. This has been a subject of a long line of research,
culminating in [3] which establishes that $e(G_{t})=n^{3/2+o(1)}$. General
$H$-removal processes were studied much less, mostly motivated by extending
the setting of the Erdős–Hanani conjecture resolved in [25], see e.g. [22,
26]. A process which looks like a dual process in many aspects is the
following one, called the _$H$ -free process_. Let $H$ be a fixed graph. We
start with the edgeless graph $G_{0}$. In each step $t$ we select, uniformly
at random, a non-edge whose addition to $G_{t-1}$ does not create a copy of
$H$, and turn it into an edge. Hence, when the process stops, $G_{t}$ is a
maximal $H$-free graph. The case $H=K_{3}$ is now well understood due to
analyses by Bohman and Keevash [5] and Fiz Pontiveros, Griffiths, and Morris
[10]. In particular, these results imply the currently best known lower bound
for the off-diagonal Ramsey number $R(3,k)$. Among the numerous further papers
studying the triangle-free process and other $H$-free processes, let us
highlight [21, 4, 28]. The last class of processes we mention before turning
to the main subject of this paper are the _Achlioptas processes_ , introduced
in [1]. We start with the edgeless graph on $[n]$. In each step we select
$k=2$ random non-edges (natural generalizations for larger $k$ exist)
$f_{1}=x_{1}y_{1}$ and $f_{2}=x_{2}y_{2}$. Then, we choose one of them to add
into the graph according to a predetermined rule. For example, the so-called
‘product rule’ selects the non-edge $f_{i}$ which minimizes the product of the
sizes of the connected components to which $x_{i}$ and $y_{i}$ belong. Indeed,
the motivation behind many Achlioptas rules was to alter the time of the
emergence of the giant component. See, e.g. [23, 24], for more on Achlioptas
processes.

Let us note that an obvious generalization of the processes above would be to
start them from graphs other than the complete or the edgeless one. It seems
that the reason such generalizations were not studied was that it was not
clear what the observed features should be.

###  1.2. Flip processes, basics

In [12], the following general class of random graph processes was introduced.
Let $k\in\mathbb{N}$ be given and let $\mathcal{H}_{k}$ be the set of all
graphs on the vertex set $[k]$. Let
$\mathcal{R}\in[0,1]^{\mathcal{H}_{k}\times\mathcal{H}_{k}}$ be a matrix which
is stochastic, that is, for every $F\in\mathcal{H}_{k}$ we have
$\sum_{H\in\mathcal{H}_{k}}\mathcal{R}_{F,H}=1$. We call $k$ the _order_ and
$\mathcal{R}$ the _rule_ of the flip process. Given $\mathcal{R}$, an integer
$n\geq k$ and an _initial graph_ $G_{0}$ with vertex set $[n]$, the
corresponding _flip process_ proceeds as follows. For each $t\in\mathbb{N}$,
we sample uniformly at random an ordered tuple
$\mathbf{v}=(v_{1},\cdots,v_{k})$ of distinct vertices in $[n]$. Let
$F\in\mathcal{H}_{k}$ be the _drawn graph_ , that is, the graph on $[k]$ such
that $ij\in E(F)$ if and only if $v_{i}v_{j}\in G_{t-1}$. Next, we sample a
graph $H$, which we term the _replacement graph_ , according to the
probability distribution $(\mathcal{R}_{F,H})_{H}$ and replace
$G_{t-1}[\mathbf{v}]$ by $H$ in the graph $G_{t-1}$ to obtain $G_{t}$. To be
precise, we place a copy of $H$ on $\mathbf{v}$ so that $ij\in E(H)$ if and
only if $v_{i}v_{j}\in G_{t}$. A flip process is a discrete time Markov
process. It is (unlike all the previously mentioned processes) defined for all
times.

We observe that the Erdős–Rényi process and the triangle removal process have
flip process variants. The _Erdős–Rényi flip process_ starts with an arbitrary
graph on $n\geq 2$ vertices. In each step, a random pair of vertices is chosen
and turned into an edge. If the pair is already an edge then the step is idle.
The _triangle removal flip process_ starts with an arbitrary graph on $n\geq
3$ vertices. In each step, a random triple of vertices is chosen. If the
triple forms a triangle then its three edges are removed. Otherwise, the step
is idle. Note that the difference between the original processes and their
flip process variants is the idle steps in the latter. While $H$-removal
processes can be viewed as flip processes, other classes mentioned in Section
1.1, like the $H$-free process and Achlioptas processes, cannot.

In [12], flip processes were studied from the perspective of dense graph
limits. Recall that the main objects of this theory, introduced in [19, 7],
are two-variable symmetric measurable functions defined on the square of a
probability space $(\Omega,\pi)$ (which we assume to have a separable sigma-
algebra and atomless measure) with values in $[0,1]$. These functions are
called _graphons_. We denote the set of all graphons by $\mathcal{W}_{0}$.
Recall that one of the most important metrics on $\mathcal{W}_{0}$ is the _cut
norm distance_ , which is given by

(1) $d_{\square}(U,W)=\left\lVert
U-W\right\rVert_{\square}=\sup_{S,T\subseteq\Omega}\left|\int_{S\times
T}(U-W)\,\mathrm{d}\pi^{2}\right|\;.$

Recall also that each finite graph $G$ can be represented as a graphon. To
this end, take an arbitrary partition $(\Omega_{v}:v\in V(G))$ of $\Omega$
into sets of equal measure. Let the graphon $W_{G}$ be defined to be $1$ on
each rectangle $\Omega_{u}\times\Omega_{v}$ for which $uv\in E(G)$, and 0
elsewhere. Note that this graphon representation depends on the choice of the
partition $(\Omega_{v}:v\in V(G))$. However, we will assume that graphs on the
same vertex set are represented using the same partition of $\Omega$. Since
each step of a flip process of order $k$ flips at most $\binom{k}{2}$ pairs of
vertices (from a non-edge to an edge or vice versa), it follows that we need
to perform $\Omega(n^{2})$ steps to see a change in the evolution of an
$n$-vertex graph through the lens of dense graph limits. Indeed, one of the
main results of [12] is the following correspondence.

######  Theorem 1.1 (Informal, with loose quantification; see Theorem
LABEL:FIRSTPAPER.thm:conc_proc in [12]).

For every $k\in\mathbb{N}$ and for every rule $\mathcal{R}$ of order $k$,
there exists an _evolution function_
$\Phi:\mathcal{W}_{0}\times[0,\infty)\rightarrow\mathcal{W}_{0}$ so that,
writing $\Phi^{t}W=\Phi(W,t)$ and treating $\mathcal{W}_{0}$ as the metric
space with metric $d_{\square}$, we have the following.

  1. (i)

For any fixed graphon $W\in\mathcal{W}_{0}$, we have $\Phi^{0}W=W$ ($W$ is the
‘initial graphon’) and the map
$t\mapsto\Phi^{t}W:[0,\infty)\rightarrow\mathcal{W}_{0}$, which we call the
_trajectory starting at $W$_, is continuous.

  2. (ii)

The trajectory depends continuously on the initial conditions, i.e., for any
fixed time $t\geq 0$, the map
$\Phi^{t}(\cdot):\mathcal{W}_{0}\rightarrow\mathcal{W}_{0}$ is continuous. The
variable $t$ is ‘time’.

  3. (iii)

Let $G_{0},G_{1},\dots$ be the flip process starting with an $n$-vertex graph
$G_{0}$. Denote by $W_{\ell}$, $\ell=0,1,\dots$, the (random) graphon that
represents the graph $G_{\ell}$. For every $\varepsilon>0$ and $T\geq 0$, with
probability $1-\exp(-\Omega(n^{2}))$ for every
$\ell\in\mathbb{N}\cap[0,Tn^{2}]$ we have
$d_{\square}(W_{\ell},\Phi^{\ell/n^{2}}W_{0})<\varepsilon$.

The evolution function
$\Phi:\mathcal{W}_{0}\times[0,\infty)\rightarrow\mathcal{W}_{0}$ is
constructed in a way which is only partly explicit. More specifically, given a
rule $\mathcal{R}$, a _velocity field_
$\mathfrak{V}_{\>}:\mathcal{W}_{0}\rightarrow\mathcal{W}$ is explicitly
constructed (here, $\mathcal{W}$ is the space of 2-variable symmetric
functions in $L^{\infty}(\Omega^{2})$), and the trajectory starting at any
initial graphon $W\in\mathcal{W}_{0}$ is then defined as the unique solution
of the (Banach-space-valued) differential equation

$\frac{\,\mathrm{d}}{\,\mathrm{d}t}\Phi^{t}W=\mathfrak{V}_{\>}\left(\Phi^{t}W\right)\;\mbox{with
initial condition}\;\Phi^{0}W=W\;,$

which can be equivalently formulated as the integral equation

(2)
$\Phi^{t}W=W+\int_{0}^{t}\mathfrak{V}_{\>}\left(\Phi^{\tau}W\right)\,\mathrm{d}\tau\;.$

As we shall see in this paper, obtaining explicit trajectories is a difficult
task even for fairly simple rules.

In the rest of this introduction we motivate further key notions in the theory
of flip processes.

###  1.3. Flip processes, going back in time

Theorem 1.1(iii) says that for any time $t\geq 0$ the graphon $\Phi^{t}W$
approximately describes the structure of a typical graph after $tn^{2}$ steps
of the flip process started at an $n$-vertex graph $G_{0}$ which is close to
$W$. We may ask a complementary question: does there exist a graphon $U$ such
that, starting at an $n$-vertex graph $H_{0}$ that is close to $U$, after
$tn^{2}$ steps we typically arrive to a graph which is similar to $W$? In such
a case, it is natural to write $\Phi^{-t}W:=U$, and the above property can be
written as $\Phi^{t}(\Phi^{-t}W)=W$. Note that $\Phi^{-t}W$ need not always
exist. To give a specific example, in the Erdős–Rényi flip process, there is
no way we could arrive at an edgeless graph after performing any number of
steps starting from any graph. This means that $\Phi^{-t}0$ does not exist for
any $t>0$. As a generalization of this example, for any constant graphon
$C\in(0,1)$, the backwards trajectory $\Phi^{-t}C$ is a constant graphon which
decreases as $t$ increases until it reaches 0 (at time
$t=-\frac{1}{2}\ln(1-C)$; this quantity can be obtained by considering the
inverse of the trajectory starting at zero, see [12, equation
(LABEL:FIRSTPAPER.eq:solutionErdosRenyi)]), and for larger $t$, $\Phi^{-t}C$
is not defined. Switching back to the general setting, we call the supremum of
times $t$ for which $\Phi^{-t}W$ exists the _age of a graphon $W$_.
Furthermore, if $\mathrm{age}(W)<\infty$ then it can be shown that
$\mathrm{orig}(W):=\Phi^{-\mathrm{age}(W)}W$ is well-defined (see Theorem
LABEL:FIRSTPAPER.thm:flowLABEL:FIRSTPAPER.en:life in [12]). We call
$\mathrm{orig}(W)$ the _origin_ of $W$. To return to the example of the
Erdős–Rényi flip process, the origin of every constant graphon $C\in[0,1)$ is
the constant-$0$. The constant-$1$ does not have an origin, but it has an
infinite age and $\Phi^{t}1=1$ for every time $t$, positive or negative.

###  1.4. Flip processes, destinations

For a general rule and a fixed initial graphon $W$, there are several
qualitatively different possible evolutions of the trajectory
$(\Phi^{t}W)_{t\geq 0}$. The simplest one is when $W$ is a _fixed point_ ,
that is, $\Phi^{t}W=W$ for all $t\in\mathbb{R}$. The next simplest is when
$\Phi^{t}W$ converges as $t\to\infty$. Here we choose the weakest sensible
notion of convergence, that is, cut norm distance convergence.111However, in
[12] it is conjectured that this setting actually implies convergence in the
$L^{1}$-norm and possibly even in the $L^{\infty}$-norm. In such a setting we
denote the limit by $\mathrm{dest}(W)$ and call it the _destination of_ $W$.
There are more complicated types of trajectories. For example, in [12] it was
shown that a periodic trajectory exists for a certain rule. Further, when a
starting graphon is taken in an proximity of such a periodic trajectory, its
trajectory spirals towards the periodic one. However, at this moment we do not
see a classification of trajectories beyond convergent/nonconvergent (where
the former also contains fixed points).

For a convergent trajectory, it is of interest to investigate the speed of
convergence. Bounds which are independent of the starting graphon are
particularly interesting. More formally, suppose that $\mathcal{R}$ is a rule
for which every trajectory converges. We can define for each $\delta>0$ the
_lower convergence time_

$\tau^{-}(\delta)=\sup\\{\inf\\{T:d_{\square}(\Phi^{T}W,\mathrm{dest}(W))<\delta\\}:W\in\mathcal{W}_{0}\\}$

and the _upper convergence time_

$\tau^{+}(\delta)=\sup\\{\sup\\{T:d_{\square}(\Phi^{T}W,\mathrm{dest}(W))\geq\delta\\}:W\in\mathcal{W}_{0}\\}\;.$

###  1.5. Our results

This paper investigates properties of some natural flip processes, with a
particular emphasis on the description of their trajectories. Due to the key
Theorem 1.1, this provides information about the typical evolution of an
$n$-vertex graph in the next $\Theta(n^{2})$ steps.

Let us briefly and informally introduce these flip processes and highlight the
main results we obtain about them. The main results that concern either
explicit description of trajectories, destinations, speed of convergence or
speed of these flip processes are listed in Table 1. (In addition to those,
some flip processes have specific features.)

| trajectories | destination | age | speed
---|---|---|---|---
ignorant | Proposition 4.2
balanced stirring | Proposition 5.2 | Proposition 5.4 |
complementing | Proposition 6.1
extremist |  | Theorem 7.4 |  |
| Theorem 7.6 |  |
monotone |  | Proposition 8.2 |  |
| Proposition 8.3 |  |
component completion |  | Theorem 9.6 |  |
removal |  | Fact 10.5 |  | Theorem 10.9
| Theorem 10.7 |  | Proposition 10.10
Table 1. Summary of our main (and easily categorizable) results

####  1.5.1. Ignorant flip processes (Section 4)

Ignorant flip processes are flip processes where the distribution for the
replacement graph does not depend on the drawn graph. That is, the rule
$\mathcal{R}$ satisfies that for any $F,F^{\prime},H$, we have
$\mathcal{R}_{F,H}=\mathcal{R}_{F^{\prime},H}$. Ignorant flip processes are
one of the few examples where we can describe the trajectories explicitly;
this gives a complete description of their behaviour. In particular, all the
trajectories of an ignorant flip process converge to the same constant graphon
whose value is the expected edge density222The _density_ of a graph $H$ is
defined as ${e(H)}/{\binom{v(H)}{2}}$. according to the output distribution
$\\{\mathcal{R}_{F,H}\\}_{H}$ (here $F$ is arbitrary). The Erdős–Renyi flip
process is a prominent example of an ignorant flip process.

####  1.5.2. Stirring flip processes (Section 5)

While the output distribution in an ignorant flip process does not depend on
the drawn graph at all, in a stirring flip process it depends only on a very
basic graph parameter — its number of edges. In Section 5 we investigate
balanced stirring flip processes, in which the expected number of edges in the
replacement graph is equal to the number of edges in the drawn graph. We
explicitly describe the trajectories of any balanced stirring flip process.
Not surprisingly, the edge density is preserved along each trajectory. The
description does not depend on the actual rule but only on its order. That is,
any balanced stirring flip process of a given order yields the same
trajectories.

####  1.5.3. Complementing flip processes (Section 6)

The complementing flip process is a flip process where we replace the drawn
graph by its graph complement. Informally, we thus sparsify the host graph at
places where its density lies above $\frac{1}{2}$ and densify it at places
where its density lies below $\frac{1}{2}$. It follows that each trajectory
should converge to the constant-$\frac{1}{2}$ graphon. We work out the
trajectories explicitly, confirming this intuition.

####  1.5.4. Extremist flip processes (Section 7)

The extremist flip process is defined as follows. If the drawn graph has edge
density less than $1/2$, we replace it by the edgeless graph. If the edge
density is greater than $1/2$, we replace it by the clique. If the density is
exactly $1/2$, then there is some freedom in defining the replacement graph
(our default choice is do nothing). Intuitively, dense graph(on)s converge to
the complete graph (constant-$1$ graphon) while sparse graph(on)s converge to
the edgeless graph (constant-$0$ graphon). The main focus of our treatment of
extremist flip processes is in making this precise. Further, we study the
limit behaviour as $k$ grows.

####  1.5.5. Monotone flip processes (Section 8)

We introduce several variants, but, roughly speaking, a monotone flip process
is a flip process where in each step we add edges, or at least add edges in
expectation. In such a situation we expect the trajectories to be increasing
in time and in particular to converge. Indeed, most of our treatment of
monotone flip processes focuses on these features (including one negative
example).

####  1.5.6. Component completion flip processes (Section 9)

In a component completion flip process, we replace the drawn graph (which may
have several connected components) by its so-called component completion
graph, that is, we turn each connected component into a clique. Hence, the
component structure of the graph does not change during the evolution. Note
also that this procedure is void for orders $k=1,2$. For $k\geq 3$ we prove
that the trajectories converge to a graphon with the same component structure,
where each component is constant-$1$.

####  1.5.7. Removal flip processes (Section 10)

Removal flip processes generalize the triangle removal flip process. We fix a
graph $F\in\mathcal{H}_{k}$. In each step of the process, we delete a copy of
$F$, should the drawn graph contain it. More formally, for
$H\in\mathcal{H}_{k}$ which contains $F$ as a subgraph (preserving the labels)
we have $\mathcal{R}_{H,H-F}=1$ while for $H$ which does not contain $F$ as a
labelled subgraph we have $\mathcal{R}_{H,H}=1$. The theory of removal flip
processes is particularly elegant. There are two results which we could obtain
only with the help of Szemerédi’s regularity lemma: that convergence times for
removal processes are finite and uniformly bounded and that the map which maps
each graphon to its destination is continuous in the cut norm distance.

####  1.5.8. Quadratically many steps and beyond

Most of the results we obtain concern trajectories. Due to the correspondence
in Theorem 1.1, this tells us about the typical evolution of a finite
$n$-vertex graph in a flip process for $\Theta(n^{2})$ steps. However, for the
extremist and removal flip processes we found interesting questions which go
beyond this time horizon.

##  2\. Definitions and basics

This section recalls some basic facts, which we sometimes reprove in variants
that are tailored to our applications.

For $k\in\mathbb{N}$, we write $(k)_{2}=k(k-1)$. When using little-o notation,
we sometimes use a subscript to emphasize the parameter of asymptotics. For
example, $\lim_{k\to\infty}\frac{o_{k}(k^{2})}{k^{2}}=0$.

###  2.1. Differential equations

####  2.1.1. Grönwall’s inequality

Here we state two variants of Grönwall’s inequality. The following lemma is a
variant of Grönwall’s inequality in integral form.

######  Lemma 2.1 ([27, Theorem 1.10]).

Let $f:[t_{0},t_{1}]\rightarrow[0,\infty)$ be a continuous non-negative
function. Suppose that for some constants $A\geq 0$, $C>0$ we have

(3) $f(t)\leq A+C\int_{t_{0}}^{t}f(x)\,\mathrm{d}x$

for every $t\in[t_{0},t_{1}]$. Then we have

(4) $f(t)\leq Ae^{C(t-t_{0})}\quad\text{ for all }t\in[t_{0},t_{1}]\;.$

The following lemma is a variant of Grönwall’s inequality for differentiable
functions where the differential inequality holds subject to a condition on
the value of the function.

######  Lemma 2.2.

Let $D,K>0$ and $f\colon[0,\infty)\to[0,\infty)$ be a differentiable function
satisfying $f(0)\leq D$ and $f^{\prime}(t)\leq-Kf(t)$ for all $t\in[0,\infty)$
such that $f(t)\leq D$. Then for all $t\in[0,\infty)$ we have $f(t)\leq
f(0)e^{-Kt}$.

###### Proof.

First we show that we have $f(t)\leq D$ for all $t\in[0,\infty)$. Indeed,
suppose that we have $f(t^{\prime})>D$ for some $t^{\prime}>0$. Let
$T:=\inf\\{t\geq 0:f(t)>D\\}$. By the continuity of $f$ we have $f(T)=D$, so
we have $f^{\prime}(T)\leq-Kf(T)=-KD<0$. By the definition of $f^{\prime}(T)$,
there exists $\varepsilon_{0}>0$ such that for all
$0<\varepsilon<\varepsilon_{0}$ we have

$f(T+\varepsilon)\leq f(T)+\varepsilon(KD/2+f^{\prime}(T))\leq
f(T)-KD\varepsilon/2<D.$

This contradicts the definition of $T$, so we have $f(t)\leq D$ for all
$t\in[0,\infty)$.

The function $g\colon[0,\infty)\to[0,\infty)$ given by $g(s):=f(s)e^{Ks}$ is
differentiable with $g^{\prime}(s)=f^{\prime}(s)e^{Ks}+Kf(s)e^{Ks}\leq 0$, so
for every $t\geq 0$ we have $g(t)\leq g(0)=f(0)$ and hence
$f(t)=g(t)e^{-Kt}\leq f(0)e^{-Kt}$, as desired. ∎

####  2.1.2. On notation of integrals

For the sake of brevity and clarity we sometimes use simplified notation to
denote an integral, namely we often write $\int_{x=a}^{b}f(x)$ (or
$\int_{x=a}^{b}f$) instead of $\int_{a}^{b}f(x)\,\mathrm{d}x$ for functions of
a single real argument (that is, the underlying measure is the Lebesgue
measure) and $\int_{x\in A}f(x)$ (or $\int_{x\in A}f$) instead of
$\int_{A}f(x)\,\mathrm{d}\mu(x)$ for functions on some abstract measure space
when the measure $\mu$ is clear from the context.

####  2.1.3. Differential equations in Banach spaces

We need to recall concepts of the derivative and the integral in Banach
spaces. However we do not need almost any results from the abstract theory of
differential equations in Banach spaces since we only need to recall results
obtained already in [12]. Let $\mathcal{E}$ be a Banach space with norm
$\|\cdot\|$. Suppose that a function $f:I\to\mathcal{E}$ is defined for an
open set $I\subset\mathbb{R}$. If $t\in I$ is such that there is an element
$z\in\mathcal{E}$ for which

$\lim_{\varepsilon\to
0}\left\|\frac{f(t+\varepsilon)-f(t)}{\varepsilon}-z\right\|=0\;,$

then we say that _$f$ is differentiable at $t$_ and call
$\frac{\,\mathrm{d}}{\,\mathrm{d}t}f(t)=z$ the _derivative of $f$ at $t$_. At
the heart of the theory of flip processes are first-order autonomous
differential equations of the type

(5) $\frac{\,\mathrm{d}}{\,\mathrm{d}t}f(t)=\mathfrak{O}(f(t))\;\mbox{with
initial condition}\;f(0)=z\;,$

where $z\in\mathcal{E}$, $f$ takes values in $\mathcal{E}$, and
$\mathfrak{O}:\mathcal{E}\rightarrow\mathcal{E}$ is (locally) Lipschitz. Such
a differential equation can be rewritten as the integral equation

(6) $f(t)=z+\int_{0}^{t}\mathfrak{O}(f(s))\,\mathrm{d}s\;,$

where the integral is the so-called Cauchy–Bochner integral in the Banach
space $\mathcal{E}$ (it is easy to show that this integral is well-defined,
since $s\mapsto\mathfrak{O}(f(s))$ is continuous). The integral has all usual
properties of the Riemann integral of continuous real-valued functions, with
the norm playing the role of the absolute value (see Section
LABEL:FIRSTPAPER.app:Banach_calc in [12]).

In this paper, we specifically consider differential equations in the Banach
space $(\mathcal{W},\left\lVert\cdot\right\rVert_{\infty})$, which is a closed
subspace of $L^{\infty}(\Omega^{2})$ (where $\Omega$ is the probability space
on which our graphons are defined). Recall that the elements of
$L^{\infty}(\Omega^{2})$ are equivalence classes (where equivalent means equal
almost everywhere) of measurable functions, which means that it is not
formally meaningful to evaluate an element $f\in L^{\infty}(\Omega^{2})$ at a
given point $(x,y)\in\Omega^{2}$. However, it is much more intuitive to
pretend we can do this and, for example (i) evaluate $f(t)$ (see (2) for a
prominent example) at point $(x,y)$ by integrating a real-valued curve
$s\mapsto\mathfrak{V}_{\>}\left(f(s)\right)(x,y)$; (ii) deduce that $f(t)\leq
g(t)$ for every $t\in[a,b]$ implies $\int_{a}^{b}f(t)\leq\int_{a}^{b}g(t)$
(where the inequalities are understood to hold almost everywhere). In [12] it
was shown that this apparently non-rigorous approach can be perfectly
justified. We believe that this approach of dealing with trajectories
“pointwise” has an advantage on the intuitive level, and we stick to it,
referring a meticulous reader to the required technical tools for
justification in Appendix LABEL:FIRSTPAPER.app:Banach_calc in [12].

What follows is the only abstract fact we need that is not available in [12].
It says that a solution of a differential equation of the type in (5) changes
only little if we perturb the velocity field. This statement is very likely
standard, but we found it easier to give a four-line proof than to find a
source in the literature.

######  Lemma 2.3.

Consider a Banach space $\mathcal{E}$ with norm $\|\cdot\|$. Let
$\mathcal{U}\subset\mathcal{E}$ be a set, and $A,K>0$ be constants. Let
$X,Y:\mathcal{U}\rightarrow\mathcal{E}$ be functions. Suppose that $X$ is
$K$-Lipschitz, that is, we have

(7) $\left\|X(x)-X(y)\right\|\leq K\left\|x-y\right\|\quad\text{ for all
}x,y\in\mathcal{U}\;.$

Suppose further that for each $x\in\mathcal{U}$ we have

(8) $\|X(x)-Y(x)\|\leq A\;.$

Given $x_{0}\in\mathcal{U}$, let $\alpha,\beta:[0,T]\rightarrow\mathcal{U}$
satisfy the integral equations

$\alpha(t)=x_{0}+\int_{s=0}^{t}X(\alpha(s))\quad\beta(t)=x_{0}+\int_{s=0}^{t}Y(\beta(s))\quad\mbox{for
each $t\in[0,T]$}$

Then for each $t\in[0,T]$ we have $\|\alpha(t)-\beta(t)\|\leq AT\exp(Kt)$.

###### Proof.

Set $f(t):=\|\alpha(t)-\beta(t)\|$. Then

$\displaystyle f(t)$
$\displaystyle\leq\int_{s=0}^{t}\left\|X(\alpha(s))-Y(\beta(s))\right\|\overset{\mbox{\tiny{\eqref{eq:BMo}}}}{\leq}\int_{s=0}^{t}\big{(}A+\left\|X(\alpha(s))-X(\beta(s))\right\|\big{)}$
$\displaystyle\overset{\mbox{\tiny{\eqref{eq:AMo}}}}{\leq}\int_{s=0}^{t}\big{(}A+Kf(s)\big{)}\leq
AT+K\int_{s=0}^{t}f(t)\;.$

Hence, the claim follows from Lemma 2.1. ∎

###  2.2. Graphons

Our notation regarding graphons follows [18]. Recall that $(\Omega,\pi)$ is an
atomless probability space with an implicit separable sigma-algebra. We write
$\mathcal{W}\subset L^{\infty}(\Omega^{2})$ for the set of bounded symmetric
measurable functions; these are called _kernels_. _Graphons_ , which we denote
by $\mathcal{W}_{0}$, are then those kernels whose range is a subset of
$[0,1]$.

####  2.2.1. Densities and degrees

The notion of homomorphism densities of a finite graph is one of the
cornerstones of the theory of graph limits.

For a function $f:\Omega^{V}\to\mathbb{R}$ and a subset $S\subset V$ we write

$\int f\,\mathrm{d}\pi^{S}=\int_{\Omega^{S}}f(x_{i}:i\in V)\prod_{i\in
S}\pi(\,\mathrm{d}x_{i}).$

######  Definition 2.4.

Given a kernel $W$ and a graph $F=(V,E)$, we define the _density of $F$_ in
$W$ as

$t(F,W)\coloneqq\int\prod_{ij\in E}W(x_{i},x_{j})\,\mathrm{d}\pi^{V}\;.$

and the _induced density of $F$_ in $W$ as

${t_{\mathrm{ind}}}(F,W)\coloneqq\int\prod_{ij\in
E}W(x_{i},x_{j})\prod_{ij\notin
E}\left(1-W(x_{i},x_{j})\right)\,\mathrm{d}\pi^{V}\;.$

In particular, the _edge density of $W$_ is the number $t(K_{2},W)=\int
W\,\mathrm{d}\pi^{2}$.

A _rooted graph_ is a triple $(R,V,E)$, where $(V,E)$ is a graph and $R$ is a
subset of $V$; we call the elements of $R$ the _roots_.

######  Definition 2.5 (Rooted densities).

Given a graphon $W$, a rooted graph $F=(R,V,E)$, and ${\mathbf{x}}=(x_{i}:i\in
R)\in\Omega^{R}$ we define the functions

$\displaystyle t^{\mathbf{x}}(F,W)$ $\displaystyle\coloneqq\int\prod_{ij\in
E}W(x_{i},x_{j})\,\mathrm{d}\pi^{V\setminus R}\;\textrm{ and}$ $\displaystyle
t_{\mathrm{ind}}^{\mathbf{x}}(F,W)$ $\displaystyle\coloneqq\int\prod_{ij\in
E}W(x_{i},x_{j})\prod_{ij\notin
E}\left(1-W(x_{i},x_{j})\right)\,\mathrm{d}\pi^{V\setminus R}\;.$

Further, if $\mathbf{A}=(A_{i})_{i\in R}$ is a collection of sets
$A_{i}\subset\Omega$ then we define the quantities

$t^{\mathbf{A}}(F,W)\coloneqq\int_{\mathbf{x}\in\prod_{i}A_{i}}t^{\mathbf{x}}(F,W)\quad\text{and}\quad
t_{\mathrm{ind}}^{\mathbf{A}}(F,W)\coloneqq\int_{\mathbf{x}\in\prod_{i}A_{i}}t_{\mathrm{ind}}^{\mathbf{x}}(F,W)\;.$

One of the key properties of densities is that they, as functions of a
graphon, are continuous with respect to the cut norm distance.

######  Lemma 2.6 (Counting lemma, [18, Lemma 10.23]).

Suppose that we have a graph $F$ of order $k$ and two graphons $U$ and $W$.
Then we have

$|t(F,U)-t(F,W)|\leq\textstyle\binom{k}{2}d_{\square}(U,W).$

Lastly, we introduce the notions of degree and degree-regularity.

######  Definition 2.7.

The _degree function_ of a kernel $W$ is the function
$\deg_{W}:\Omega\to\mathbb{R}$ defined as
$\deg_{W}(x)=\int_{y\in\Omega}W(x,y)$. We say that a kernel $W$ of edge
density $d$ is _degree-regular_ if for $\pi$-almost every $x\in\Omega$ we have
$\deg_{W}(x)=d$.

####  2.2.2. Sampling

A graphon $W$ defines, for every $k\in\mathbb{N}$, a probability distribution
on $\mathcal{H}_{k}$ as follows. Sample independent $\pi$-random elements
$U_{v}$, $v\in[k]$ of $\Omega$ and then connect each pair of distinct vertices
$u,v\in[k]$ independently with probability $W(U_{u},U_{v})$. We write
$F\sim\mathbb{G}(k,W)$ for the random graph obtained this way and sometimes
even use $\mathbb{G}(k,W)$ to denote the random graph itself. For many
properties of sampling we refer to Section 10 of [18]. The following lemma
asserts that for large $k$ this random graph is close to $W$ with high
probability. To this end we use the notion of _cut distance_ between a finite
graph $G$ and a graphon $W$, which is defined as
$\delta_{\square}(G,W)=\inf\\{d_{\square}(U,W)\\}$, where $U$ ranges over all
graphon representations of $G$.

######  Lemma 2.8 (Sampling lemma, [18, Lemma 10.16]).

For $k=2,3,\dots$ and every $W\in\mathcal{W}_{0}$ we have

$\mathbb{P}\left(\delta_{\square}(\mathbb{G}(k,W),W)\leq
22/\sqrt{\log_{2}k}\right)\geq 1-\exp(-k/(2\log_{2}k))\;.$

####  2.2.3. Regularity lemma

In Section 10 we study removal flip processes. To study their speed of
convergence, we need to recall a regularity lemma. While for many purposes in
the area of graph limits the Frieze–Kannan regularity lemma is sufficient,
here we need Szemerédi’s regularity lemma. The notions of density and
regularity are standard, but typically appear in the setting of finite graphs.
The graphon setting is used for example in [20].

######  Definition 2.9.

Suppose that $W$ is a graphon and $C,D\subset\Omega$ are sets of positive
measure. The _density of $(C,D)$_ in $W$ is defined as

$d(C,D):=\frac{1}{\pi(C)\pi(D)}\int_{C\times D}W\,\mathrm{d}\pi^{2}\;.$

Given $\alpha>0$, we say that $(C,D)$ is _$\alpha$ -regular_ in $W$ if for
every $C^{\prime}\subset C$ and $D^{\prime}\subset D$ we have

(9) $\left|\pi(C^{\prime})\pi(D^{\prime})d(C,D)-\int_{C^{\prime}\times
D^{\prime}}W\,\mathrm{d}\pi^{2}\right|\leq\alpha\pi(C)\pi(D)\;.$

######  Definition 2.10.

Suppose that $W$ is a graphon. For $\alpha>0$, we say that a partition
$\\{P_{1},\ldots,P_{M}\\}$ of $\Omega$ is an _$\alpha$ -regular partition of
$W$_ if

  * •

$\alpha\geq 1/M$,

  * •

for each $i$ we have $\pi(P_{i})=1/M$,

  * •

the number of pairs $(i,j)\in[M]^{2}$ for which $(P_{i},P_{j})$ is not an
$\alpha$-regular pair in $W$ is at most $\alpha M^{2}$.

We call the sets $P_{1},\ldots,P_{M}$ _clusters_.

With this terminology, we can state a version of Szemerédi’s regularity lemma
tailored to our purposes.

######  Theorem 2.11.

For each $\alpha>0$ there exists $M_{0}\in\mathbb{N}$ so that for each graphon
$W$ there exists an $\alpha$-regular partition of $W$ with at most $M_{0}$
sets.

In the setting of regular pairs, homomorphism densities can be controlled.
This is the subject of the counting lemma, which we state in a version
tailored to our purposes.

######  Lemma 2.12.

Let $\alpha>0$ and $W$ be a graphon. Let $F=(R,R,E)$ be a graph which
satisfies $|R|\geq 3$ and whose vertices are all roots. Suppose that
$\mathbf{A}=(A_{i})_{i\in R}$ be a tuple of subsets of $\Omega$ such that for
every $i,j\in R$ we have $\pi(A_{i})=\pi(A_{j})$, and for every $\\{i,j\\}\in
E$ the pair $(A_{i},A_{j})$ is an $\alpha$-regular pair in $W$. Then

(10) $t^{\mathbf{A}}(F,W)=\left(\prod_{ij\in
E}d(A_{i},A_{j})\pm\alpha|R|^{|R|}\right)\prod_{i\in R}\pi(A_{i})\;.$

###### Proof.

We derive this from the version of the counting lemma stated as Lemma 10.24 in
[18], where we refer to the notion of decorated graphs and the corresponding
homomorphism density. That counting lemma is tailored to the notion of cut
norm distance, which is linked to the weak regularity lemma. On the other
hand, Lemma 2.12 is phrased in the setting of Szemerédi’s regularity lemma,
which is used much less in the theory of graph limits.333Actually, we are not
aware of a similar application of Szemerédi’s regularity lemma in the setting
of graphons. In particular, the error bound (10) is relative to $\prod_{i\in
R}\pi(A_{i})$. So, the routine work below is to transfer to that setting,
which we do so by zooming in on the sets $A_{i}$.

Further, assume that $R=[r]$ for some $r\in\mathbb{N}$. For $i\in[r]$, write
$I_{i}:=[\frac{i-1}{r},\frac{i}{r})$. Further, write
$I=\bigcup_{i=1}^{r}I_{i}=[0,1)$. For every $i$ we define two probability
measures: the $r$-times rescaled Lebesgue measure
$\mu_{i}(\cdot)=r\mathrm{Leb}(\cdot)$ on $I_{i}$ and
$\pi_{i}(\cdot)=\frac{\pi(\cdot)}{\pi(A_{i})}$ on $A_{i}$. Since
$(\Omega,\pi)$ is atomless and separable, the Isomorphism theorem for measure
spaces tells us that there exists a measure-preserving map
$f_{i}:(I_{i},\mu_{i})\to(A_{i},\pi_{i})$. For example, if
$\Omega=([0,1],\mathrm{Leb})$, we can define $f_{i}:I_{i}\rightarrow A_{i}$ as
$f_{i}(z):=\inf\\{t\in
A_{i}:\pi(A_{i}\cap[0,t])\geq(rz-(i-1))\cdot\pi(A_{i})\\}$.

Define $f:I\to\Omega$ by setting $f(z)=\sum_{i\in R}f_{i}(z)\mathbb{I}_{z\in
I_{i}}$. Define $W^{f}:I^{2}\rightarrow[0,1]$ by setting

$W^{f}(x,y):=W\left(f(x),f(y)\right)\;.$

Consider the complete graph $K$ on the vertex set $R$. We construct two
decorated graphs $u=(U_{e}:e\in E(K))$ and $u^{\prime}=(U^{\prime}_{e}:e\in
E(K))$ on the ground space $I$ as follows. For every $e=\\{i,j\\}\in E(K)$,
writing $d_{e}=d(A_{i},A_{j})$, we define

$\displaystyle U_{e}$ $\displaystyle=\mathbb{I}_{I_{i}\times I_{j}\cup
I_{j}\times I_{i}}\cdot\begin{cases}W^{f},&\quad\text{if $e\in E$,}\\\
1,&\quad\text{if $e\in E(K)\setminus E$,}\end{cases}$ $\displaystyle
U^{\prime}_{e}$ $\displaystyle=\mathbb{I}_{I_{i}\times I_{j}\cup I_{j}\times
I_{i}}\cdot\begin{cases}d_{e},&\quad\text{if $e\in E$,}\\\ 1,&\quad\text{if
$e\in E(K)\setminus E$.}\end{cases}$

It is obvious that for every $x_{1},\ldots,x_{r}\in I$ we have

(11) $\prod_{ij\in E(K)}U_{ij}(x_{i},x_{j})=\prod_{i,j\in
E}W^{f}(x_{i},x_{j})\prod_{i\in[r]}\mathbb{I}_{I_{i}}(x_{i}).$

Similarly,

(12) $\prod_{ij\in E(K)}U^{\prime}_{ij}(x_{i},x_{j})=\prod_{e\in
E}d_{e}\prod_{i\in[r]}\mathbb{I}_{I_{i}}(x_{i}).$

Note that $(x_{1},\dots,x_{r})\mapsto(f(x_{1}),\dots f(x_{r}))$ is a measure-
preserving map between the product of probability spaces $(I_{i},\mu_{i})$ and
the product of probability spaces $\left(A_{i},\pi_{i}\right)$. Therefore by
(11),

$r^{r}t(K,u)=\int_{\prod_{i}I_{i}}\prod_{ij\in
E}W^{f}(x_{i},x_{j})\prod_{i}\,\mathrm{d}\mu_{i}=\int_{\prod_{i}A_{i}}\prod_{ij\in
E}W(y_{i},y_{j})\prod_{i}\,\mathrm{d}\pi_{i}=\frac{t^{\mathbf{A}}(F,W)}{\prod_{i}\pi(A_{i})}$

and, by (12),

$r^{r}t(K,u^{\prime})=\int_{\prod_{i}I_{i}}\prod_{e\in
E}d_{e}\prod_{i}\,\mathrm{d}\mu_{i}=\prod_{e\in E}d_{e}.$

To sum up,

(13)
$\displaystyle\begin{split}t(K,u)&=t^{\mathbf{A}}(F,W)\cdot\frac{r^{-r}}{\prod_{i\in
R}\pi(A_{i})}\;\quad\mbox{and}\\\ t(K,u^{\prime})&=\prod_{e\in E}d_{e}\cdot
r^{-r}\;.\end{split}$

We claim that for each $e\in E(K)$ we have $\left\lVert
U_{e}-U^{\prime}_{e}\right\rVert_{\square}\leq 2\alpha r^{-2}$. We shall
postpone the proof of this to the end, and first show how it implies the
asserted statement. By Lemma 10.24 in [18], we have

$|t(K,u)-t(K,u^{\prime})|\leq\sum_{e\in E(K)}\left\lVert
U_{e}-U^{\prime}_{e}\right\rVert_{\square}\leq\binom{r}{2}2\alpha
r^{-2}<\alpha\;.$

Substituting the expressions from (13) and multiplying by
$r^{r}\cdot\prod_{i\in R}\pi(A_{i})$, we obtain

$\left|t^{\mathbf{A}}(F,W)-\prod_{e\in E}d_{e}\cdot\prod_{i\in
R}\pi(A_{i})\right|\leq\alpha\cdot r^{r}\cdot\prod_{i\in R}\pi(A_{i})\;,$

as needed.

We now return to the deferred claim that for each $e=\\{a,b\\}\in E(K)$ we
have $\left\lVert U_{e}-U^{\prime}_{e}\right\rVert_{\square}\leq 2\alpha
r^{-2}$. Note that for $e=ab\notin E$ we have
$U_{\\{a,b\\}}=U^{\prime}_{\\{a,b\\}}=\mathbb{I}_{I_{a}\times I_{b}\cup
I_{b}\times I_{a}}$ hence trivially $\left\lVert
U_{e}-U^{\prime}_{e}\right\rVert_{\square}=0$. It remains to consider the case
$e\in E$. Suppose that $S,T\subset I$ are arbitrary as in (1). Let
$C_{a}:=S\cap I_{a}$, $C_{b}:=S\cap I_{b}$, $D_{a}:=T\cap I_{a}$, and
$D_{b}:=T\cap I_{b}$. Since $I_{a},I_{b}$ are disjoint and
$U_{e},U^{\prime}_{e}$ are zero outside of $I_{a}\times I_{b}\cup I_{b}\times
I_{a}$, we have

$\displaystyle\left|\int_{S\times
T}(U_{e}-U^{\prime}_{e})\,\mathrm{d}x_{a}\,\mathrm{d}x_{b}\right|$
$\displaystyle\leq\left|\int_{C_{a}\times
D_{b}}(U_{e}-U^{\prime}_{e})\,\mathrm{d}x_{a}\,\mathrm{d}x_{b}\right|+\left|\int_{C_{b}\times
D_{a}}(U_{e}-U^{\prime}_{e})\,\mathrm{d}x_{a}\,\mathrm{d}x_{b}\right|\;.$

Since $(x_{a},x_{b})\mapsto(f(x_{a}),f(x_{b}))$ is a measure preserving map
between $(I_{a},\mu_{a})\times(I_{b},\mu_{b})$ and
$(A_{a},\pi_{a})\times(A_{b},\pi_{b})$, we have

$\displaystyle r^{2}$ $\displaystyle\left|\int_{C_{a}\times
D_{b}}(U_{e}-U^{\prime}_{e})\,\mathrm{d}x_{a}\,\mathrm{d}x_{b}\right|=\left|\int_{C_{a}\times
D_{b}}(W^{f}-d_{e})\,\mathrm{d}\mu_{a}\,\mathrm{d}\mu_{b}\right|$
$\displaystyle=\left|\int_{f(C_{a})\times
f(D_{b})}(W-d_{e})\,\mathrm{d}\pi_{a}\,\mathrm{d}\pi_{b}\right|$
$\displaystyle=\frac{1}{\pi(A_{a})\pi(A_{b})}\left|\int_{f(C_{a})\times
f(D_{b})}W\,\mathrm{d}\pi^{2}-\pi(f(C_{a}))\pi(f(D_{b}))d_{e}\right|\overset{\mbox{\tiny{\eqref{eq:IAmRegular}}}}{\leq}\alpha.$

To conclude,

$\left|\int_{C_{a}\times
D_{b}}(U_{e}-U^{\prime}_{e})\,\mathrm{d}\pi^{2}\right|\leq\alpha r^{-2}\;.$

Together with the same bound for $\left|\int_{C_{b}\times
D_{a}}(U_{e}-U^{\prime}_{e})\,\mathrm{d}\pi^{2}\right|$ we get that
$\left|\int_{S\times T}(U_{e}-U^{\prime}_{e})\,\mathrm{d}\pi^{2}\right|\leq
2\alpha r^{-2}$, as was needed. ∎

####  2.2.4. Inequality between clique densities

Here we shall prove an inequality which relates clique densities in graphons.
This is a consequence of the Kruskal–Katona theorem [16, 15]. In fact, our
proof uses a slightly weaker version due to Lovász [17, Exercise 13.31(b)].
While we need this inequality only for the case $r=2$ (which can be derived
from [9]), we shall state and prove the general case for possible future use.
For $m\in\mathbb{N}$ and a real number $x\geq m$ we write
$\binom{x}{m}:=\frac{x(x-1)\ldots(x-m+1)}{m!}$.

######  Proposition 2.13.

Let $W\in\mathcal{W}_{0}$ be a graphon and $r,k\in\mathbb{N}$ satisfy $r<k$.
Then we have

$t(K_{r},W)\geq t(K_{k},W)^{r/k}\;.$

In particular, for all $k\geq 3$ we have $\int
W\,\mathrm{d}\pi^{2}=t(K_{2},W)\geq t(K_{k},W)^{2/k}$.

###### Proof.

Define $\alpha:=t(K_{k},W)^{1/k}$. Pick a sequence $(G_{n})_{n\in\mathbb{N}}$
of graphs with $v(G_{n})=n$ which converges to the graphon $W$. Let
$(u_{n})_{n\in\mathbb{N}}$ be a sequence of real numbers so that the number of
$k$-cliques in $G_{n}$ is $\binom{u_{n}}{k}$, that is,
$t(K_{k},G_{n})={\binom{u_{n}}{k}}/{\binom{n}{k}}$; this implies
$u_{n}\sim\alpha n$. Exercise 13.31 in Lovász [17] (for $H$ consisting of the
vertex sets of $k$-cliques) implies that the number of $r$-cliques in $G_{n}$
is at least $\binom{u_{n}}{r}$, whence

$t(K_{r},W)=\lim_{n\to\infty}t(K_{r},G_{n})\geq\lim_{n\to\infty}\frac{\binom{u_{n}}{r}}{\binom{n}{r}}=\alpha^{r}=t(K_{k},W)^{r/k}\;,$

as required. ∎

###  2.3. Probability

The classical Berry–Esseen theorem establishes quantitative bounds on the
accuracy of the approximation of the probability distribution of a sum of
independent and identically distributed random variables by a normal
distribution with the same mean and variance. We will apply this to prove
Theorem 7.7.

######  Theorem 2.14 (Berry–Esseen theorem).

There is a positive constant $C$ such that the following holds. Suppose that
$X_{1},\dots,X_{k}$ are i.i.d. random variables with $\mathbb{E}X_{i}=0$,
$\operatorname{Var}X_{i}=\sigma^{2}<\infty$ and
$\mathbb{E}|X_{i}|^{3}=\beta<\infty$ for all $i\in[k]$. Let
$X=\sum_{i=1}^{k}X_{i}$. Then for all $x\in\mathbb{R}$ we have

$\left|\mathbb{P}\left(X\leq x\sigma\sqrt{k}\right)-\mathbb{P}\left(Z\leq
x\right)\right|\leq\frac{C\beta}{\sigma^{3}\sqrt{k}},$

where $Z\sim N(0,1)$ is a standard Gaussian random variable.

##  3\. Flip processes as dynamical systems on graphons: a recap

In this section, we review the theory from [12]. With the kind permission of
the authors of [12], we include the relevant parts into this section with
varying degrees of additional edits.

###  3.1. The velocity operator

Let $W$ be a graphon and let $\mathcal{R}$ be a rule of order $k$. Given a
graph $F\in\mathcal{H}_{k}$ and an ordered pair $1\leq a\neq b\leq k$ define
an operator $T_{F}^{a,b}:\mathcal{W}\rightarrow L^{\infty}(\Omega^{2})$ by
setting

$(T_{F}^{a,b}W)(x,y)=t_{\mathrm{ind}}^{(x,y)}(F^{a,b},W)\;.$

The _velocity operator for $\mathcal{R}$_ is the operator
$\mathfrak{V}_{\mathcal{R}}:\mathcal{W}\to\mathcal{W}$ given by

(14) $\mathfrak{V}_{\mathcal{R}}W:=\sum_{F,H\in\mathcal{H}_{k}}\sum_{1\leq
a\neq b\leq k}\mathcal{R}_{F,H}\cdot
T_{F}^{a,b}W\cdot\left(\mathbb{I}_{\left\\{ab\in H\setminus
F\right\\}}-\mathbb{I}_{\left\\{ab\in F\setminus H\right\\}}\right)\;,$

where $ab$ is shorthand for $\left\\{a,b\right\\}$.

It is convenient to have alternative reformulations of the velocity operator.
Let $W$ be a graphon and $\mathcal{R}$ be a rule of order $k$. Let the random
variables $(U_{v}:v\in[k])$ and the random graph $\mathbb{G}(k,W)$ be as
defined in Section 2.2.2. Let $(\mathbb{F},\mathbb{H})$ be a pair of random
graphs in $\mathcal{H}_{k}$ such that $\mathbb{F}\sim\mathbb{G}(k,W)$ and
$\mathbb{P}\left(\mathbb{H}=H\,|\,\mathbb{F}=F\right)=\mathcal{R}_{F,H}$ for
all $F,H\in\mathcal{H}_{k}$. Then we have (see equation
(LABEL:FIRSTPAPER.eq:vel_prob) in [12])

(15) $\mathfrak{V}_{\mathcal{R}}W(x,y)=\sum_{a\neq
b}\left[\mathbb{P}\left(ab\in\mathbb{H}\,|\,U_{a}=x,U_{b}=y\right)-W(x,y)\right].$

It follows that

(16) $\displaystyle\int\mathfrak{V}_{\mathcal{R}}W\,\mathrm{d}\pi^{2}$
$\displaystyle=2\mathbb{E}\left(e(\mathbb{H})-e(\mathbb{F})\right)$ (17)
$\displaystyle=2\mathbb{E}e(\mathbb{H})-(k)_{2}t(K_{2},W).$

###  3.2. Trajectories

In this subsection, we recap the notion of trajectories which we mentioned
informally in Theorem 1.1. We make several adjustments, following the way
trajectories were constructed in [12]. Firstly, we define trajectories not
only for graphons but for general kernels. Secondly, we define not only
forward evolution in time but also backward evolution. It turns out that in
order to allow for these generalizations, we cannot prescribe the time domain
for a trajectory in advance.

######  Definition 3.1.

Given a rule $\mathcal{R}$ and a kernel $W\in\mathcal{W}$, a _trajectory
starting at $W$_ is a differentiable function
$\Phi^{\cdot}W:I\to(\mathcal{W},\left\lVert\cdot\right\rVert_{\infty})$
defined on an open interval $I\subseteq\mathbb{R}$ containing zero, that
satisfies the autonomous differential equation

(18)
$\frac{\,\mathrm{d}}{\,\mathrm{d}t}\Phi^{t}W=\mathfrak{V}_{\>}\Phi^{t}W\;$

with the initial condition

(19) $\Phi^{0}W=W\;.\\\ $

The following theorem implies that if a trajectory starts a graphon (rather
than a general kernel), it is unique (provided we extended it maximally) and
is defined for all positive times. Such a trajectory is always defined for
some negative times (as $\mathcal{D}_{W}$ is open), but it might leave the
graphon space immediately (i.e., we might have $I_{W}=[0,\infty)$).

######  Theorem 3.2 (Theorem LABEL:FIRSTPAPER.thm:flow in [12]).

Suppose that $\mathcal{R}$ is a rule and $W\in\mathcal{W}$ is a kernel. Then
the following hold.

  1. (i)

There is an open interval $\mathcal{D}_{W}\subseteq\mathbb{R}$ containing $0$
and a trajectory $\Phi^{\cdot}W:\mathcal{D}_{W}\to\mathcal{W}$ starting at $W$
such that any other trajectory starting at $W$ is a restriction of
$\Phi^{\cdot}W$ to a subinterval of $\mathcal{D}_{W}$.

  2. (ii)

For any $u\in\mathcal{D}_{W}$ we have
$\mathcal{D}_{\Phi^{u}W}=\\{t\in\mathbb{R}:t+u\in\mathcal{D}_{W}\\}$ and for
every $t\in\mathcal{D}_{\Phi^{u}W}$ we have

$\Phi^{t}\Phi^{u}W=\Phi^{t+u}W.$

  3. (iii)

If $W\in\mathcal{W}_{0}$ is a graphon, the set
$I_{W}:=\\{t\in\mathcal{D}_{W}:\Phi^{t}W\in\mathcal{W}_{0}\\}$ is a closed
interval containing $[0,\infty)$.

######  Definition 3.3.

For $W\in\mathcal{W}_{0}$ we write $\mathrm{age}(W):=-\inf
I_{W}\in[0,\infty]$.

######  Remark 3.4 (Remark LABEL:FIRSTPAPER.rem:integral_form in [12]).

A trajectory $\Phi^{\cdot}W:I\to\mathcal{W}$ satisfies

$\Phi^{t}W=W+\int_{0}^{t}\mathfrak{V}_{\mathcal{R}}\Phi^{\tau}W\,\mathrm{d}\tau,\quad
t\in I,$

where the integral is defined with respect to the norm
$\left\lVert\cdot\right\rVert_{\infty}$.

The last preliminary result we shall need about trajectories says the
following. Let $\mathcal{R}$ be a rule and $\mathcal{A}$ be a set of graphons
which have a certain profile on a fixed rectangle
$\Omega_{1}\times\Omega_{2}$. Suppose that for each graphon in $\mathcal{A}$,
the velocity restricted to the rectangle $\Omega_{1}\times\Omega_{2}$ is zero.
Then each trajectory which starts in $\mathcal{A}$ stays confined to
$\mathcal{A}$.

######  Proposition 3.5 (Proposition LABEL:FIRSTPAPER.prop:zeroonasection in
[12]).

Let $\mathcal{R}$ be a rule and $\alpha:S\rightarrow[0,1]$ be a symmetric
function where
$S:=\Omega_{1}\times\Omega_{2}\cup\Omega_{2}\times\Omega_{1}\subset\Omega^{2}$.
Let $\mathcal{A}=\\{W\in\mathcal{W}_{0}:W{\restriction_{S}}=\alpha\\}$.
Suppose that for each $W\in\mathcal{A}$ we have
$(\mathfrak{V}_{\>}W){\restriction_{S}}=0$. Then for each $U\in\mathcal{A}$
and each $t\geq 0$ we have $\Phi^{t}U\in\mathcal{A}$.

###  3.3. Continuity properties of trajectories

In this subsection we assume that $\mathcal{R}$ is a rule of order $k$.

######  Lemma 3.6 (Lemma LABEL:FIRSTPAPER.lem:contderLinfty in [12]).

For every $W\in\mathcal{W}_{0}$ we have

(20) $-(k)_{2}\cdot W\leq\mathfrak{V}_{\mathcal{R}}W\leq(k)_{2}\cdot(1-W)\;.$

######  Lemma 3.7 (Lemma LABEL:FIRSTPAPER.lem:LinftyCont in [12]).

Write $C_{k}=2\binom{k}{2}^{2}2^{\binom{k}{2}}$. For every
$W\in\mathcal{W}_{0}$ and every $t,u\in[-\mathrm{age}(W),+\infty)$ we have

$\left\lVert\Phi^{t}W-\Phi^{u}W\right\rVert_{\infty}\leq(k)_{2}|t-u|,$

and for every $\delta>0$ we have

(21)
$\left\lVert\frac{\Phi^{\delta}W-W}{\delta}-\mathfrak{V}_{\mathcal{R}}W\right\rVert_{\infty}\leq
C_{k}(k)_{2}\delta.$

######  Theorem 3.8 (Theorem LABEL:FIRSTPAPER.thm:genome in [12]).

Write $C_{\square,k}=4\textstyle\binom{k}{2}^{2}2^{\binom{k}{2}}$. Then for
each $U,W\in\mathcal{W}_{0}$ and
$t\in[-\min(\mathrm{age}(U),\mathrm{age}(W)),+\infty)$, we have

$\left\lVert\Phi^{t}U-\Phi^{t}W\right\rVert_{\square}\leq\exp(C_{\square,k}|t|)\cdot\left\lVert
U-W\right\rVert_{\square}\;.$

###  3.4. Destinations and speed of convergence

Let $\mathcal{R}$ be a rule. We say that the trajectory of a graphon $U$ is
_convergent_ if there exists a _destination_ of $U$, that is, a graphon
denoted by $\mathrm{dest}_{\mathcal{R}}(U)$ such that
$\Phi^{t}U\xrightarrow{\square}\mathrm{dest}_{\mathcal{R}}(U)$ as
$t\to\infty$. We say that the flip process with rule $\mathcal{R}$ is
_convergent_ if all its trajectories converge.

######  Proposition 3.9 ([12, Proposition
LABEL:FIRSTPAPER.prop:destinations]).

If $W=\mathrm{dest}_{\mathcal{R}}(U)$ for some $U\in\mathcal{W}_{0}$, then
$\mathfrak{V}_{\mathcal{R}}W~{}=~{}0$.

For a rule $\mathcal{R}$, and $\delta>0$ we define the _lower convergence
time_ $\tau_{\mathcal{R}}^{-}(\delta)$ and the _upper convergence time_
$\tau_{\mathcal{R}}^{+}(\delta)$ by

$\displaystyle\tau_{\mathcal{R}}^{-}(\delta)$
$\displaystyle:=\sup\\{\inf\\{t:d_{\square}(\Phi^{t}W,\mathrm{dest}_{\mathcal{R}}(W))<\delta\\}:W\in\mathcal{W}_{0}\\}\;,$
$\displaystyle\tau_{\mathcal{R}}^{+}(\delta)$
$\displaystyle:=\sup\\{\sup\\{t:d_{\square}(\Phi^{t}W,\mathrm{dest}_{\mathcal{R}}(W))\geq\delta\\}:W\in\mathcal{W}_{0}\\}\;.$

##  4\. Ignorant flip processes

The first and in a sense the most trivial class of flip processes we introduce
are the ignorant flip processes. These are flip processes in which the
replacement graph is selected independently of the drawn graph.

######  Definition 4.1.

Let $k\in\mathbb{N}$. We say that a rule $\mathcal{R}$ of order $k$ is
_ignorant_ if for any $F,F^{\prime},H\in\mathcal{H}_{k}$ we have
$\mathcal{R}_{F,H}=\mathcal{R}_{F^{\prime},H}$. The _ignorant output density_
is $d:=\frac{1}{\binom{k}{2}}\sum_{H\in\mathcal{H}_{k}}\mathcal{R}_{F,H}e(H)$
(here $F$ is arbitrary).

Observe that the Erdős–Rényi flip process is an ignorant flip process of order
2 with output distribution
$\\{\mathcal{R}_{F,H}\\}_{H\in\mathcal{H}_{2}}=\boldsymbol{\delta}_{K_{2}}$
for each $F\in\mathcal{H}_{2}$.

Our main result about ignorant rules is Proposition 4.2, which explicitly
describes their trajectories, destinations, speed of convergence and age.

######  Proposition 4.2.

Let $k\in\mathbb{N}$. Suppose that $\mathcal{R}$ is an ignorant rule of order
$k$ with ignorant output density $d$. Then for each graphon
$W\in\mathcal{W}_{0}$ and $t\in I_{W}$ we have

(22) $\Phi^{t}W=d+(W-d)\cdot e^{-(k)_{2}t}.$

Hence, we have $\mathrm{dest}(W)\equiv d$ and

(23)
$\tau_{\mathcal{R}}^{-}(\delta)=\tau_{\mathcal{R}}^{+}(\delta)=\frac{1}{(k)_{2}}\ln\left(\frac{\max\\{d,1-d\\}}{\delta}\right)$

for each $0<\delta<\frac{1}{2}$. Furthermore, writing
$i_{W}:=\operatorname*{ess\,inf}(W)$ and $s_{W}:=\operatorname*{ess\,sup}(W)$,
we have

(24)
$\mathrm{age}(W)=\begin{cases}\frac{1}{(k)_{2}}\min\left\\{\ln\frac{d}{d-i_{W}}\;,\;\ln\frac{1-d}{s_{W}-d}\right\\}\quad&\text{if
}i_{W}<d<s_{W}\;,\\\ \frac{1}{(k)_{2}}\ln\frac{d}{d-i_{W}}\quad&\text{if
}i_{W}<s_{W}\leq d\;,\\\ \frac{1}{(k)_{2}}\ln\frac{1-d}{s_{W}-d}\quad&\text{if
}d\leq i_{W}<s_{W}\;,\\\ \infty&\text{ if }W\equiv d.\end{cases}$

In particular, $\mathrm{age}(W)$ is finite unless $W\equiv d$.

###### Proof.

Let $W\in\mathcal{W}_{0}$. We first compute the velocity
$\mathfrak{V}_{\mathcal{R}}$ using the notation preceding equation (15). Since
the distribution of $\mathbb{H}$ is independent of $(U_{v},v\in[k])$, by (15)
we have

$\displaystyle\mathfrak{V}_{\mathcal{R}}W(x,y)$ $\displaystyle=\sum_{a\neq
b}\left[\mathbb{P}\left(ab\in\mathbb{H}\,|\,U_{a}=x,U_{b}=y\right)-W(x,y)\right]$
$\displaystyle=2\mathbb{E}e(\mathbb{H})-(k)_{2}W(x,y)=(k)_{2}\left(d-W(x,y)\right).$

It is clear that the initial condition $\Phi^{t}W=W$ is satisfied. By the
uniqueness of trajectories, it is enough to verify that the function on the
right hand side of (22) satisfies the differential equation (18). For
$x,y\in\Omega$ we set $f(t)=d+(W(x,y)-d)\cdot e^{-(k)_{2}t}$. Observe that for
each $t\geq 0$ we have

$\frac{f(t+\varepsilon)-f(t)}{\varepsilon}\to
f^{\prime}(t)=(k)_{2}\left(d-W(x,y)\right)e^{-(k)_{2}t}=(k)_{2}\left(d-f(t)\right)$

as $\varepsilon\to 0$, where the convergence is uniform over all choices of
$(x,y)\in\Omega^{2}$ by Taylor’s theorem because $W$ is bounded. This implies
that (22) indeed describes the trajectory starting at $W$ under the ignorant
rule $\mathcal{R}$.

Clearly, all trajectories converge to the same destination, the constant-$d$
graphon. By (22) we have
$d_{\square}(\Phi^{t}W,d)\leq\left\lVert\Phi^{t}W-d\right\rVert_{\infty}\leq\max\\{d,1-d\\}e^{-(k)_{2}t}$,
with both equalities attained at the constant-$0$ graphon if $d\geq 1/2$ and
at the constant-$1$ graphon if $d\leq 1/2$. Hence, we have
$\tau_{\mathcal{R}}^{-}(\delta)=\tau_{\mathcal{R}}^{+}(\delta)=\frac{1}{(k)_{2}}\ln\left(\frac{\max\\{d,1-d\\}}{\delta}\right)$
for each $\delta\in(0,\frac{1}{2})$. Now observe that (22) tells us that for a
point $(x,y)$ where $W(x,y)<d$, the value of $\Phi^{-t}W$ dips below $0$ at
$t=\frac{1}{(k)_{2}}\ln\frac{d}{d-W(x,y)}$, and for a point $(x,y)$ where
$W(x,y)>d$, the value of $\Phi^{-t}W$ exceeds $1$ at
$t=\frac{1}{(k)_{2}}\ln\frac{1-d}{W(x,y)-d}$. This implies (24). ∎

##  5\. Stirring flip processes

All trajectories of ignorant flip processes converge to a constant given by
the ignorant output density. Being a bit less ignorant this time, we introduce
_stirring flip processes_ , which takes into account the edge count (but
nothing else) of the drawn graph. In this section we focus on _balanced_
stirring flip processes, in which the expected number of edges in the
replacement graph is equal to the number of edges in the drawn graph. In
Section 7 we will study _extremist flip processes_ , which are “very
unbalanced” stirring flip processes.

######  Definition 5.1.

Let $k\in\mathbb{N}$. We say that a rule $\mathcal{R}$ of order $k$ is
_stirring_ if for each $F$ and $F^{\prime}$ with $e(F)=e(F^{\prime})$ and each
$H$, we have $\mathcal{R}_{F,H}=\mathcal{R}_{F^{\prime},H}$. We say that the
rule $\mathcal{R}$ is _balanced_ if for each $F\in\mathcal{H}_{k}$ we have
$e(F)=\sum_{H\in\mathcal{H}_{k}}\mathcal{R}_{F,H}e(H)$.

Two natural examples of a balanced stirring rule are the rule where a drawn
graph with $\ell$ edges is replaced by the Erdős–Rényi uniform random graph
with $\ell$ edges and the rule where a drawn graph with $\ell$ edges is
replaced by the Erdős–Rényi binomial random graph with edge probability
$\ell/\binom{k}{2}$.

Our main result describes the trajectories of a stirring flip process in the
most important balanced case.

######  Proposition 5.2.

Suppose that $\mathcal{R}$ is a balanced stirring rule of order $k\geq 3$ and
let $W\in\mathcal{W}_{0}$. Then for every $t\in I_{W}$ we have

(25) $\begin{split}\Phi^{t}W(x,y)&=\left\lVert
W\right\rVert_{1}+(\deg_{W}(x)+\deg_{W}(y)-2\left\lVert
W\right\rVert_{1})\cdot e^{-t(k-1)_{2}}\\\
&\quad+(W(x,y)-\deg_{W}(x)-\deg_{W}(y)+\left\lVert W\right\rVert_{1})\cdot
e^{-t((k)_{2}-2)}\;.\end{split}$

In particular, the edge density stays constant along the trajectory and
$\mathrm{dest}(W)=\left\lVert W\right\rVert_{1}$.

###### Proof.

Let $W\in\mathcal{W}_{0}$ and set $d:=\left\lVert W\right\rVert_{1}$. The
following is our key claim.

######  Claim 5.3.

Given a graphon $W\in\mathcal{W}_{0}$, for all $x,y\in\Omega$ we have

(26)
$\mathfrak{V}_{\mathcal{R}}W(x,y)=(2k-4)(\deg_{W}(x)+\deg_{W}(y))+(k-2)_{2}d-\left((k)_{2}-2\right)W(x,y).$

Before we prove this claim, let us first demonstrate how it implies our
theorem. By the uniqueness of trajectories, it is enough to verify that (25)
satisfies the differential equation (18). Write $f_{(x,y)}(t)$ for the right-
hand side of (25), set $U_{t}$ to be the graphon given by
$U_{t}(x,y):=f_{(x,y)}(t)$ and set
$g_{x}(t):=\deg_{U_{t}}(x)=d+(\deg_{W}(x)-d)e^{-t(k-1)_{2}}$. Observe that

$\displaystyle f^{\prime}_{(x,y)}(t)$
$\displaystyle=-(k-1)_{2}(\deg_{W}(x)+\deg_{W}(y)-2d)e^{-t(k-1)_{2}}$
$\displaystyle\;\quad-((k)_{2}-2)(W(x,y)-\deg_{W}(x)-\deg_{W}(y)+d)e^{-t((k)_{2}-2)}$
$\displaystyle=\left((k)_{2}-2\right)(d-f_{(x,y)}(t))+2(k-2)(\deg_{W}(x)+\deg_{W}(y)-2d)e^{-t(k-1)_{2}}$
$\displaystyle=(2k-4)(g_{x}(t)+g_{y}(t))+(k-2)_{2}d-\left((k)_{2}-2\right)f_{(x,y)}(t)\;.$

Furthermore, for each $t\geq 0$ the convergence in
$(f_{(x,y)}(t+\varepsilon)-f_{(x,y)}(t))/\varepsilon\to f^{\prime}_{(x,y)}(t)$
is uniform over all choices of $(x,y)\in\Omega^{2}$ by Taylor’s theorem
because $W$ is bounded. This implies that
$\frac{\,\mathrm{d}}{\,\mathrm{d}t}U_{t}=\mathfrak{V}_{\mathcal{R}}U_{t}$ in
the norm $\left\lVert\cdot\right\rVert_{\infty}$. Moreover, we have that
$U_{0}=W$. Hence, by uniqueness (25) indeed describes the trajectory starting
at $W$ under a balanced stirring rule.

It remains to prove Claim 5.3.

###### Proof of Claim 5.3.

Let $W\in\mathcal{W}_{0}$ and $x,y\in\Omega$. Using the notation preceding
equation (15), observe that

(27)
$\begin{split}\mathbb{E}\left(e(\mathbb{F})\,|\,U_{1}=x,U_{2}=y\right)&=\frac{1}{2}\sum_{a\neq
b}\mathbb{P}\left(ab\in\mathbb{F}\,|\,U_{1}=x,U_{2}=y\right)\\\
&=W(x,y)+(k-2)\left(\deg_{W}(x)+\deg_{W}(y)\right)+\binom{k-2}{2}d.\end{split}$

Setting
$q_{m}(ab):=\mathbb{P}\left(ab\in\mathbb{H}\,|\,e(\mathbb{F})=m\right)$, we
have

(28) $\sum_{a\neq
b}q_{m}(ab)=2\mathbb{E}\left(e(\mathbb{H})\,|\,e(\mathbb{F})=m\right)=2m.$

Since the distribution of $\mathbb{F}$ is invariant under permutation of
vertices, for any pair of distinct vertices $a$ and $b$ the quantity
$\mathbb{P}\left(e(\mathbb{F})=m\,|\,U_{a}=x,U_{b}=y\right)$ is the same; we
shall denote it by $p_{x,y}(m)$. We have

(29)
$\mathbb{P}\left(ab\in\mathbb{H}\,|\,U_{a}=x,U_{b}=y\right)=\sum_{m=0}^{\textstyle\binom{k}{2}}p_{x,y}(m)q_{m}(ab).$

By summing (29) over all pairs $a,b$ of distinct vertices, interchanging the
order of summation, and applying (28), we obtain

$\displaystyle\sum_{a\neq
b}\mathbb{P}\left(ab\in\mathbb{H}\,|\,U_{a}=x,U_{b}=y\right)=\sum_{m=0}^{\textstyle\binom{k}{2}}p_{x,y}(m)\sum_{a\neq
b}q_{m}(ab)$
$\displaystyle=\sum_{m=0}^{\textstyle\binom{k}{2}}\left[p_{x,y}(m)\cdot
2m\right]$
$\displaystyle=2\mathbb{E}\left(e(\mathbb{F})\,|\,U_{1}=x,U_{2}=y\right).$

Now by recalling (15) and applying (27), we obtain

$\displaystyle\mathfrak{V}_{\mathcal{R}}W(x,y)$ $\displaystyle=\sum_{a\neq
b}\left[\mathbb{P}\left(ab\in\mathbb{H}\,|\,U_{a}=x,U_{b}=y\right)-W(x,y)\right],$
$\displaystyle=2\mathbb{E}\left(e(\mathbb{F})\,|\,U_{1}=x,U_{2}=y\right)-(k)_{2}W(x,y)$
$\displaystyle=(2k-4)(\deg_{W}(x)+\deg_{W}(y))+(k-2)_{2}d-W(x,y)\left((k)_{2}-2\right)$

as required. ∎

This completes the proof of the proposition. ∎

###  5.1. Age of a balanced stirring process

Recall that the age of a graphon $W$ is the infimum of times $t\geq 0$ for
which the range of $\Phi^{-t}W$ is not wholly contained in $[0,1]$. That is,
given a balanced stirring rule as in Proposition 5.2, we want to know the
infimum of $t\geq 0$ where we have for some $x,y\in\Omega$ that

(30) $\begin{split}\left\lVert
W\right\rVert_{1}&+(\deg_{W}(x)+\deg_{W}(y)-2\left\lVert
W\right\rVert_{1})\cdot e^{t(k-1)_{2}}+\\\
&+(W(x,y)-\deg_{W}(x)-\deg_{W}(y)+\left\lVert W\right\rVert_{1})\cdot
e^{t((k)_{2}-2)}\;\end{split}$

is more than 1 or less than 0. While there is no simple formula to deduce the
age from (30) in general because we have two exponential terms with different
coefficients and exponents, in the next proposition we give a formula for the
age in two special cases: degree-regular graphons and graphons with a
separable form. These correspond to the cases where only one exponential term
has a positive coefficient. Further, we show that the age is finite except
when the graphon is constant.

######  Proposition 5.4.

Suppose that $\mathcal{R}$ is a balanced stirring rule of order $k\geq 3$.
Then the following hold for all $W\in\mathcal{W}_{0}$. Write $d:=\left\lVert
W\right\rVert_{1}$. If $W=d$, then $\mathrm{age}(W)=\infty$. Otherwise, we
have $\mathrm{age}(W)<\infty$ and in particular:

  1. (i)

if $W$ is degree-regular, then

$\mathrm{age}(W)=\frac{1}{(k)_{2}-2}\cdot\min\left\\{\ln\frac{d}{d-\operatorname*{ess\,inf}(W)}\;,\;\ln\frac{1-d}{\operatorname*{ess\,sup}(W)-d}\right\\}\;;$

  2. (ii)

if $W$ is of the form $W(x,y)=f(x)+f(y)$, then

$\mathrm{age}(W)=\frac{1}{(k-1)_{1}}\cdot\min\left\\{\ln\frac{d}{d-\operatorname*{ess\,inf}(W)}\;,\;\ln\frac{1-d}{\operatorname*{ess\,sup}(W)-d}\right\\}\;.$

###### Proof.

$W=d$ is clearly a fixed point, so we have $\mathrm{age}(W)=\infty$. We now
show that $\mathrm{age}(W)=\infty$ only if $W=d$. Suppose that
$\mathrm{age}(W)=\infty$. Since $(k-1)_{2}\neq(k)_{2}-2$, the expression in
(30) can stay in $[0,1]$ for all $x,y\in\Omega$ only if the coefficients of
both exponential terms are zero. The first one implies $\deg_{W}\equiv d$ and
then the second one implies $W\equiv d$.

Hence, we further assume that $W$ is not constant, which implies
$\operatorname*{ess\,inf}W<d<\operatorname*{ess\,sup}W$. In the case (i), the
equation (30) simplifies to

$d+(W(x,y)-d)\cdot e^{t((k)_{2}-2)}\;,$

and then the formula for age indeed expresses the time when the values of
$\Phi^{-t}W$ first cross one of the two thresholds $0$ and $1$.

The case (ii) is equivalent to $W(x,y)=\deg_{W}(x)+\deg_{W}(y)-d$. Hence (30)
simplifies to

$d+(W(x,y)-d)\cdot e^{t(k-1)_{1}}\;,$

which implies the age in the same way as in the case (i). ∎

##  6\. Complementing flip processes

The _complementing rule of order $k$_ is the rule of order $k$ where the
replacement graph is the complement of the drawn graph. Our main result about
complementing rules is Proposition 6.1, which explicitly describes their
trajectories, destinations, speed of convergence and age.

######  Proposition 6.1.

Suppose that $\mathcal{R}$ is the complementing rule of order $k\geq 2$. Then
for each graphon $W\in\mathcal{W}_{0}$ and $t\in I_{W}$ we have

(31) $\Phi^{t}W(x,y)=\frac{1}{2}+\left(W(x,y)-\frac{1}{2}\right)\cdot
e^{-2(k)_{2}t}\;.$

Hence, we have $\mathrm{dest}(W)\equiv 1/2$ and

(32)
$\tau_{\mathcal{R}}^{-}(\delta)=\tau_{\mathcal{R}}^{+}(\delta)=\frac{-\ln(2\delta)}{2(k)_{2}}$

for each $0<\delta<\frac{1}{2}$. Furthermore, writing
$i_{W}:=\operatorname*{ess\,inf}(W)$ and $s_{W}:=\operatorname*{ess\,sup}(W)$,
we have

(33)
$\mathrm{age}(W)=\begin{cases}\frac{1}{2(k)_{2}}\min\left\\{\ln\frac{1}{1-2i_{W}}\;,\;\ln\frac{1}{2s_{W}-1}\right\\}\quad&\text{if
}i_{W}<1/2<s_{W}\;,\\\ \frac{1}{2(k)_{2}}\ln\frac{1}{1-2i_{W}}\quad&\text{if
}i_{W}<s_{W}\leq 1/2\;,\\\ \frac{1}{2(k)_{2}}\ln\frac{1}{2s_{W}}\quad&\text{if
}1/2\leq i_{W}<s_{W}\;,\\\ \infty&\text{ if }W\equiv 1/2.\end{cases}$

###### Proof.

We calculate the velocity using the notation preceding the formula (15). Note
that $ab\in\mathbb{H}$ if and only if $ab\notin\mathbb{F}$, so

$\mathbb{P}\left(ab\in\mathbb{H}\,|\,U_{a}=x,U_{b}=y\right)=\mathbb{P}\left(ab\notin\mathbb{F}\,|\,U_{a}=x,U_{b}=y\right)=1-W(x,y)\;.$

Hence, by (15) we have

$\mathfrak{V}_{\mathcal{R}}W(x,y)=\sum_{1\leq a\neq b\leq
k}(1-W(x,y)-W(x,y))=(k)_{2}(1-2W(x,y))\;.$

Write $f_{(x,y)}(t)$ for the right-hand side of (31). Observe that for each
$t\geq 0$ we have

$\frac{f_{(x,y)}(t+\varepsilon)-f_{(x,y)}(t)}{\varepsilon}\to
f^{\prime}_{(x,y)}(t)=(k)_{2}(1-2W(x,y))e^{-2(k)_{2}t}=(k)_{2}\left(1-2f_{(x,y)}(t)\right)$

as $\varepsilon\to 0$, where the convergence is uniform over all choices of
$(x,y)\in\Omega^{2}$ by Taylor’s theorem because $W$ is bounded. Since the
trajectory $\Phi^{\cdot}W$ is unique by Theorem 3.2, we have
$\Phi^{t}W(x,y)=f_{(x,y)}(t)$ as desired.

Clearly, the unique destination is the constant-$\frac{1}{2}$ graphon. By (22)
we have
$d_{\square}(\Phi^{t}W,\frac{1}{2})\leq\left\lVert\Phi^{t}W-\frac{1}{2}\right\rVert_{\infty}\leq\frac{1}{2}e^{-2(k)_{2}t}$,
with both equalities attained at the constant-$0$ and constant-$1$ graphons.
Hence, we have
$\tau_{\mathcal{R}}^{-}(\delta)=\tau_{\mathcal{R}}^{+}(\delta)=\frac{-\ln(2\delta)}{2(k)_{2}}$
for each $\delta\in(0,\frac{1}{2})$. Note that (31) tells us that for a point
$(x,y)$ where $W(x,y)<\frac{1}{2}$, the value of $\Phi^{-t}W$ dips below $0$
at $t=-\frac{1}{2(k)_{2}}\ln(1-2W(x,y))$, and for a point $(x,y)$ where
$W(x,y)>\frac{1}{2}$, the value of $\Phi^{-t}W$ exceeds $1$ at
$t=-\frac{1}{2(k)_{2}}\ln(2W(x,y)-1)$. This implies (33). ∎

We conjecture that the complementing flip process exhibits the fastest
convergence among flip processes whose trajectories converge to a single
destination. Observe that the convergence time of the complementing flip
process (see (32)) is half that of an ignorant process with output density
$1/2$ (cf. (23)).

######  Conjecture 6.2.

Suppose that $\mathcal{R}$ is a convergent flip process of order $k$ with a
single destination. Then for each $\delta\in(0,\frac{1}{2})$ we have
$\tau_{\mathcal{R}}^{-}(\delta)\geq\frac{-\ln(2\delta)}{2(k)_{2}}$.

##  7\. Extremist flip processes

In this section we define the extremist rules and prove results about their
behaviour.

######  Definition 7.1 (Extremist rule).

Let $k\in\mathbb{N}$. The _extremist_ rule $\mathcal{R}$ of order $k$ is
defined by

(34) $\mathcal{R}_{F,H}=\begin{cases}1&\textrm{ if
}e(F)<\frac{1}{2}\binom{k}{2}\textrm{ and }H=\overline{K_{k}},\\\ 1&\textrm{
if }e(F)>\frac{1}{2}\binom{k}{2}\textrm{ and }H=K_{k},\\\ 1&\textrm{ if
}e(F)=\frac{1}{2}\binom{k}{2}\textrm{ and }H=F,\\\ 0&\textrm{ otherwise
}.\end{cases}$

A possible variation of the extremist rule is to permit the replacement of
graphs with $\binom{k}{2}/2$ edges by a clique or empty graph with equal
probabilities. In fact, most proofs from this section (except for Theorem 7.6)
work for this variation, but for the sake of simplicity we shall not consider
it.

###  7.1. Behaviour on constants

We begin by considering the behaviour of trajectories under extremist rules on
constant graphons. Recall that a trajectory that starts with a constant
graphon takes values only among constant graphons and the velocity is a
constant function (see [12, Corollary LABEL:FIRSTPAPER.coro:steps_stay]).
Therefore, we shall identify the constant-$p$ kernel with the number $p$. We
prove the following proposition, which implies that the trajectory of an
extremist rule which starts from the constant-$p$ graphon converges to $0$ if
$p<1/2$, to $1$ if $p>1/2$ and is fixed for $p=1/2$.

######  Proposition 7.2.

If $\mathcal{R}$ is the extremist rule of order $k\geq 3$, then we have
$\mathfrak{V}_{\mathcal{R}}(p)=0$ for $p\in\left\\{0,1/2,1\right\\}$,
$\mathfrak{V}_{\mathcal{R}}(p)<0$ for $p\in(0,1/2)$ and
$\mathfrak{V}_{\mathcal{R}}(p)>0$ for $p\in(1/2,1)$.

###### Proof.

Since $\mathfrak{V}_{\mathcal{R}}(p)$ is a constant kernel, we have
$\mathfrak{V}_{\mathcal{R}}(p)\equiv\int_{\Omega^{2}}\mathfrak{V}_{\mathcal{R}}(p)$.
Therefore, by (17) and denoting by $\mathbb{G}$ the random graph
$\mathbb{G}(k,p)$, we have

$\displaystyle\mathfrak{V}_{\mathcal{R}}(p)$
$\displaystyle=2\left[\textstyle\binom{k}{2}\mathbb{P}\left(e(\mathbb{G})>\textstyle\binom{k}{2}/2\right)+\textstyle\binom{k}{2}/2\cdot\mathbb{P}\left(e(\mathbb{G})=\textstyle\binom{k}{2}/2\right)\right]-(k)_{2}p.$

Writing $n=\binom{k}{2}$ and $B_{n,p}$ for a binomial random variable with
parameters $n$ and $p$, we have

$\displaystyle\mathfrak{V}_{\mathcal{R}}(p)$
$\displaystyle=2n\mathbb{P}(B_{n,p}>n/2)+n\mathbb{P}(B_{n,p}=n/2)-2np$
$\displaystyle=n\big{(}\mathbb{P}(B_{n,p}>n/2)+\mathbb{P}(B_{n,p}\geq
n/2)-2p\big{)}.$

It is clear that $\mathfrak{V}_{\mathcal{R}}(p)=0$ for
$p\in\left\\{0,1/2,1\right\\}$. To prove the proposition, it is enough to show
that for the function

$f_{n}(p):=\mathbb{P}(B_{n,p}>n/2)+\mathbb{P}(B_{n,p}\geq n/2)$

its derivative $f_{n}^{\prime}$ is strictly increasing on $(0,1/2)$ and
strictly decreasing on $(1/2,1)$. Indeed, this implies that $p\mapsto
f_{n}(p)$ is strictly convex on $(0,1/2)$ and strictly concave on $(1/2,1)$.
Then, these properties are inherited by
$p\mapsto\mathfrak{V}_{\mathcal{R}}(p)$, thereby implying that
$\mathfrak{V}_{\mathcal{R}}(p)$ is negative on $(0,1/2)$ and positive on
$(1/2,1)$. Observe that

$\displaystyle\frac{\,\mathrm{d}}{\,\mathrm{d}p}\left(\mathbb{P}(B_{n,p}=k)\right)$
$\displaystyle=\frac{\,\mathrm{d}}{\,\mathrm{d}p}\left(\binom{n}{k}p^{k}(1-p)^{n-k}\right)$
$\displaystyle=\binom{n}{k}\left(kp^{k-1}(1-p)^{n-k}-(n-k)p^{k}(1-p)^{n-k-1}\right)$
$\displaystyle=n\left[\binom{n-1}{k-1}p^{k-1}(1-p)^{n-k}-\binom{n-1}{k}p^{k}(1-p)^{n-k-1}\right]$
$\displaystyle=n\left[\mathbb{P}(B_{n-1,p}=k-1)-\mathbb{P}(B_{n-1,p}=k)\right].$

Therefore, we have

$\displaystyle f_{n}^{\prime}(p)$
$\displaystyle=n\sum_{k>n/2}\left[\mathbb{P}(B_{n-1,p}=k-1)-\mathbb{P}(B_{n-1,p}=k)\right]$
$\displaystyle\quad+n\sum_{k\geq
n/2}\left[\mathbb{P}(B_{n-1,p}=k-1)-\mathbb{P}(B_{n-1,p}=k)\right]$
$\displaystyle=n\cdot\left(\mathbb{P}\left(B_{n-1,p}=\left\lfloor\frac{n-1}{2}\right\rfloor\right)+\mathbb{P}\left(B_{n-1,p}=\left\lceil\frac{n-1}{2}\right\rceil\right)\right)$
$\displaystyle=n\cdot\begin{cases}2\mathbb{P}(B_{n-1,p}=\left\lfloor\frac{n-1}{2}\right\rfloor),&\quad
n\text{ odd}\\\
\mathbb{P}(B_{n-1,p}=\left\lfloor\frac{n-1}{2}\right\rfloor)\left(1+\frac{p}{1-p}\right)&\quad
n\text{ even}\end{cases}$ $\displaystyle=\left(1+\mathbb{I}_{n\text{
odd}}\right)n\cdot\binom{n-1}{\left\lfloor\frac{n-1}{2}\right\rfloor}(p(1-p))^{\left\lfloor\frac{n-1}{2}\right\rfloor},$

Now $k\geq 3$ implies that $\left\lfloor\frac{n-1}{2}\right\rfloor\geq 1$, so
the polynomial $f^{\prime}_{n}(p)$ inherits from the parabola $p(1-p)$ the
property of being strictly increasing on $(0,1/2)$ and strictly decreasing on
$(1/2,1)$. This completes our proof. ∎

###  7.2. Density thresholds

In the previous subsection we saw that for constant graphons we have
$\mathrm{dest}_{\mathcal{R}}(W)=0$ as soon as the density of $W$ is below
$1/2$. In this subsection we consider when we start with an arbitrary initial
graphon $W$ and investigate what density guarantees
$\mathrm{dest}_{\mathcal{R}}(W)=0$. We define the _density threshold_ for the
extremist rule $\mathcal{R}$ of order $k\geq 3$ to be

$\theta(k):=\sup\\{p\in[0,1]:\forall W\in\mathcal{W}_{0}\ \left\lVert
W\right\rVert_{1}\leq p\text{ implies }\mathrm{dest}_{\mathcal{R}}(W)=0\\}.$

In the following proposition, we collect a few useful properties related to
the density threshold.

######  Proposition 7.3.

The following holds for the extremist rule $\mathcal{R}$ of order $k\geq 3$.

  1. (i)

For every $W\in\mathcal{W}_{0}$ and every $t\in I_{W}$ we have
$\Phi^{t}(1-W)=1-\Phi^{t}W$. In particular, if
$\mathrm{dest}_{\mathcal{R}}(W)=0$, then $\mathrm{dest}_{\mathcal{R}}(1-W)=1$.

  2. (ii)

For each $W\in\mathcal{W}_{0}$ satisfying $\left\lVert
W\right\rVert_{1}>1-\theta(k)$ we have $\mathrm{dest}_{\mathcal{R}}(W)=1$.

  3. (iii)

$\theta(k)\leq 1/2$.

###### Proof.

First we show (i). From formula (15) it is easy to see that for any graphon
$W$ we have $\mathfrak{V}_{\>}(1-W)=-\mathfrak{V}_{\>}W$, so
$\frac{\,\mathrm{d}}{\,\mathrm{d}t}(1-\Phi^{t}W)=-\mathfrak{V}_{\>}\Phi^{t}W=\mathfrak{V}_{\>}(1-\Phi^{t}(W))$,
that is, $t\mapsto 1-\Phi^{t}W$ is a trajectory. Since it starts at the same
graphon as the trajectory $t\mapsto\Phi^{t}(1-W)$, by uniqueness (see Theorem
3.2) it follows that $\Phi^{t}(1-W)=1-\Phi^{t}W$ for every $t\in I_{W}$. The
second conclusion is obvious.

To prove (ii), let $W\in\mathcal{W}_{0}$ satisfy $\left\lVert
W\right\rVert_{1}>1-\theta(k)$. Since $\left\lVert
1-W\right\rVert_{1}=1-\left\lVert W\right\rVert_{1}<\theta(k)$, we have
$\mathrm{dest}_{\mathcal{R}}(1-W)=0$ and therefore (i) implies
$\mathrm{dest}_{\mathcal{R}}(W)=1$.

Part (iii) follows from the fact that the constant-$1/2$ graphon $W$ satisfies
$\mathrm{dest}_{\mathcal{R}}(W)=1/2$. ∎

We prove the following lower bound on the density threshold. In particular, we
show that the density threshold is strictly positive for $k\geq 5$.

######  Theorem 7.4.

Let $k\geq 5$ be an integer and define
$\sigma(k):=\max\\{2^{-4-24/(k-5)},1/2-\sqrt{48/k}\\}$ for $k\geq 6$ and
$\sigma(5)=1/30$. For the extremist rule $\mathcal{R}$ of order $k$ we have
that

$\theta(k)\geq\sigma(k)>0.$

###### Proof.

The following is our key claim.

######  Claim 7.5.

Given a graphon $U\in\mathcal{W}_{0}$ satisfying $\left\lVert
U\right\rVert_{1}\leq\sigma(k)$, we have

(35)
$\int\mathfrak{V}_{\mathcal{R}}U\,\mathrm{d}\pi^{2}\leq-\binom{k}{2}\left\lVert
U\right\rVert_{1}.$

Before we prove this claim, let us first demonstrate how it implies our
theorem. Fix $W\in\mathcal{W}_{0}$ satisfying $\left\lVert
W\right\rVert_{1}\leq\sigma(k)$. Consider the function
$f(t):=\left\lVert\Phi^{t}W\right\rVert_{1}$ defined for $t\in[0,\infty)$.
Aiming to apply Lemma 2.2 with $D=\sigma(k)$, we note that $f(0)\leq\sigma(k)$
and $f(t)\geq 0$ for all $t\geq 0$. We argue that
$f^{\prime}(t)=\int\mathfrak{V}_{\mathcal{R}}\Phi^{t}W\,\mathrm{d}\pi^{2}$.
Indeed, we have that

$f^{\prime}(t)=\lim_{\varepsilon\rightarrow
0}\frac{\left\lVert\Phi^{t+\varepsilon}W\right\rVert_{1}-\left\lVert\Phi^{t}W\right\rVert_{1}}{\varepsilon}=\lim_{\varepsilon\rightarrow
0}\int\frac{\Phi^{t+\varepsilon}W-\Phi^{t}W}{\varepsilon}\,\mathrm{d}\pi^{2}.$

Now by Lemma 3.7 the integrand is $O(\varepsilon)$-close to
$\mathfrak{V}_{\mathcal{R}}\Phi^{t}W$ in the $L^{\infty}$-norm (and thus in
the $L^{1}$-norm), so in the limit we get
$f^{\prime}(t)=\int\mathfrak{V}_{\mathcal{R}}\Phi^{t}W\,\mathrm{d}\pi^{2}$.
Together with (35) we get that $f^{\prime}(t)\leq-\textstyle\binom{k}{2}f(t)$
whenever $f(t)\leq\sigma(k)$, so by Lemma 2.2 we have $f(t)\leq
f(0)e^{-\binom{k}{2}t}$ for all $t\in[0,\infty)$. Therefore, it follows that
$\mathrm{dest}_{\mathcal{R}}(W)=0$ and we conclude that
$\theta(k)\geq\sigma(k)>0$.

It remains to prove Claim 7.5.

###### Proof of Claim 7.5.

Set $p:=\left\lVert U\right\rVert_{1}$. Sample $\mathbb{F}\sim\mathbb{G}(k,U)$
and sample $\mathbb{H}$ according to the distribution
$\mathbb{P}\left(\mathbb{H}=H\,|\,\mathbb{F}=F\right)=\mathcal{R}_{F,H}$. We
first obtain an upper bound for $\mathbb{E}e(\mathbb{H})$. Since
$\mathbb{E}\left(e(\mathbb{H})\,|\,\mathbb{F}=F\right)=0$ for any
$F\in\mathcal{H}_{k}$ with fewer than $\frac{1}{2}\binom{k}{2}$ edges, we have

(36)
$\mathbb{E}e(\mathbb{H})\leq\binom{k}{2}\mathbb{P}\left(e(\mathbb{F})\geq\frac{1}{2}\binom{k}{2}\right).$

Now suppose that we have

(37)
$\mathbb{P}\left(e(\mathbb{F})\geq\frac{1}{2}\binom{k}{2}\right)\leq\frac{p}{2}.$

Then by (17) and (36) we conclude that

$\int\mathfrak{V}_{\mathcal{R}}U\,\mathrm{d}\pi^{2}=2\mathbb{E}e(\mathbb{H})-(k)_{2}\cdot
p\leq p\left(\binom{k}{2}-(k)_{2}\right)=-p\binom{k}{2},$

which yields (35). Hence, it remains to prove (37).

We begin with $k=5$ and $p\leq 1/30$. Note that if $\mathbb{F}$ has at least
$\frac{1}{2}\textstyle\binom{k}{2}=5$ edges then it has a matching with $2$
edges. There are $\binom{5}{2}\binom{3}{2}/2=15$ such matchings in $K_{5}$ and
each of them appears in $\mathbb{F}$ with probability $p^{2}$ (as each edge
occurs independently with probability $p$), so we have

$\mathbb{P}\left(e(\mathbb{F})\geq\frac{1}{2}\binom{k}{2}\right)\leq\mathbb{P}\left(\mathbb{F}\text{
contains a $2$-matching}\right)\leq 15p^{2}\leq\frac{p}{2}.$

Next, we consider $k\geq 6$ and $p\leq 2^{-4-24/(k-5)}$. We partition $K_{k}$
into disjoint maximum matchings $M_{1},\dots,M_{r}$, with
$r=\binom{k}{2}/\left\lfloor\frac{k}{2}\right\rfloor\in\\{k-1,k\\}$. If
$e(\mathbb{F})\geq\binom{k}{2}/2$ then there exists $i\in[r]$ such that

$e(\mathbb{F}\cap
M_{i})\geq\left\lceil\frac{\textstyle\binom{k}{2}}{2r}\right\rceil=\left\lceil\frac{\left\lfloor
k/2\right\rfloor}{2}\right\rceil=\left\lfloor\frac{k+2}{4}\right\rfloor=:k^{\prime}\;.$

Therefore, using $r\leq k\leq 2^{k/2}$ and $\binom{\lfloor
k/2\rfloor}{k^{\prime}}\leq 2^{k/2}$, we have

$\mathbb{P}\left(e(\mathbb{F})\geq\frac{1}{2}\binom{k}{2}\right)\leq\sum_{i\in[r]}\mathbb{P}\left(e(\mathbb{F}\cap
M_{i})\geq k^{\prime}\right)\leq r\binom{\lfloor
k/2\rfloor}{k^{\prime}}p^{k^{\prime}}\leq 2^{k}p^{(k-1)/4}\leq\frac{p}{2}.$

Finally, we consider $2^{-4-24/(k-5)}\leq p\leq 1/2-\sqrt{48/k}$; here we may
assume that $k\geq 192$. We consider the function $f(G):=e(G)/(v(G)-1)$. Since
$f$ varies by at most $1$ under the editing of edges incident to any fixed
vertex, by [18, Theorem 10.3] we obtain

$\mathbb{P}\left(e(\mathbb{F})\geq\frac{1}{2}\binom{k}{2}\right)=\mathbb{P}\left(f(\mathbb{F})\geq\mathbb{E}f(\mathbb{F})+(\tfrac{1}{2}-p)k/2\right)\leq\exp\left(-\frac{(1/2-p)^{2}k}{8}\right).$

Now we have $e>2$ and $\frac{(1/2-p)^{2}k}{8}\geq 6\geq 5+\frac{24}{k-5}$, so
we obtain

$\mathbb{P}\left(e(\mathbb{F})\geq\textstyle\binom{k}{2}/2\right)\leq
2^{-5-24/(k-5)}\leq\frac{p}{2}$

as required. ∎

This completes our proof. ∎

Now we show that the results of Theorem 7.4 cannot be extended to
$k\in\\{3,4\\}$.

######  Theorem 7.6.

$\theta(3)=\theta(4)=0$.

###### Proof.

Let $\mathcal{R}$ be the extremist rule of order $k\in\\{3,4\\}$. Define

$\displaystyle B_{1}$
$\displaystyle:=\left\\{(F,a,b):F\in\mathcal{H}_{k},e(F)<\frac{1}{2}\binom{k}{2},ab\in
E(F)\right\\}\ \textrm{ and }$ $\displaystyle B_{2}$
$\displaystyle:=\left\\{(F,a,b):F\in\mathcal{H}_{k},e(F)>\frac{1}{2}\binom{k}{2},ab\notin
E(F)\right\\}.$

By (14) and (34), for each $W\in\mathcal{W}_{0}$ and each $(x,y)\in\Omega^{2}$
we have

(38) $\mathfrak{V}_{\mathcal{R}}W(x,y)=\sum_{(F,a,b)\in
B_{2}}t_{\mathrm{ind}}^{(x,y)}(F^{a,b},W)-\sum_{(F,a,b)\in
B_{1}}t_{\mathrm{ind}}^{(x,y)}(F^{a,b},W).$

We shall construct a sequence $(W_{n})_{n\in\mathbb{N}}$ of graphons so that
$\left\lVert W_{n}\right\rVert_{1}\to 0$ as $n\to\infty$ and for each
$n\in\mathbb{N}$ we have
$\left\lVert\Phi^{t}W_{n}\right\rVert_{\square}\nrightarrow 0$ as
$t\to\infty$. Fix an arbitrary sequence $(\Omega_{n})_{n\in\mathbb{N}}$ of
subsets of $\Omega$ such that for each $n\in\mathbb{N}$ we have
$\pi(\Omega_{n})=1/n$ and $\Omega_{n+1}\subseteq\Omega_{n}$. For each
$n\in\mathbb{N}$ set
$S_{n}:=((\Omega\setminus\Omega_{n})\times\Omega_{n})\cup(\Omega_{n}\times(\Omega\setminus\Omega_{n}))$
and $\mathcal{A}_{n}:=\\{W\in\mathcal{W}_{0}:W{\restriction_{S_{n}}}=1\\}$.
For each $n\in\mathbb{N}$ define the graphon $W_{n}:=\mathbb{I}_{S_{n}}$. Note
that $\left\lVert
W_{n}\right\rVert_{1}=\frac{2}{n}\left(1-\frac{1}{n}\right)\to 0$ as
$n\to\infty$.

Fix $n\in\mathbb{N}$. We have $W_{n}\in\mathcal{A}_{n}$. By Theorem 3.2 there
is a unique trajectory $\Phi^{t}W_{n}$ on $[0,\infty)$. Let
$U\in\mathcal{A}_{n}$. For any $(F,a,b)\in B_{1}\cup B_{2}$ and $(x,y)\in
S_{n}$ we have $t_{\mathrm{ind}}^{(x,y)}(F^{a,b},U)=0$, so by (38) we have
$(\mathfrak{V}_{\mathcal{R}}U){\restriction_{S_{n}}}=0$. Now by applying
Proposition 3.5 with $\mathcal{A}_{n}$ we have
$\Phi^{t}W_{n}\in\mathcal{A}_{n}$ for all $t\in[0,\infty)$. We have
$\left\lVert\Phi^{t}W_{n}\right\rVert_{\square}\geq\frac{2}{n}\left(1-\frac{1}{n}\right)$
for all $t\in[0,\infty)$; in particular,
$\left\lVert\Phi^{t}W_{n}\right\rVert_{\square}\nrightarrow 0$ as
$t\to\infty$. Hence, we have $\theta(3)=\theta(4)=0$. ∎

We also prove an upper bound on the density threshold.

######  Theorem 7.7.

There exists $K\in\mathbb{N}$ such that for every $k\geq K$, setting
$C_{k}:=(k)_{2}^{2}2^{\binom{k}{2}-1}$, we have
$\theta(k)\leq\frac{1}{2}-\frac{(k)_{2}}{2\cdot 10^{5}C_{k}}$.

###### Proof.

Let $C$ be the constant returned by Theorem 2.14 and set $K:=400C^{2}$. Let
$\mathcal{R}$ be the extremist rule of order $k\geq K$ and set
$f(k):=\frac{(k)_{2}}{2\cdot 10^{5}C_{k}}$. Suppose for a contradiction that
$\theta(k)>1/2-f(k)$.

Set $\delta:=\frac{1}{2}\sqrt{1-2\theta(k)+2f(k)}$ and $\gamma:=1/2-\delta$.
Fix a subset $\Omega^{\prime}\subseteq\Omega$ such that
$\pi(\Omega^{\prime})=\gamma$. Set
$S:=((\Omega\setminus\Omega^{\prime})\times\Omega^{\prime})\cup(\Omega^{\prime}\times(\Omega\setminus\Omega^{\prime}))$.
Let $W:=\mathbb{I}_{S}$. Note that $\left\lVert
W\right\rVert_{1}=\theta(k)-f(k)<\theta(k)$. Sample
$\mathbb{F}\sim\mathbb{G}(k,W)$ and sample $\mathbb{H}$ according to the
distribution
$\mathbb{P}\left(\mathbb{H}=H\,|\,\mathbb{F}=F\right)=\mathcal{R}_{F,H}$. Note
that

(39)
$\mathbb{E}e(\mathbb{H})\geq\binom{k}{2}\mathbb{P}\left(e(\mathbb{F})>\frac{1}{2}\binom{k}{2}\right).$

Set $Y:=e(\mathbb{F})$. By the structure of $W$ we have
$B\sim\operatorname{Bin}(k,\gamma)$ such that $Y=B(k-B)$. Write
$B=\sum_{i=1}^{k}B_{i}$ as the sum of $k$ independent random variables
$B_{i}\sim\operatorname{Ber}(\gamma)$. Set $X_{i}:=B_{i}-\gamma$ for $i\in[k]$
and $X:=\sum_{i=1}^{k}X_{i}$. We have

$\displaystyle\mathbb{P}\left(Y>\frac{1}{2}\binom{k}{2}\right)=\mathbb{P}\left(\left|B-\frac{k}{2}\right|<\frac{\sqrt{k}}{2}\right)$
$\displaystyle\geq\mathbb{P}\left(|X|<\frac{\sqrt{k}}{2}-k\delta\right)$
$\displaystyle\geq\mathbb{P}\left(\frac{|X|}{\sqrt{\operatorname{Var}(X)}}<\frac{1-\sqrt{4kf(k)}}{\sqrt{1-4f(k)}}\right)$
$\displaystyle\geq\mathbb{P}\left(\frac{|X|}{\sqrt{\operatorname{Var}(X)}}<0.99\right).$

Now by Theorem 2.14 we have

$\mathbb{P}\left(\frac{|X|}{\sqrt{\operatorname{Var}(X)}}<0.99\right)\geq\mathbb{P}\left(Z<0.99\right)-\frac{1}{9}\geq
0.55,$

where $Z\sim N(0,1)$ is a standard Gaussian random variable. Then by (17) and
(39) we have

(40)
$\int\mathfrak{V}_{\>}W\,\mathrm{d}\pi^{2}\geq(k)_{2}\left(\mathbb{P}\left(Y>\frac{1}{2}\binom{k}{2}\right)-\left\lVert
W\right\rVert_{1}\right)\geq\frac{(k)_{2}}{100}.$

Set $T:=\frac{1}{200C_{k}}$. By (21) in Lemma 3.7 we have

$\int\left(\Phi^{T}W-W-T\mathfrak{V}_{\mathcal{R}}W\right)\,\mathrm{d}\pi^{2}\leq\left\lVert\Phi^{T}W-W-T\mathfrak{V}_{\mathcal{R}}W\right\rVert_{\infty}\leq
C_{k}(k)_{2}T^{2},$

so by (40) we have

$\displaystyle\left\lVert\Phi^{T}W\right\rVert_{1}=\int\Phi^{T}W\,\mathrm{d}\pi^{2}$
$\displaystyle\geq\int
W\,\mathrm{d}\pi^{2}+T\int\mathfrak{V}_{\>}W\,\mathrm{d}\pi^{2}-C_{k}(k)_{2}T^{2}$
$\displaystyle\geq\left\lVert W\right\rVert_{1}+\frac{(k)_{2}}{2\cdot
10^{4}C_{k}}-\frac{(k)_{2}}{4\cdot
10^{4}C_{k}}\geq\frac{1}{2}+\frac{(k)_{2}}{8\cdot 10^{4}C_{k}}>1-\theta(k).$

Hence, by Proposition 7.3(ii) we have
$\mathrm{dest}(W)=\mathrm{dest}(\Phi^{T}W)=1$. On the other hand, $\left\lVert
W\right\rVert_{1}<\theta(k)$ implies that $\mathrm{dest}(W)=0$. This is a
contradiction, so we must have $\theta(k)\leq 1/2-f(k)$. ∎

###  7.3. Trajectory rescaling for large $k$

Observe that the order of a rule can significantly restrict the maximum rate
of change in its trajectories. Indeed, suppose that $\mathcal{R}$ is a rule of
order $k\in\mathbb{N}$. Then, by (20) we have
$-(k)_{2}\leq\mathfrak{V}_{\mathcal{R}}W\leq(k)_{2}$ for all graphons $W$. To
adjust for the fact that larger values of $k$ permit greater rates of change,
we shall introduce the following limit notion of rescaling. Let
$(\mathcal{R}_{k})_{k\geq 2}$ be a sequence of rules such that
$\mathcal{R}_{k}$ is a rule of order $k$ for each $k\geq 2$. We say that
$(\mathcal{R}_{k})_{k\geq 2}$ is _rescalable_ at a graphon $W$ if the Banach-
space limit

$\lim_{k\to\infty}\Phi_{\mathcal{R}_{k}}^{t/(k)_{2}}W$

exists for all $t\in[0,\infty)$. Then, we write
$\Psi^{t}(W):=\lim_{k\to\infty}\Phi_{\mathcal{R}_{k}}^{t/(k)_{2}}W$ and call
this a _rescaled trajectory_. Let $\mathcal{B}\subseteq\mathcal{W}_{0}$ be the
set of graphons at which $(\mathcal{R}_{k})_{k\geq 2}$ is rescalable. We
define the _rescaling core_ of $(\mathcal{R}_{k})_{k\geq 2}$, which we denote
by $\mathcal{B}^{\bullet}$, to be the set of elements in the interior of
$\mathcal{B}$ (with respect to the topology induced by the cut norm) at which
the maps $W\mapsto\Psi^{t}(W)$, for $t\geq 0$, are continuous (with respect to
the topology induced by the cut norm). In particular, the rescaling core of
$(\mathcal{R}_{k})_{k\geq 2}$ is a set of graphons $W$ such that
$\Psi^{t(k)_{2}}(W)$ is a good approximation for
$\Phi_{\mathcal{R}_{k}}^{t}(\tilde{W})$ when $k$ is sufficiently large and
$\tilde{W}$ is sufficiently close to $W$. (Let us note that in principle, we
might investigate rescaled trajectories outside of the rescaling core as well,
and this indeed seems to be doable using the main result from [13]. However,
the favourable continuity property is lost in this case, and in particular
such rescaled trajectories would have no connection to flip processes on
finite graphs, as provided by Theorem 1.1.)

Theorem 7.8 characterizes the rescaling core of the sequence of extremist
rules and explicitly describes the rescaled trajectories.

######  Theorem 7.8.

The rescaling core of the sequence $(\mathcal{R}_{k})_{k\geq 2}$ of extremist
rules is the set of graphons whose density is not $\frac{1}{2}$. The following
holds for each graphon $W\in\mathcal{W}_{0}$.

  1. (i)

If $\left\lVert W\right\rVert_{1}>\frac{1}{2}$ then
$\Psi^{t}W=1-e^{-t}\cdot(1-W)$ for each $t\geq 0$.

  2. (ii)

If $\left\lVert W\right\rVert_{1}<\frac{1}{2}$ then $\Psi^{t}W=e^{-t}\cdot W$
for each $t\geq 0$.

We only prove Theorem 7.8(i). Indeed, then Theorem 7.8(ii) follows by
symmetry. Further, the set of graphons of density other than $\frac{1}{2}$ is
open and the maps $W\mapsto\Psi^{t}(W)$ are continuous. So, it only needs to
be argued that the rescaling core does not contain any graphon of density
$\frac{1}{2}$. This is because such a graphon can be approximated by graphons
of density more than $\frac{1}{2}$ and less than $\frac{1}{2}$ at the same
time, which are mapped by $\Psi^{3}(\cdot)$ to a graphon of density more than
$0.9$ and less than $0.1$, respectively, demonstrating a discontinuity.

###### Proof of Theorem 7.8(i).

Fix $\varepsilon>0$ and consider an extremist rule $\mathcal{R}_{k}$ of
sufficiently large order $k$. We write $\mathfrak{V}_{k}$ and $\Phi_{k}$ for
the velocity operator and the trajectory of $\mathcal{R}_{k}$, respectively.
Let $\mathcal{U}$ denote the set of all graphons with density at least
$\frac{1}{2}+\varepsilon$. We begin with the following claim, which
approximates $\mathfrak{V}_{k}$ for graphons in $\mathcal{U}$.

######  Claim 7.9.

If $U\in\mathcal{U}$ then we have

$\left\lVert\mathfrak{V}_{k}U-(k)_{2}\cdot(1-U)\right\rVert_{\infty}=o_{k}(k^{2})\;.$

###### Proof.

Set $d^{\prime}:=\left\lVert U\right\rVert_{1}$. Observe that we have

(41) $\sum_{F\in\mathcal{H}_{k}:ab\notin E(F)}(T_{F}^{a,b}W)(x,y)=1-W(x,y)\;.$

For $1\leq a\neq b\leq k$ and a labelled graph $J$ on $[k]\setminus\\{a,b\\}$,
let $\mathcal{F}^{a,b}_{J}\subset\mathcal{H}_{k}$ be the set of all graphs on
$[k]$ from which the removal of $a$ and $b$ yields $J$. Observe that we have

(42)
${t_{\mathrm{ind}}}(J,U)=\sum_{F\in\mathcal{F}^{a,b}_{J}}{t_{\mathrm{ind}}}(F,U)\;.$

For $\alpha,\beta\in[0,1]$ and $\ell\in\mathbb{N}$, let
$\mathcal{H}_{\ell}^{\alpha,\beta}\subset\mathcal{H}_{\ell}$ be the set of all
graphs whose density is $\alpha\pm\beta$. Since ${t_{\mathrm{ind}}}(J,U)$
represents the probability that $\mathbb{G}(k,U)=J$, Lemma 2.8 tells us that

(43)
$\sum_{J\in\mathcal{H}_{k-2}\setminus\mathcal{H}_{k-2}^{d^{\prime},\varepsilon/3}}{t_{\mathrm{ind}}}(J,U)=o_{k}(1/k^{2})$

Since any graph $F\in\mathcal{H}_{k}^{d^{\prime},\varepsilon/2}$ has density
greater than $\frac{1}{2}$, we have $\mathcal{R}_{F,K_{k}}=1$. On the other
hand, since $k$ is sufficiently large and at most $2k=o_{k}(k^{2})$ edges are
incident to $a$ or $b$, a graph $F\in\mathcal{F}^{a,b}_{J}$ does not have
density $d^{\prime}\pm\varepsilon/2$ only if $J$ does not have density
$d^{\prime}\pm\varepsilon/3$. Hence, we may rewrite (14) as

$\displaystyle\mathfrak{V}_{k}U(x,y)$ $\displaystyle=\sum_{1\leq a\neq b\leq
k}\sum_{F\in\mathcal{H}_{k}:ab\notin E(F)}(T_{F}^{a,b}U)(x,y)\pm 2\sum_{1\leq
a\neq b\leq
k}\sum_{F\in\mathcal{H}_{k}\setminus\mathcal{H}_{k}^{d^{\prime},\varepsilon/2}}(T_{F}^{a,b}U)(x,y)$
by (41) $\displaystyle=(k)_{2}\cdot(1-U(x,y))\pm 2\sum_{1\leq a\neq b\leq
k}\sum_{J\in\mathcal{H}_{k-2}\setminus\mathcal{H}_{k-2}^{d^{\prime},\varepsilon/3}}\sum_{F\in\mathcal{F}^{a,b}_{J}}{t_{\mathrm{ind}}}(F,U)$
by (42) and (43) $\displaystyle=(k)_{2}\cdot(1-U(x,y))\pm o_{k}(1))\;,$

finishing the proof. ∎

Now we apply Claim 7.9 to show that trajectories which start in $\mathcal{U}$
are confined to $\mathcal{U}$.

######  Claim 7.10.

If $U\in\mathcal{U}$, then we have $\Phi_{k}^{t}U\in\mathcal{U}$ for all
$t\geq 0$.

###### Proof.

Let $U\in\mathcal{U}$ and suppose that $\Phi_{k}^{t}U\notin\mathcal{U}$ for
some $t\geq 0$. Set $T:=\inf\\{t\geq 0:\Phi_{k}^{t}U\notin\mathcal{U}\\}$. By
the continuity of $\Phi_{k}^{\cdot}U$, the graphon $\Phi_{k}^{T}U$ has density
$\frac{1}{2}+\varepsilon$. Set
$S=\left((k)_{2}^{3}2^{\binom{k}{2}}\right)^{-1}$ and let $0<s\leq S$. By (21)
for $s$ and Claim 7.9, we have

$\left\lVert\frac{\Phi_{k}^{T+s}U-\Phi_{k}^{T}U}{s}-(k)_{2}\cdot(1-\Phi_{k}^{T}U)\right\rVert_{\infty}=o_{k}(k^{2}).$

Then, we obtain

$\left\lVert\Phi_{k}^{T+s}U\right\rVert_{1}=\left\lVert\Phi_{k}^{T}U\right\rVert_{1}+s((k)_{2}\left\lVert
1-\Phi_{k}^{T}U\right\rVert_{1}-o_{k}(k^{2}))\geq\left\lVert\Phi_{k}^{T}U\right\rVert_{1}=\frac{1}{2}+\varepsilon,$

so we have $\Phi_{k}^{T+s}U\in\mathcal{U}$. This contradicts the definition of
$T$, so $\Phi_{k}^{t}U\in\mathcal{U}$ for all $t\geq 0$. ∎

Let $W\in\mathcal{U}$. We first consider the integral equation
$\Gamma_{k}^{\tau}:=W+\int_{s=0}^{\tau}\mathfrak{Z}_{k}(\Gamma^{s})\,\mathrm{d}s$,
where $\mathfrak{Z}_{k}(U)=(k)_{2}\cdot(1-U)$. The solution of this integral
equation is

$\Gamma_{k}^{\tau}=1-e^{-(k)_{2}\tau}\cdot(1-W)\;.$

Recall that in fact $\Phi_{k}^{\cdot}W$ is the solution of the integral
equation (2), that is,

$\Phi_{k}^{\tau}W=W+\int_{0}^{\tau}\mathfrak{V}_{k}\left(\Phi_{k}^{s}W\right)\,\mathrm{d}s\;.$

Now $\mathfrak{Z}_{k}(\cdot)$ is $(k)_{2}$-Lipschitz, both
$\Gamma_{k}^{\cdot}$ and $\Phi_{k}^{\cdot}W$ are confined to $\mathcal{U}$ and
Claim 7.9 tells us that
$\left\lVert\mathfrak{V}_{k}(\cdot)-\mathfrak{Z}_{k}(\cdot)\right\rVert_{\infty}=o_{k}(k^{2})$
on $\mathcal{U}$, so Lemma 2.3 gives us

$\left\lVert\Phi_{k}^{\tau}W-\Gamma^{\tau}_{k}\right\rVert_{\infty}\leq
o_{k}(k^{2})\tau\cdot e^{(k)_{2}\tau}\;.$

Hence, we conclude that for any fixed $t\geq 0$, we have that
$\Phi_{k}^{t/(k)_{2}}W$ converges uniformly to $1-e^{-t}\cdot(1-W)$ as
$k\to\infty$. ∎

###  7.4. Stabilization in an extremist flip process

Let us consider a flip process of order $k$ with rule $\mathcal{R}$. Let $G$
be an $n$-vertex graph ($n\geq k$), and $G_{0}:=G,G_{1},G_{2},\ldots$ be an
evolution of the graph $G$ with respect to the flip process with rule
$\mathcal{R}$. The _stabilization time_ $\kappa_{\mathcal{R}}(G)$ is a random
variable defined as
$\kappa_{\mathcal{R}}(G)=\min\\{\ell:G_{\ell}=G_{\ell+1}=G_{\ell+2}=\ldots\\}$
if it exists and $\kappa_{\mathcal{R}}(G)=\infty$ otherwise. For example, if
$\mathcal{R}_{F,F}=0$ for all $F\in\mathcal{H}_{k}$ then each step of the flip
process changes the graph and $\kappa_{\mathcal{R}}(G)=\infty$ almost surely.

We now consider the concept of stabilization time in the context of an
extremist flip process of a given order $k\geq 3$. Suppose that the initial
graph has $n$ vertices. It can be shown that the stabilization time is finite
almost surely, and further, if $n\geq n_{0}(k)$ is sufficiently large,
stabilization occurs (almost surely) at the moment the flip process reaches
the edgeless or the complete graph (which are graphs at which stabilization
obviously occurs).

We leave it as an interesting question to find universal bounds on
stabilization times.

######  Question 7.11.

For each $k\geq 3$ with the corresponding extremist rule $\mathcal{R}_{k}$, we
seek a function $b_{k}:\mathbb{N}\rightarrow\mathbb{N}$ growing as slowly as
possible so that

$\min_{G\in\mathcal{H}_{n}}\mathbb{P}\left(\kappa_{\mathcal{R}_{k}}(G)\leq
b_{k}(n)\right)\to 1,\quad\text{ as }n\to\infty\;.$

It seems very likely that quasirandom graphs of edge density around
$\frac{1}{2}$ have the largest stabilization time, and that we have to take
$b_{k}(n)\approx\exp(n^{C})$ for some $C\in(0,2]$. In particular, the number
of steps goes far beyond $\Theta(n^{2})$, and so this question is outside the
framework of our graphon trajectories.444Recall Theorem 1.1.

##  8\. Monotone flip processes

Broadly speaking, monotone flip processes are those where the number of edges
does not decrease in any step. Formally, we define a few different notions of
monotonicity.

######  Definition 8.1.

Let $\mathcal{R}$ be a rule of order $k\in\mathbb{N}$. We say that
$\mathcal{R}$ is

  * •

_non-decreasing_ if for each $F\in\mathcal{H}_{k}$ we have
$\mathcal{R}_{F,H}=0$ whenever $H$ is not a (labelled) supergraph of $F$.

  * •

_increasing_ if it is non-decreasing and in addition for each
$F\in\mathcal{H}_{k}\setminus\\{K_{k}\\}$ there exists a proper supergraph $H$
of $F$ with $\mathcal{R}_{F,H}>0$.

  * •

_density-non-decreasing_ if for each $F\in\mathcal{H}_{k}$ we have
$\sum_{H\in\mathcal{H}_{k}}\mathcal{R}_{F,H}e(H)\geq e(F)$.

  * •

_density-increasing_ if it is density-non-decreasing and further for each
$F\in\mathcal{H}_{k}\setminus\\{K_{k}\\}$ the above inequality is strict.

In particular, a non-decreasing rule is density-non-decreasing and an
increasing rule is density-increasing.

The following proposition asserts that non-decreasing and density-increasing
flip processes are convergent, but this need not be true for density-non-
decreasing flip processes.

######  Proposition 8.2.

  1. (i)

Each trajectory of a non-decreasing rule $\mathcal{R}$ has a destination.

  2. (ii)

Let $\mathcal{R}$ be a density-increasing rule. The destination of each
trajectory is the constant-$1$ graphon. The age of each graphon except the
constant-$1$ graphon is finite.

  3. (iii)

There is a density-non-decreasing rule with a non-convergent trajectory.

###### Proof of Proposition 8.2(i).

Let $W\in\mathcal{W}_{0}$ be a graphon. Observe that since $\mathcal{R}$ is
non-decreasing, the negative terms of (14) have coefficient zero. Hence, the
velocity is pointwise non-negative. In other words, for each point $(x,y)$,
the function $t\mapsto\Phi^{t}W(x,y)$ is non-decreasing. In this case it is
obvious that the destination is the pointwise limit of $\Phi^{t}W$. ∎

###### Proof of Proposition 8.2(ii).

Suppose $\mathcal{R}$ is of order $k$. Let

$\delta=\min_{F\in\mathcal{H}_{k}\setminus\\{K_{k}\\}}\sum_{H\in\mathcal{H}_{k}}\mathcal{R}_{F,H}(e(H)-e(F)).$

Since $\mathcal{R}$ is density-increasing, we have $\delta>0$. We shall show
that for every graphon $W$ we have

(44) $\int\mathfrak{V}_{\>}W\,\mathrm{d}\pi^{2}\geq 2\delta(1-t(K_{k},W))\;.$

Let $(\mathbb{F},\mathbb{H})$ be a pair of random graphs in $\mathcal{H}_{k}$
such that $\mathbb{F}\sim\mathbb{G}(k,W)$ and
$\mathbb{P}\left(\mathbb{H}=H\,|\,\mathbb{F}=F\right)=\mathcal{R}_{F,H}$ for
all $F,H\in\mathcal{H}_{k}$. For $F\neq K_{k}$ we have

(45)
$\mathbb{E}\left(e(\mathbb{H})\,|\,\mathbb{F}=F\right)=\sum_{H\in\mathcal{H}_{k}}\mathcal{R}_{F,H}e(H)\geq
e(F)+\delta.$

Now by (16) we have

$\displaystyle\int\mathfrak{V}_{\>}W\,\mathrm{d}\pi^{2}$
$\displaystyle=2\mathbb{E}\left[e(\mathbb{H})-e(\mathbb{F})\right]=2\sum_{F\in\mathcal{H}_{k}}t(F,W)\mathbb{E}\left(e(\mathbb{H})-e(\mathbb{F})\,|\,\mathbb{F}=F\right)$
$\displaystyle=2\sum_{F\in\mathcal{H}_{k}}t(F,W)\left[\mathbb{E}\left(e(\mathbb{H})\,|\,\mathbb{F}=F\right)-e(F)\right]$
$\displaystyle\overset{\mbox{\tiny{\eqref{eq:yImrl}}}}{\geq}2\sum_{F\neq
K_{k}}t(F,W)\delta=2\left(1-t(K_{k},W)\right)\delta\;,$

which shows (44).

The growth given by (44) allows us to prove the statement. Indeed, let $U$ be
an arbitrary graphon. Let $f:[-\mathrm{age}(U),+\infty)\rightarrow[0,1]$ be
defined by $f(t):=\int\Phi^{t}U\,\mathrm{d}\pi^{2}$. Then (44) gives

$\frac{\,\mathrm{d}}{\,\mathrm{d}t}f(t)\geq
2\delta(1-t(K_{k},\Phi^{t}U))\overset{\mbox{\tiny{Prop~{}\ref{prop:KruskalKatona}}}}{\geq}2\delta(1-f(t)^{k/2})\;.$

Firstly, this implies that $f(t)\rightarrow 1$ as $t\rightarrow\infty$, i.e.,
that the destination of $U$ is the constant-$1$ graphon. Secondly, it gives
that $f(t)$ is increasing, and hence for $t<0$, we have that
$\frac{\,\mathrm{d}}{\,\mathrm{d}t}f(t)\geq 2\delta(1-f(0)^{2/k})$. That means
that unless $f(0)=1$, the derivative of $f$ in the negative domain is bounded
from below by a positive constant. Since $f\in[0,1]$, this means that the age
is finite. ∎

###### Sketch of proof of Proposition 8.2(iii).

We build on Section LABEL:FIRSTPAPER.ssec:oscillatory of [12] where a flip
process with a periodic trajectory was constructed. We briefly recall this
construction. Fix a partition $\Omega=\Omega_{1}\cup\Omega_{2}$ with
$\pi(\Omega_{1})=\pi(\Omega_{2})=1/2$. We take $k$ large and $\alpha>0$ small
(probably $k=2000$ and $\alpha=0.01$ would work). Fix $r=0.1$, $a:=0.2$,
$b:=0.8$. Let $\mathsf{circle}(a,b;r)$ be the circle centered at the point
$(a,b)$ and of radius $r$. For input $F\in\mathcal{H}_{k}$ the rule is as
follows. If $F$ consists of two components $C_{1}$ and $C_{2}$, each of order
$(\frac{1}{2}\pm\alpha)k$, say $C_{1}$ of density $d_{1}$ and $C_{2}$ of
density $d_{2}$ with the condition that the point $(d_{1},d_{2})$ is within
distance of $0.01$ from $\mathsf{circle}(a,b;r)$ then we add or delete edges
into $C_{1}$ and $C_{2}$ so that the expected change of edges in $C_{1}$ and
$C_{2}$ is given by the first and the second coordinate of
$(g+h)(d_{1},d_{2})$, respectively. Here,
$g,h:\mathbb{R}^{2}\setminus\\{(a,b)\\}\rightarrow\mathbb{R}^{2}$ are defined
as follows,

$\displaystyle g(x,y)$
$\displaystyle=\frac{1}{\sqrt{(-y+b)^{2}+(x-a)^{2}}}\cdot(-y+b,x-a)\;,$
$\displaystyle h(x,y)$
$\displaystyle=\left(\tfrac{r}{\sqrt{(x-a)^{2}+(y-b)^{2}}}-1\right)\cdot(x-a,y-b)\;.$

No edges between $C_{1}$ and $C_{2}$ are added. For other $F$s, the rule is
arbitrary. Observe that values of $g$ are tangent vectors of circles centered
at $(a,b)$. Furthermore, $h$ vanishes on $\mathsf{circle}(a,b;r)$ and pushes
towards $\mathsf{circle}(a,b;r)$ elsewhere.

Fix $(x,y)\in\mathsf{circle}(a,b;r)$. Consider a graphon $U$ taking value $x$
on $\Omega_{1}\times\Omega_{1}$, value $y$ on $\Omega_{2}\times\Omega_{2}$ and
$0$ elsewhere. If it were true that for each such graphon we would have with
probability 1 that the sampled $F$ has the two components as above and
$d_{1}=x$ and $d_{2}=y$ then $\mathsf{circle}(a,b;r)$ would indeed be a
periodic trajectory of the flip process. However, because the law of large
numbers is not perfect, the above statement holds only with probability
$1-o_{k}(1)$ and only with $d_{1}=x\pm o_{k}(1)$ and $d_{2}=y\pm o_{k}(1)$.
Considering a trajectory that starts at a graphon corresponding to the point
$(x,y)$, the correcting function $h$ pushes the trajectory towards
$\mathsf{circle}(a,b;r)$ in case of any substantial deviations (this part of
the argument needs the Poincaré-Bendixson Theorem and we refer to [12]).

The above flip process is clearly not density-non-decreasing. However, we can
modify it as follows. Partition
$\Omega=\Omega_{1}\cup\Omega_{2}\cup\Omega_{\mathrm{reservoir}}$ with
$\pi(\Omega_{1})=\pi(\Omega_{2})=1/4$ and
$\pi(\Omega_{\mathrm{reservoir}})=1/2$. Now, the rule is as follows. If the
sampled graph $F$ is such that it consists of three components, say $C_{1}$,
$C_{2}$ and $C_{\mathrm{reservoir}}$, such that $C_{1}$ and $C_{2}$ have
orders $(\frac{1}{4}\pm\alpha)k$ and $C_{\mathrm{reservoir}}$ has order
$(\frac{1}{2}\pm\alpha)k$ and the densities of $C_{1}$ and $C_{2}$ are as
above555Note that in this setting, the components $C_{1}$, $C_{2}$ and
$C_{\mathrm{reservoir}}$ are uniquely determined. and the density of
$C_{\mathrm{reservoir}}$ is between $0.2$ and $0.8$ then we add or delete
edges from $C_{1}$ and $C_{2}$ according to $(g+h)(d_{1},d_{2})$ and then add
or delete edges from $C_{\mathrm{reservoir}}$ so that the total number of
edges in this step does not change. If $F$ is not of this form then we have an
idle step.

Since the number of edges does not change, the flip process is non-density-
decreasing. Starting with a graphon $W$ whose values on
$\Omega_{i}\times\Omega_{j}$ ($i,j\in[2])$ are defined as for $U$, and further
which is constant-$\frac{1}{2}$ on $\Omega_{\mathrm{reservoir}}^{2}$ and zero
on $(\Omega_{1}\cup\Omega_{2})\times\Omega_{\mathrm{reservoir}}^{2}$ we see
that the densities on $\Omega_{1}^{2}$ and on $\Omega_{2}$ evolve close to
$\mathsf{circle}(a,b;r)$ while $\Omega_{\mathrm{reservoir}}$ just serves to
keep the overall density constant. In particular, this trajectory does not
have a destination. ∎

Our next result says that for a non-decreasing rule the limit of the
destinations of a convergent sequence of graphons is greater than or equal to
the destination of the limit.

######  Proposition 8.3.

Let $\mathcal{R}$ be a non-decreasing rule of order $k\in\mathbb{N}$ and
$(U_{n})_{n\in\mathbb{N}}$ be a sequence of graphons which converges to a
graphon $U$ in the cut norm distance. Suppose that the sequence
$(\mathrm{dest}(U_{n}))_{n\in\mathbb{N}}$ converges in the cut norm distance
to a graphon $S$. Then $S\geq\mathrm{dest}(U)$.

######  Remark 8.4.

Observe that the converse inequality does not hold in general. Indeed, for
each $k\geq 3$ consider a flip process of order $k$ in which a drawn graph
containing a single edge and $k-2$ isolated vertices is replaced by $K_{k}$
while the step is idle for other drawn graphs. Let $(U_{n})_{n\in\mathbb{N}}$
be the sequence of graphons where $U_{n}$ is the constant-$1/n$ graphon. On
the one hand, this sequence of graphons converges to the constant-$0$ graphon
$U$; here we have $\mathrm{dest}(U)=0$. On the other hand,
$(\mathrm{dest}(U_{n}))_{n\in\mathbb{N}}$ is a sequence of constant-$1$
graphons, which clearly converges to the constant-$1$ graphon.

Nevertheless, we show in Theorem 10.7 that we do have equality for removal
flip processes (which are also monotone, though non-increasing).

###### Proof of Proposition 8.3.

We shall prove that for arbitrary sets $A,B\subset\Omega$ and an arbitrary
$\varepsilon>0$ we have $\int_{A\times B}\mathrm{dest}(U)\leq\int_{A\times
B}S+\varepsilon$ (how this implies the proposition, is an exercise in measure
theory which we leave to the reader). To this end, let $T$ be such that
$d_{\square}(\mathrm{dest}(U),\Phi^{T}U)<\varepsilon/2$. Define
$\delta:=\varepsilon/(4\exp(C_{k}T))$, where $C_{k}$ is from Theorem 3.8. Then
by Theorem 3.8, for every $U_{i}$ for which $d_{\square}(U_{i},U)<\delta$, we
have $d_{\square}(\Phi^{T}U_{i},\Phi^{T}U)<\varepsilon/2$. In particular, this
means that $\int_{A\times B}\mathrm{dest}(U)\leq\int_{A\times
B}\Phi^{T}U_{i}+\varepsilon$. Since we have a non-decreasing flip process,
$\Phi^{T}U_{i}\leq\mathrm{dest}(U_{i})$ and hence $\int_{A\times
B}\mathrm{dest}(U)\leq\int_{A\times B}\mathrm{dest}(U_{i})+\varepsilon$. As
$\mathrm{dest}(U_{1}),\mathrm{dest}(U_{2}),\ldots\xrightarrow{\square}S$, we
get $\int_{A\times B}\mathrm{dest}(U)\leq\int_{A\times B}S+\varepsilon$ as
needed. ∎

##  9\. Component completion flip processes

In this section we define the component completion rule and prove Theorem 9.6,
which characterizes the destinations of the component completion rule. The
component completion rule completes the components of the drawn graph $F$ by
adding edges between all non-edge pairs of vertices in the same connected
component of $F$. We give a formal definition below.

######  Definition 9.1 (Component completion graph).

Let $k\in\mathbb{N}$ and $F\in\mathcal{H}_{k}$. For distinct $a,b\in[k]$ write
$a\sim_{F}b$ to mean that there is a path between $a$ and $b$ in $F$. The
_component completion graph_ $\mathcal{C}(F)$ of $F$ is the labelled graph on
vertex set $[k]$ with edge set $\\{ab:a,b\in[k],a\neq b,a\sim_{F}b\\}$.

######  Definition 9.2 (Component completion rule).

Let $k\in\mathbb{N}$. A rule $\mathcal{R}$ of order $k$ is _component
completion_ if for all $F,H\in\mathcal{H}_{k}$ we have

(46) $\mathcal{R}_{F,H}=\begin{cases}1&\textrm{ if }H=\mathcal{C}(F),\\\
0&\textrm{ otherwise }.\end{cases}$

To prepare for the statement and proof of Theorem 9.6, we give definitions of
connectedness, component decomposition and component completeness for
graphons.

######  Definition 9.3 (Connectedness).

A graphon $W$ is _disconnected_ if $W=0$ or there is a subset
$A\subseteq\Omega$ with $\pi(A)\in(0,1)$ such that $W=0$ a.e. on
$A\times\left(\Omega\setminus A\right)$. Otherwise, $W$ is _connected_.

######  Definition 9.4 (Component decomposition).

A _component decomposition_ of a graphon $W$ is a partition
$\Omega=\bigsqcup_{i=0}^{K}\Omega_{i}$ into disjoint measurable sets
$\Omega_{i}$ with $0\leq K\leq\infty$ such that the following hold.

  1. (GC1)

$\alpha_{i}:=\pi(\Omega_{i})>0$ for all $i\geq 1$ but $\Omega_{0}$ may be
empty.

  2. (GC2)

For all $i\geq 1$ the graphon $W{\restriction_{\Omega_{i}^{2}}}$ on
$\left(\Omega_{i},(\alpha_{i}^{-1}\pi){\restriction_{\Omega_{i}}}\right)$ is
connected.

  3. (GC3)

$W=0$ a.e. on
$\Omega^{2}\setminus\left(\bigsqcup_{i=1}^{K}\Omega_{i}^{2}\right)$.

######  Definition 9.5 (Component completeness).

A graphon $W$ is _component complete_ if it has a component decomposition
$\Omega=\bigsqcup_{i=0}^{K}\Omega_{i}$ such that
$W{\restriction_{\Omega_{i}^{2}}}=1$ for all $i\geq 1$.

Theorem 9.6 characterizes the destinations of the component completion rule.

######  Theorem 9.6.

Suppose that $\mathcal{R}$ is a component completion rule of order $k\geq 3$.
Then the following hold.

  1. (i)

Every trajectory of $\mathcal{R}$ has a destination.

  2. (ii)

Every destination of $\mathcal{R}$ is component complete. Moreover, the
destination of a graphon with component decomposition
$\Omega=\bigsqcup_{i=0}^{K}\Omega_{i}$ is component complete with the same
component decomposition.

  3. (iii)

Every component complete graphon is a destination of $\mathcal{R}$.

To prepare for the proof of Theorem 9.6, we state two lemmas. We begin with
Lemma 5.5 from [14] about component decomposition for graphons.

######  Lemma 9.7.

Every graphon has a component decomposition.

Next, we give a technical lemma which, roughly speaking, says that every
graphon with zero density of $3$-vertex induced paths is $\\{0,1\\}$-valued
and in fact complete if connected. Its proof is given at the end of this
section.

######  Lemma 9.8.

Let $W$ be a graphon which satisfies

(47) $\int_{\Omega^{3}}(1-W(x,y))W(x,z)W(y,z)\,\mathrm{d}\pi^{3}=0.$

Then $W(x,y)\in\\{0,1\\}$ a.e. on $\Omega^{2}$. If in addition $W$ is
connected, then $W=1$.

Now we shall prove Theorem 9.6. Let us briefly describe the key ideas. The
action of the non-decreasing rule $\mathcal{R}$ is driven by the addition of
edges between non-edge pairs of vertices which are connected by a path. Hence,
the component decomposition of the initial graphon remains intact. Since our
result is concerned with destinations of trajectories, which are a form of
limit behaviour, $3$-vertex induced paths are particularly relevant because
every induced path between non-adjacent vertices contains a $3$-vertex induced
path. Lemma 9.8 implies that the components of a destination must be complete.

###### Proof of Theorem 9.6.

Since $\mathcal{R}$ is a non-decreasing rule, every trajectory of
$\mathcal{R}$ has a destination by Proposition 8.2(i). Let

$B:=\\{(F,a,b):F\in\mathcal{H}_{k},ab\notin E(F),a\sim_{F}b\\}.$

By (14) and (46), for each $W\in\mathcal{W}_{0}$ and each $(x,y)\in\Omega^{2}$
we have

(48) $\mathfrak{V}_{\mathcal{R}}W(x,y)=\sum_{(F,a,b)\in
B}t_{\mathrm{ind}}^{(x,y)}(F^{a,b},W).$

Let $U\in\mathcal{W}_{0}$, with a fixed component decomposition
$\Omega=\bigsqcup_{i=0}^{K}\Omega_{i}$ of $U$ given by Lemma 9.7. We set
$\Lambda_{i}:=(\Omega_{i}\times(\Omega\setminus\Omega_{i}))\cup((\Omega\setminus\Omega_{i})\times\Omega_{i})$
for $i\in[K]$ and
$\Lambda_{0}:=(\Omega_{0}\times\Omega)\cup(\Omega\times\Omega_{0})$. Set
$\Lambda:=\Omega^{2}\setminus\left(\bigsqcup_{i=1}^{K}\Omega_{i}^{2}\right)=\bigsqcup_{i=0}^{K}\Lambda_{i}$.
For each $i\in[K]$ we show that the component completion rule does not change
the value of $W$ at points $(x,y)\in\Lambda_{i}$, that is, pairs of vertices
that go between $\Omega_{i}$ and its complement. This is intuitive because the
rule would behave in the same way on graphs.

For $i\geq 0$ set
$\mathcal{A}_{i}:=\\{W\in\mathcal{W}_{0}:W{\restriction_{\Lambda_{i}}}=0\\}$.
We show that a trajectory starting at a graphon $W\in\mathcal{A}_{i}$ stays in
$\mathcal{A}_{i}$ for every $i\geq 0$. Indeed for any $(F,a,b)\in B$ and
$(x,y)\in\Lambda_{i}$ we have that $t_{\mathrm{ind}}^{(x,y)}(F^{a,b},W)=0$
exactly because any copy of $F^{a,b}$ sampled from $W$ with $x=a$ and $y=b$
sends the vertices $a$ and $b$ into different components. Hence, by (48) we
have $(\mathfrak{V}_{\mathcal{R}}W){\restriction_{\Lambda_{i}}}=0$. Then, by
applying Proposition 3.5 with $\mathcal{A}_{i}$ for each $i\in[K]\cup\\{0\\}$
we have $\Phi^{t}U=0$ on $\Lambda$ for all $t\in[0,\infty)$. Since
$\Phi^{t}U\xrightarrow{\square}\mathrm{dest}(U)=:S$, it follows that $S=0$
a.e. on $\Lambda$. By (48), for all $t\in[0,\infty)$ we have
$\mathfrak{V}_{\mathcal{R}}\Phi^{t}U\geq 0$ pointwise. Since
$S=U+\int_{[0,\infty)}\mathfrak{V}_{\mathcal{R}}\Phi^{s}U{\,\mathrm{d}}s$, we
have $S\geq U$. Hence, for all $i\geq 1$ the graphon
$S{\restriction_{\Omega_{i}^{2}}}$ on
$\left(\Omega_{i},(\alpha_{i}^{-1}\pi){\restriction_{\Omega_{i}}}\right)$
remains connected.

Define

$Q:=\left\\{(x,y)\in\Omega^{2}:(1-S(x,y))\int_{z\in\Omega}S(x,z)S(y,z)>0\right\\}.$

We aim to prove that $Q$ has measure zero. To this end, consider any $(x,y)\in
Q$. Let $H$ be the labelled graph on $\\{1,2,3\\}$ with edge set
$\\{13,23\\}$. Observe that we have $t_{\mathrm{ind}}^{(x,y)}(H^{1,2},S)>0$
and

$t_{\mathrm{ind}}^{(x,y)}(H^{1,2},S)=\sum_{F}t_{\mathrm{ind}}^{(x,y)}(F^{1,2},S),$

where the sum is over all labelled graphs $F\in\mathcal{H}_{k}$ which induce a
labelled copy of $H$ on $\\{1,2,3\\}$. Hence, there is a labelled graph
$F\in\mathcal{H}_{k}$ which induces a labelled copy of $H$ on $\\{1,2,3\\}$
such that $t_{\mathrm{ind}}^{(x,y)}(F^{1,2},S)>0$. This implies that
$\mathfrak{V}_{\mathcal{R}}S(x,y)>0$. Now since $S$ satisfies
$\mathfrak{V}_{\mathcal{R}}S=0$ by Proposition 3.9 and
$\mathfrak{V}_{\mathcal{R}}S(x,y)>0$ for all $(x,y)\in Q$, the set
$Q\subseteq\Omega^{2}$ has measure zero. Hence, we have (47) for $S$ and
$S{\restriction_{\Omega_{i}^{2}}}$ for all $i\geq 1$ and so by Lemma 9.8 we
have $S=1$ a.e. on $\Omega_{i}^{2}$ for all $1\leq i\leq K$. Therefore, $S$ is
a component complete graphon with component decomposition
$\Omega=\bigsqcup_{i=0}^{K}\Omega_{i}$.

Finally, by (ii) a component complete graphon is clearly its own destination.
∎

To close this section, we provide the proof of Lemma 9.8.

###### Proof of Lemma 9.8.

Define the following sets.

$\displaystyle M$ $\displaystyle:=\\{(x,y)\in\Omega^{2}:W(x,y)\in(0,1)\\},$
$\displaystyle N_{1}$
$\displaystyle:=\left\\{(x,y)\in\Omega^{2}:\int_{z\in\Omega}W(x,z)W(y,z)\,\mathrm{d}\pi>0\right\\},$
$\displaystyle N_{2}$
$\displaystyle:=\left\\{(x,y)\in\Omega^{2}:\int_{z\in\Omega}W(x,z)(1-W(y,z))\,\mathrm{d}\pi>0\right\\},$
$\displaystyle N$ $\displaystyle:=N_{1}\cup N_{2},$ $\displaystyle P$
$\displaystyle:=\\{x\in\Omega:(x,y)\in M\setminus N\textrm{ for some
}y\in\Omega\\}.$

For each $(x,y)\notin N$ we have $\int_{z\in\Omega}W(x,z)\,\mathrm{d}\pi=0$.
By Fubini’s theorem we have

$0\leq\int_{M\setminus
N}W(x,y)\,\mathrm{d}\pi^{2}\leq\int_{P}\int_{\Omega}W(x,y)\,\mathrm{d}\pi(y)\,\mathrm{d}\pi(x)=0.$

Hence, we have $\pi^{2}(M\setminus N)=0$. By (47) and Fubini’s theorem we have
$\pi^{2}(M\cap N_{1})=\pi^{2}(M\cap N_{2})=0$, so we have $\pi^{2}(M)=0$, i.e.
$W(x,y)\in\\{0,1\\}$ a.e. on $\Omega^{2}$.

Now suppose that $W$ is connected. For each $x\in\Omega$ define the following.

$\displaystyle S_{x}$ $\displaystyle:=\\{y\in\Omega:W(x,y)>0\\},\qquad
S_{x}^{+}:=S_{x}\cup\\{x\\},$ $\displaystyle P_{x}$
$\displaystyle:=\\{(y,z)\in S_{x}^{+}\times(\Omega\setminus
S_{x}^{+}):W(y,z)>0\\},$ $\displaystyle I(x)$
$\displaystyle:=\int_{\Omega}W(x,y)\,\mathrm{d}\pi(y).$

In addition, we define the following.

$\displaystyle S$ $\displaystyle:=\\{(x,y)\in\Omega^{2}:W(x,y)>0\\},\qquad
J:=\\{x\in\Omega:I(x)>0\\},$ $\displaystyle P$
$\displaystyle:=\\{(x,y,z)\in\Omega^{3}:x\in J,(y,z)\in P_{x}\\},$
$\displaystyle Q$ $\displaystyle:=\\{(x,y,z)\in\Omega^{3}:x\in J,(y,z)\in
S_{x}^{2}\setminus S\\}.$

Set $f(x,y,z):=(1-W(x,y))W(x,z)W(y,z)$ for $(x,y,z)\in\Omega^{3}$.

Since $W$ is connected, we have $\pi^{2}(S)=\int_{S}\,\mathrm{d}\pi^{2}>0$.
Now by Fubini’s theorem we have
$\int_{\Omega}I(x)\,\mathrm{d}\pi(x)=\int_{\Omega^{2}}W(x,y)\,\mathrm{d}\pi^{2}>0$,
so we have $\pi(J)>0$. Let $x\in J$. Since $I(x)>0$, we have $\pi(S_{x})>0$.
Suppose that $\pi(S_{x}^{+})<1$. Since $W$ is connected, we have
$\pi^{2}(P_{x})>0$. By Fubini’s theorem we have

$\int_{P}\,\mathrm{d}\pi^{3}=\int_{J}\int_{P_{x}}\,\mathrm{d}\pi^{2}(y,z)\,\mathrm{d}\pi(x)>0,$

so we have $\pi^{3}(P)>0$. Since $f(x,z,y)>0$ for all $(x,y,z)\in P$, we have
$\int_{\Omega^{3}}f(x,z,y)\,\mathrm{d}\pi^{3}>0$. This contradicts (47), so we
have $\pi(S_{x})=\pi(S_{x}^{+})=1$.

Now suppose that $\pi^{2}(\Omega^{2}\setminus S)>0$. Since $\pi(S_{x}^{2})=1$,
we have $\pi^{2}(S_{x}^{2}\setminus S)>0$. By Fubini’s theorem we have

$\int_{Q}\,\mathrm{d}\pi^{3}=\int_{J}\int_{S_{x}^{2}\setminus
S}\,\mathrm{d}\pi^{2}(y,z)\,\mathrm{d}\pi(x)>0,$

so we have $\pi^{3}(Q)>0$.

Since $f(y,z,x)>0$ for all $(x,y,z)\in Q$, we have
$\int_{Q}f(y,z,x)\,\mathrm{d}\pi^{3}>0$. This contradicts (47), so
$\pi^{2}(S)=1$. Now since $W(x,y)\in\\{0,1\\}$ a.e. on $\Omega^{2}$, in fact
we have $W=1$. ∎

##  10\. Removal flip processes

In a removal flip process, we have a graph $F\in\mathcal{H}_{k}$ which we
remove if it is contained in the drawn graph while drawing an $F$-free graph
leads to an idle step. A formal definition follows.

######  Definition 10.1.

Let $k\in\mathbb{N}$ and $F\in\mathcal{H}_{k}$. A rule $\mathcal{R}$ of order
$k$ is _$F$ -removal_ if for each $H\in\mathcal{H}_{k}$ which contains $F$ as
a labelled subgraph we have $\mathcal{R}_{H,H-F}=1$ while for each $H$ which
does not contain $F$ as a labelled subgraph we have $\mathcal{R}_{H,H}=1$. Of
course, all the remaining entries of the matrix $\mathcal{R}$ are $0$.

######  Remark 10.2.

Observe that Definition 10.1 is concerned with the removal of _non-induced_
copies of $F$. While we could define even flip processes removing induced
copies, such a concept would not have the nice properties we study here. For
example, the dual666The _dual_ of a flip process $\mathcal{R}$ is a flip
process $\mathcal{R}^{*}$ of the same order in which $\mathcal{R}^{*}_{F,H}$
is defined using the graph complements $\overline{F}$ and $\overline{H}$,
$\mathcal{R}^{*}_{F,H}:=\mathcal{R}_{\overline{F},\overline{H}}$. to the flip
process from Remark 8.4 shows that for such flip processes we do not have
Theorem 10.7.

######  Remark 10.3.

Consider Definition 10.1 for the labelled two-edge path $F$ with
$E(F)=\\{12,23\\}$. Observe that only in one out of three samples of $P_{2}$
will that path actually be removed; if a triangle is sampled, then two of its
three edges are removed. While this may seem to be at odds with the spirit of
$P_{2}$-removal, this is not actually the case; indeed, eventually all copies
of $P_{2}$ are removed.

######  Remark 10.4.

It is not entirely apparent how to define removal rules which remove a family
of graphs. For example, how should we define a removal rule of order $5$ which
removes the $4$-leaf star and the pentagon at the same time? One possibility
would be to remove all edges that belong to some $4$-leaf star or to some
pentagon. We leave it to the reader whether they find this definition natural
and appealing.

Given a graph $F\in\mathcal{H}_{k}$ we say that a graphon $W$ is _$F$ -free_
if $t(F,W)=0$. In the rest of this section we write $(i,j)\in E(F)$ for any
_ordered_ pair of vertices that forms an edge of a graph $F$. We substitute
into (14) and see that for the $F$-removal rule $\mathcal{R}$, we have

(49) $\mathfrak{V}_{\mathcal{R}}W(x,y)=\sum_{(i,j)\in
E(F)}\sum_{G\in\mathcal{H}_{k}:F\subseteq
G}t_{\mathrm{ind}}^{x,y}(G^{i,j},W)\cdot(-1)=-\sum_{(i,j)\in
E(F)}t^{x,y}(F^{(i,j)},W).$

Most interesting features about removal flip processes concern their
destinations and the way they are approached. Observe that a removal flip
process is non-increasing and thus by (the dual version of) Proposition 8.2(i)
each graphon has a destination. We have the following fact about these
destinations.

######  Fact 10.5.

If $\mathcal{R}$ is the $F$-removal rule and $e(F)\geq 1$, then

$\left\\{\mathrm{dest}_{\mathcal{R}}(W):W\in\mathcal{W}_{0}\right\\}=\left\\{W\in\mathcal{W}_{0}:W\text{
is $F$-free}\right\\}.$

###### Proof.

Indeed, if $W$ is not $F$-free, then $\mathfrak{V}_{\>}W\neq 0$ and
Proposition 3.9 tells us that $W$ is not a destination. The converse
implication is clear. ∎

We give a useful identity. For the sake of brevity, we shall denote
$\Phi^{\infty}W=\mathrm{dest}(W)$.

######  Lemma 10.6.

Let $k\in\mathbb{N}$, $F\in\mathcal{H}_{k}$ and $\mathcal{R}$ be the
$F$-removal rule. For every graphon $W$, every
$T_{1}\in(-\mathrm{age}(W),\infty)$ and $T_{2}\in(T_{1},\infty]$ and every
pair of sets $S_{1},S_{2}\subset\Omega$ we have

$\displaystyle\int_{S_{1}\times
S_{2}}\left(\Phi^{T_{1}}W-\Phi^{T_{2}}W\right)=\sum_{(i,j)\in
E(F)}\int_{t=T_{1}}^{T_{2}}\int_{(x,y)\in S_{1}\times
S_{2}}t^{x,y}(F^{(i,j)},\Phi^{t}W)\;.$

###### Proof.

By Remark 3.4, the left-hand side of the equation is

$\Phi^{T_{1}}W-\Phi^{T_{2}}W=\int_{t=T_{1}}^{T_{2}}(-\mathfrak{V}_{\>}\Phi^{t}W)\;.$

Therefore, except when $T_{2}=\infty$, the Lemma follows by applying Fubini’s
Theorem together with (49). For $T_{2}=\infty$ we have

$\int_{S_{1}\times
S_{2}}\lim_{T\rightarrow\infty}\int_{T_{1}}^{T}(-\mathfrak{V}_{\>}\Phi^{t}W)=\lim_{T\rightarrow\infty}\int_{S_{1}\times
S_{2}}\int_{T_{1}}^{T}(-\mathfrak{V}_{\>}\Phi^{t}W),$

by the Monotone Convergence Theorem (since the velocity is always non-positive
for a removal rule). Therefore, we obtain the desired outcome for
$T_{2}=\infty$ by applying (49) and Fubini’s Theorem inside the limit on the
right-hand side of the equation above. ∎

###  10.1. Destination of a limit

Our next theorem says that the destination is continuous for removal rules.
Recall that in Remark 8.4 we saw that this feature does not hold in the more
general class of monotone rules.

######  Theorem 10.7.

Let $k\in\mathbb{N}$, $F\in\mathcal{H}_{k}$ and $\mathcal{R}$ be an
$F$-removal rule. Suppose that $e(F)>0$. Then the function
$U\mapsto\mathrm{dest}_{\mathcal{R}}(U)$ is continuous as a function from
$\left(\mathcal{W}_{0},d_{\square}\right)$ to itself.

Theorem 10.7 is an important stepping stone towards our proof of Theorem 10.9,
which shows that convergence time is finite and uniformly bounded. The proof
of Theorem 10.7 is quite involved. In particular, it uses Szemerédi’s
regularity lemma, but the advantage is that then the proof of Theorem 10.9 is
short and conceptually simple. On the other hand, Theorem 10.9 is very similar
in spirit to the classical removal lemma. In particular, we ask whether
Theorem 10.9 could be proven using the removal lemma instead of the
Szemerédi’s regularity lemma.

###### Proof.

The statement is obvious when $F$ has at most 2 vertices. So, let us assume
that $v(F)\geq 3$.

Given a graphon $W$, we write $W_{t}=\Phi^{t}W$ and
$W_{\infty}=\mathrm{dest}(W)$. We will show that for every $\gamma>0$ (without
loss of generality, $\gamma<1$) there exists $\delta$ such that if
$d_{\square}(W,U)<\delta$ then $d_{\square}(W_{\infty},U_{\infty})<\gamma$.
With foresight of the cooking process, we set

$\beta:=\frac{\gamma}{8k^{2}},\quad\alpha:=\frac{\beta^{e(F)}}{2k^{k}}.$

Let $M_{0}$ be given by Theorem 2.11 with error parameter $\alpha$. Let
$\varepsilon:=\beta^{e(F)}/(2k^{2}(M_{0})^{k})$. Fix an arbitrary graphon $U$
and pick $T$ such that

(50) $d_{\square}(U_{T},U_{\infty})<\frac{\varepsilon}{2}\;.$

Let $\delta:=\varepsilon/(2\exp(C_{k}T))$, where $C_{k}$ comes from Theorem
3.8.

From now on we fix a graphon $W$ satisfying $d_{\square}(W,U)<\delta$. Theorem
3.8 implies that

$d_{\square}(W_{T},U_{T})\leq\exp(C_{k}T)\cdot
d_{\square}(W,U)<\frac{\varepsilon}{2}\;,$

which we combine with (50) to get that

(51) $d_{\square}(W_{T},U_{\infty})<\varepsilon\;.$

We will show that

(52) $f:=d_{\square}(W_{T},W_{\infty})<\gamma/2$

and combine with (51) to finish the proof.

First notice that since $U_{\infty}$ is a destination, Fact 10.5 implies that
$t(F,U_{\infty})=0$ and therefore Lemma 2.6 yields

(53)
$t(F,W_{T})<k^{2}d_{\square}(W_{T},U_{\infty})\overset{\mbox{\tiny{\eqref{eq:8TWO}}}}{\leq}k^{2}\varepsilon\;.$

The strategy is to obtain a contradiction by showing that if $W_{T}$ is not
too close to its destination, then it has substantial density $t(F,W_{T})$.
Since the $F$-removal rule is non-increasing, we have $W_{T}\geq W_{\infty}$
and in particular

$f=d_{\square}(W_{T},W_{\infty})=\int_{\Omega^{2}}(W_{T}-W_{\infty})\;.$

We apply Theorem 2.11 to find an $\alpha$-regular partition $\mathcal{P}$ of
the graphon $W_{T}-W_{\infty}$ with $M\leq M_{0}$ parts.

Given $\mathbf{S}=(S_{1},\ldots,S_{k})\in\mathcal{P}^{k}$, recall Definition
2.5 and set

$w_{\mathbf{S}}:=\int_{t=T}^{\infty}t^{\mathbf{S}}(F,W_{t})\;.$

From Lemma 10.6 we get that

(54) $\displaystyle f$
$\displaystyle=\int_{\Omega^{2}}\left(W_{T}-W_{\infty}\right)=\sum_{(i,j)\in
E(F)}\int_{t=T}^{\infty}\int_{(x,y)\in\Omega^{2}}t^{x,y}(F^{(i,j)},W_{t})$
(55) $\displaystyle=\sum_{(i,j)\in
E(F)}\int_{t=T}^{\infty}\sum_{\mathbf{S}\in\mathcal{P}^{k}}t^{\mathbf{S}}(F,W_{t})=\sum_{(i,j)\in
E(F)}\sum_{\mathbf{S}\in\mathcal{P}^{k}}w_{\mathbf{S}}\;.$

By (54), there exists $(i,j)\in E(F)$ such that

(56) $\sum_{\mathbf{S}\in\mathcal{P}^{k}}w_{\mathbf{S}}\geq\frac{f}{k^{2}}\;.$

Let $\mathcal{B}_{2}\subset\mathcal{P}^{2}$ be the set of (ordered) pairs that
are either not $\alpha$-regular in the graphon $W_{T}-W_{\infty}$ or have
density below $\beta=\frac{\gamma}{8k^{2}}$. Let
$\mathcal{B}_{k}\subset\mathcal{P}^{k}$ be the set of $k$-tuples $\mathbf{S}$
such that there exists $(i,j)\in E(F)$ such that
$(S_{i},S_{j})\in\mathcal{B}_{2}$. We have

$\begin{split}\sum_{\mathbf{S}\in\mathcal{B}_{k}}w_{\mathbf{S}}&\leq\sum_{(S^{\prime}_{1},S^{\prime}_{2})\in\mathcal{B}_{2}}\sum_{(i,j)\in
E(F)}\sum_{\mathbf{S}:S_{i}=S^{\prime}_{1},S_{j}=S^{\prime}_{2}}w_{\mathbf{S}}\\\
&=\sum_{(S^{\prime}_{1},S^{\prime}_{2})\in\mathcal{B}_{2}}\sum_{(i,j)\in
E(F)}\int_{t=T}^{\infty}\int_{(x,y)\in S_{1}^{\prime}\times
S_{2}^{\prime}}t^{x,y}(F^{(i,j)},W_{t})\\\ \framebox{\tiny{Lemma
\ref{lem:removalrectangle}}}\quad&=\sum_{(S^{\prime}_{1},S^{\prime}_{2})\in\mathcal{B}_{2}}\int_{S^{\prime}_{1}\times
S^{\prime}_{2}}(W_{T}-W_{\infty})\;.\end{split}$

Since, by $\alpha$-regularity of $\mathcal{P}$, the total measure of
rectangles $S_{1}^{\prime}\times S_{2}^{\prime}$ that are not $\alpha$-regular
is at most $\alpha M^{2}\cdot M^{-2}=\alpha$, and the integral over the
remaining rectangles is at most $\beta$, we obtain

(57)
$\sum_{\mathbf{S}\in\mathcal{B}_{k}}w_{\mathbf{S}}\leq\alpha+\beta\leq\frac{\gamma}{4k^{2}}\;.$

We are now in a position to complete the proof by showing (52). Suppose for
contradiction that $f\geq\gamma/2$. Then from (56) and (57) we have

$\sum_{\mathbf{S}\in\mathcal{P}^{k}\setminus\mathcal{B}_{k}}w_{\mathbf{S}}\geq\frac{\gamma}{4k^{2}}>0\;.$

In particular, that means that
$\mathcal{P}^{k}\setminus\mathcal{B}_{k}\neq\emptyset$. Let us take an
arbitrary $\mathbf{S}\in\mathcal{P}^{k}\setminus\mathcal{B}_{k}$. By the
definition of $\mathcal{B}_{k}$, for each $(a,b)\in E(F)$ we have, in the
graphon $W_{T}-W_{\infty}$, that $(S_{a},S_{b})$ is an $\alpha$-regular pair
of density at least $\beta$. Lemma 2.12 gives that

$t(F,W_{T})\geq
t^{\mathbf{S}}(F,W_{T}-W_{\infty})\geq\left(\beta^{e(F)}-\alpha
k^{k}\right)\left(\frac{1}{M_{0}}\right)^{k}\geq\frac{\beta^{e(F)}}{2M_{0}^{k}}\geq
k^{2}\varepsilon\;,$

a contradiction to (53). Hence, we conclude that $f<\gamma/2$, as was needed.
∎

######  Remark 10.8.

One of the main steps in the proof above is similar to the standard deduction
of the removal lemma from Szemerédi’s regularity lemma. That is, substantial
density of $F$ in $W_{T}$ is deduced from a single copy of $F$ in the cluster