# A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph
Process

Pu Gao  Department of Combinatorics and Optimization, University of Waterloo,
Waterloo, Canada<EMAIL_ADDRESS>,  Calum MacRury  Department of Computer
Science, University of Toronto, Toronto, Canada<EMAIL_ADDRESS>and
Paweł Prałat  Department of Mathematics, Toronto Metropolitan University,
Toronto, Canada<EMAIL_ADDRESS>
###### Abstract.

The semi-random graph process is a single player game in which the player is
initially presented an empty graph on $n$ vertices. In each round, a vertex
$u$ is presented to the player independently and uniformly at random. The
player then adaptively selects a vertex $v$, and adds the edge $uv$ to the
graph. For a fixed monotone graph property, the objective of the player is to
force the graph to satisfy this property with high probability in as few
rounds as possible.

We focus on the problem of constructing a Hamiltonian cycle in as few rounds
as possible. In particular, we present an adaptive strategy for the player
which achieves it in $\alpha n$ rounds, where $\alpha<2.01678$ is derived from
the solution to some system of differential equations. We also show that the
player cannot achieve the desired property in less than $\beta n$ rounds,
where $\beta>1.26575$. These results improve the previously best known bounds
and, as a result, the gap between the upper and lower bounds is decreased from
1.39162 to 0.75102.

##  1\. Introduction and Main Results

###  1.1. Definitions

In this paper, we consider the semi-random graph process suggested by Peleg
Michaeli, introduced formally in [3], and studied recently in [2, 9, 10, 1, 7,
12] that can be viewed as a “one player game”. The process starts from
$G_{0}$, the empty graph on the vertex set $[n]:=\\{1,\ldots,n\\}$ where
$n\geq 1$. In each step $t$, a vertex $u_{t}$ is chosen uniformly at random
from $[n]$. Then, the player (who is aware of graph $G_{t}$ and vertex
$u_{t}$) must select a vertex $v_{t}$ and add the edge $u_{t}v_{t}$ to $G_{t}$
to form $G_{t+1}$. The goal of the player is to build a (multi)graph
satisfying a given property $\mathcal{P}$ as quickly as possible. It is
convenient to refer to $u_{t}$ as a square, and $v_{t}$ as a circle so every
edge in $G_{t}$ joins a square with a circle. We say that $v_{t}$ is paired to
$u_{t}$ in step $t$. Moreover, we say that vertex $x\in[n]$ is covered by the
square $u_{t}$ arriving at round $t$, provided $u_{t}=x$. The analogous
definition extends to the circle $v_{t}$. Equivalently, we may view $G_{t}$ as
a directed graph where each arc directs from $u_{t}$ to $v_{t}$, and thus we
may use $(u_{t},v_{t})$ to denote the edge added in step $t$. For this paper,
it is easier to consider squares and circles for counting arguments.

A strategy $\mathcal{S}$ is defined by specifying for each $n\geq 1$, a
sequence of functions $(f_{t})_{t=1}^{\infty}$, where for each
$t\in\mathbb{N}$, $f_{t}(u_{1},v_{1},\ldots,u_{t-1},v_{t-1},u_{t})$ is a
distribution over $[n]$ which depends on the vertex $u_{t}$, and the history
of the process up until step $t-1$. Then, $v_{t}$ is chosen according to this
distribution. If $f_{t}$ is an atomic distribution, then $v_{t}$ is determined
by $u_{1},v_{1},\ldots,u_{t-1},v_{t-1},u_{t}$. We then denote
$(G_{i}^{\mathcal{S}}(n))_{i=0}^{t}$ as the sequence of random (multi)graphs
obtained by following the strategy $\mathcal{S}$ for $t$ rounds; where we
shorten $G_{t}^{\mathcal{S}}(n)$ to $G_{t}$ or $G_{t}(n)$ when clear.

Suppose $\mathcal{P}$ is a monotonely increasing property. Given a strategy
$\mathcal{S}$ and a constant $0<q<1$, let
$\tau_{\mathcal{P}}(\mathcal{S},q,n)$ be the minimum $t\geq 0$ for which
$\mathbb{P}[G_{t}\in\mathcal{P}]\geq q$, where
$\tau_{\mathcal{P}}(\mathcal{S},q,n):=\infty$ if no such $t$ exists. Define

$\tau_{\mathcal{P}}(q,n)=\inf_{\mathcal{S}}\tau_{\mathcal{P}}(\mathcal{S},q,n),$

where the infimum is over all strategies on $[n]$. Observe that for each
$n\geq 1$, if $0\leq q_{1}\leq q_{2}\leq 1$, then
$\tau_{\mathcal{P}}(q_{1},n)\leq\tau_{\mathcal{P}}(q_{2},n)$ as $\mathcal{P}$
is increasing. Thus, the function
$q\rightarrow\limsup_{n\to\infty}\tau_{\mathcal{P}}(q,n)$ is non-decreasing,
and so the limit,

$\tau_{\mathcal{P}}:=\lim_{q\to
1^{-}}\limsup_{n\to\infty}\frac{\tau_{\mathcal{P}}(q,n)}{n},$

is guaranteed to exist. The goal is typically to compute upper and lower
bounds on $\tau_{\mathcal{P}}$ for various properties $\mathcal{P}$.

###  1.2. Main Results

In this paper, we concentrate on the property of having a Hamiltonian cycle,
which we denote by ${\tt HAM}$. As observed in [3], if $G_{t}$ has a
Hamiltonian cycle, then $G_{t}$ has minimum degree at least 2. Thus,
$\tau_{\tt HAM}\geq\tau_{\mathcal{P}}=\ln 2+\ln(1+\ln 2)\geq 1.21973$, where
$\mathcal{P}$ corresponds to having minimum degree $2$. On the other hand, it
is known that the famous $3$-out process is Hamiltonian with probability
tending to 1 as $n\to\infty$ (_a.a.s._) [6]. As the semi-random process can be
coupled with the $3$-out process, we get that $\tau_{\tt HAM}\leq 3$. A new
upper bound was obtained in [9] in terms of an optimal solution to an
optimization problem whose value is believed to be $2.61135$ by numerical
support. In the same paper, the lower bound mentioned above was shown to not
be tight. The lower bound was increased by $\varepsilon=10^{-8}$ and so
numerically negligible.

The upper bound on $\tau_{\tt HAM}$ of $3$ obtained by simulating the $3$-out
process is non-adaptive. That is, the strategy does not depend on the history
of the semi-random process. The above mentioned improvement proposed in [9]
uses an adaptive strategy but in a weak sense. The strategy consists of 4
phases, each lasting a linear number of rounds, and the strategy is adjusted
_only_ at the end of each phase (for example, the player might identify
vertices of low degree, and then focus on connecting circles to them during
the next phase).

In this paper, we propose a fully adaptive strategy that pays attention to the
graph $G_{t}$ and the position of $u_{t}$ for every single step $t$. As
expected, such a strategy creates a Hamiltonian cycle substantially faster
than our weakly adaptive strategy, and it allows us to improve the upper bound
from $2.61135$ to $2.01678$.

######  Theorem 1.1.

$\tau_{\texttt{HAM}}\leq\alpha\leq 2.01678$, where $\alpha$ is derived from a
system of differential equations.

The numerical results presented in this paper were obtained using the Julia
language [5]. We would like to thank Bogumił Kamiński from SGH Warsaw School
of Economics for helping us to implement it. The program is available on-
line.111https://math.ryerson.ca/~pralat/research.html#publications

Moreover, by investigating some specific structures that are generated by the
semi-random process, which guarantee the existence of a large set of families
of edges that cannot simultaneously contribute to the construction of a
Hamiltonian cycle, we improve the lower bound of $\ln 2+\ln(1+\ln 2)\geq
1.21973$ to $1.26575$. The structures we investigate in this work are
different from the ones in [9]. We attain a simpler proof than in [9], and a
much stronger bound.

######  Theorem 1.2.

Let
$f(s)=2+e^{-3s}(s+1)\left(1-\frac{s^{2}}{2}-\frac{s^{3}}{3}-\frac{s^{4}}{8}\right)+e^{-2s}\left(2s+\frac{5s^{2}}{2}+\frac{s^{3}}{2}\right)-e^{-s}\left(3+2s\right)$,
and let $\beta\approx 1.26575$ be the positive root of $f(s)-1=0$. Then,
$\tau_{\texttt{HAM}}\geq\beta$.

###  1.3. Previous Results

Let us briefly describe a few known results on the semi-random process. In the
very first paper [3], it was shown that the process is general enough to
approximate (using suitable strategies) several well-studied random graph
models. In the same paper, the process was studied for various natural
properties such as having minimum degree $k\in{\mathbb{N}}$ or having a fixed
graph $H$ as a subgraph. In particular, it was shown that _a.a.s._ one can
construct $H$ in less than $n^{(d-1)/d}\omega$ rounds where $d\geq 2$ is the
degeneracy of $G$ and $\omega=\omega(n)$ is any function that tends to
infinity as $n\to\infty$. This property was recently revisited in [1] where
the conjecture from [3] was proven for any graph $H$: _a.a.s._ it takes at
least $n^{(d-1)/d}/\omega$ rounds to create $H$.

Another property that was studied in the context of semi-random processes is a
property of having a perfect matching, which we denote by PM. Since the
$2$-out process has a perfect matching _a.a.s._ [8], we immediately get that
$\tau_{\texttt{PM}}\leq 2$. By coupling the semi-random process with another
random graph that is known to have a perfect matching _a.a.s._ [11], the bound
can be improved to $1+2/e<1.73576$. This bound was recently improved by the
authors of this paper by investigating another fully adaptive algorithm [10].
The currently best upper bound is $\tau_{\texttt{PM}}<1.20524$. In the same
paper, the lower bound observed in [3]
($\tau_{\texttt{PM}}\geq\ln(2)>0.69314$) was improved as well, and now we know
that $\tau_{\texttt{PM}}>0.93261$ [10].

Finally, let us discuss what is known about the property of containing a given
spanning graph $H$ as a subgraph. It was asked by Noga Alon whether for any
bounded-degree $H$, one can construct a copy of $H$ _a.a.s._ in $O(n)$ rounds.
This question was answered positively in a strong sense in [2], in which it
was shown that any graph with maximum degree $\Delta$ can be constructed
_a.a.s._ in $(3\Delta/2+o(\Delta))n$ rounds. They also proved that if
$\Delta=\omega(\log(n))$, then this upper bound improves to
$(\Delta/2+o(\Delta))n$ rounds. Note that both of these upper bounds are
asymptotic in $\Delta$. When $\Delta$ is constant in $n$, such as in both the
perfect matching and Hamiltonian cycle setting, determining the optimal
dependence on $\Delta$ for the number of rounds needed to construct $H$
remains open.

##  2\. Proof of Theorem 1.1

###  2.1. Algorithmic Preliminaries

In this section, we introduce some notation as well as the basic ideas used in
the design of all of our strategies.

The main ingredient for proving Theorem 1.1 is to specify a strategy which
keeps augmenting or extending a path, until the path becomes Hamiltonian.
Then, with a few more steps, the Hamiltonian path can be completed into a
Hamiltonian cycle. Let us suppose that after $t\geq 0$ steps, we have
constructed the graph $G_{t}$ which contains the path $P_{t}$. Define $U_{t}$
to be the set of vertices not in $P_{t}$, which we refer to as the unsaturated
vertices of $[n]$. It will be convenient to denote the (induced) distance
between vertices $x,y\in V(P_{t})$ on the path $P_{t}$ by $d_{P_{t}}(x,y)$. We
also define $d_{P_{t}}(x,Q):=\min_{q\in Q}d_{P_{t}}(x,q)$ for $x\in V(P_{t})$
and $Q\subseteq V(P_{t})$.

Let us first assume that $u_{t+1}$ lands in $U_{t}$. In this case, we can
clearly extend the path $P_{t}$ by an edge by choosing $v_{t+1}$ to be an
endpoint of $P_{t}$. We call such a move a (greedy) path extension. Now,
suppose that $u_{t+1}$ lands on a vertex $x\in P_{t}$. In this case, we cannot
perform a greedy path extension, however we can still choose $v_{t+1}$ in a
way that will help us extend the path in the future rounds. Specifically, set
$v_{t+1}:=r$ for some $r\in U_{t}$, and colour the vertex $x$ as well as the
edge $xr$. Suppose that in some round $i>t+1$, $u_{i}$ lands on $y$ next to
the coloured vertex $x$ on $P_{i}$ (i.e., $d_{P_{i}}(x,y)=1$). In this case,
set $v_{i}=r$. Observe now that we can add $r$ to the current path by adding
the edges $yr$ and $xr$ to it, and by removing the edge $yx$. Thus, despite
$u_{s}$ not landing on an unsaturated vertex, we are still able to perform a
move which extends its length by one. We call such an operation a path
augmentation.

###  2.2. Proof Overview

In order to prove Theorem 1.1, we analyze a strategy which proceeds in three
distinct stages. In the first stage, we execute $\mathtt{DegreeGreedy}$, an
algorithm which makes greedy path extensions whenever possible, and otherwise
sets up path augmentation operations for future rounds in a degree greedy
manner. Specifically, $v_{t+1}$ is chosen amongst the unsaturated vertices of
minimum coloured in-degree. This degree greedy decision is done to minimize
the number of coloured vertices which are destroyed when path augmentations
and extensions are made in later rounds. This stage lasts for $N$ phases,
where $N$ is any non-negative integer that may be viewed as the parameter of
the algorithm (here a phase is a contiguous set of steps shorter than the full
stage). For the claimed (numerical) upper bound of Theorem 1.1, $N$ is set to
$100$. Setting smaller values of the parameter $N$—in particular, setting
$N=0$—yields an algorithm that is easier to analyse. Setting $N>100$ can
slightly improve the bound in Theorem 1.1, but the gain is rather
insignificant. The second stage starts at some random step $t_{0}$ (i.e.
$t_{0}-1$ is the total number of steps in stage one), and we execute
$\mathtt{FullyRandomized}$, an algorithm which makes greedy path extensions
whenever possible, and otherwise chooses $v_{t+1}$ randomly amongst the
unsaturated vertices. We execute $\mathtt{FullyRandomized}$ until we are left
with $\varepsilon n$ unsaturated vertices, where $\varepsilon=\varepsilon(n)$
tends to $0$ as $n\rightarrow\infty$ arbitrarily slowly. At this point, we
proceed to the final stage where a clean-up algorithm is run, which also uses
path augmentations. Using elementary concentration inequalities we prove that
a Hamiltonian cycle can be constructed in an additional
$O(\sqrt{\varepsilon}n)=o(n)$ steps.

In Section 2.3, we first describe $\mathtt{FullyRandomized}$, as it is easier
to state and analyze than $\mathtt{DegreeGreedy}$. Moreover, if we take $N=0$,
which corresponds to executing $\mathtt{FullyRandomized}$ from the beginning,
then we will be left with a path on all but $\varepsilon n$ vertices after
$\alpha^{*}n$ steps where $\alpha^{*}\leq 2.07721$. Our third stage clean-up
algorithm from Section 2.4 allows us to complete the Hamiltonian cycle in
another $o(n)$ steps. Thus, Sections 2.3 and 2.4 provide a self-contained
proof of an upper bound on $\tau_{\mathtt{HAM}}$ of $\alpha^{*}\leq 2.07721$
(see Theorem 2.6). Afterwards, in Section 2.5 we formally state and analyze
our first stage algorithm. This is the most technical section of the paper, as
$\mathtt{DegreeGreedy}$ makes decisions in a more intelligent manner than
$\mathtt{FullyRandomized}$ which necessitates more random variables in its
analysis. By executing these three stages in the aforementioned order, we
attain the claimed upper bound of Theorem 1.1.

###  2.3. A Fully Randomized Algorithm

In order to describe our algorithm, it will be convenient to colour certain
edges of $G_{t}$ red. This helps us define certain vertices used by our
algorithm for path augmentations. Specifically, $x\in V(P_{t})$ is one-red
provided it is adjacent to precisely one red edge of $G_{t}$. Similarly, $x\in
V(P_{t})$ is two-red, provided it is adjacent to precisely two red edges of
$G_{t}$. We denote the one-red vertices and two-red vertices by
$\mathcal{L}^{1}_{t}$ and $\mathcal{L}^{2}_{t}$, respectively, and refer to
$\mathcal{L}_{t}:=\mathcal{L}^{1}_{t}\cup\mathcal{L}^{2}_{t}$ as the red
vertices of $G_{t}$. By definition, $\mathcal{L}^{1}_{t}$ and
$\mathcal{L}^{2}_{t}$ are disjoint. It will also be convenient to maintain a
set of permissible vertices $\mathcal{Q}_{t}\subseteq V(P_{t})$ which
specifies which uncoloured vertices on the path can be turned red. In order to
simplify our analysis, we specify the size of $\mathcal{Q}_{t}$ and ensure
that it only contains vertices of path distance at least $3$ from the red
vertices on $P_{t}$. Formally:

  1. (i)

$|\mathcal{Q}_{t}|=|V(P_{t})|-5|\mathcal{L}_{t}|$.

  2. (ii)

If $\mathcal{L}_{t}\neq\emptyset$, then each $x\in\mathcal{Q}_{t}$ satisfies
$d_{P_{t}}(x,\mathcal{L}_{t})\geq 3$.

When $\mathcal{L}_{t}=\emptyset$, we simply take $\mathcal{Q}_{t}=V(P_{t})$.
Otherwise, since $|\\{x\in V(P_{t}):d_{P_{t}}(x,\mathcal{L}_{t})\leq 2\\}|\leq
5|\mathcal{L}_{t}|$, we can maintain these properties by initially taking
$\\{x\in V(P_{t}):d_{P_{t}}(x,\mathcal{L}_{t})\geq 3\\}$, and then (if needed)
arbitrarily removing $|\\{x\in V(P_{t}):d_{P_{t}}(x,\mathcal{L}_{t})\geq
3\\}|-(|V(P_{t})|-5|\mathcal{L}_{t}|)$ vertices from it.

Upon the arrival of $u_{t+1}$, there are four main cases our algorithm must
handle. The first two cases involve extending the length of the path, whereas
the latter two describe what to do when it is not possible to extend the path
in the current round.

  1. (1)

If $u_{t+1}$ lands within $U_{t}$, then greedily extend $P_{t}$.

  2. (2)

If $u_{t+1}$ lands at path distance one from some $x\in\mathcal{L}_{t}$, then
augment $P_{t}$ via an arbitrary red edge of $x$.

  3. (3)

If $u_{t+1}$ lands in $\mathcal{Q}_{t}$, then choose $v_{t+1}$ u.a.r. amongst
$U_{t}$, and colour $u_{t+1}v_{t+1}$ red. This case creates a one-red vertex.

  4. (4)

If $u_{t+1}$ lands in $\mathcal{L}^{1}_{t}$, then choose $v_{t+1}$ u.a.r.
amongst $U_{t}$ and colour $u_{t+1}v_{t+1}$ red. This case converts a one-red
vertex to a two-red vertex.

In all the remaining cases, we choose $v_{t+1}$ arbitrarily, and interpret the
algorithm as passing on the round, meaning the edge $u_{t}v_{t}$ will not be
used to construct a Hamiltonian cycle. In particular, the algorithm passes
rounds in which $u_{t+1}$ lands at path distance two from some
$x\in\mathcal{L}_{t}$. This guarantees that no two red vertices are at
distance two from each other and so when $u_{t+1}$ lands next to a red vertex,
this neighbouring red vertex is uniquely identified. Let us say that a red
vertex is well-spaced, provided it is at distance at least $3$ on the path
from all other red vertices, and it is not an endpoint of $P_{t}$. Observe
that each well-spaced red vertex yields precisely two vertices on $P_{t}$
where a path augmentation involving $u_{t+1}$ can occur. By construction, all
but at most $2$ of the algorithm’s red vertices are well-spaced.

We now formally describe step $t+1$ of the algorithm when $u_{t+1}$ is drawn
u.a.r. from $[n]$. Specifically, we describe how the algorithm chooses
$v_{t+1}$, how it constructs $P_{t+1}$, and how it adjusts the colours of
$G_{t+1}$, thus updating $\mathcal{L}^{1}_{t}$ and $\mathcal{L}^{2}_{t}$.

Algorithm $\mathtt{FullyRandomized}$ Step $t+1$

1:if $u_{t+1}\in U_{t}$ then $\triangleright$ greedily extend the path.

2: Let $v_{t+1}$ be an arbitrarily chosen endpoint of $P_{t}$.

3: Set $V(P_{t+1})=V(P_{t})\cup\\{u_{t+1}\\}$,
$E(P_{t+1})=E(P_{t})\cup\\{u_{t+1}v_{t+1}\\}$.

4: Uncolour all of the edges adjacent to $u_{t+1}$.

5:else if $d_{P_{t}}(u_{t+1},\mathcal{L}_{t})=1$ then $\triangleright$ path
augment via red vertices

6: Let $x\in\mathcal{L}_{t}$ be the (unique) red vertex adjacent to $u_{t+1}$

7: Denote $xr\in E(G_{t})$ an arbitrary red edge of $x$, and set $v_{t+1}=r$,
where $r\in U_{t}$.

8: Set $V(P_{t+1})=V(P_{t})\cup\\{r\\}$ and
$E(P_{t+1})=E(P_{t})\cup\\{u_{t+1}r,xr\\}\setminus\\{u_{t+1}x\\}$.

9: Uncolour all of the edges adjacent to $r$.

10:else if $u_{t+1}\in\mathcal{Q}_{t}\cup\mathcal{L}_{t}$ then
$\triangleright$ construct red vertices

11: Choose $v_{t+1}$ u.a.r. from $U_{t}$.

12: Colour $u_{t+1}v_{t+1}$ red. $\triangleright$ construct a one-red or two-
red vertex

13: Set $P_{t+1}=P_{t}$.

14:else $\triangleright$ pass on using edge $u_{t+1}v_{t+1}$.

15: Choose $v_{t+1}$ arbitrarily from $[n]$.

16: Set $P_{t+1}=P_{t}$.

17:end if

18:Update $\mathcal{Q}_{t+1}$ such that
$|\mathcal{Q}_{t+1}|=|V(P_{t+1})|-5|\mathcal{L}_{t+1}|$.

We define the random variables $X(t)=|V(P_{t})|$,
$L_{1}(t)=|\mathcal{L}^{1}_{t}|$, $L_{2}(t)=|\mathcal{L}^{2}_{t}|$, and
$L(t)=|\mathcal{L}_{t}|=L_{1}(t)+L_{2}(t)$. Note that $L(t)$ is an auxiliary
random variable which we define only for convenience. We use $\Delta$ to
denote the one step changes in our random variables (i.e., $\Delta
X(t):=X(t+1)-X(t)$). Recall that $t_{0}$ is the step when
$\mathtt{FullyRandomized}$ is called. Let us first show that our random
variables cannot change drastically in one round.

######  Lemma 2.1 (Boundedness Hypothesis – $\mathtt{FullyRandomized}$).

With probability $1-O(n^{-1})$,

$\max\\{|\Delta X(t)|,|\Delta L_{1}(t)|,|\Delta L_{2}(t)|\\}=O(\log n)$

for all $t_{0}\leq t\leq 3n$ with $n-X(t)\geq n/\log n$.

###### Proof.

Note that, by design, the path can only increase its length but it cannot
absorb more than one vertex in each round. Hence, the desired property clearly
holds for the random variable $X(t)$. To estimate the maximum change for the
random variables $L_{1}(t)$ and $L_{2}(t)$, we need to upper bound the number
of red edges adjacent to any particular unsaturated vertex $v$. Observe that
at any step $t\leq 3n$, since we have assumed there are at least $n/\log n$
unsaturated vertices, the number of red edges adjacent to $v$ is
stochastically upper bounded by the binomial random variable
$\mathrm{Bin}(3n,\log n/n$) with expectation $3\log n$. It follows immediately
from Chernoff’s bound that with probability $1-O(n^{-3})$, the number of red
edges adjacent to $v$ is $O(\log n)$, and so the desired bound holds by union
bounding over all $3n^{2}$ vertices and steps. ∎

Let us denote $H_{t}=(X(i),L_{1}(i),L_{2}(i))_{0\leq i\leq t}$. Note that
$H_{t}$ does not encompass the entire history of the random process after $t$
rounds (i.e., $G_{0},\ldots,G_{t}$, the first $t+1$ graphs constructed by the
algorithm). This deferred information exposure permits a tractable analysis of
the random positioning of $v_{t}$ when $u_{t}$ is red. We observe the
following expected difference equations.

######  Lemma 2.2 (Trend Hypothesis – $\mathtt{FullyRandomized}$).

For each $t\geq t_{0}$, if $n-X(t)\geq n/\log n$, then

$\displaystyle\mathbb{E}[\Delta X(t)\mid H_{t}]$ $\displaystyle=$
$\displaystyle 1-\frac{X(t)}{n}+\frac{2L(t)}{n}+O(\log n/n)$ (1)
$\displaystyle\mathbb{E}[\Delta L_{1}(t)\mid H_{t}]$ $\displaystyle=$
$\displaystyle\frac{X(t)-5L(t)}{n}+\frac{2L_{1}(t)}{n}\left(\frac{2L_{2}(t)}{n-X(t)}-\frac{L_{1}(t)}{n-X(t)}-1\right)$
(2)
$\displaystyle+\frac{2L_{2}(t)}{n}\left(1+\frac{2L_{2}(t)}{n-X(t)}-\frac{L_{1}(t)}{n-X(t)}\right)-\frac{L_{1}(t)}{n}$
$\displaystyle+\left(1-\frac{X(t)}{n}\right)\left(\frac{2L_{2}(t)}{n-X(t)}-\frac{L_{1}(t)}{n-X(t)}\right)+O(\log
n/n)$ $\displaystyle\mathbb{E}[\Delta L_{2}(t)\mid H_{t}]$ $\displaystyle=$
$\displaystyle\frac{L_{1}(t)}{n}-\left(1-\frac{X(t)}{n}\right)\frac{2L_{2}(t)}{n-X(t)}-\frac{2L_{1}(t)}{n}\frac{2L_{2}(t)}{n-X(t)}$
(3)
$\displaystyle-\frac{2L_{2}(t)}{n}\left(1+\frac{2L_{2}(t)}{n-X(t)}\right)+O(\log
n/n).$

The proof is obtained by examining how the landing of $u_{t}$ affects the
random variables under study. For instance, for $X(t)$, observe that $\Delta
X(t)$ is $1$ when $u_{t+1}$ lands on an unsaturated vertex, or adjacent to a
red vertex; and is 0 otherwise. Combining with the probabilities of the above
two events yields (1). The proofs for (2) and (3) are similar and the details
can be found in Appendix A.

In order to analyze $\mathtt{FullyRandomized}$, we shall employ the
differential equation method [14]. This method is commonly used in
probabilistic combinatorics to analyze random processes that evolve step by
step. The step changes must be small in relation to the entirety of the
discrete structure. For instance, in our application, this refers to adding
one edge at a time to the graph on $[n]$ vertices. The method allows us to
derive tight bounds on the associated random variables which hold a.a.s. at
every step of the random process. We refer the reader to [4] for a gentle
introduction to the methodology. The execution of $\mathtt{FullyRandomized}$
starts at some random step $t_{0}$, which we will prove is a.a.s. asymptotic
to $s_{0}n$ for some constant $0\leq s_{0}<1$. Let $X(t_{0})$ denote the
number of vertices on $P_{t}$ after the execution of $\mathtt{DegreeGreedy}$.
We shall prove that there exists some constant $\hat{x}(s_{0})$ such that
$|X(t_{0})/n-\hat{x}(s_{0})|\leq\lambda$ for some $\lambda=o(1)$. If $N$ is
set to 0, then $t_{0}=s_{0}=X(0)=\hat{x}(0)=0$.

Let us now fix a sufficiently small constant $\varepsilon>0$, and define the
bounded domain

$\mathcal{D}_{\varepsilon}:=\\{(s,x,\ell_{1},\ell_{2}):-1<s<3,-1<x<1-\varepsilon,|\ell_{1}|<2,|\ell_{2}|<2\\}.$

Consider the system of differential equations in variable $s$ with functions
$x=x(s),\ell_{1}=\ell_{1}(s)$, and $\ell_{2}=\ell_{2}(s)$:

$\displaystyle x^{\prime}$ $\displaystyle=$ $\displaystyle
1-x+2(\ell_{1}+\ell_{2})$ (4) $\displaystyle\ell_{1}^{\prime}$
$\displaystyle=$ $\displaystyle
x-5(\ell_{1}+\ell_{2})+\ell_{1}\left(\frac{2\ell_{2}-\ell_{1}}{1-x}-1\right)+2\ell_{2}\left(1+\frac{2\ell_{2}-\ell_{1}}{1-x}\right)-\ell_{1}+2\ell_{2}-\ell_{1}$
(5) $\displaystyle\ell_{2}^{\prime}$ $\displaystyle=$
$\displaystyle\ell_{1}-2\ell_{2}-2\ell_{1}\left(\frac{2\ell_{2}}{1-x}\right)-2\ell_{2}\left(1+\frac{2\ell_{2}}{1-x}\right).$
(6)

The right-hand side (r.h.s.) of each of the above equations is Lipchitz on the
domain $\mathcal{D}_{\varepsilon}$. Define

$T_{\mathcal{D}_{\varepsilon}}=\min\\{t\geq 0:\
(t/n,X(t)/n,L_{1}(t)/n,L_{2}(t)/n)\notin\mathcal{D}_{\varepsilon}\\}.$

Now, the ‘Initial Condition’ of Theorem D.1 is satisfied with values
$(s_{0},\hat{x}(s_{0}),0,0)$ and some $\lambda=o(1)$. Moreover, the ‘Trend
Hypothesis’ and ‘Boundedness Hypothesis’ are satisfied with some
$\delta=O(\log n/n)$, $\beta=O(\log n)$ and $\gamma=o(n^{-1})$, by Lemmas 2.1
and 2.2. Thus, for every $\delta>0$, $X(t)=nx(t/n)+o(n)$,
$L_{1}(t)=n\ell_{1}(t/n)+o(n)$ and $L_{2}(t)=n\ell_{2}(t/n)+o(n)$ uniformly
for all $t_{0}\leq t\leq(\sigma(\varepsilon)-\delta)n$, where $x$, $\ell_{1}$
and $\ell_{2}$ are the unique solution to (4)–(6) with initial conditions
$x(s_{0})=\hat{x}(s_{0})$, $\ell_{1}(s_{0})=\ell_{2}(s_{0})=0$, and
$\sigma(\varepsilon)$ is the supremum of $s$ to which the solution can be
extended before reaching the boundary of $\mathcal{D}_{\varepsilon}$. For
$N=0$, $s_{0}=0$ and the initial conditions are simply
$x(0)=\ell_{1}(0)=\ell_{2}(0)=0$. This immediately yields the following.

######  Lemma 2.3 (Concentration of $\mathtt{FullyRandomized}$’s Random
Variables).

For every $\delta>0$, a.a.s. for all $t_{0}\leq
t\leq(\sigma(\varepsilon)-\delta)n$,

$\max\\{|X(t)-x(t/n)n|,|L_{1}(t)-\ell_{1}(t/n)n|,|L_{2}(t)-\ell_{2}(t/n)n|\\}=o(n).$

As $\mathcal{D}_{\varepsilon}\subseteq\mathcal{D}_{\varepsilon^{\prime}}$ for
every $\varepsilon>\varepsilon^{\prime}$, $\sigma(\varepsilon)$ is monotonely
nondecreasing as $\varepsilon\to 0$. Thus,

$\alpha^{*}:=\lim_{\varepsilon\to 0+}\sigma(\varepsilon)$ (7)

exists. It is obvious that $|L_{1}(t)/n|$ and $|L_{2}(t)/n|$ are both bounded
by 1 for all $t$ and thus, when $t/n$ approaches $\alpha^{*}$, either $X(t)/n$
approaches 1 or $t/n$ approaches 3. Formally, we have the following
proposition.

######  Proposition 2.4.

For every $\varepsilon>0$, there exists $\delta>0$ such that a.a.s. one of the
following holds.

  * •

$X(t)>(1-\varepsilon)n$ for all $t\geq(\alpha^{*}-\delta)n$;

  * •

$\alpha^{*}=3$.

The ordinary differential equations (4)–(6) do not have an analytical
solution. In both cases $N=0$ and $N=100$, numerical solutions show that
$\alpha^{*}<2.1$. (For $N=0$, $\alpha^{*}\approx 2.07721$.) Thus, by the end
of the execution of $\mathtt{FullyRandomized}$, there are $\varepsilon n$
unabsorbed vertices remaining, for some $\varepsilon=o(1)$.

###  2.4. A Clean-up Algorithm

Suppose that we are presented a path $P$ on $(1-\varepsilon)n$ vertices of
$[n]$, where $0<\varepsilon=\varepsilon(n)<1/1000$. The assumption on
$\varepsilon$ is a mild but convenient assumption. We will apply the argument
for $\varepsilon=o(1)$. In this section, we provide an algorithm for the semi-
random graph process which absorbs the remaining $\varepsilon n$ vertices into
$P$ to form a Hamiltonian path, after which a Hamiltonian cycle can be
constructed. The whole procedure takes
$O(\sqrt{\varepsilon}n+n^{3/4}\log^{2}n)=o(n)$ further steps in the semi-
random graph process. Moreover, the algorithm is self-contained in that it
only uses the edges of $P$ in its execution.

######  Lemma 2.5 (Clean-up Algorithm).

Let $0<\varepsilon=\varepsilon(n)<1/1000$, and suppose that $P$ is a path on
$(1-\varepsilon)n$ vertices of $[n]$. Then, given $P$ initially, there exists
a strategy for the semi-random graph process which builds a Hamiltonian cycle
from $P$ in $O(\sqrt{\varepsilon}n+n^{3/4}\log^{2}n)$ steps a.a.s.

######  Remark 1.

The constant hidden in the $O(\cdot)$ notation does not depend on
$\varepsilon$. The strategy used in the clean-up algorithm is similar to that
in $\mathtt{FullyRandomized}$ but the analysis is done in a much less accurate
way, as we only need to prove an $o(n)$ bound on the number of steps required
to absorb $\varepsilon n$ vertices. The proof is presented in Appendix A.

By setting $N=0$ we immediately get an algorithm which a.a.s. constructs a
Hamiltonian cycle in $\hat{\alpha}n$ steps, where $\hat{\alpha}\leq 2.07721$.
To obtain the better bound in Theorem 1.1, we set $N=100$, and the execution
of $\mathtt{DegreeGreedy}$ will be analysed in the next subsection.

######  Theorem 2.6.

$\tau_{\mathtt{HAM}}\leq\hat{\alpha}\leq 2.07721$, where $\hat{\alpha}$ is
defined in (7) with initial conditions for (4)–(6) set by
$x(0)=\ell_{1}(0)=\ell_{2}(0)=0$.

###### Proof.

This follows by Proposition 2.4, the numerical value of $\alpha^{*}$, and
Lemma 2.5.∎

###  2.5. A Degree-Greedy Algorithm

Let us suppose that after $t\geq 0$ steps, we have constructed the graph
$G_{t}$ which contains the path $P_{t}$. As before, our algorithm uses path
augmentations, and we colour the edges of $G_{t}$ to help keep track of when
these augmentations can be made. We now use two colours, namely red and blue,
to distinguish between edges which are added randomly (red) and greedily
(blue). Our blue edges will be chosen so as to minimize the number of blue
edges destroyed by path augmentations in future rounds.

We say that $x\in V(P_{t})$ is blue, provided it is adjacent to a single blue
edge of $G_{t}$, and no red edge. Similarly, $x\in V(P_{t})$ is red, provided
it is adjacent to a single red edge of $G_{t}$, and no blue edge. Finally, we
say that $x\in V(P_{t})$ is magenta (mixed), provided it is adjacent to a
single red edge, and a single blue red. We denote the blue vertices, red
vertices, and magenta (mixed) vertices by $\mathcal{B}_{t},\mathcal{R}_{t}$
and $\mathcal{M}_{t}$, respectively, and define
$\mathcal{L}_{t}:=\mathcal{B}_{t}\cup\mathcal{R}_{t}\cup\mathcal{M}_{t}$ to be
the coloured vertices. By definition, $\mathcal{B}_{t},\mathcal{R}_{t}$ and
$\mathcal{M}_{t}$ are disjoint. Once again, we denote our unsaturated vertices
by $U_{t}$, and also maintain a set of permissible vertices $\mathcal{Q}_{t}$
which indicate which saturated vertices are allowed to be coloured blue.
Specifically, using the same reasoning as before, we ensure the following:

  1. (i)

$|\mathcal{Q}_{t}|=|V(P_{t})|-5|\mathcal{L}_{t}|$.

  2. (ii)

If $\mathcal{L}_{t}\neq\emptyset$, then each $x\in\mathcal{Q}_{t}$ satisfies
$d_{P_{t}}(x,\mathcal{L}_{t})\geq 3$.

Upon the arrival of $u_{t+1}$, there are five main cases our algorithm must
handle. The first two cases involve extending the length of the path, whereas
the latter three describe what to do when it is not possible to extend the
path in the current round.

  1. (1)

If $u_{t+1}$ lands within $U_{t}$, then greedily extend $P_{t}$.

  2. (2)

If $u_{t+1}$ lands at path distance one from $x\in\mathcal{L}_{t}$, then
augment $P_{t}$ via a coloured edge of $x$, where a blue edge is taken over a
red edge if possible.

  3. (3)

If $u_{t+1}$ lands in $\mathcal{Q}_{t}$, then choose $v_{t+1}$ u.a.r. amongst
those vertices of $U_{t}$ with minimum blue degree. The edge $u_{t+1}v_{t+1}$
is then coloured blue, and a single blue vertex is created.

  4. (4)

If $u_{t+1}$ lands in $\mathcal{R}_{t}$, then choose $v_{t+1}$ u.a.r. amongst
those vertices of $U_{t}$ with minimum blue degree. The edge $u_{t+1}v_{t+1}$
is then coloured blue, and a single red vertex is converted to a magenta
(mixed) vertex.

  5. (5)

If $u_{t+1}$ lands in $\mathcal{B}_{t}$, then choose $v_{t+1}$ u.a.r. amongst
$U_{t}$ and colour $u_{t+1}v_{t+1}$ red. This case converts a blue vertex to a
magenta vertex.

In all the remaining cases, we choose $v_{t+1}$ uniformly at random, and
interpret the algorithm as passing on the round. Below we formally describe
step $t+1$ of the algorithm upon receiving $u_{t+1}$:

Algorithm $\mathtt{DegreeGreedy}$ Step $t+1$

1:if $u_{t+1}\in U_{t}$ then $\triangleright$ greedily extend the path

2: Let $v_{t+1}$ be an arbitrarily chosen endpoint of $P_{t}$.

3: Set $V(P_{t+1})=V(P_{t})\cup\\{u_{t+1}\\}$,
$E(P_{t+1})=E(P_{t})\cup\\{u_{t+1}v_{t+1}\\}$.

4: Uncolour all of the edges adjacent to $u_{t+1}$.

5:else if $d(u_{t+1},\mathcal{L}_{t})=1$ then $\triangleright$ path augment
via coloured vertices

6: Let $x\in\mathcal{L}_{t}$ be the (unique) coloured vertex adjacent to
$u_{t+1}$

7: if $x$ is red then

8: Denote $xy\in E(G_{t})$ the red edge of $x$, where $y\in U_{t}$.

9: else $\triangleright$ $x$ is blue or magenta

10: Denote $xy\in E(G_{t})$ the blue edge of $x$, where $y\in U_{t}$.

11: end if

12: Set $v_{t+1}=y$.

13: Set $V(P_{t+1})=V(P_{t})\cup\\{y\\}$ and
$E(P_{t+1})=E(P_{t})\cup\\{u_{t+1}y,xy\\}\setminus\\{u_{t+1}x\\}$.

14: Uncolour all of the edges adjacent to $y$.

15:else if $u_{t+1}\in\mathcal{Q}_{t}\cup\mathcal{R}_{t}$ then
$\triangleright$ construct coloured vertices

16: Choose $v_{t+1}$ u.a.r. from the vertices of $U_{t}$ of minimum blue
degree.

17: Colour $u_{t+1}v_{t+1}$ blue. $\triangleright$ create a blue or magenta
vertex

18: Set $P_{t+1}=P_{t}$.

19:else if $u_{t+1}\in\mathcal{B}_{t}$ then

20: Choose $v_{t+1}$ u.a.r. from $U_{t}$.

21: Colour the edge $u_{t+1}v_{t+1}$ red. $\triangleright$ create a magenta
vertex

22: Set $P_{t+1}=P_{t}$.

23:else $\triangleright$ pass on using edge $u_{t+1}v_{t+1}$

24: Choose $v_{t+1}$ u.a.r. from $[n]$.

25: Set $P_{t+1}=P_{t}$.

26:end if

27:Update $\mathcal{Q}_{t+1}$ such that
$|\mathcal{Q}_{t+1}|=|V(P_{t+1})|-5|\mathcal{L}_{t+1}|$. $\triangleright$
update permissible vertices

As in $\mathtt{FullyRandomized}$, we ensure that all of the algorithm’s
coloured vertices are at path distance at least $3$ from each other, and we
define a coloured vertex to be well spaced in the same way. Note that red
vertices are only created when the blue edges of magenta vertices are
uncoloured as a side effect of path extensions and augmentations (see lines
(4) and (14)).

For each $t\geq 0$, define the random variables $X(t):=|V(P_{t})|$,
$B(t):=|\mathcal{B}_{t}|$, $R(t):=|\mathcal{R}_{t}|$,
$M(t):=|\mathcal{M}_{t}|$ and $L(t):=|\mathcal{L}_{t}|=B(t)+R(t)+M(t)$. For
each $q\geq 0$ and $t\geq 0$, define $D_{q}(t)$ to be the number of
unsaturated vertices adjacent to precisely $q$ blue edges. We define the
stopping time $\tau_{q}$ to be the smallest $t\geq 0$ such that $D_{j}(t)=0$
for all $j<q$, and $D_{q}(t)>0$. It is obvious that $\tau_{q}$ is well-defined
and is non-decreasing in $q$. By definition, $\tau_{0}=0$. Let us refer to
phase $q$ as those $\tau_{q-1}\leq t<\tau_{q}$. Observe that during phase $q$,
each unsaturated vertex has blue degree $q-1$ or $q$.

###  2.6. Analyzing phase $q$

Suppose that $\tau_{q-1}\leq t<\tau_{q}$. It will be convenient to denote
$D(t):=D_{q-1}(t)$. Given $k_{1},k_{2}\geq 0$, we say that $y\in U_{t}$ is of
type $(k_{1},k_{2})$, provided it is adjacent to $k_{1}$ blue edges within
$\mathcal{B}_{t}$ and $k_{2}$ blue edges within $\mathcal{M}_{t}$. Similarly,
$x\in\mathcal{B}_{t}\cup\mathcal{M}_{t}$ is of type $(k_{1},k_{2})$, provided
its (unique) blue edge connects to an unsaturated vertex of type
$(k_{1},k_{2})$. We denote the number of unsaturated vertices of type
$(k_{1},k_{2})$ by $C_{k_{1},k_{2}}(t)$, the blue vertices of type
$(k_{1},k_{2})$ by $B_{k_{1},k_{2}}(t)$, and the magenta (mixed) vertices of
type $(k_{1},k_{2})$ by $M_{k_{1},k_{2}}(t)$. Observe that
$B_{k_{1},k_{2}}(t)=k_{1}\cdot C_{k_{1},k_{2}}(t)$ and
$M_{k_{1},k_{2}}(t)=k_{2}\cdot C_{k_{1},k_{2}}(t)$. Moreover,
$D_{j}(t)=\sum_{\begin{subarray}{c}k_{1},k_{2}:\\\
k_{1}+k_{2}=j\end{subarray}}C_{k_{1},k_{2}}(t)$.

In Appendix B.2, we inductively define the functions $x,r$ and
$c_{k_{1},k_{2}}$ for $k_{1}+k_{2}\geq 0$, as well as a constant
$\sigma_{q}\geq 0$, such that the following lemma holds:

######  Lemma 2.7.

A.a.s. $\tau_{q}\sim\sigma_{q}n$ for every $0\leq q\leq N$.222For functions
$f=f(n)$ and $g=g(n)$, $f\sim g$ is shorthand for $f=(1+o(1))g$. Moreover, at
step $\tau_{q}$, a.a.s.

$\displaystyle X(\tau_{q})\sim x(\sigma_{q})n,\quad R(\tau_{q})\sim
r(\sigma_{q})n,$ $\displaystyle C_{k_{1},k_{2}}(\tau_{q})\sim
c_{k_{1},k_{2}}(\sigma_{q})n\quad\mbox{for all $(k_{1},k_{2})$ where
$k_{1}+k_{2}=q$.}$

Although the method in the proof for Lemma 2.7 is similar to that of Lemmas
2.1, 2.2, 2.3 and Proposition 2.4, the analysis is much more intricate and
involved. We postpone the details to Appendix B, and now complete the proof of
Theorem 1.1.

###### Proof of Theorem 1.1.

Set $N=100$. By Lemma 2.7, the execution of $\mathtt{DegreeGreedy}$ ends at
some step $t_{0}\sim\sigma_{N}n$. Moreover, $X(t_{0})\sim x(\sigma_{N})n$.
Numerical computation shows that $\sigma_{N}\approx 2.00189$. Next, the
algorithm executes $\mathtt{FullyRandomized}$. Let $\alpha^{*}$ be as defined
in (7) where the initial conditions to the differential equations (4)–(6) are
set by $s_{0}=\sigma_{N}$, $x(s_{0})=x(\sigma_{N})\approx 0.99991$, and
$\ell_{1}(s_{0})=\ell_{2}(s_{0})=0$. Numerical computations show that
$\alpha^{*}\approx 2.01678$. By Proposition 2.4 and the fact that
$\alpha^{*}<3$, the execution of the first two stages ($\mathtt{DegreeGreedy}$
and $\mathtt{FullyRandomized}$) finishes at some step $(\alpha^{*}+o(1))n$,
and the number of unsaturated vertices remaining is $o(n)$. Finally, the
clean-up algorithm constructs a Hamiltonian cycle with an additional $o(n)$
steps by Lemma 2.5. The theorem follows. ∎

##  3\. Proof of Theorem 1.2

Suppose $G_{t}$ has a Hamiltonian cycle $H_{t}=H$ after $t\geq 0$ steps.
Recall that for the (directed) semi-random edge $(u_{i},v_{i})$, we refer to
$u_{i}$ as its square and $v_{i}$ as its circle. We begin with the following
observations:

  1. ($O_{1}$)

$H$ uses exactly $n$ squares;

  2. ($O_{2}$)

$H$ uses at most $2$ squares on each vertex;

  3. ($O_{3}$)

Suppose $(u_{i},v_{i})$ is an edge of $G_{t}$, and $v_{i}$ received at least
two squares. Then, either $H$ uses at most one square on $v_{i}$, or $H$ does
not contain the edge $(u_{i},v_{i})$.

The first two observations above are obvious. For ($O_{3}$), notice that if
$H$ uses exactly $2$ squares on $v_{i}$, then these $2$ squares correspond to
2 edges in $H$ that are incident to $v_{i}$. Moreover, neither of these edges
can be $(u_{i},v_{i})$, as $u_{i}$ is the square of $(u_{i},v_{i})$. Thus, the
edge $(u_{i},v_{i})$ cannot be used by $H$ as $v_{i}$ has degree 2 in $H$.

Define $Z_{x}$ as the number of squares on vertex $x\in[n]$, the observation
($O_{2}$) above indicates the consideration of the random variable

$Z=\sum_{x=1}^{n}\left(\bm{1}_{Z_{x}=1}+2\cdot\bm{1}_{Z_{x}\geq
2}\right)=2n-\sum_{x=1}^{n}\left(2\cdot\bm{1}_{Z_{x}=0}+\bm{1}_{Z_{x}=1}\right),$

which counts the total number of squares that can possibly contribute to $H$,
truncated at 2 for each vertex. Observation ($O_{3}$) above indicates the
consideration of the following two sets of structures:

Let ${\mathcal{W}}_{1}$ be the set of pairs of vertices $(x,y)$ at time $t$
such that

  1. (a)

$x$ receives its first square in some step $i<t$, and $y$ receives the
corresponding circle in the same step;

  2. (b)

no more squares land on $x$ after step $i$;

  3. (c)

at least two squares land on $y$ after step $i$.

Let ${\mathcal{W}}_{2}$ be the set of pairs of vertices $(x,y)$ at time $t$
such that

  1. (a)

$x$ receives its first square in some step $i<t$, and $y$ receives the
corresponding circle in the same step;

  2. (b)

exactly one more square lands on $x$ either before or after step $i$;

  3. (c)

at least two squares land on $y$ after step $s$.

Note that for every $(x,y)\in{\mathcal{W}}_{1}$, at most 2 squares on $x$ and
$y$ together can be used in $H$, although $x$ and $y$ together contribute $3$
to the value of $Z$. Similarly, for every $(x,y)\in{\mathcal{W}}_{2}$, at most
3 squares on $x$ and $y$ together can be used in $H$, although $x$ and $y$
together contribute $4$ to the value of $Z$.

Therefore, the total number of squares contributing to $H$ is at most
$Z-|{\mathcal{W}}_{1}|-|{\mathcal{W}}_{2}|+W$, where $W$ accounts for double
counting, which sometimes happens when there are
$(x_{1},y_{1}),(x_{2},y_{2})\in{\mathcal{W}}_{1}\cup{\mathcal{W}}_{2}$ where
$\\{x_{1},y_{1}\\}\cap\\{x_{2},y_{2}\\}\neq\emptyset$. More precisely, let

$\displaystyle{\mathcal{T}}_{1}$ $\displaystyle=$
$\displaystyle\\{((x_{1},y_{1}),(x_{2},y_{2}))\in{\mathcal{W}}_{1}\times{\mathcal{W}}_{2}:\
y_{1}=x_{2}\\}$ $\displaystyle{\mathcal{T}}_{2}$ $\displaystyle=$
$\displaystyle\\{((x_{1},y_{1}),(x_{2},y_{2}))\in{\mathcal{W}}_{2}\times{\mathcal{W}}_{2}:\
y_{1}=x_{2}\\}.$

Then, $W:=|{\mathcal{T}}_{1}|+|{\mathcal{T}}_{2}|$.333Note that the cases
where
$((x_{1},y_{1}),(x_{2},y_{2}))\in{\mathcal{W}}_{1}\times{\mathcal{W}}_{1}$
such that $y_{1}=y_{2}$ and
$((x_{1},y_{1}),(x_{2},y_{2}))\in{\mathcal{W}}_{2}\times{\mathcal{W}}_{2}$
such that $y_{1}=x_{2}$ do not cause double counting.

The random variable $Z$ is well understood. From the limiting Poisson
distribution of the number of squares in a single vertex, we immediately get
that a.a.s. $Z\sim(2-2e^{-s}-e^{-s}s)n$ for $s:=t/n$.

We will estimate the expectation of
$|{\mathcal{W}}_{1}|,|{\mathcal{W}}_{2}|,|{\mathcal{T}}_{1}|,|{\mathcal{T}}_{2}|$
as well as the concentration of these random variables. However, concentration
may fail if the semi-random process uses a strategy which places many circles
on a single vertex. Intuitively, placing many circles on a single vertex is
not a good strategy for quickly building a Hamiltonian cycle, as it wastes
many edges. To formalise this idea, let $\mu:=\sqrt{n}$ (indeed, choosing any
$\mu$ such that $\mu\to\infty$ and $\mu=o(n)$ will work). We say that a
strategy for the semi-random process is $\mu$-well-behaved up until step $t$,
if no vertex receives more than $\mu$ circles in the first $t$ steps. In [10,
Definition 3.2 – Proposition 3.4], it was proven that it is sufficient to
consider $\mu$-well-behaved strategies in the first $t=O(n)$ steps for
establishing a lower bound on the number of steps needed to build a perfect
matching. These definitions and proofs can be easily adapted for building
Hamilton cycles in an obvious way. We thus omit the details and only give a
high-level explanation below.

The key idea is that within $t=O(n)$ steps of any semi-random process, the
number of vertices of in-degree greater than $\mu$ is at most $O(n/\mu)=o(n)$.
Therefore, if a Hamiltonian cycle $C$ is built in $t$ steps, then the subgraph
$H$ of $C$ induced by the set $S$ of vertices of in-degree at most $\mu$ in
$G_{t}$ is a collection of paths spanning all vertices in $S$ which must also
contain $n-O(n/\mu)=(1-o(1))n$ edges. We call such a pair $(S,H)$ an
approximate Hamiltonian cycle. It follows from the above argument that it
takes at least as long time to build a Hamiltonian cycle as to build an
approximate Hamiltonian cycle. It is then easy to show by a coupling argument
that if a strategy builds an approximate Hamiltonian cycle in $t=O(n)$ steps,
then there exists a well-behaved strategy that builds an approximate
Hamiltonian cycle in $t$ steps as well. Note that observations
($O_{2}$)–($O_{3}$) hold for approximate Hamiltonian cycles, and ($O_{1}$)
holds for approximate Hamiltonian cycles with $n$ replaced by $(1-o(1))n$.
Thus, no approximate Hamiltonian cycles can be built until step
$Z-|{\mathcal{W}}_{1}|-|{\mathcal{W}}_{2}|+W\geq(1-o(1))n$. We now estimate
the sizes of ${\mathcal{W}}_{1}$, ${\mathcal{W}}_{2}$, ${\mathcal{T}}_{1}$,
and ${\mathcal{T}}_{2}$ in the semi-random process when executing a well-
behaved strategy $\mathcal{S}$. Crucially, the sizes of these sets do not rely
on the decisions made by $\mathcal{S}$. Recall that
$(G^{{\mathcal{S}}}_{s})_{s\geq 0}$ denotes the sequence of graphs produced by
${\mathcal{S}}$.

######  Lemma 3.1.

Suppose ${\mathcal{S}}$ is $\mu$-well-behaved. For every $t=\Theta(n)$, the
following a.a.s. holds in $G^{{\mathcal{S}}}_{t}$,

$Z-|{\mathcal{W}}_{1}|-|{\mathcal{W}}_{2}|+W\sim f(s)n,$

where $s:=t/n$ and $f(s)$ is defined in Theorem 1.2.

###### Proof of Theorem 1.2.

Recall that $\beta$ is the positive root of $f(s)=1$. Then, for every
$\varepsilon>0$,
$Z-|{\mathcal{W}}_{1}|-|{\mathcal{W}}_{2}|+W\leq(1-O(\varepsilon))n$ a.a.s. in
$G^{{\mathcal{S}}}_{(\beta-\varepsilon)n}$ for any $\mu$-well-behaved
${\mathcal{S}}$. Therefore, $\tau_{\texttt{HAM}}\geq\beta$. ∎

##  4\. Conclusion and Open Problems

We have made significant progress on reducing the gap between the previous
best upper and lower bounds on $\tau_{{\tt HAM}}$. That being said, we do not
believe that any of our new bounds are tight. For instance, in the case of our
lower bound, one could study the appearance of more complicated substructures
which prevent any strategy from building a Hamiltonian cycle. One way to
likely improve the upper bound would be to analyze an adaptive algorithm whose
decisions are all made greedily. Rather, in the terminology of
$\mathtt{DegreeGreedy}$, when a (second) square lands on a blue vertex, the
edge is greedily chosen amongst unsaturated vertices of minimum blue degree
(opposed to u.a.r.). Unfortunately, it seems challenging to analyze this
algorithm via the differential equation method, but it is likely that this
algorithm will lead to an improved upper bound on $\tau_{{\tt HAM}}$ of less
than $2$.

Another direction is to understand which graph properties exhibit sharp
thresholds. Given property $\mathcal{P}$, the definition of
$\tau_{\mathcal{P}}$ ensures that there exists a strategy $\mathcal{S}^{*}$
such that for all $\varepsilon>0$, $G_{t}^{\mathcal{S}^{*}}(n)$ satisfies
$\mathcal{P}$ a.a.s. for $t\geq(\tau_{\mathcal{P}}+\varepsilon)n$. On the
other hand, $G_{t}^{\mathcal{S^{*}}}(n)$ may satisfy $\mathcal{P}$ with
constant probability for $t\leq(\tau_{\mathcal{P}}-\varepsilon)n$ without
contradicting the definition of $\tau_{\mathcal{P}}$. Thus, for $\mathcal{P}$
to have a sharp threshold, the following property must also hold. For each
strategy $\mathcal{S}$ and $\varepsilon>0$, if
$t\leq(\tau_{\mathcal{P}}-\varepsilon)n$, then a.a.s. $G_{t}^{\mathcal{S}}(n)$
does not satisfy $\mathcal{P}$. It is known that for basic properties, such as
minimum degree $k\geq 1$, sharp thresholds do exist [3]. Moreover, in [2] it
was shown that if $H$ is a spanning graph with max degree $\Delta=\omega(\log
n)$, then the appearance of $H$ takes $(\Delta/2+o(\Delta))n$ rounds, and $H$
(deterministically) cannot be constructed in fewer than $\Delta n/2$ rounds.
However, in general it remains open as to whether or not a sharp threshold
exists when $H$ is sparse (i.e., $\Delta=O(\log n)$). Very recently, the
second author and Surya [12], a developed a general machinery for proving the
existence of sharp thresholds in adaptive random graph processes. Applied to
the semi-random graph process, they show that sharp thresholds exist for the
property of being Hamiltonian as well as to containing a perfect matching.
This provides some evidence that sharp thresholds do exist when $\Delta=O(\log
n)$, and we leave this an interesting open problem.

## References

  * [1] Natalie Behague, Trent Marbach, Paweł Prałat, and Andrzej Ruciński.  Subgraph games in the semi-random graph process and its generalization to hypergraphs.  arXiv preprint arXiv:2105.07034, 2022.
  * [2] Omri Ben-Eliezer, Lior Gishboliner, Dan Hefetz, and Michael Krivelevich.  Very fast construction of bounded-degree spanning graphs via the semi-random graph process.  Proceedings of the 31st Symposium on Discrete Algorithms (SODA’20), pages 728–737, 2020.
  * [3] Omri Ben-Eliezer, Dan Hefetz, Gal Kronenberg, Olaf Parczyk, Clara Shikhelman, and Miloš Stojaković.  Semi-random graph process.  Random Structures & Algorithms, 56(3):648–675, 2020.
  * [4] Patrick Bennett and Andrzej Dudek.  A gentle introduction to the differential equation method and dynamic concentration.  CoRR, 2020.
  * [5] J. Bezanson, A. Edelman, S. Karpinski, and V.B. Shah.  Julia: A fresh approach to numerical computing.  SIAM review, 59(1):65–98, 2017.
  * [6] Tom Bohman and Alan Frieze.  Hamilton cycles in 3-out.  Random Structures & Algorithms, 35(4):393–417, 2009.
  * [7] Sofiya Burova and Lyuben Lichev.  The semi-random tree process, 2022.
  * [8] Alan M Frieze.  Maximum matchings in a class of random graphs.  Journal of Combinatorial Theory, Series B, 40(2):196–212, 1986\.
  * [9] Pu Gao, Bogumił Kamiński, Calum MacRury, and Paweł Prałat.  Hamilton cycles in the semi-random graph process.  European Journal of Combinatorics, 99:103423, 2022.
  * [10] Pu Gao, Calum MacRury, and Paweł Prałat.  Perfect matchings in the semi-random graph process.  SIAM Journal on Discrete Mathematics, in press, 2022.
  * [11] Michal Karoński, Ed Overman, and Boris Pittel.  On a perfect matching in a random digraph with average out-degree below two.  Journal of Combinatorial Theory, Series B, 143, 03 2020.
  * [12] Calum MacRury and Erlang Surya.  Sharp thresholds in adaptive random graph processes.  CoRR, 2022.
  * [13] Lutz Warnke.  On wormald’s differential equation method.  CoRR, abs/1905.08928, 2019.
  * [14] Nicholas C Wormald.  The differential equation method for random graph processes and greedy algorithms.  Lectures on approximation and randomized algorithms, 73:155, 1999\.

##  Appendix A Proofs of Lemmas 2.2 and 2.5

###### Proof of Lemma 2.2.

As discussed, $\mathtt{FullyRandomized}$ ensures that at time $t$ there are at
most $2$ red vertices which are not well-spaced. Thus, since our expected
differences each allow for a $O(\log n/n)$ term, without loss of generality,
we can assume that all our red vertices are well-spaced. Note that all our
explanations below assume that we have conditioned on $H_{t}$.

The first expected difference is easy to see. Observe that $\Delta X(t)$ is
$1$ when $u_{t+1}$ lands on an unsaturated vertex, or adjacent to a red
vertex. Clearly, these are disjoint events, and they occur with probabilities
$1-X(t)/n$ and $2L(t)/n$, respectively.

In order to derive the second and third expected differences, we make use of
the following crucial observation:

  1. ($O_{1}$)

Conditional on $H_{t}$, the circles of the red edges of $\mathcal{L}_{t}$ are
distributed u.a.r. amongst the unsaturated vertices $U_{t}$.

Note that were we to condition on the full history, i.e.,
$G_{0},\ldots,G_{t}$, then these circles would be determined by the history of
the process, and so the only randomness in the expectations would be over the
draw of $u_{t+1}$. By averaging over this additional randomness, we are able
to get the claimed expected differences.

Consider now the second expected difference and assume that $u_{t+1}$ lands on
an unsaturated vertex. Firstly, observe that this event occurs with
probability $1-X(t)/n$. On the other hand, all the red edges adjacent to
$u_{t+1}$ will be uncoloured after the path augmentation involving $u_{t+1}$
is made. Now, because of ($O_{1}$), there are $\frac{L_{1}(t)}{n-X(t)}$ red
edges belonging to $\mathcal{L}^{1}_{t}$ which are adjacent to $u_{t+1}$ in
expectation. After the path augmentation involving $u_{t+1}$, these edges are
uncoloured and so $\frac{L_{1}(t)}{n-X(t)}$ one-red vertices are destroyed in
expectation. Now, in expectation there are also
$\frac{2L_{2}(t)}{n-X(t)}+O(\log n/n)$ red edges adjacent to $u_{t+1}$ which
belong to distinct two-red vertices. To see this, fix a two-red vertex
$x\in\mathcal{L}_{t}^{2}$ and observe that because of ($O_{1}$), precisely one
red edge of $x$ is adjacent to $u_{t+1}$ with probability
$\frac{2}{n-X(t)}-\frac{1}{(n-X(t))^{2}}$. Since $n-X(t)\geq n/\log n$ by
assumption, this probability is $\frac{2}{n-X(t)}+O((\log n/n)^{2})$, and so
the $\frac{2L_{2}(t)}{n-X(t)}+O(\log n/n)$ term follows after summing over all
the vertices of $\mathcal{L}_{t}^{2}$. Now, after the path augmentation
involving $u_{t+1}$, these red edges are uncoloured. Since these red edges
belonged to distinct two-red vertices, the path augmentation creates
$\frac{2L_{2}(t)}{n-X(t)}+O(\log n/n)$ new one-red vertices in expectation.
These two cases explain the
$\left(1-\frac{X(t)}{n}\right)\left(\frac{2L_{2}(t)}{n-X(t)}-\frac{L_{1}(t)}{n-X(t)}\right)$
term.

Let us now consider when $u_{t+1}$ lands on a saturated vertex and
$d_{P_{t}}(u_{t+1},\mathcal{L}_{t})=1$, where $x$ is the unique red vertex
adjacent to $u_{t+1}$. If $x$ is a one-red vertex, then let $r$ be such that
$xr$ is the red edge of $x$. Observe that after the augmentation, $xr$ will be
uncoloured, and $x$ will no longer be a red vertex. Moreover, in expectation
there are $\frac{L_{1}(t)}{n-X(t)}+O(\log n/n)$ other red edges belonging to
$\mathcal{L}^{1}_{t}$ which will be uncoloured. Thus,
$1+\frac{L_{1}(t)}{n-X(t)}+O(\log n/n)$ one-red vertices will be destroyed in
expectation. On the other hand, there are $\frac{2L_{2}(t)}{n-X(t)}+O(\log
n/n)$ red edges adjacent to $r$ which belong to distinct two-red vertices in
expectation. Thus, $\frac{2L_{2}(t)}{n-X(t)}+O(\log n/n)$ two-red vertices
will become one-red vertices in expectation after augmenting via $xr$ and
$u_{t+1}r$. Since $u_{t+1}$ lands next to a one-red vertex with probability,
$\frac{2L_{1}(t)}{n}$, this explains the
$\frac{2L_{1}(t)}{n}\left(\frac{2L_{2}(t)}{n-X(t)}-\frac{L_{1}(t)}{n-X(t)}-1\right)$
term. An analogous argument explains the
$\frac{2L_{2}(t)}{n}\left(1+\frac{2L_{2}(t)}{n-X(t)}-\frac{L_{1}(t)}{n-X(t)}\right)$
term.

Consider when $u_{t+1}$ lands in $\mathcal{Q}_{t}$. Observe that this occurs
with probability $\frac{|\mathcal{Q}_{t}|}{n}=\frac{X(t)-5L(t)}{n}$. In this
case, $v_{t+1}$ is chosen u.a.r. amongst $U_{t}$ and $u_{t+1}v_{t+1}$ is
coloured red. Thus, $u_{t+1}$ becomes a red vertex, and so $L_{1}(t)$
increases by $1$ and we get $\Delta L_{1}(t)=1$. This explains the
$\frac{X(t)-5L(t)}{n}$ term.

The final case to consider is when $u_{t+1}$ lands on a saturated vertex, and
$u_{t+1}\in\mathcal{L}^{1}_{t}$. Observe that this occurs with probability
$\frac{L_{1}(t)}{n}$. Moreover, the algorithm will then choose $v_{t+1}$
u.a.r. amongst $U_{t}$ and colour the edge $u_{t+1}v_{t+1}$ red. After this
move, $u_{t+1}$ will be converted from a one-red vertex to a two-red vertex,
and so $\Delta L_{1}(t)=1$. This explains the $\frac{-L_{1}(t)}{n}$ term.

By combining the contributions from all of the above cases, we get the second
expected difference. The third expected difference follows via an analogous
argument. ∎

###### Proof of Lemma 2.5.

Let $j_{0}=\varepsilon n$. For each $k\geq 1$, let $j_{k}=(1/2)j_{k-1}$ if
$j_{k-1}>n^{1/4}$, and let $j_{k}=j_{k-1}-1$ otherwise. Clearly, $j_{k}$ is a
decreasing function of $k$. Let $\tau_{1}$ be the smallest natural number $k$
such that $j_{k}\leq n^{1/4}$. Let $\tau$ be the natural number $k$ such that
$j_{k}=0$. Obviously, $\tau_{1}=O(\log n)$ and $\tau=O(n^{1/4})$.

We use a cleaning-up algorithm, which runs in iterations. The $k$-th iteration
repeatedly absorbs $j_{k-1}-j_{k}$ vertices into $P$, leaving $j_{k}$
unsaturated vertices in the end. The $k$-th iteration of the cleaning-up
algorithm works as follows.

  * (i)

(Initialising): Uncolour all vertices in the graph;

  * (ii)

(Building reservoir): Let $m_{k}:=\sqrt{\varepsilon}(1/2)^{k/2}n$ for
$k\leq\tau_{1}$ and $m_{k}:=n^{1/2}$ if $\tau_{1}<k\leq\tau$. Add $m_{k}$
semi-random edges as follows. If $u_{t}$ lands on an unsaturated vertex, a red
vertex or a neighbour of a red vertex in $P$, then let $v_{t}$ be chosen
arbitrarily. This edge $u_{t}v_{t}$ will not be used in our construction.
Otherwise, colour $u_{t}$ red and choose an arbitrary $v_{t}$ among those
unsaturated vertices with the minimum number of red neighbours. Colour
$u_{t}v_{t}$ red. Note that each red vertex is adjacent to exactly one red
edge;

  * (iii)

(Absorbing via path augmentations): Add semi-random edges as follows. Suppose
that $u_{t}$ lands on $P$ and at least one neighbour of $u_{t}$ on $P$ is red.
(Otherwise, $v_{t}$ is chosen arbitrarily, and this edge will not be used in
our construction.) Let $x$ be such red vertex (if $u_{t}$ has two neighbours
on $P$ that are red, then select one of them arbitrarily). Let $y$ by the
neighbour of $x$ where $xy$ is red, and let $v_{t}=y$. Extend $P$ by deleting
the edge $xu_{t}$ and adding the edges $xy$ and $yu_{t}$. Uncolour all red
edges incident to $y$ and all red neighbours of $y$ (which, of course,
includes vertex $x$).

Notice that, in each iteration, $m_{k}\geq n^{1/2}$. Indeed, this is obviously
true for $\tau_{1}<k\leq\tau$. On the other hand, if $k\leq\tau_{1}$, then
$j_{k}=\varepsilon n(1/2)^{k}$ and so $m_{k}=\sqrt{nj_{k}}\geq\sqrt{n}$ (in
fact, $m_{k}=\Omega(n^{5/8})$).

Let $T_{k}$ denote the length of the $k$-th iteration of the cleaning-up
algorithm. It remains to prove that a.a.s.
$\sum_{k\leq\tau}T_{k}=O(\sqrt{\varepsilon}n+n^{3/4}\log^{2}n)$. Let $R_{k}$
be the number of red vertices obtained after step (ii) of iteration $k$.
Obviously, $R_{k}\leq m_{k}$. On the other hand, each $u_{t}$ is coloured red
with probability at least $1-j_{k-1}/n-3m_{k}/n\geq
1-\varepsilon-3\sqrt{\varepsilon}\geq 0.95$. Hence, $R_{k}$ can be
stochastically lower bounded by the binomial random variable
$\mathrm{Bin}(m_{k},0.95)$. By the Chernoff bound, with probability at least
$1-n^{-1}$, $R_{k}\geq 0.9m_{k}$, as $m_{k}\geq n^{1/2}$.

First, we consider iterations $k\leq\tau_{1}$. Let $\tilde{R}_{k}$ be the
number of red vertices at the end of step (iii). Note that the minimum degree
property of step (ii) ensures each unsaturated vertex is adjacent to at most
$R_{k}/j_{k-1}+1\leq m_{k}/j_{k-1}+1$ red vertices. Moreover, exactly
$j_{k-1}-j_{k}=(1/2)j_{k-1}$ vertices are absorbed in step (iii). As a result,

$\tilde{R}_{k}\geq
R_{k}-\left(\frac{m_{k}}{j_{k-1}}+1\right)\cdot\frac{j_{k-1}}{2}\geq
0.9m_{k}-\frac{m_{k}}{2}-\frac{j_{k-1}}{2}\geq 0.3m_{k},$

as $j_{k-1}=2j_{k}\leq 2\sqrt{\varepsilon}m_{k}\leq 0.1m_{k}$. It follows that
throughout step (iii), there are at least $0.3m_{k}$ red vertices. Thus, for
each semi-random edge added to the graph, the probability that a path
extension can be performed is at least
$0.3m_{k}/n=0.3\sqrt{\varepsilon}(1/2)^{k/2}$. Again, by the Chernoff bound,
with probability at least $1-n^{-1}$, the number of semi-random edges added in
step (iii) is at most

$2(j_{k-1}-j_{k})\cdot\frac{2^{k/2}}{0.3\sqrt{\varepsilon}}\leq
7\sqrt{\varepsilon}(1/2)^{k/2}n.$

Combining the number of semi-random edges added in step (ii), it follows that
with probability at least $1-n^{-1}$, $T_{k}\leq
m_{k}+7\sqrt{\varepsilon}(1/2)^{k/2}n=8\sqrt{\varepsilon}(1/2)^{k/2}n$.

Next, consider iterations $\tau_{1}<k\leq\tau$. In each iteration, exactly one
unsaturated vertex gets absorbed. The number of semi-random edges added in
step (ii) is $m_{k}=n^{1/2}$. We have argued that with probability at least
$1-n^{-1}$, $R_{k}\geq 0.9m_{k}$. Thus, for each semi-random edge added to the
graph, the probability that a path extension can be performed is at least
$0.9m_{k}/n=0.9n^{-1/2}$. By the Chernoff bound, with probability at least
$1-n^{-1}$, the number of semi-random edges added in step (iii) is at most
$n^{1/2}\log^{2}n.$ Thus, with probability at least $1-n^{-1}$, $T_{k}\leq
n^{1/2}+n^{1/2}\log^{2}n\leq 2n^{1/2}\log^{2}n$.

Taking the union bound over all $k\leq\tau$, since $\tau=O(n^{1/4})$, it
follows that a.a.s.

$\sum_{k\leq\tau}T_{k}\leq\sum_{k\leq\tau_{1}}8\sqrt{\varepsilon}(1/2)^{k/2}n+\sum_{\tau_{1}<k\leq\tau}2n^{1/2}\log^{2}n=O(\sqrt{\varepsilon}n+n^{3/4}\log^{2}n)$

We have shown that a.a.s. by adding $O(\sqrt{\varepsilon}n+n^{3/4}\log^{2}n)$
additional semi-random edges we can construct a Hamiltonian path $P$. To
complete the job and turn it into a Hamiltonian cycle, let $u$ and $v$ denote
the left and, respectively, the right endpoint of $P$. First, add $n^{1/2}$
semi-random edges $u_{t}v_{t}$ where $v_{t}$ is always $u$, discarding any
multiple edges that could possibly be created. For each such semi-random edge
$u_{t}u$, colour the left neighbour of $u_{t}$ on $P$ blue. Next, add add
$n^{1/2}\log^{2}n$ semi-random edges $u_{t}v_{t}$ where $v_{t}$ is always $v$.
Suppose that some $u_{t}=x$ is blue. Then, a Hamiltonian cycle is obtained by
deleting $xy$ from $P$ and adding the edges $xv$ and $uy$, where $y$ is the
right neighbour of $x$ on $P$. By Chernoff bound, a.a.s. a semi-random edge
added during the second round hits a blue vertex, completing the proof. ∎

##  Appendix B Proof of Lemma 2.7

We once again must first argue that our random variables cannot change
drastically in one round during phase $q$.

######  Lemma B.1 (Lipschitz Condition – $\mathtt{DegreeGreedy}$).

If $|\Delta
C(t)|:=\max_{\begin{subarray}{c}k_{1},k_{2}\in{\mathbb{N}}\cup\\{0\\}:\\\
k_{1}+k_{2}\in\\{q-1,q\\}\end{subarray}}|\Delta C_{k_{1},k_{2}}(t)|$, then
with probability $1-O(n^{-1})$,

$\max\\{|\Delta X(t)|,|\Delta C(t)|,|\Delta R(t)|\\}=O(\log n)$

for all $\tau_{q-1}\leq t<\tau_{q}$ with $n-X(t)=\Omega(n)$.

###### Proof.

Since $q\leq N$ is a constant which does not depend on $n$, we can apply the
same argument to bound the red edges of each $\Delta C_{k_{1},k_{2}}(t)$ as in
Lemma 2.1, and then union bound over all $k_{1},k_{2}\geq 0$ such that
$k_{1}+k_{2}\in\\{q-1,q\\}$. ∎

Let $H_{t}$ denote the history of the above random variables during the first
$t$ rounds. We now state the conditional expected differences of our random
variables, where we assume that $\tau_{q-1}\leq t<\tau_{q}$ is such that
$n-X(t)=\Omega(n)$. Firstly, observe that once again:

$\displaystyle\mathbb{E}[\Delta X(t)\mid H_{t}]$ $\displaystyle=$
$\displaystyle 1-\frac{X(t)}{n}+\frac{2L(t)}{n}+O(1/n)$ (8)

We now consider $\Delta R(t)$:

$\displaystyle\mathbb{E}[\Delta R(t)\mid H_{t}]$ $\displaystyle=$
$\displaystyle\frac{M(t)}{n}-\frac{R(t)}{n}-\frac{2(B(t)+M(t))}{n}\frac{R(t)}{(n-X(t))}$
(9) $\displaystyle+\sum_{\begin{subarray}{c}j,h:\\\
j+h\in\\{q-1,q\\}\end{subarray}}\frac{2h(M_{j,h}(t)+B_{j,h}(t))}{n}$
$\displaystyle-\frac{2R(t)}{n}\left(1+\frac{R(t)}{n-X(t)}-\frac{M(t)}{n-X(t)}\right)-\frac{R(t)}{n}+O(1/n)$

Consider $\Delta C_{k_{1},k_{2}}(t)$ and first assume that $k_{1}+k_{2}=q-1$:

$\displaystyle\mathbb{E}[\Delta C_{k_{1},k_{2}}(t)\mid H_{t}]$
$\displaystyle=$
$\displaystyle\frac{M_{k_{1}-1,k_{2}+1}(t)}{n}\cdot\bm{1}_{k_{1}>0}-\frac{C_{k_{1},k_{2}}(t)}{n}-\frac{M_{k_{1},k_{2}}(t)}{n}$
(10)
$\displaystyle+\frac{2(B(t)+M(t))}{n}\left(\frac{M_{k_{1}-1,k_{2}+1}(t)}{n-X(t)}\cdot\bm{1}_{k_{1}>0}-\frac{M_{k_{1},k_{2}}(t)}{n-X(t)}\right)-\frac{2(B_{k_{1},k_{2}}(t)+M_{k_{1},k_{2}}(t))}{n}$
$\displaystyle+\frac{2R(t)}{n}\left(\frac{M_{k_{1}-1,k_{2}+1}(t)}{n-X(t)}\cdot\bm{1}_{k_{1}>0}-\frac{M_{k_{1},k_{2}}(t)}{n-X(t)}-\frac{C_{k_{1},k_{2}}(t)}{n-X(t)}\right)$
$\displaystyle-\frac{(X(t)-5L(t))}{n}\frac{C_{k_{1},k_{2}}(t)}{D(t)}$
$\displaystyle+\frac{B_{k_{1}+1,k_{2}-1}(t)}{n}\cdot\bm{1}_{k_{2}>0}-\frac{R(t)}{n}\frac{C_{k_{1},k_{2}}(t)}{D(t)}-\frac{B_{k_{1},k_{2}}(t)}{n}+O(1/n)$

When $k_{1}+k_{2}=q$, two terms from the above expression are modified
slightly, and have their signs reversed:

$\displaystyle\mathbb{E}[\Delta C_{k_{1},k_{2}}(t)\mid H_{t}]$
$\displaystyle=$
$\displaystyle\frac{M_{k_{1}-1,k_{2}+1}(t)}{n}\cdot\bm{1}_{k_{1}>0}-\frac{C_{k_{1},k_{2}}(t)}{n}-\frac{M_{k_{1},k_{2}}(t)}{n}$
(11)
$\displaystyle+\frac{2(B(t)+M(t))}{n}\left(\frac{M_{k_{1}-1,k_{2}+1}(t)}{n-X(t)}\cdot\bm{1}_{k_{1}>0}-\frac{M_{k_{1},k_{2}}(t)}{n-X(t)}\right)-\frac{2(B_{k_{1},k_{2}}(t)+M_{k_{1},k_{2}}(t))}{n}$
$\displaystyle+\frac{2R(t)}{n}\left(\frac{M_{k_{1}-1,k_{2}+1}(t)}{n-X(t)}\cdot\bm{1}_{k_{1}>0}-\frac{M_{k_{1},k_{2}}(t)}{n-X(t)}-\frac{C_{k_{1},k_{2}}(t)}{n-X(t)}\right)$
$\displaystyle+\frac{(X(t)-5L(t))}{n}\frac{C_{k_{1}-1,k_{2}}(t)}{D(t)}$
$\displaystyle+\frac{B_{k_{1}+1,k_{2}-1}(t)}{n}\cdot\bm{1}_{k_{2}>0}+\frac{R(t)}{n}\frac{C_{k_{1},k_{2}-1}(t)}{D(t)}-\frac{B_{k_{1},k_{2}}(t)}{n}+O(1/n)$

###  B.1. Proving the Expected Differences

Consider step $t$ of phase $q$ which we assume satisfies $n-X(t)=\Omega(n)$.
Similarly to $\mathtt{FullyRandomized}$, $\mathtt{DegreeGreedy}$ ensures that
all but at most $2$ of its coloured vertices are well-spaced. Thus, we may
assume without loss of generality that all of our coloured vertices are well-
spaced. Since every well-spaced coloured vertex has its own two neighbouring
vertices where a path augmentation may occur, it follows that
$\mathbb{E}[\Delta X(t)\mid H_{t}]=1-\frac{X(t)}{n}+\frac{2L(t)}{n}+O(1/n)$.

In order to prove the remaining expected differences, we analyze the expected
values of the random variables $\Delta R(t)$ and $\Delta C_{k_{1},k_{2}}(t)$
when $u_{t+1}$ lands in subset $A\subseteq[n]$ for a number of choices of $A$.
More precisely, we derive tables for $\mathbb{E}[\Delta
R(t)\cdot\bm{1}_{u_{t+1}\in A}\mid H_{t}]$ and $\mathbb{E}[\Delta
C_{k_{1},k_{2}}(t)\cdot\bm{1}_{u_{t+1}\in A}\mid H_{t}]$ when $A\subseteq[n]$
varies across a number of subsets. Since these are disjoint subsets of $[n]$,
and the random variables are $0$ if $u_{t+1}$ lands outside of these subsets,
we can sum the second column entries to get the claimed expected differences.
Note that the entries of our tables do not contain the often necessary
$O(1/n)$ term.

In the below derivations, we once again make use of the following crucial
observation:

  1. ($O_{1}$)

Conditional on $H_{t}$, the circles of the red edges of $\mathcal{L}_{t}$ are
distributed u.a.r. amongst the unsaturated vertices $U_{t}$.

In all our below explanations, we assume that we have conditioned on $H_{t}$.
We also abuse notation and simultaneously identify our random variables as
sets (i.e., $C_{k_{1},k_{2}}(t)$ denotes the set of unsaturated vertices of
type $(k_{1},k_{2})$ after $t$ steps).

Table 1. Expected Changes to $\Delta R(t)$ $A\subseteq[n]$ | $\mathbb{E}[\Delta R(t)\cdot\bm{1}_{u_{t+1}\in A}\mid H_{t}]$
---|---
$U_{t}$ | $\frac{M(t)}{n}-\frac{R(t)}{n}$
Path distance $1$ from $\mathcal{B}_{t}\cup\mathcal{M}_{t}$ | $-\frac{2(B(t)+M(t))}{n}\frac{R(t)}{n-X(t)}+\sum_{\begin{subarray}{c}j,h:\\\ j+h\in\\{q-1,q\\}\end{subarray}}\frac{2(B_{j,h}(t)+M_{j,h}(t))\cdot h}{n}$
Path distance $1$ from $\mathcal{R}_{t}$ | $-\frac{2R(t)}{n}\left(1+\frac{R(t)}{n-X(t)}\right)+\frac{2R(t)}{n}\frac{M(t)}{n-X(t)}$
$\mathcal{R}_{t}$ | $\frac{-R(t)}{n}$

###### Proof of Table 1.

We provide complete proofs only of row entries $1$ and $3$, as $2$ follows
similarly to $3$ and $4$ follows similarly to $1$.

In order to see the first row entry, observe that there are $\frac{R(t)}{n}$
red edges between $\mathcal{R}_{t}$ and $U_{t}$. Moreover, if $u_{t+1}$ lands
on an unsaturated vertex, then a path extension is made, and all the edges
adjacent to $u_{t+1}$ are uncoloured. Thus, in expectation $\frac{R(t)}{n}$
red vertices are destroyed when $u_{t+1}$ lands in $U_{t}$. We also claim that
$\frac{M(t)}{n}$ red vertices are created in expectation when $u_{t+1}$ lands
in $U_{t}$. In order to see this, suppose that $x$ is a magenta vertex, with
blue edge $xb$ and red edge $xr$, where $b,r\in U_{t}$. Now, if $r\neq b$ and
$u_{t+1}$ lands on $b$, then the edge $xb$ is uncoloured, and $x$ becomes a
red vertex. On the other hand, $r$ is distributed u.a.r. amongst $U_{t}$ (see
($O_{1}$)), and in particular, is distinct from $b$ with probability
$1-\frac{1}{n-X(t)}$. Thus, $x$ is converted to a red vertex with probability
$\frac{1}{n}\left(1-\frac{1}{n-X(t)}\right)=1/n+O(1/n^{2})$, since
$n-X(t)=\Omega(n)$. By summing over all the magenta vertices, we recover a
$M(t)/n+O(1/n)$ term which implies the $M(t)/n-R(t)/n$ row entry.

Let us now consider what happens when $u_{t+1}$ lands on $P_{t}$ next to a red
vertex. Clearly, this event occurs with probability $2R(t)/n$, as we have
assumed that all the red vertices are well-spaced. Let us suppose that
$u_{t+1}$ lands on red vertex $x$, and its red edge is $xr$ for some $r\in
U_{t}$. In this case, a path augmentation involving $xr$ occurs and all the
adjacent edges of $r$ are uncoloured after $r$ is added to the path. By
($O_{1}$), there are $1+\frac{R(t)-1}{n-X(t)}$ red edges adjacent to $r$ in
expectation. This accounts for the
$-\frac{2R(t)}{n}\left(1+\frac{R(t)}{n-X(t)}\right)$ term. In order to see the
second term of this row entry, first observe that

$M(t)=\sum_{\begin{subarray}{c}j,h:\\\ j+h\in\\{q-1,q\\}\end{subarray}}h\cdot
C_{j,h}(t).$ (12)

Now, fix $j,h\geq 0$ such that $j+h\in\\{q-1,q\\}$, and consider $c\in
C_{j,h}(t)$. Observe that by definition, $c$ is adjacent to precisely $h$
magenta vertices of $M_{j,h}(t)$ via blue edges. We claim that all $h$ of
these magenta vertices will be reclassified as red vertices provided the
following events occur:

  * •

The circle $v_{t+1}$ lands on $c$.

  * •

All the red edges of these $h$ magenta vertices are not adjacent to $c$.

By ($O_{1}$), the first event occurs with probability $1/(n-X(t))$. and the
latter with probability $\left(1-\frac{1}{n-X(t)}\right)^{h}$. Thus, since $h$
is a constant, each $c\in C_{j,h}(t)$ contributes

$\frac{h}{n-X(t)}\left(1-\frac{1}{n-X(t)}\right)^{h}=\frac{h}{n-X(t)}+O(1/n^{2})$

red vertices in expectation. By summing over $c\in C_{j,h}(t)$, this accounts
for the $\frac{h\cdot C_{j,h}(t)}{n-X(t)}$ term. Finally, we sum over $j,h$
and apply (12) to get the $\frac{M(t)}{n-X(t)}$ term.

∎

Consider now $\Delta C_{k_{1},k_{2}}(t)$, where $k_{1}+k_{2}=q-1$.

Table 2. Expected Changes to $\Delta C_{k_{1},k_{2}}(t)$ for $k_{1}+k_{2}=q-1$ $A\subseteq[n]$ | $\mathbb{E}[\Delta C_{k_{1},k_{2}}(t)\cdot\bm{1}_{u_{t+1}\in A}\mid H_{t}]$
---|---
$U_{t}$ | $\frac{M_{k_{1}-1,k_{2}+1}(t)}{n}\cdot\bm{1}_{k_{1}>0}-\frac{C_{k_{1},k_{2}}(t)}{n}-\frac{M_{k_{1},k_{2}}(t)}{n}$
Path distance $1$ from $\mathcal{B}_{t}\cup\mathcal{M}_{t}$ | $\frac{2(B(t)+M(t))}{n}\left(\frac{M_{k_{1}-1,k_{2}+1}(t)}{n-X(t)}\cdot\bm{1}_{k_{1}>0}-\frac{M_{k_{1},k_{2}}(t)}{n-X(t)}\right)-\frac{2(B_{k_{1},k_{2}}(t)+M_{k_{1},k_{2}}(t))}{n}$
Path distance $1$ from $\mathcal{R}_{t}$ | $\frac{2R(t)}{n}\left(\frac{M_{k_{1}-1,k_{2}+1}(t)}{n-X(t)}\cdot\bm{1}_{k_{1}>0}-\frac{M_{k_{1},k_{2}}(t)}{n-X(t)}-\frac{C_{k_{1},k_{2}}(t)}{n-X(t)}\right)$
$\mathcal{Q}_{t}$ | $-\frac{(X(t)-5L(t))}{n}\frac{C_{k_{1},k_{2}}(t)}{D(t)}$
$\mathcal{R}_{t}$ | $-\frac{R(t)}{n}\frac{C_{k_{1},k_{2}}(t)}{D(t)}$
$\mathcal{B}_{t}$ | $-\frac{B_{k_{1},k_{2}}(t)}{n}+\frac{B_{k_{1}+1,k_{2}-1}(t)}{n}\cdot\bm{1}_{k_{2}>0}$

###### Proof of Table 2.

Assume that $k_{1},k_{2}$ are both non-zero, as this is the most involved
case. We provide complete proofs of row entries $1,3$ and $4$. Row entry $2$
follows similarly to row entry $3$, and row entry $5$ follows similarly to row
entry $4$. Row entry $5$ has a simple proof, so we omit it.

We begin with row entry $1$ when $u_{t+1}$ lands on an unsaturated vertex.
First consider the
$-\left(\frac{C_{k_{1},k_{2}}(t)}{n}+\frac{M_{k_{1},k_{2}}(t)}{n}\right)$
term. Fix a unsaturated vertex $c$ of type $(k_{1},k_{2})$, and suppose that
$x_{1},\ldots,x_{k_{2}}$ are its magenta neighbours of type $(k_{1},k_{2})$.
By definition, $cx_{i}$ is coloured blue, and each $x_{i}$ also has a red edge
$r_{i}x_{i}$ for $i=1,\ldots,k_{2}$. We claim that $c$ is destroyed with
probability $(k_{2}+1)/n+O(1/n^{2})$. In order to see this, first observe that
because of ($O_{1}$), the vertices $c,r_{1},\ldots,r_{k_{2}}$ are distinct
with probability

$\prod_{i=1}^{k_{2}}\left(1-\frac{i}{n-X(t)}\right)=1+O(1/n).$

Let us now condition on these vertices being distinct. Observe that if
$u_{t+1}$ lands on $c$, then $u_{t+1}$ is added to the path, and so $c$ is
destroyed. On the other hand, if $u_{t+1}$ lands on $r_{i}$, then $r_{i}$ is
added to the path, and so the edge $r_{i}x_{i}$ is no longer red. In
particular, $x_{i}$ is converted to a blue vertex, and so the type of $c$ is
reclassified as $(k_{1}+1,k_{2}-1)$. In either case, $c$ is destroyed. Thus,
conditional on the vertices $b,r_{1},\ldots,r_{k_{2}}$ being distinct, $c$ is
destroyed with probability $(k_{2}+1)/n$. As such, $c$ is destroyed with the
claimed probability of $(k_{2}+1)/n+O(1/n^{2})$. By summing over all $c\in
C_{k_{1},k_{2}}(t)$ and using the fact that $k_{2}\cdot
C_{k_{1},k_{2}}(t)=M_{k_{1},k_{2}}(t)$, we attain the
$-\left(\frac{C_{k_{1},k_{2}}(t)}{n}+\frac{M_{k_{1},k_{2}}(t)}{n}\right)$
term. The $\frac{M_{k_{1}-1,k_{2}+1}(t)}{n}$ term follows similarly, where
reclassifying unsaturated vertices of type $(k_{1}-1,k_{2}+1)$ to type
$(k_{1},k_{2})$ causes $C_{k_{1},k_{2}}(t)$ to increase.

We now consider the third row entry when $u_{t+1}$ lands at path distance one
from $\mathcal{R}_{t}$. First observe that this event occurs with probability
$2R(t)/n$. At this point, using the previous argument and ($O_{1}$), the path
augmentation involving $v_{t+1}$ causes each $c\in C_{k_{1},k_{2}}(t)$ to be
destroyed with probability $(k_{2}+1)/(n-X(t))+O(1/n^{2})$. Moreover, each
$c^{\prime}\in C_{k_{1}-1,k_{2}+1}(t)$ is reclassified as type $(k_{1},k_{2})$
with probability $(k_{2}+1)/(n-X(t))+O(1/n^{2})$. By summing over $c\in
C_{k_{1},k_{2}}(t)$ and $c^{\prime}\in C_{k_{1}-1,k_{2}+1}(t)$, we attain the
$\frac{M_{k_{1}-1,k_{2}+1}(t)}{n-X(t)}-\frac{M_{k_{1},k_{2}}(t)}{n-X(t)}-\frac{C_{k_{1},k_{2}}(t)}{n-X(t)}$
expression. After multiplying by $2R(t)/n$, we attain row entry $3$.

Let us now consider row entry $4$ when $u_{t+1}$ lands on a permissible vertex
$x\in\mathcal{Q}_{t}$. Clearly, this event occurs with probability
$|\mathcal{Q}_{t}|/n=(X(t)-5L(t))/n$. In this case, the algorithm chooses
$v_{t+1}$ u.a.r. amongst $D(t)$, the unsaturated vertices of minimum degree
$q-1$, and colours the edge $xv_{t+1}$ blue. Thus, if we fix $c\in
C_{k_{1},k_{2}}(t)$, then $c$ will be chosen with probability $1/D(t)$ since
$k_{1}+k_{2}=q-1$. In this case, $c$ gains a blue edge connected to a blue
vertex, and thus will be reclassified as type $(k_{1}+1,k_{2})$. Thus, each
$c\in C_{k_{1},k_{2}}(t)$ will be reclassified with probability

$\frac{X(t)-5L(t)}{n}\frac{1}{D(t)}.$

By summing over all $c\in C_{k_{1},k_{2}}(t)$, we get the
$-\frac{(X(t)-5L(t))}{n}\frac{C_{k_{1},k_{2}}(t)}{D(t)}$ term. ∎

Finally, when $k_{1}+k_{2}=q$, the expressions in rows $(4)$ and $(5)$ are
modified slightly.

Table 3. Expected Changes to $\Delta C_{k_{1},k_{2}}(t)$ for $k_{1}+k_{2}=q$ $A\subseteq[n]$ | $\mathbb{E}[\Delta C_{k_{1},k_{2}}(t)\cdot\bm{1}_{u_{t+1}\in A}\mid H_{t}]$
---|---
$U_{t}$ | $\frac{M_{k_{1}-1,k_{2}+1}(t)}{n}\cdot\bm{1}_{k_{1}>0}-\frac{C_{k_{1},k_{2}}(t)}{n}-\frac{M_{k_{1},k_{2}}(t)}{n}$
Path distance $1$ from $\mathcal{B}_{t}\cup\mathcal{M}_{t}$ | $\frac{2(B(t)+M(t))}{n}\left(\frac{M_{k_{1}-1,k_{2}+1}(t)}{n-X(t)}\cdot\bm{1}_{k_{1}>0}-\frac{M_{k_{1},k_{2}}(t)}{n-X(t)}\right)-\frac{2(B_{k_{1},k_{2}}(t)+M_{k_{1},k_{2}}(t))}{n}$
Path distance $1$ from $\mathcal{R}_{t}$ | $\frac{2R(t)}{n}\left(\frac{M_{k_{1}-1,k_{2}+1}(t)}{n-X(t)}\cdot\bm{1}_{k_{1}>0}-\frac{M_{k_{1},k_{2}}(t)}{n-X(t)}-\frac{C_{k_{1},k_{2}}(t)}{n-X(t)}\right)$
$\mathcal{Q}_{t}$ | $\frac{(X(t)-5L(t))}{n}\frac{C_{k_{1}-1,k_{2}}(t)}{D(t)}$
$\mathcal{R}_{t}$ | $\frac{R(t)}{n}\frac{C_{k_{1},k_{2}-1}(t)}{D(t)}$
$\mathcal{B}_{t}$ | $-\frac{B_{k_{1},k_{2}}(t)}{n}+\frac{B_{k_{1}+1,k_{2}-1}(t)}{n}\cdot\bm{1}_{k_{2}>0}$

###### Proof of Table 3.

The explanations for the case of $k_{1}+k_{2}=q$ are identical to those of
$k_{1}+k_{2}=q-1$, except that vertices of type $(k_{1},k_{2})$ are created
(instead of destroyed) when $u_{t+1}$ satisfies $u_{t+1}\in\mathcal{Q}_{t}$ or
$u_{t+1}\in\mathcal{R}_{t}$.

∎

###  B.2. Proving Lemma 2.7

In this section, we inductively prove Lemma 2.7. Firstly, when $q=0$, by
definition $\tau_{0}=0$, and so $\sigma_{0}:=0$ trivially satisfies the
conditions of Lemma 2.7. Let us now assume that $q\geq 1$ and for each of
$0\leq i\leq q-1$ we have defined $\sigma_{i}$ and functions $x,r$ and
$c_{j,h}$ on $[0,\sigma_{i}]$ for each $j,h\geq 0$ with $j+h=i$, and Lemma 2.7
holds for all $0\leq i\leq q-1$. We shall define $\sigma_{q}$ which satisfies
$\sigma_{q}>\sigma_{q-1}$, extend each $x,r$ and $c_{j,h}$ to
$[0,\sigma_{q}]$, and define new functions $c_{k_{1},k_{2}}$ on
$[0,\sigma_{q}]$ for $k_{1}+k_{2}=q$. We shall then prove that these functions
satisfy the assertion of Lemma 2.7 with respect to $\tau_{q}$ and
$\sigma_{q}$, which will complete the proof of the lemma.

Fix a sufficiently small constant $\varepsilon>0$, and define the bounded
domain

$\mathcal{D}_{\varepsilon}:=\left\\{(s,x,r,(c_{j,h})_{j+h\in\\{q-1,q\\}}):\sigma_{q-1}-1<s<3,|x|<1-\varepsilon,|r|<2,|c_{j,h}|<2,\varepsilon<\sum_{j,h:\,j+h=q-1}c_{j,h}<2\right\\}.$

It will be convenient to define auxiliary functions to simplify our equations
below. Specifically, set $b_{k_{1},k_{2}}=k_{1}\cdot c_{k_{1},k_{2}}$ and
$m_{k_{1},k_{2}}:=k_{2}\cdot c_{k_{1},k_{2}}$, as well as
$b=\sum_{\begin{subarray}{c}j,h:\\\ j+h\in\\{q-1,q\\}\end{subarray}}b_{j,h}$
and $m=\sum_{\begin{subarray}{c}j,h:\\\
j+h\in\\{q-1,q\\}\end{subarray}}m_{j,h}$. Finally, set
$d=\sum_{\begin{subarray}{c}j,h:\\\ j+h=q-1\end{subarray}}c_{j,h}$. Observe
the following system of differential equations:

$\displaystyle x^{\prime}$ $\displaystyle=$ $\displaystyle 1-x+2$ (13)
$\displaystyle r^{\prime}$ $\displaystyle=$ $\displaystyle
m-r-\frac{2(b+m)r}{1-x}+\sum_{\begin{subarray}{c}j,h:\\\
j+h\in\\{q-1,q\\}\end{subarray}}2h(m_{j,h}+b_{j,h})$ (14)
$\displaystyle-2r\left(1+\frac{r}{1-x}-\frac{m}{1-x}\right)-r$

If $k_{1}+k_{2}=q-1$, then:

$\displaystyle c_{k_{1},k_{2}}^{\prime}$ $\displaystyle=$ $\displaystyle
m_{k_{1}-1,k_{2}+1}\cdot\bm{1}_{k_{1}>0}-c_{k_{1},k_{2}}-m_{k_{1},k_{2}}$ (15)
$\displaystyle+2(b+m)\left(\frac{m_{k_{1}-1,k_{2}+1}\cdot\bm{1}_{k_{1}>0}-m_{k_{1},k_{2}}}{1-x}\right)-2(b_{k_{1},k_{2}}+m_{k_{1},k_{2}})$
$\displaystyle+2r\left(\frac{m_{k_{1}-1,k_{2}+1}\cdot\bm{1}_{k_{1}>0}-m_{k_{1},k_{2}}-c_{k_{1},k_{2}}}{1-x}\right)$
$\displaystyle-(x-5\ell)\frac{c_{k_{1},k_{2}}}{d}+b_{k_{1}+1,k_{2}-1}\cdot\bm{1}_{k_{2}>0}-r\frac{c_{k_{1},k_{2}}}{d}-b_{k_{1},k_{2}}$

Otherwise, if $k_{1}+k_{2}=q$, then:

$\displaystyle c_{k_{1},k_{2}}^{\prime}$ $\displaystyle=$ $\displaystyle
m_{k_{1}-1,k_{2}+1}\cdot\bm{1}_{k_{1}>0}-c_{k_{1},k_{2}}-m_{k_{1},k_{2}}$ (16)
$\displaystyle+2(b+m)\left(\frac{m_{k_{1}-1,k_{2}+1}\cdot\bm{1}_{k_{1}>0}-m_{k_{1},k_{2}}}{1-x}\right)-2(b_{k_{1},k_{2}}+m_{k_{1},k_{2}})$
$\displaystyle+2r\left(\frac{m_{k_{1}-1,k_{2}+1}\cdot\bm{1}_{k_{1}>0}-m_{k_{1},k_{2}}-c_{k_{1},k_{2}}}{1-x}\right)$
$\displaystyle+(x-5\ell)\frac{c_{k_{1}-1,k_{2}}}{d}+b_{k_{1}+1,k_{2}-1}\cdot\bm{1}_{k_{2}>0}+r\frac{c_{k_{1},k_{2}-1}}{d}-b_{k_{1},k_{2}}$

The right-hand side (r.h.s.) of each of the above equations is Lipchitz on the
domain $\mathcal{D}_{\varepsilon}$, as $d$ is bounded below by $\varepsilon$.
Define

$T_{\mathcal{D}_{\varepsilon}}:=\min\\{t\geq
0:(t/n,X(t)/n,R(t)/n,(C_{k_{1},k_{2}}(t)/n)_{k_{1}+k_{2}\in\\{q,q-1\\}})\notin\mathcal{D}_{\varepsilon}\\}$

By the inductive assumption, the ‘Initial Condition’ of Theorem D.1 is
satisfied for some $\lambda=o(1)$ and values
$\sigma_{q-1},x(\sigma_{q-1}),r(\sigma_{q-1})$ and $c_{j,h}(\sigma_{q-1})$,
where $c_{j,h}(\sigma_{q-1}):=0$ for $j+h=q$. Moreover, the ‘Trend Hypothesis’
is satisfied with $\delta=O(1/n)$, by the expected differences of (8)-(11).
Finally, the ‘Boundedness Hypothesis’ is satisfied with $\beta=O(\log n)$ and
$\gamma=O(n^{-1})$ by Lemma B.1. Thus, by Theorem D.1, for every $\delta>0$,
a.a.s. $X(t)=nx(t/n)+o(n)$, $R(t)=nr(t/n)+o(n)$ and
$C_{k_{1},k_{2}}(t)=nc_{k_{1},k_{2}}(t/n)+o(n)$ uniformly for all
$\sigma_{q-1}n\leq t\leq(\sigma(\varepsilon)-\delta)n$, where $x$, $\ell_{1}$
and $c_{k_{1},k_{2}}$ are the unique solution to (13)-(16) with the above
initial conditions, and $\sigma(\varepsilon)$ is the supremum of $s$ to which
the solution can be extended before reaching the boundary of
$\mathcal{D}_{\varepsilon}$. This immediately yields the following lemma.

######  Lemma B.2 (Concentration of $\mathtt{DegreeGreedy}$’s Random
Variables).

For every $\delta>0$, a.a.s. for all $\tau_{q-1}\leq
t\leq(\sigma(\varepsilon)-\delta)n$ and $k_{1},k_{2}\geq 0$ such that
$k_{1}+k_{2}\in\\{q,q-1\\}$,

$\max\\{|X(t)-x(t/n)n|,|R(t)-r(t/n)n|,|C_{k_{1},k_{2}}(t)-c_{k_{1},k_{2}}(t/n)n||\\}=o(n).$

As $\mathcal{D}_{\varepsilon}\subseteq\mathcal{D}_{\varepsilon^{\prime}}$ for
every $\varepsilon>\varepsilon^{\prime}$, $\sigma(\varepsilon)$ is monotonely
nondecreasing as $\varepsilon\to 0$, and so $\sigma_{q}:=\lim_{\varepsilon\to
0+}\sigma(\varepsilon)$ exists. Moreover, the derivatives of the functions
$x,r,$ and $c_{k_{1},k_{2}}$ are uniformly bounded on
$(\sigma_{q-1},\sigma_{q})$, which implies that the functions must be
uniformly continuous. The latter condition implies that the functions are
(uniquely) continuously extendable to $[\sigma_{q-1},\sigma_{q}]$, and so the
following limits exist:

$\displaystyle x(\sigma_{q})$ $\displaystyle:=$
$\displaystyle\lim_{s\to\sigma_{q}-}x(s)$ (17) $\displaystyle r(\sigma_{q})$
$\displaystyle:=$ $\displaystyle\lim_{s\to\sigma_{q}-}r(s)$ (18)
$\displaystyle c_{k_{1},k_{2}}(\sigma_{q})$ $\displaystyle:=$
$\displaystyle\lim_{s\to\sigma_{q}-}c_{k_{1},k_{2}}(s).$ (19)

Random variables $|R(t)/n|$ and $|C_{k_{1},k_{2}}(t)/n|$ for
$k_{1}+k_{2}\in\\{q,q-1\\}$ are both bounded by $1$ for all $t$. Thus, when
$t/n$ approaches $\sigma_{q}$, $X(t)/n$ approaches $1$, or $t/n$ approaches
$3$, or $D(t)/n:=\sum_{\begin{subarray}{c}j,h:\\\
j+h=q-1\end{subarray}}C_{j,h}(t)/n$ approaches $0$. Formally, we have the
following proposition:

######  Proposition B.3.

For every $\varepsilon>0$, there exists $\delta>0$ such that a.a.s. one of the
following holds.

  * •

$D(t)<\varepsilon n$ for all $t\geq(\sigma_{q}-\delta)n$;

  * •

$X(t)>(1-\varepsilon)n$ for all $t\geq(\sigma_{q}-\delta)n$;

  * •

$\sigma_{q}=3$.

The ordinary differential equations (13)-(16) again do not have an analytical
solution. However, numerical solutions show that $\sigma_{q}<3$, and
$x(\sigma_{q})<1$. Thus, after executing $\mathtt{DegreeGreedy}$ for
$t=\sigma_{q}n+o(n)$ steps, there are $D(t)<\varepsilon n$ vertices of type
$q-1$ remaining for some $\varepsilon=o(1)$. At this point, by observing the
numerical solution (17)–(19) at $\sigma_{q}$, we know that there exists some
absolute constant $0<p<1$ such that $(X(t)-5L(t))/n\geq p$, where we recall
that $L(t)$ counts the total number of coloured vertices at time $t$. Hence,
at each step, some vertex of type $q-1$ becomes of type $q$ with probability
at least $p$. Thus, by applying Chernoff’s bound, one can show that a.a.s.
after another $O(\varepsilon n/p)=o(n)$ rounds, all vertices of type $q-1$ are
destroyed. It follows that a.a.s. $|\tau_{q}/n-\sigma_{q}|=o(1)$, and so Lemma
2.7 is proven.

##  Appendix C Proof of Lemma 3.1

######  Lemma C.1.

Suppose ${\mathcal{S}}$ is $\mu$-well-behaved up until time $t=\Theta(n)$.
A.a.s. the following holds for $G^{{\mathcal{S}}}_{t}$:

$\displaystyle|{\mathcal{W}}_{1}|$ $\displaystyle\sim n\sum_{i\leq
t}\frac{1}{n}\left(1-\frac{1}{n}\right)^{t}\sum_{i\leq j_{1}<j_{2}\leq
t}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{j_{2}}$ (20)
$\displaystyle|{\mathcal{W}}_{2}|$ $\displaystyle\sim n\sum_{i_{1}\leq
i_{2}\leq t}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{t}\left(\sum_{i_{1}\leq
j_{1}<j_{2}\leq
t}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{j_{2}}+\sum_{i_{2}<j_{1}<j_{2}\leq
t}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{j_{2}}\right)$ (21)
$\displaystyle|{\mathcal{T}}_{1}|$ $\displaystyle\sim n\sum_{i\leq
t}\frac{1}{n}\left(1-\frac{1}{n}\right)^{t}\sum_{i\leq j_{1}<j_{2}\leq
t}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{t}$
$\displaystyle\times\left(\sum_{j_{1}\leq h_{1}<h_{2}\leq
t}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{h_{2}}+\sum_{j_{2}<h_{1}<h_{2}\leq
t}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{h_{2}}\right)$ (22)
$\displaystyle|{\mathcal{T}}_{2}|$ $\displaystyle\sim n\sum_{i_{1}<i_{2}\leq
t}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{t}\sum_{i_{1}\leq j_{1}<j_{2}\leq
t}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{t}$
$\displaystyle\times\left(\sum_{j_{1}\leq h_{1}<h_{2}\leq
t}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{h_{2}}+\sum_{j_{2}<h_{1}<h_{2}\leq
t}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{h_{2}}\right)$
$\displaystyle+\sum_{i_{1}<i_{2}\leq
t}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{t}\sum_{i_{2}\leq j_{1}<j_{2}\leq
t}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{t}$
$\displaystyle\times\left(\sum_{j_{1}\leq h_{1}<h_{2}\leq
t}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{h_{2}}+\sum_{j_{2}<h_{1}<h_{2}\leq
t}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{h_{2}}\right).$ (23)

###### Proof.

We prove (20) and briefly explain the expressions in (21)–(23) whose proofs
are similar to that of (20). Fix a vertex $x\in[n]$ and a square $u_{i}$ for
$i\leq t$. The probability that $u_{i}$ lands on $x$ in step $i$ is $1/n$.
Condition on this event. The probability that $x$ receives no squares in any
steps other than $i$ is $(1-1/n)^{t-1}\sim(1-1/n)^{t}$. Let $y$ be the vertex
which the strategy chooses to pair with $u_{i}$ with. Fix any two integers
$i<j_{1}<j_{2}\leq t$, the probability that $y$ receives its first two squares
at times $j_{1}$ and $j_{2}$ is $n^{-2}(1-1/n)^{j_{2}-2}\sim
n^{-2}(1-1/n)^{j_{2}}$. Summing over all possible values of $i,j_{1},j_{2}$
and multiplying by $n$, the number of choices for $x$, gives
${\mathbb{E}}|{\mathcal{W}}_{1}|$.

For concentration of $|{\mathcal{W}}_{1}|$ we prove that
${\mathbb{E}}|{\mathcal{W}}_{1}|^{2}\sim({\mathbb{E}}|{\mathcal{W}}_{1}|)^{2}$.
For any pair of $((x_{1},y_{1}),(x_{2},y_{2}))$ in
${\mathcal{W}}_{1}\times{\mathcal{W}}_{1}$, either $x_{1},y_{1},x_{2},y_{2}$
are pairwise distinct, or $y_{1}=y_{2}$. It is easy to see that the expected
number of pairs where $x_{1},y_{1},x_{2},y_{2}$ are pairwise distinct is

$n^{2}\sum_{\begin{subarray}{c}i_{1}\leq t\\\ i_{2}\leq
t\end{subarray}}\frac{1}{n^{2}}\left(1-\frac{1}{n}\right)^{2(t-1)}\sum_{\begin{subarray}{c}i_{1}\leq
j_{1}<j_{2}\leq t\\\ i_{2}\leq h_{1}<h_{2}\leq
t\end{subarray}}\frac{1}{n^{4}}\left(1-\frac{1}{n}\right)^{j_{2}-2+h_{2}-2}\sim({\mathbb{E}}|{\mathcal{W}}_{1}|)^{2}.$

The expected number of pairs where $y_{1}=y_{2}$ is at most $\mu n$ as there
are most $n$ choices for $x_{1}$ and given $(x_{1},y_{1})$, there can be at
most $\mu$ choices for $(x_{2},y_{2})$ since ${\mathcal{S}}$ is $\mu$-well-
behaved. Since $\mu=o(n)$, $\mu n=o(n^{2})$ which is
$o(({\mathbb{E}}|{\mathcal{W}}_{1}|)^{2})$. Thus we have verified that
${\mathbb{E}}|{\mathcal{W}}_{1}|^{2}\sim({\mathbb{E}}|{\mathcal{W}}_{1}|)^{2}$
and thus by the second moment method, a.a.s.
$|{\mathcal{W}}_{1}|\sim{\mathbb{E}}|{\mathcal{W}}_{1}|$.

The proofs for the expectation and concentration of $|{\mathcal{W}}_{2}|$,
$|{\mathcal{T}}_{1}|$ and $|{\mathcal{T}}_{2}|$ are similar. We briefly
explain the expressions in (21)–(23):

In (21), $i_{1}$ and $i_{2}$ denote the two steps at which $x$ receives a
square. Since there are two squares on $x$, there are two choices of circles,
namely $v_{i_{1}}$ and $v_{i_{2}}$. The two summations over $(j_{1},j_{2})$
accounts for the two choices of $v_{i_{1}}$ and $v_{i_{2}}$, depending on
which is to be covered by two squares. Thus, $j_{1}$ and $j_{2}$ denote the
steps where the first two squares on $v_{i_{1}}$ or $v_{i_{2}}$ arrive.

In (22), $i$ denotes the step where $x_{1}$ receives its only square; $j_{1}$
and $j_{2}$ denote the two steps where $y_{1}=x_{2}$ receives its two squares.
Hence, there are two choices for $y_{2}$, and $h_{1}$ and $h_{2}$ denote the
two steps of the first two squares $y_{2}$ receives.

In (23), $i_{1}$ and $i_{2}$ denote the two steps where $x_{1}$ receives its
two squares—hence there are two choices for $y_{1}$. Integers $j_{1}$ and
$j_{2}$ denote the two steps where $y_{1}=x_{1}$ receives its two
squares—hence there are two choices for $y_{2}$. Finally, $h_{1}$ and $h_{2}$
denote the steps where $y_{2}$ receives its first two squares. ∎

From Lemma C.1, we deduce that for $t=sn$,

$\displaystyle|{\mathcal{W}}_{1}|$ $\displaystyle\sim
ne^{-s}\int_{0}^{s}dx\int_{x}^{s}dy_{1}\int_{y_{1}}^{s}e^{-y_{2}}dy_{2}=ne^{-s}\left(1-\frac{e^{-s}s^{2}}{2}-e^{-s}s-e^{-s}\right)$
$\displaystyle|{\mathcal{W}}_{2}|$ $\displaystyle\sim
ne^{-s}\int_{0}^{s}dx_{1}\int_{x_{1}}^{s}dx_{2}\left(\int_{x_{1}}^{s}dy_{1}\int_{y_{1}}^{s}e^{-y_{2}}dy_{2}+\int_{x_{2}}^{s}dy_{1}\int_{y_{1}}^{s}e^{-y_{2}}dy_{2}\right)$
$\displaystyle=ne^{-s}\left(s-e^{-s}s^{2}-\frac{e^{-s}s^{3}}{2}-e^{-s}s\right)$
$\displaystyle|{\mathcal{T}}_{1}|$ $\displaystyle\sim
ne^{-2s}\int_{0}^{s}dx\int_{x}^{s}dy_{1}\int_{y_{1}}^{s}dy_{2}\left(\int_{y_{1}}^{s}dz_{1}\int_{z_{1}}^{s}e^{-z_{2}}dz_{2}+\int_{y_{2}}^{s}dz_{1}\int_{z_{1}}^{s}e^{-z_{2}}dz_{2}\right)$
$\displaystyle=ne^{-2s}\left(-1+s-\frac{e^{-s}s^{3}}{3}-\frac{e^{-s}s^{2}}{2}-\frac{e^{-s}s^{4}}{8}+e^{s}\right)$
$\displaystyle|{\mathcal{T}}_{2}|$ $\displaystyle\sim
ne^{-2s}\int_{0}^{s}dx_{1}\int_{x_{1}}^{s}dx_{2}\int_{x_{1}}^{s}dy_{1}\int_{y_{1}}^{s}dy_{2}\left(\int_{y_{1}}^{s}dz_{1}\int_{z_{1}}^{s}e^{-z_{2}}dz_{2}+\int_{y_{2}}^{s}dz_{1}\int_{z_{1}}^{t}e^{-z_{2}}dz_{2}\right)$
$\displaystyle+ne^{-2s}\int_{0}^{s}dx_{1}\int_{x_{1}}^{s}dx_{2}\int_{x_{2}}^{s}dy_{1}\int_{y_{1}}^{s}dy_{2}\left(\int_{y_{1}}^{s}dz_{1}\int_{z_{1}}^{s}e^{-z_{2}}dz_{2}+\int_{y_{2}}^{s}dz_{1}\int_{z_{1}}^{s}e^{-z_{2}}dz_{2}\right)$
$\displaystyle=ne^{-2s}\left(-s+s^{2}-e^{-s}s\left(\frac{s^{4}}{8}+\frac{s^{3}}{3}+\frac{s^{2}}{2}-1\right)\right)$

It follows now that $Z-|{\mathcal{W}}_{1}|-|{\mathcal{W}}_{2}|+W\sim f(s)n$
where recall that

$f(s)=2+e^{-3s}(s+1)\left(1-\frac{s^{2}}{2}-\frac{s^{3}}{3}-\frac{s^{4}}{8}\right)+e^{-2s}\left(2s+\frac{5s^{2}}{2}+\frac{s^{3}}{2}\right)-e^{-s}\left(3+2s\right).$

##  Appendix D The Differential Equation Method

In this section, we provide a self-contained non-asymptotic statement of the
differential equation method. The statement combines [13, Theorem $2$], and
its extension [13, Lemma $9$], in a form convenient for our purposes, where we
modify the notation of [13] slightly. In particular, we rewrite [13, Lemma
$9$] in a less general form in terms of a stopping time $T$. We need only
check the ‘Boundedness Hypothesis’ (see below) for $0\leq t\leq T$, which is
exactly the setting of Lemmas 2.1 and B.1.

Suppose we are given integers $a,n\geq 1$, a bounded domain
$\mathcal{D}\subseteq\mathbb{R}^{a+1}$, and functions $(F_{k})_{1\leq k\leq
a}$ where each $F_{k}:\mathcal{D}\to\mathbb{R}$ is $L$-Lipschitz-continuous on
$\mathcal{D}$ for $L\geq 0$. Moreover, suppose that $R\in[1,\infty)$ and
$S\in(0,\infty)$ are any constants which satisfy $\max_{1\leq k\leq
a}|F_{k}(x)|\leq R$ for all $x=(s,y_{1},\ldots,y_{a})\in\mathcal{D}$ and
$0\leq s\leq S$.

######  Theorem D.1 (Differential Equation Method, [13]).

Suppose we are given $\sigma$-fields
$\mathcal{F}_{0}\subseteq\mathcal{F}_{1}\subseteq\cdots$, and for each $t\geq
0$, random variables $((Y_{k}(t))_{1\leq k\leq a}$ which are
$\mathcal{F}_{t}$-measurable. Define $T_{\mathcal{D}}$ to be the minimum
$t\geq 0$ such that

$(t/n,Y_{1}(t)/n,\ldots,Y_{k}(t)/n)\notin\mathcal{D}.$

Let $T\geq 0$ be an (arbitrary) stopping time444The stopping time $T\geq 0$ is
adapted to $(\mathcal{F}_{t})_{t\geq 0}$, provided the event $\\{\tau=t\\}$ is
$\mathcal{F}_{t}$-measurable for each $t\geq 0$. adapted to
$(\mathcal{F}_{t})_{t\geq 0}$, and assume that the following conditions hold
for $\delta,\beta,\gamma\geq 0$ and $\lambda\geq\delta\min\\{S,L^{-1}\\}+R/n$:

  1. (i)

The ‘Initial Condition’: For some
$(0,\hat{y}_{1},\ldots,\hat{y}_{a})\in\mathcal{D}$,

$\max_{1\leq k\leq a}|Y_{k}(0)-\hat{y}_{k}n|\leq\lambda n.$

  2. (ii)

The ‘Trend Hypothesis’: For each $t\leq\min\\{T,T_{\mathcal{D}}-1\\}$,

$|\mathbb{E}[Y_{k}(t+1)-Y_{k}(t)\mid\mathcal{F}_{t}]-F_{k}(t/n,Y_{1}(t)/n,\ldots,Y_{a}(t)/n)|\leq\delta.$

  3. (iii)

The ‘Boundedness Hypothesis’: With probability $1-\gamma$,

$|Y_{k}(t+1)-Y_{k}(t)|\leq\beta,$

for each $t\leq\min\\{T,T_{\mathcal{D}}-1\\}$:

Then, with probability at least
$1-2a\exp\left(\frac{-n\lambda^{2}}{8S\beta^{2}}\right)-\gamma$, we have that

$\max_{0\leq t\leq\min\\{T,\sigma n\\}}\max_{1\leq k\leq
a}|Y_{k}(t)-y_{k}(t/n)n|<3\lambda\exp(LS)n,$ (24)

where $(y_{k}(s))_{1\leq k\leq a}$ is the unique solution to the system of
differential equations

$y_{k}^{\prime}(s)=F_{k}(s,y_{1}(s),\ldots,y_{a}(s))\quad\mbox{with
$y_{k}(0)=\hat{y}_{k}$ for $1\leq k\leq a$,}$ (25)

and $\sigma=\sigma(\hat{y}_{1},\ldots,\hat{y}_{a})\in[0,S]$ is any choice of
$\sigma\geq 0$ with the property that $(s,y_{1}(s),\ldots,y_{a}(s))$ has
$\ell^{\infty}$-distance at least $3\lambda\exp(LS)$ from the boundary of
$\mathcal{D}$ for all $s\in[0,\sigma)$.

######  Remark 2.

Standard results for differential equations guarantee that (25) has a unique
solution $(y_{k}(s))_{1\leq k\leq a}$ which extends arbitrarily close to the
boundary of $\mathcal{D}$.