# Adaptable and conflict colouring multigraphs with no cycles of length three
or four

Jurgen Aliaj  Michael Molloy

( University of Toronto
Department of Computer Science
10 King’s College Road
Toronto, ON, Canada, M5S 3G4
<EMAIL_ADDRESS>
)

###### Abstract

The adaptable choosability of a multigraph $G$, denoted $\mathrm{ch}_{a}(G)$,
is the smallest integer $k$ such that any edge labelling, $\tau$, of $G$ and
any assignment of lists of size $k$ to the vertices of $G$ permits a list
colouring, $\sigma$, of $G$ such that there is no edge $e=uv$ where
$\tau(e)=\sigma(u)=\sigma(v)$. Here we show that for a multigraph $G$ with
maximum degree $\Delta$ and no cycles of length 3 or 4,
$\mathrm{ch}_{a}(G)\leq(2\sqrt{2}+o(1))\sqrt{\Delta/\ln\Delta}$. Under natural
restrictions we can show that the same bound holds for the conflict
choosability of $G$, which is a closely related parameter recently defined by
Dvořák, Esperet, Kang and Ozeki.
Keywords: adaptable colouring; conflict colouring; high girth graphs;
probabilistic method

##  1 Introduction

Hell and Zhu introduced the adaptable chromatic number [19]. This variant on
the chromatic number was also introduced independently (under different names)
by Erdös and Gyárfás [7], Cochand and Duchet [3], and Archer [1].

The basic idea is this: we are given an edge labelling of a graph $G$ and we
assign colours to the vertices of $G$ such that there is no edge $e=uv$ where
$u$, $v$, and $e$ are all the same colour. Such a colouring is called an
adaptable colouring of $G$. I.e. in conventional graph colouring each edge
forbids its endpoints from both receiving the same colour, whereas in
adaptable colouring each edge forbids its endpoints from both receiving a
particular colour, namely its edge label. Note that an adaptable colouring may
be improper in the sense that two adjacent vertices may both receive the
colour red, so long as the edge connecting them is not also labelled with the
colour red.

We can take this a step further by including multiple edges between adjacent
vertices, to further constrain the colours assigned to them. In fact, a
conventional colouring problem with $k$ colours can be reduced to an adaptable
colouring problem by passing to the corresponding multigraph with multiplicity
$k$, and such that each edge between two endpoints is given a unique colour
from $[k]=\\{1,\dots,k\\}$. Therefore it is natural—and in fact important—to
allow multiple edges in our graphs.

For a formal definition: let $G=(V,E)$ be a multigraph. Let
$\tau:E\to\mathbb{N}$ be an edge labelling of $G$, we say that a vertex
colouring, $\sigma:V\to\mathbb{N}$, of $G$ is a proper adaptable colouring if
there is no edge $e=uv$ such that $\sigma(u)=\sigma(v)=\tau(e)$. The adaptable
chromatic number of $G$, denoted $\chi_{a}(G)$, is the minimum integer $k$
such that every edge labelling of $G$ using labels from $[k]$ permits a proper
adaptable colouring of $G$ from $[k]$. Since every proper vertex colouring of
$G$ is a proper adaptable colouring of $G$ for any edge labelling, we can see
that $\chi_{a}(G)\leq\chi(G)$, where $\chi(G)$ is the usual chromatic number
of $G$. Applications of this problem include job scheduling [21], matrix and
list partitions of graphs [12, 11], as well as full constraint satisfaction
problems [10].

Here we present a result for adaptable list colouring, which is defined
naturally. Suppose each $v\in G$ is assigned a list $L(v)\subset\mathbb{N}$ of
candidate colours. Then a proper adaptable list colouring of $G$ is a proper
adaptable colouring where each vertex $v$ is assigned a colour from $L(v)$.
The adaptable choosability of $G$, denoted $\mathrm{ch}_{a}(G)$, is the
smallest integer $k$ such that any edge labelling of $G$ and any assignment of
lists of size $k$ to the vertices of $G$ permits a proper adaptable list
colouring of $G$. If $\mathrm{ch}_{a}(G)=k$, then assigning $L(v)=[k]$ for
each $v\in G$ permits a proper adaptable colouring, hence
$\chi_{a}(G)\leq\mathrm{ch}_{a}(G)$. Moreover, since any proper vertex
colouring of $G$ from lists of size $k$ permits a proper adaptable colouring
of $G$ for any edge labelling, we have $\mathrm{ch}_{a}(G)\leq\mathrm{ch}(G)$,
where $\mathrm{ch}(G)$ is the usual choosability of $G$. Adaptable colouring
and adaptable list colouring have been studied in [18, 25, 19, 27, 16, 9].

In the case of conventional graph colouring, much attention has been given to
colouring graphs of high girth [4, 15, 17], as typically fewer colours are
required. We will see that the same phenomenon can be observed with adaptable
list colouring.

Two results in particular are of interest to us. The first is by Kim [20] who
showed that if $\Delta$ is the maximum degree of a simple graph $G$ with girth
at least 5 (i.e. no cycles of length 4 or less), then
$\mathrm{ch}(G)\leq(1+o(1))\frac{\Delta}{\ln\Delta}$. The second is by Molloy
and Thron [26], who showed that for a general multigraph $G$ with maximum
degree $\Delta$, $\mathrm{ch_{a}}(G)\leq(1+o(1))\sqrt{\Delta}$. In a sense, we
combine these results by presenting an upper bound on the adaptable
choosability, which we show for essentially the same class of graphs
considered by Kim.

Recall that it is important to allow multiple edges in the graphs we consider.
So if we would like to study adaptable colouring in a high girth setting, we
must define a notion of high girth for multigraphs. The most natural course of
action is to permit 2-cycles, i.e. multiple edges, while disallowing other
short cycles in our graphs. In particular we consider multigraphs with no
cycles of length 3 or 4, which is the most natural analogue to Kim’s setting.
We get the following result:

######  Theorem 1.1.

Let $G$ be a multigraph with no cycles of length 3 or 4 and maximum degree
$\Delta$, then
$\mathrm{ch}_{a}(G)\leq(2\sqrt{2}+o(1))\sqrt{\Delta/\ln\Delta}$.

We comment briefly on the tightness of Theorem 1.1. For any $g$ and
$\Delta\geq 3$, random $\Delta$-regular graphs have girth at least $g$ and
satisfy $\chi(G)\geq(\frac{1}{2}+o(1))\frac{\Delta}{\ln\Delta}$ with high
probability [14]. Moreover it is known that for any graph $G$,
$\chi_{a}(G)\geq(1+o(1))\sqrt{\chi(G)}$ by [22]. Combining these two facts
implies the existence of a graph $G$ with maximum degree $\Delta$ and no 3 or
4-cycles, satisfying
$\chi_{a}(G)\geq(\frac{\sqrt{2}}{2}+o(1))\sqrt{\Delta/\ln\Delta}$. And since
$\mathrm{ch}_{a}(G)\geq\chi_{a}(G)$, this implies the bound in Theorem 1.1 is
within a factor of 4 of the best possible (note that Kim’s result is within a
factor of 2 of the best possible, see remark 3.5 to understand why this
changes to a 4 in our case).

We achieve Theorem 1.1 by showing a more general result for a problem called
conflict colouring. In adaptable colouring, we are given an edge labelling
$\tau$ so that each edge $e=uv$ constrains the colours assigned to $u$ and $v$
symmetrically. I.e. the edge colour $c=\tau(e)$ acts as a constraint
preventing $u$ and $v$ from both receiving the same colour $c$. In conflict
colouring we allow for the possibility of an asymmetric constraint, meaning
that instead of the edge label being a single colour, it can now be an ordered
pair of colours $(c,c^{\prime})$ which is meant to prevent $u$ from receiving
$c$ and $v$ from receiving $c^{\prime}$ simultaneously. The problem was
introduced independently by Dvořák and Postle [6] and Fraigniaud, Heinrich and
Kosowski [13].

We should point out that in [6, 13], the authors present slightly different
(but equivalent) representations of what we call the conflict colouring
problem. For instance, in [6] the authors consider correspondence colouring.
In this variant we are given a simple graph where each edge $e=uv$ corresponds
to a partial matching, $M_{e}$, between the candidate colours $L(u)$ and
$L(v)$. A pair $f\in M_{e}$ forbids $u$ and $v$ from both receiving the
colours corresponding to the entries of $f$. This is of course the same
problem we consider here, the only important difference being that in our case
the pairs in $M_{e}$ are instead included in our graph as parallel edges
between $u$ and $v$, and therefore they contribute to the maximum degree. Our
setting most closely resembles that of Dvořák, Esperet, Kang and Ozeki [5],
and we use the same notion of conflict degree (we define this in a moment)
seen in [13].

For a multigraph $G=(V,E)$, Dvořák et al. [5] defined the conflict
choosability of $G$, denoted $\mathrm{ch}_{\nleftrightarrow}(G)$, as the
smallest integer $k$ such that any edge labelling
$\tau:E\to\mathbb{N}\times\mathbb{N}$ and any assignment of lists
$L(v)\subset\mathbb{N}$ to every $v\in G$, each of size $k$, permits a vertex
colouring $\sigma:V\to L(v)$ such that there is no edge $e=uv\in G$ where
$\tau(e)=(\sigma(u),\sigma(v))$. We call $\sigma$ a proper conflict colouring.

The reader may notice some ambiguity here, since for a label
$\tau(e)=(c,c^{\prime})$ it is not clear which of the endpoints of $e$ should
be forbidden from receiving $c$ and which should be forbidden from receiving
$c^{\prime}$. We will define some convenient notation to overcome this (see
the comment at the beginning of section 3). For now, what we mean will be made
clear by the context.

Observe that for any edge labelling and list assignments of size $k$, we can
rename the colours in $L(v)$ as well as the colours assigned by $\tau$
accordingly while preserving the existence of a proper conflict colouring. So
in fact we may assume $L(v)=[k]$ for each $v\in G$. I.e. conflict colouring
and conflict list colouring are one and the same.

It turns out that it is not possible to obtain the same bound for conflict
choosability as in Theorem 1.1, which will be made clear by the following
example.

######  Example 1.2.

Let $\Delta$ be a natural number and $L$ be a set of colours with size
$\ell\leq\sqrt{\Delta}$. Consider the multigraph $G$ with only two vertices,
$u$ and $v$, each assigned the same set $L$ of colours and connected by
$\ell^{2}$ edges. Note the maximum degree of $G$ is $\ell^{2}\leq\Delta$, so
if needed we can increase the maximum degree to be exactly $\Delta$ by adding
dummy vertices. Define $\tau$ such that each edge between $u$ and $v$ is given
a unique label from one of the $\ell^{2}$ possible pairs of colours, and
observe that $G$ does not have a proper conflict colouring. I.e. $G$ is a
multigraph with no cycles of length 3 or 4, but
$\mathrm{ch}_{\nleftrightarrow}(G)>\sqrt{\Delta}$.

To investigate what went wrong in the previous example we need to first define
a parameter called the conflict degree.

######  Definition 1.3.

Given a multigraph $G=(V,E)$, an edge labelling
$\tau:E\to\mathbb{N}\times\mathbb{N}$, a colour $c$, and a pair of vertices
$u$ and $v$, define $d(\tau,c,u,v)$ to be the number of edges $e=uv\in G$ such
that $\tau(e)=(c,c^{\prime})$ for some colour $c^{\prime}$. Define the
conflict degree of $\tau$, denoted $D(\tau)$, to be the maximum of
$d(\tau,c,u,v)$ over all colours $c$ and pairs $u,v$.

Notice that in Example 1.2 we considered an edge labelling $\tau$ with
$D(\tau)=\ell$, the size of our lists. In other words if we allow the conflict
degree to become too high then we have no hope of finding a proper conflict
colouring. In the specific case where we consider lists of size
$\ell=(2\sqrt{2}+o(1))\sqrt{\Delta/\ln\Delta}$, the same problem occurs if
$D(\tau)$ is as high as $\ell^{15/16}$, which will be made clear by Example
1.7. Note that Example 1.7 is more involved, and so we include the details at
the end of the section. We simply summarize the main point here.

######  Fact 1.4.

For any constant $\alpha\geq 1$, there is a multigraph $G$ with maximum degree
$\Delta$, no cycles of length 3 or 4, an assignment of lists each with size
$\ell=\alpha\sqrt{\Delta/\ln\Delta}$, an edge labelling $\tau$ with
$D(\tau)=\ell^{f(\alpha)}$, and such that $G$ does not have a proper conflict
colouring, where $f(\alpha)$ is non-negative for $\alpha\geq 1$, non-
decreasing, and tending to 1 as $\alpha$ approaches infinity. In particular,
when $\alpha=2\sqrt{2}+o(1)$ we have $f(\alpha)=\frac{15}{16}$.

The function $f$ will be defined precisely in Example 1.7.

Clearly, Fact 1.4 requires us to restrict the types of edge labellings we
consider. Moving forward, we restrict the type of edge labelling that is
allowed on our graph by imposing an upper bound on the conflict degree. Such
an approach has been taken in [13]. Note that since we consider lists of size
$\ell=(2\sqrt{2}+o(1))\sqrt{\Delta/\ln\Delta}$, Fact 1.4 means we must
restrict the conflict degree to be at most
$\ell^{15/16}\approx\Delta^{15/32}$. Unfortunately we run into problems even
when allowing the conflict degree to be this large. Instead we aim for
something closer to $\Delta^{1/4}$, we make no attempt to determine if this is
optimal. We arrive at the following generalization of Theorem 1.1:

######  Theorem 1.5.

For any $\epsilon>0$, there exists $\Delta_{0}$ such that if $G$ is a
multigraph with maximum degree $\Delta>\Delta_{0}$, no cycles of length 3 or
4, an assignment of lists $L(v)$ for each vertex $v$ such that
$|L(v)|\geq(2\sqrt{2}+\epsilon)\sqrt{\Delta/\ln\Delta}$, and an edge labelling
$\tau$ with $D(\tau)\leq\Delta^{\frac{1}{4}\epsilon^{2}/(\epsilon+5)^{2}}$,
then there exists a proper conflict colouring of $G$ from these lists.

The important point here is that there is a tradeoff between the bound on our
conflict degree and our list sizes. We can make our list sizes arbitrarily
close to $2\sqrt{2}\sqrt{\Delta/\ln\Delta}$ and the conflict degree
arbitrarily close to $\Delta^{1/4}$, but not at the same time.

It is easy to see that Theorem 1.5 implies Theorem 1.1. The key observation is
that an instance of an adaptable colouring problem is exactly an instance of a
conflict colouring problem with conflict degree 1.

Notice that since Theorem 1.1 is implied by Theorem 1.5, this means the
discussion following the statement of Theorem 1.1 applies to Theorem 1.5 as
well. That is, the choice of list sizes in 1.5 is within a factor of 4 of the
best possible, even when $D(\tau)\leq 1$.

As mentioned, we cannot quite allow our conflict degree to be as large as
$\Delta^{1/4}$, but by allowing the list size to be large we can come close. A
direct result of Theorem 1.5 is the following more visually appealing
statement, which can be seen by taking $\epsilon=45$.

######  Corollary 1.6.

There exists $\Delta_{0}$ such that if $G$ is a multigraph with maximum degree
$\Delta>\Delta_{0}$, no cycles of length 3 or 4, an assignment of lists $L(v)$
for each vertex $v$ such that $|L(v)|\geq 50\sqrt{\Delta/\ln\Delta}$, and an
edge labelling $\tau$ with $D(\tau)\leq\Delta^{1/5}$, then there exists a
proper conflict colouring of $G$ from these lists.

Actually, if one is more careful with the analysis (in particular the proof of
Lemma 3.13), then Theorem 1.5 can be strengthened slightly and as a result the
“50” in Corollary 1.6 can be improved to a “10”. We opt for the weaker
statement here to keep the proof cleaner.

In the following sections we give a proof of Theorem 1.5 by colouring $G$
using a semi-random procedure. Similar procedures have been used in many
places. The procedures in [29, 26] are particularly close to the one presented
here. Our analysis is heavily based on Kim’s result [20], as presented in
chapter 12 of [23]. One of the important differences is Modification 1, where
we remove certain “bad” colours before starting our procedure. This idea has
been used in [26], but in our case the situation is slightly more delicate,
and so we take greater care with how many colours we choose to remove (see
remark 3.5). Another key difference is a new parameter (see $t_{i}(v,u,c)$
defined in section 3) which is closely related to the conflict degree. We must
ensure that this parameter is sufficiently small to guarantee concentration
results of the main parameters considered in chapter 12 of [23].

As promised, we now give the details of Example 1.7, which serves as a proof
of Fact 1.4.

######  Example 1.7.

For any $\Delta$, it is easy to find simple graphs with no cycles of length 3
or 4 which are $\Delta$-regular. Let $G$ be such a graph. By Proposition 6 of
[5], such a graph satisfies
$\mathrm{ch}_{\nleftrightarrow}(G)>\sqrt{\Delta/\ln\Delta}=\ell$. This means
there is at least one edge labelling of $G$ from $[\ell]$ which does not
permit a proper conflict colouring of the vertices from $[\ell]$. Let $\tau$
be this edge labelling (to be clear, each label assigned by $\tau$ is a pair
of colours). Note that since $G$ is simple, $D(\tau)=1$.

Now consider the following graph $G^{\prime}$, constructed by replacing each
edge in $G$ by $\ell^{\prime}=\ell^{2}$ parallel edges. Consider the set
$C=[\ell^{\prime}]$ of $\ell^{\prime}$ colours. We partition $C$ into
$\sqrt{\ell^{\prime}}=\ell$ contiguous pieces each of size $\ell$. Let $C_{i}$
be the $i^{th}$ piece of the partition. For each pair $i,j$, we define the
following set of pairs of colours: $P_{ij}=\\{(c_{1},c_{2}):c_{1}\in
C_{i},c_{2}\in C_{j}\\}$. Note that $|P_{ij}|=\ell^{2}$. Now we define an edge
labelling $\tau^{\prime}$ on $G^{\prime}$ as follows. For each edge $e\in G$
such that $\tau(e)=(i,j)$, assign a unique pair from $P_{ij}$ to each of the
corresponding $\ell^{2}$ parallel edges in $G^{\prime}$.

Now we show that $\tau^{\prime}$ does not permit a proper conflict colouring
on $G^{\prime}$. Suppose to the contrary that $\tau^{\prime}$ does permit a
proper conflict colouring, say $\sigma^{\prime}$. We define a vertex colouring
on $G$ as follows. For each $v\in G$, $\sigma^{\prime}(v)$ is contained
uniquely in some partition $C_{i}$, so we let $\sigma(v)=i$. So for any edge
$e=uv\in G$ with $\tau(e)=(i,j)$, it can not be the case that $\sigma(u)=i$
while $\sigma(v)=j$ simultaneously since it is not possible for
$\sigma^{\prime}(u)$ to be contained in $C_{i}$ while $\sigma^{\prime}(v)$ is
contained in $C_{j}$ simultaneously (using the fact that $\sigma^{\prime}$ is
a proper conflict colouring). This means $\tau$ permits a proper conflict
colouring of $G$, contrary to assumption.

Note that the maximum degree of $G^{\prime}$ is
$\Delta^{\prime}=\Delta\times\ell^{\prime}=\Delta\times\ell^{2}=\Delta^{2}/\ln\Delta$.
Using this fact, let us compute $\ell^{\prime}$ as a function of
$\Delta^{\prime}$. We have:

$\displaystyle\sqrt{\frac{\Delta^{\prime}}{\ln\Delta^{\prime}}}=\sqrt{\frac{\Delta^{2}}{\ln\Delta\ln\Delta^{\prime}}}$
(1)

Note that $\ln\Delta^{\prime}=2\ln\Delta-\ln\ln\Delta=(2-o(1))\ln\Delta$. So
continuing (1) we get:

$\displaystyle\sqrt{\frac{\Delta^{2}}{(2-o(1))\ln^{2}\Delta}}=\frac{1}{\sqrt{2}-o(1)}\frac{\Delta}{\ln\Delta}=\frac{1}{\sqrt{2}-o(1)}\ell^{\prime}.$

So after rearranging terms we have
$\ell^{\prime}=(\sqrt{2}-o(1))\sqrt{\Delta^{\prime}/\ln\Delta^{\prime}}$.

Now let us examine the relationship between the new conflict degree and the
previous. By construction, each edge in $G$ is replaced by $\ell^{2}$ parallel
edges, and each colour conflicting with say $k$ colours in $G$ will be
replaced by a colour conflicting with $k\times\ell$ colours in $G^{\prime}$.
I.e. we have $D(\tau^{\prime})=D(\tau)\times\ell=\sqrt{\ell^{\prime}}$.

Let us take a moment to realize what was just accomplished. We started with an
uncolourable graph and obtained another uncolourable graph, increasing the
coefficient on our list sizes by approximately $\sqrt{2}$, but this came at
the cost of increasing the conflict degree to the square root of the new list
size.

In fact, the same construction can be applied several times. Let
$\Delta_{i},\ell_{i},\tau_{i}$ be the maximum degree, list size, and edge
labelling on the resulting graph after the $i^{th}$ application. Initially we
have:

$\displaystyle\ell_{0}$ $\displaystyle=\ell,$ $\displaystyle\Delta_{0}$
$\displaystyle=\Delta,$ $\displaystyle D(\tau_{0})$ $\displaystyle=D(\tau).$

And by construction we have the following recurrences for $i>0$:

$\displaystyle\ell_{i}$ $\displaystyle=\ell_{i-1}^{2},$
$\displaystyle\Delta_{i}$ $\displaystyle=\Delta_{i-1}\times\ell_{i-1}^{2},$
$\displaystyle D(\tau_{i})$ $\displaystyle=D(\tau_{i-1})\times\ell_{i-1}.$

From these recurrences we have $D(\tau_{i})=\ell_{i}^{1-2^{-i}}$ which the
reader can easily verify by reasoning inductively. Also, the same analysis as
in (1) reveals that
$\ell_{i}=(\sqrt{2}-o(1))^{i}\sqrt{\Delta_{i}/\ln\Delta_{i}}$. So after
repeating 4 times, we get an uncolourable graph with maximum degree $\Delta$,
lists of size $\ell>(2\sqrt{2}+o(1))\sqrt{\Delta/\ln\Delta}$, and an edge
labelling with conflict degree $\ell^{15/16}$.

More generally, for any constant $\alpha\geq 1$ we have to repeat the
construction precisely $\lfloor\log_{\sqrt{2}}\alpha\rfloor+1$ times to obtain
an uncolourable graph with maximum degree $\Delta$ and lists of size at least
$\alpha\sqrt{\Delta/\ln\Delta}$. So the function $f$ from Fact 1.4 is given
by:

$f(\alpha)=1-2^{-\lfloor\log_{\sqrt{2}}\alpha\rfloor-1}.$

##  2 Probabilistic Tools

Here we describe three probabilistic tools which will be useful in proving our
main theorem. The first is the Lovász Local Lemma which is used several times
in the proof. There are several versions of the lemma, the version we present
here is not the most powerful but nevertheless it is sufficient for our
purposes. The original proof can be found in [8].

######  The Lovász Local Lemma.

Consider a set $\mathcal{E}$ of “bad” events in a probability space, such that
for each $A\in\mathcal{E}$:

  1. a)

$\mathbf{Pr}(A)\leq p<1$, and

  2. b)

$A$ is mutually independent of a set of all but at most $d$ of the other
events.

If $4pd\leq 1$ then with positive probability, none of the events in
$\mathcal{E}$ occur.

We use two concentration bounds, the first of which is known as the Chernoff
Bound. The original statement can be found in [2], we use the version which
can be found in chapter 5 of [23].

######  The Chernoff Bound.

For any $t\geq 0$:

$\mathbf{Pr}(|BIN(n,p)-np|>t)\leq
2e^{-((1+\frac{t}{np})\ln(1+\frac{t}{np})-\frac{t}{np})np}$

Our second concentration bound is Talagrand’s Inequality. The original
statement can be found in [30] but once again we use the weaker version which
appears in [24].

######  Talagrand’s Inequality.

Let $X$ be a non-negative random variable determined by the independent trials
$T_{1},T_{2},\dots,T_{n}$. Suppose that for every set of possible outcomes of
the trials, we have:

  1. a)

changing the outcome of any one trial can affect $X$ by at most $q$, and

  2. b)

for each $s>0$, if $X\geq s$, then there is a set of at most $rs$ trials whose
outcomes certify that $X\geq s$ (we make this precise below).

Then for any $t\geq 0$, we have

$\mathbf{Pr}(|X-\mathbf{E}(X)|>t+20q\sqrt{r\mathbf{E}(X)}+64q^{2}r)\leq
4e^{-\frac{t^{2}}{8q^{2}r(\mathbf{E}(X)+t)}}$

Let us be more precise with condition ($b$) above. Suppose there is a set
$I\subseteq[n]$, and outcomes $\\{t_{i}:i\in I\\}$ such that $X\geq s$
whenever $T_{i}=t_{i}$ for each $i\in I$. We say that the set of outcomes
$\\{t_{i}:i\in I\\}$ for trials $\\{T_{i}:i\in I\\}$ certify that $X\geq s$.

##  3 Proof of Main Theorem

Fix $\epsilon>0$. Let $G=(V,E)$ be a multigraph with no cycles of length 3 or
4 and maximum degree $\Delta$. Let $\tau:E\to\mathbb{N}\times\mathbb{N}$ be an
edge labelling on $G$ with
$D(\tau)\leq\Delta^{\frac{1}{4}\epsilon^{2}/(\epsilon+5)^{2}}$. Instead of
specifying a value for $\Delta_{0}$, throughout the proof we will use the fact
that $\Delta$ is a sufficiently large constant.

A brief comment on terminology and notation.

For convenience, if $u$ and $v$ are neighbouring vertices we define the set
$\mathcal{T}(u,v)$ as the set of all labels between $u$ and $v$. That is,
$\mathcal{T}(u,v)=\\{\tau(e):e\textit{ is an edge between u and v}\\}$. By
convention, all pairs of colours in $\mathcal{T}(u,v)$ are ordered so that if
$(c,c^{\prime})\in\mathcal{T}(u,v)$, then $c$ corresponds to the colour
disallowed for $u$ while $c^{\prime}$ corresponds to the colour disallowed for
$v$. We write $\mathcal{T}(v,u)$ to indicate that the pairs are ordered the
opposite way.

Also recall that each label on an edge $e$ constrains the colours assigned to
the endpoints of $e$. For this reason it is useful to think of a label on an
edge as a constraint, and so throughout the proof we use the terms “label” and
“constraint” interchangeably. We also speak of the endpoints $u,v$ of a
constraint $(c,c^{\prime})$, and by this we simply mean that
$(c,c^{\prime})\in\mathcal{T}(u,v)$. Similarly for neighbouring vertices $u,v$
we write that $u$ and $v$ are constrained by $(c,c^{\prime})$ to mean that
$(c,c^{\prime})\in\mathcal{T}(u,v)$. This terminology will simplify our
discussion significantly.

Consider the following semi-random procedure for colouring $G$. As mentioned,
during the procedure we maintain a list $L(v)$ for each vertex $v$, which
represents the set of colours available to $v$.

Wasteful Colouring Procedure ($i^{th}$ iteration)

  1. 1.

Truncate the lists so they all have size $L_{i-1}$ (to be defined later)

  2. 2.

For each uncoloured vertex $v$, activate $v$ with probability
$\frac{K}{\ln\Delta}$ ($K$ is a constant which will be defined precisely
later).

  3. 3.

For each activated vertex $v$, assign $v$ a colour uniformly at random from
$L(v)$.

  4. 4.

For each activated vertex $v$: If $v$ is assigned the colour $c$, for each
uncoloured neighbour $u$ of $v$ and each colour $c^{\prime}$ such that
$(c,c^{\prime})\in\mathcal{T}(v,u)$, remove $c^{\prime}$ from $L(u)$.

  5. 5.

For each pair of adjacent vertices $v$ and $u$ which receive colours $c$ and
$c^{\prime}$ respectively, uncolour both $v$ and $u$ if
$(c,c^{\prime})\in\mathcal{T}(v,u)$.

  6. 6.

Conduct an “equalizing” coin flip (to be defined later) for each vertex $v$
and colour $c\in L(v)$, removing $c$ from $L(v)$ if it loses the coin flip.

Now consider the following parameters which will allow us to analyze the
procedure. Each parameter refers to the value at the end of iteration $i$, for
$i>0$. For $i=0$, each parameter refers to the value before beginning the
procedure.

$\displaystyle\begin{aligned} L_{i}(v)&=v^{\prime}\text{s list of colours}\\\
\ell_{i}(v)&=|L_{i}(v)|\\\
\hfil\displaystyle\begin{split}N_{i}(v,u,c)&=\begin{cases}\\{(c,c^{\prime})\in\mathcal{T}(v,u):c^{\prime}\in
L_{i}(u)\\}&\text{if }u\text{ is an uncoloured neighbour of }v\\\
\emptyset&\text{otherwise}\end{cases}\end{split}\\\
N_{i}(v,c)&=\bigsqcup_{u\in N(v)}N_{i}(v,u,c)\\\
t_{i}(v,u,c)&=|N_{i}(v,u,c)|\\\ t_{i}(v,c)&=|N_{i}(v,c)|=\sum_{u\in
N(v)}t_{i}(v,u,c)\end{aligned}$

In the definition of $N_{i}(v,c)$, the symbol $\bigsqcup$ denotes the disjoint
union. Note that $v$ could have the constraint (red, red) between two
different neighbours. But these two constraints are different because they
have different endpoints, so we take the disjoint union to include both of
them.

######  Observation 1.

For each $v$, neighbour $u\in N(v)$, and $c\in L(v)$, we initially have
$t_{0}(v,u,c)\leq D(\tau)$. Since this parameter can only decrease, we have
$t_{i}(v,u,c)\leq D(\tau)$ for every relevant $i$. Because of our restriction
on the conflict degree this also means
$t_{i}(v,u,c)\leq\Delta^{\frac{1}{4}\epsilon^{2}/(\epsilon+5)^{2}}$.

Throughout the proof, many of our results rely on the list sizes being
sufficiently large. More specifically, our lemma statements will specify that
$L_{i}\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$ (as we will see,
this requirement is fulfilled by Lemma 3.13).

With list sizes this large, we have:

$\displaystyle t_{i}(v,u,c)\leq L_{i}^{1/2-\beta},\text{ where
}\beta=\frac{1}{2}-\frac{1}{2}\bigg{(}\frac{\epsilon+4}{\epsilon+5}\bigg{)}^{2}.$
(2)

We will also be concerned with the value $T_{i}$ (to be defined later), which
we also require to be sufficiently large. If
$T_{i}\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$, then again we
have:

$\displaystyle t_{i}(v,u,c)\leq T_{i}^{1/2-\beta},$ (3)

for the same value of $\beta$. The reader should not dwell on the precise
value of $\beta$, the only important detail is that $\beta$ is in the interval
$(0,\frac{1}{2})$.

For our procedure to work we require that certain parameters stay reasonably
close to their expected values (i.e. we require our parameters to be strongly
concentrated). It turns out that the parameter $t_{i}(v,c)$ is not strongly
concentrated as it can be affected by a large amount when $c$ is assigned to
$v$ in iteration $i$ (in particular it drops to 0). In fact, assigning colours
other than $c$ to $v$ could have the same effect. For this reason, the
following closely related parameters will be considered at the end of
iteration $i+1$ (the purpose of these parameters is to simply ignore the
effect of assigning a colour to $v$):

$\displaystyle\begin{aligned}
\hfil\displaystyle\begin{split}t^{\prime}_{i+1}(v,u,c)=&\text{ }0\text{, if
}u\text{ retained a colour during iteration }i+1,\\\ &\text{ otherwise the
number of labels }(c,c^{\prime})\text{ counted by }t_{i}(v,u,c)\text{ such
that in iteration }i+1\text{:}\\\ &\qquad\bullet\quad c^{\prime}\text{ was not
removed from }u\text{'s list because of a conflict with a neighbour }w\neq
v\\\ &\qquad\bullet\quad c^{\prime}\text{ was not removed from }u\text{'s list
because of an equalizing coin flip}\end{split}\\\
t^{\prime}_{i+1}(v,c)=&\sum_{u\in N(v)}t^{\prime}_{i+1}(v,u,c)\end{aligned}$

Now it turns out that the parameter $t^{\prime}_{i+1}(v,c)$ is indeed
concentrated, as we will show in Lemma 3.10. Notice that $t_{i+1}(v,c)\leq
t^{\prime}_{i+1}(v,c)$. As we will see, we only need an upper bound on
$t_{i+1}(v,c)$. So as long as we have a sufficiently strong bound on
$t^{\prime}_{i+1}(v,c)$ we should be able to achieve this.

Now, our goal is to perform several iterations of the procedure so that
eventually much of the graph is coloured, and colouring the remaining graph
becomes easy. Intuitively, by the end of the procedure we would like that for
each vertex $v$, the parameter $\ell_{i}(v)$ be large while for each colour
$c$ in $v$’s list, $t_{i}(v,c)$ should be quite small. This way, we have
several options when choosing a colour for $v$, and each is unlikely to
conflict with any neighbour. This will improve our chances of finding a proper
conflict colouring. The next lemma makes this precise.

This result was introduced by Reed [28], and has since been seen in modified
form in various places (see Proposition 2.1 of [29], Lemma 3.1 of [26]).
Likewise, we present a modified version which is suited for our purposes; the
proof is nearly identical to the original.

######  Lemma 3.1.

Let $G=(V,E)$ be a multigraph with edge labelling
$\tau:E\to\mathbb{N}\times\mathbb{N}$ and a list of colours $L(v)$ for each
vertex $v\in G$. Suppose for each vertex $v\in G$, $|L(v)|\geq\ell$. Also
suppose that for each vertex $v$, and each colour $c\in L(v)$, there are at
most $\ell/8$ edges $e=vu$ such that $\tau(e)=(c,c^{\prime})$ where
$c^{\prime}\in L(u)$. Then there is a proper conflict colouring of $G$ from
these lists.

###### Proof.

Arbitrarily truncate the lists to be exactly of size $\ell$, and assign each
vertex a colour uniformly at random from its list. Let $\sigma$ be the
resulting vertex colouring on $G$.

For an edge $e$ with endpoints $v$ and $u$, let $\tau(e)=(c,c^{\prime})$. We
consider the event $A_{e}$ where $\sigma(v)=c$ and $\sigma(u)=c^{\prime}$. Let
$\mathcal{E}$ be the set of all such events. If $c\notin L(v)$ or
$c^{\prime}\notin L(u)$, then $\mathbf{Pr}(A_{e})=0$, and this is mutually
independent of any set of events. Otherwise, $\mathbf{Pr}(A_{e})=1/\ell^{2}$.

Consider the following sets of events:

$D_{v}=\\{A_{f}:f=vv^{\prime}\neq e,(c_{1},c_{2})=\tau(f)\textit{ and
}c_{2}\in L(v^{\prime})\\}$ $D_{u}=\\{A_{f}:f=uu^{\prime}\neq
e,(c_{1},c_{2})=\tau(f)\textit{ and }c_{2}\in L(u^{\prime})\\}$

(note that these sets could contain events indexed by edges parallel to $e$).
Observe that $A_{e}$ is mutually independent of all events in
$\mathcal{E}-D_{v}-D_{u}$ by the Mutual Independence Principle (see chapter 4
of [23]).

By assumption, for each colour $c_{1}\in L(v)$, there could be at most
$\ell/8$ edges $e=vv^{\prime}$ such that $\tau(e)=(c_{1},c_{2})$ and $c_{2}\in
L(v^{\prime})$. Hence, summing over all colours in $v$’s list gives a bound of
$\ell^{2}/8$ on the size of $D_{v}$, and similarly for $D_{u}$. So each bad
event occurs with probability at most $p=1/\ell^{2}$ and is mutually
independent of all but at most $d=\ell^{2}/4$ other events. Therefore,
$4pd\leq 4(1/\ell^{2})(\ell^{2}/4)\leq 1$. So we can apply the Lovász Local
Lemma to obtain a colouring $\sigma$ such that there is no edge $e$ with
endpoints $v$ and $u$ and $\tau(e)=(c,c^{\prime})$ where $\sigma(v)=c$ and
$\sigma(u)=c^{\prime}$, i.e. $\sigma$ is a proper conflict colouring. ∎

The previous lemma permits us to focus on the parameters $\ell_{i}(v)$ and
$t_{i}(v,c)$, but instead of keeping track of the values $\ell_{i}(v)$ and
$t_{i}(v,c)$ for each $v,c$, we focus on their extreme values. We recursively
define appropriate $L_{i}$ and $T_{i}$ which we would like to serve as a lower
bound for $\ell_{i}(v)$ and an upper bound for $t_{i}(v,c)$, respectively.
Moreover, the value $t_{i}(v,u,c)$ will also be of interest to us, as if this
value is too large then $\ell_{i}(v)$ and $t_{i}(v,c)$ will not be
sufficiently concentrated.

More precisely, we will show that with positive probability the following
property holds at the end of iteration $i$:

Property P(i): For each uncoloured vertex $v$, uncoloured neighbour $u$ of
$v$, and each colour $c\in L_{i}(v)$,

$\ell_{i}(v)\geq L_{i}$

$t_{i}(v,c)\leq T_{i}$

So if for some iteration, $i$, property $P(i)$ holds and
$T_{i}\leq\frac{1}{8}L_{i}$ then the colouring can be completed by Lemma 3.1.

As mentioned in step 6 of the procedure, if $c$ is in $v$’s list near the end
of an iteration (just before step 6), we remove $c$ with some probability. We
do this in such a way that forces the probability of a vertex retaining a
given colour during the entirety of the iteration to be the same across
vertices and colours. Now we define $\mathrm{Keep}_{i}(v,c)$ to be the
probability that $c$ stays in $v$’s list by the beginning of step 6 of
iteration $i+1$, conditional on the event that $c$ is in $v$’s list after step
1 of iteration $i+1$. For a neighbour $u$ of $v$, there are $t_{i}(v,u,c)$
colours in $u$’s list which would cause $c$ to be removed from $v$’s list if
any one of them is assigned to $u$. Since the size of $u$’s list is precisely
$L_{i}$ by step 3 in the procedure, and $u$ is activated with probability
$K/\ln\Delta$, we arrive at the following expression:

$\displaystyle\mathrm{Keep}_{i}(v,c)=\prod_{u\in
N(v)}\Big{(}1-\frac{K}{\ln\Delta}\times\frac{t_{i}(v,u,c)}{L_{i}}\Big{)}$ (4)

Now we define the following value which we claim is a lower bound on
$\mathrm{Keep}_{i}(v,c)$ and will be easier to work with.

$\displaystyle\mathrm{Keep}_{i}:=\Big{(}1-\frac{K(1+\epsilon
e^{-\epsilon}/30)}{L_{i}\ln\Delta}\Big{)}^{T_{i}}$ (5)

######  Claim 3.2.

If $P(i)$ holds, $T_{i}\geq\frac{1}{8}L_{i}$, and if
$T_{i},L_{i}\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$, then
$\mathrm{Keep}_{i}(v,c)\geq\mathrm{Keep}_{i}$ for $\Delta$ sufficiently large.

###### Proof.

It suffices to show the following for $\Delta$ sufficiently large:

$\displaystyle\Big{(}1-\frac{Kt_{i}(v,u,c)}{L_{i}\ln\Delta}\Big{)}\geq\Big{(}1-\frac{K(1+\epsilon
e^{-\epsilon}/30)}{L_{i}\ln\Delta}\Big{)}^{t_{i}(v,u,c)}$ (6)

As then we have:

$\displaystyle\mathrm{Keep}_{i}(v,c)$ $\displaystyle=\prod_{u\in
N(v)}\Big{(}1-\frac{K}{\ln\Delta}\times\frac{t_{i}(v,u,c)}{L_{i}}\Big{)}$ by
(4) $\displaystyle\geq\prod_{u\in N(v)}\Big{(}1-\frac{K(1+\epsilon
e^{-\epsilon}/30)}{L_{i}\ln\Delta}\Big{)}^{t_{i}(v,u,c)}$ by (6)
$\displaystyle=\Big{(}1-\frac{K(1+\epsilon
e^{-\epsilon}/30)}{L_{i}\ln\Delta}\Big{)}^{\sum_{u\in N(v)}t_{i}(v,u,c)}$
$\displaystyle=\Big{(}1-\frac{K(1+\epsilon
e^{-\epsilon}/30)}{L_{i}\ln\Delta}\Big{)}^{t_{i}(v,c)}$
$\displaystyle\geq\Big{(}1-\frac{K(1+\epsilon
e^{-\epsilon}/30)}{L_{i}\ln\Delta}\Big{)}^{T_{i}}$ by property $P(i)$
$\displaystyle=\mathrm{Keep}_{i}$

We can show (6) by considering two well-known facts:

$\displaystyle e^{-x}$ $\displaystyle\leq 1-x+\frac{x^{2}}{2}$ for all non-
negative $x$ (7) $\displaystyle e^{-x}$ $\displaystyle\geq 1-x$ for all $x$
(8)

This comes from the fact that for Taylor polynomials of $e^{-x}$ with even
degree, the remainder is non-positive for all positive $x$. Similarly, the
Taylor polynomials of $e^{-x}$ with odd degree have a remainder that is non-
negative for all $x$. Now consider

$x=\frac{K(1+\epsilon e^{-\epsilon}/30)t_{i}(v,u,c)}{L_{i}\ln\Delta}$

and note that by (2) and since
$L_{i}\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$ by assumption,
$x$ tends to $0$ as $\Delta$ tends to infinity. So we have for $\Delta$
sufficiently large:

$\displaystyle\exp\bigg{(}-\frac{K(1+\epsilon
e^{-\epsilon}/30)t_{i}(v,u,c)}{L_{i}\ln\Delta}\bigg{)}$ $\displaystyle\leq
1-x+\frac{x^{2}}{2}$ by (7) $\displaystyle\leq 1-\frac{x}{1+\epsilon
e^{-\epsilon}/30}$ since $x$ dominates over $\frac{x^{2}}{2}$ for large
$\Delta$ $\displaystyle=1-\frac{Kt_{i}(v,u,c)}{L_{i}\ln\Delta}$ (9)

On the other hand,

$\displaystyle\exp\bigg{(}-\frac{K(1+\epsilon
e^{-\epsilon}/30)t_{i}(v,u,c)}{L_{i}\ln\Delta}\bigg{)}$
$\displaystyle\geq\exp\bigg{(}-\frac{K(1+\epsilon
e^{-\epsilon}/30)}{L_{i}\ln\Delta}\bigg{)}^{t_{i}(v,u,c)}$
$\displaystyle\geq\bigg{(}1-\frac{K(1+\epsilon
e^{-\epsilon}/30)}{L_{i}\ln\Delta}\bigg{)}^{t_{i}(v,u,c)}$ by (8)

which proves the claim. ∎

######  Remark 3.3.

We remark that Claim 3.2 remains true even if we replace the expression
$\epsilon e^{-\epsilon}$ by any positive constant. Although this expression
may seem bizarre, we choose it because we require an expression that is quite
small for all values of $\epsilon$, even values which are very large.

Equalizing coin flips.

We use Claim 3.2 to define our equalizing coin flips. Define the following
probability:

$\mathrm{Eq}_{i}(v,c):=1-\mathrm{Keep}_{i}/\mathrm{Keep}_{i}(v,c).$

We perform the equalizing coin flip described in step 6 of the procedure by
removing any colour $c$ from $v$’s list with probability
$\mathrm{Eq}_{i}(v,c)$. This way, we ensure that the probability of $c$
remaining in $v$’s list by the end of iteration $i+1$ is precisely
$(1-\mathrm{Eq}_{i}(v,c))\times\mathrm{Keep}_{i}(v,c)=\mathrm{Keep}_{i}$.

Now initially we have that for each $v$,
$\ell_{0}(v)=(2\sqrt{2}+\epsilon)\sqrt{\Delta/\ln\Delta}$. However, for a
colour $c$ in $v$’s list, $t_{0}(v,c)$ could be as high as $\Delta$. Recall
that we would like $t_{0}(v,c)$ to be quite small, and it turns out that this
is not good enough for our purposes, so we remove all colours $c$ from $v$’s
list for which $t_{0}(v,c)$ exceeds some threshold (a similar technique has
been used in [26]). The following claim makes this precise.

######  Claim 3.4.

For each vertex $v$, the number of colours $c$ for which
$t_{0}(v,c)>\frac{1}{\sqrt{2}+\epsilon/2}\sqrt{\Delta\ln\Delta}$ is at most
$(\sqrt{2}+\epsilon/2)\sqrt{\Delta/\ln\Delta}$.

###### Proof.

Suppose to the contrary that strictly more than
$(\sqrt{2}+\epsilon/2)\sqrt{\Delta/\ln\Delta}$ colours $c$ achieve a value of
$t_{0}(v,c)>\frac{1}{\sqrt{2}+\epsilon/2}\sqrt{\Delta\ln\Delta}$. Then the
number of edges incident to $v$ is is strictly more than
$(\sqrt{2}+\epsilon/2)\sqrt{\Delta/\ln\Delta}\times\frac{1}{\sqrt{2}+\epsilon/2}\sqrt{\Delta\ln\Delta}=\Delta$,
a contradiction. ∎

The previous claim allows us to modify our graph by removing “bad” colours
before starting the procedure. In the worst case we are left with at least
half of the colours we originally started with.

######  Modification 1.

For each vertex $v$ and colour $c$ in $v$’s list, remove $c$ from $v$’s list
if $t_{0}(v,c)>\frac{1}{\sqrt{2}+\epsilon/2}\sqrt{\Delta\ln\Delta}$.

######  Remark 3.5.

Eliminating half of $v$’s colours effectively means that we must start with
twice the number of colours we really need. In other words, if such “bad”
colours posed no problem, and hence there was no need to remove them, we could
get away with a leading constant of $\sqrt{2}+\epsilon$ in Theorem 1.1 and
Theorem 1.5. The reader may wonder if imposing a larger threshold in
Modification 1 (thus removing less colours) gives a smaller leading constant.
Unfortunately, there is an upper limit to what threshold can be used as we
must ensure $t_{0}(v,c)$ is not too large. Conversely, if the threshold is too
relaxed we end up removing too many colours. It turns out that the threshold
proposed is optimal in the sense that it strikes the right balance between
these two extremes.

Finally, we are ready to give recursive definitions for $L_{i}$ and $T_{i}$.
Keep in mind that in the following definitions, $\beta$ is the constant
specified by (2). Initially, by Modification 1 and Claim 3.4 we have the
following:

$L_{0}=(\sqrt{2}+\epsilon/2)\sqrt{\Delta/\ln\Delta},\ \ \ \ \
T_{0}=\frac{1}{\sqrt{2}+\epsilon/2}\sqrt{\Delta\ln\Delta},$

and we recursively define:

$\displaystyle\begin{aligned}
L_{i+1}&=L_{i}\times\mathrm{Keep}_{i}-L_{i}^{1-\beta/2}\\\ \\\
T_{i+1}&=T_{i}\Big{(}1-\frac{K}{\ln\Delta}\mathrm{Keep}_{i}\Big{)}\times\mathrm{Keep}_{i}+T_{i}^{1-\beta/2}\end{aligned}$

We also give recursive definitions for $L^{\prime}_{i},T^{\prime}_{i}$, which
are closely related to $L_{i}$ and $T_{i}$. Initially we have the following:

$L^{\prime}_{0}=L_{0},\ \ \ \ \ T^{\prime}_{0}=T_{0},$

and we recursively define:

$\displaystyle\begin{aligned}
L^{\prime}_{i+1}&=L^{\prime}_{i}\times\mathrm{Keep}_{i}\\\ \\\
T^{\prime}_{i+1}&=T^{\prime}_{i}\Big{(}1-\frac{K}{\ln\Delta}\mathrm{Keep}_{i}\Big{)}\times\mathrm{Keep}_{i}\end{aligned}$

$L^{\prime}_{i}$ and $T^{\prime}_{i}$ are much simpler to analyze, and we can
show that they do not stray too far from values $L_{i}$ and $T_{i}$,
respectively (see Lemma 3.12). This allows us to focus our attention on
analyzing these simpler equations. Now we move on to proving several lemmas,
which will allow us to complete the proof of the main theorem.

Throughout the proof, we use the fact that the ratio $T_{i}/L_{i}$ is
decreasing. We prove this in the following lemma.

######  Lemma 3.6.

If for all
$j<i,L_{j},T_{j}\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$ and
$T_{j}\geq\frac{1}{8}L_{j}$ then $T_{i}/L_{i}<T_{i-1}/L_{i-1}$

###### Proof.

The proof is by induction. We assume inductively that:

$T_{i}/L_{i}<T_{i-1}/L_{i-1}<\cdots<T_{0}/L_{0}<\ln\Delta$

and we shall abbreviate “inductive hypothesis” by $IH$. Note that by $IH$, we
have the following useful fact:

$\displaystyle\mathrm{Keep}_{i}=\Big{(}1-\frac{K(1+\epsilon
e^{-\epsilon}/30)}{L_{i}\ln\Delta}\Big{)}^{T_{i}}\geq e^{-\frac{K(1+\epsilon
e^{-\epsilon}/20)T_{i}}{L_{i}\ln\Delta}}\geq e^{-\frac{K(1+\epsilon
e^{-\epsilon}/20)T_{0}}{L_{0}\ln\Delta}}=\Omega(1).$ (10)

Now we consider $i+1$. By definition (3) we have:

$L_{i+1}=L_{i}\times\Big{(}\mathrm{Keep}_{i}-L_{i}^{-\beta/2}\Big{)}.$

Also, we have:

$\displaystyle T_{i+1}$
$\displaystyle=T_{i}\times\mathrm{Keep}_{i}-T_{i}\times\frac{K}{\ln\Delta}\mathrm{Keep}^{2}_{i}+T_{i}^{1-\beta/2}$
by definition (3) $\displaystyle\leq
T_{i}\times\mathrm{Keep}_{i}-\mathrm{Keep}_{i}^{2}\times
T_{i}^{1-\beta/8}+T_{i}^{1-\beta/2}$ since
$T_{i}\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$
$\displaystyle\leq T_{i}\times\mathrm{Keep}_{i}-T_{i}^{1-\beta/4}$ since
$\mathrm{Keep}_{i}=\Omega(1)$ by (10)
$\displaystyle=T_{i}\times\mathrm{Keep}_{i}-T_{i}^{1-\beta/2}\times
T_{i}^{\beta/4}$ $\displaystyle\leq
T_{i}\times\mathrm{Keep}_{i}-T_{i}^{1-\beta/2}\times(T_{i}/L_{i})^{\beta/2}$
since $T_{i}/L_{i}<\ln\Delta$ by $IH$
$\displaystyle=T_{i}\times\Big{(}\mathrm{Keep}_{i}-L_{i}^{-\beta/2}\Big{)}$

so $T_{i+1}/L_{i+1}<T_{i}/L_{i}$. ∎

Notice that since $T_{0}/L_{0}<\ln\Delta$ initially, the previous lemma
implies $T_{i}/L_{i}<\ln\Delta$ for every relevant $i$. It will also be useful
to have upper and lower bounds on $\mathrm{Keep}_{i}$, which we will see in
the next lemma.

######  Lemma 3.7.

If for all $j\leq
i,L_{j},T_{j}\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$ and
$T_{j}\geq\frac{1}{8}L_{j}$ then $e^{-\frac{K(1+\epsilon
e^{-\epsilon}/20)}{(\sqrt{2}+\epsilon/2)^{2}}}\leq\mathrm{Keep}_{i}\leq
1-{\color[rgb]{0,0,0}\frac{K}{10\ln\Delta}}$

###### Proof.

For the lower bound, we make use of Lemma 3.6 as well as the same argument of
(10) to get:

$\mathrm{Keep}_{i}=\Big{(}1-\frac{K(1+\epsilon
e^{-\epsilon}/30)}{L_{i}\ln\Delta}\Big{)}^{T_{i}}\geq e^{-\frac{K(1+\epsilon
e^{-\epsilon}/20)T_{i}}{L_{i}\ln\Delta}}\geq e^{-\frac{K(1+\epsilon
e^{-\epsilon}/20)T_{0}}{L_{0}\ln\Delta}}=e^{-\frac{K(1+\epsilon
e^{-\epsilon}/20)}{(\sqrt{2}+\epsilon/2)^{2}}}.$

For the upper bound, we have:

$\mathrm{Keep}_{i}=\Big{(}1-\frac{K(1+\epsilon
e^{-\epsilon}/30)}{L_{i}\ln\Delta}\Big{)}^{T_{i}}\leq e^{-\frac{K(1+\epsilon
e^{-\epsilon}/30)T_{i}}{L_{i}\ln\Delta}}\leq e^{-\frac{K(1+\epsilon
e^{-\epsilon}/30)}{8\ln\Delta}}\leq
1-{\color[rgb]{0,0,0}\frac{K}{10\ln\Delta}}$

using the assumption that $T_{i}\geq\frac{1}{8}L_{i}$ ∎

######  Remark 3.8.

We remark that by choice of $K$, the lower bound given by Lemma 3.7 is at
least $\frac{1}{2}$. We will see this in Lemma 3.13 when we precisely define
$K$ (see definition (28)).

The next step is to compute the expected values of our parameters, which we
will see in the following lemma.

######  Lemma 3.9.

If $P(i)$ holds, $T_{i}\geq\frac{1}{8}L_{i}$, and if
$T_{i},L_{i}\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$, then for
every uncoloured vertex $v$ and colour $c\in L_{i}(v)$

  1. a)

$\mathbf{E}(\ell_{i+1}(v))=L_{i}\times\mathrm{Keep}_{i}$;

  2. b)

$\mathbf{E}(t^{\prime}_{i+1}(v,c))\leq
t_{i}(v,c)(1-\frac{K}{\ln\Delta}\mathrm{Keep}_{i})\times\mathrm{Keep}_{i}+T_{i}^{3/4}$.

###### Proof.

  1. $a)$

By property $P(i)$, $\ell_{i}(v)\geq L_{i}$. So the truncation step in the
procedure is justified, and the size of $v$’s list will be precisely $L_{i}$
just after the first step of iteration $i+1$. Because of our equalizing coin
flip step in the procedure, the probability that a colour $c$ in $v$’s list
remains in $v$’s list by the end of the iteration is precisely
$\mathrm{Keep}_{i}$, and so the rest follows by linearity of expectation.

  2. $b)$

Consider any constraint $(c,c^{\prime})\in N_{i}(v,c)$ with endpoints $v,u$
where $u$ is not coloured. By linearity of expectation, it suffices to give a
bound on the probability of $u$ not retaining a colour and $c^{\prime}$ not
being lost from $u$’s list because of either:

     * •

an equalizing coin flip, or,

     * •

a conflict with a colour assigned to a neighbour $w\neq v$

during iteration $i+1$. Call this event $A$.

We consider 3 cases:

     * •

when $u$ is not activated

     * •

when $u$ is activated and not assigned $c^{\prime}$

     * •

when $u$ is activated and assigned $c^{\prime}$

and we compute the probability of $A$ occurring, conditional on each case.

Case 1: $u$ is not activated

Call this case $B_{1}$. We are interested in $\mathbf{Pr}(A|B_{1})$. If $u$ is
not activated (and therefore not assigned a colour), this is precisely the
probability that $c^{\prime}$ remains in $u$’s list or is lost due to a
conflict with $v$. By the union bound we get:

$\displaystyle\mathbf{Pr}(A|B_{1})=\mathrm{Keep}_{i}+\frac{K}{\ln\Delta}\frac{t_{i}(u,v,c^{\prime})}{L_{i}}\leq\mathrm{Keep}_{i}+L_{i}^{-1/2}$
(11)

by (2).

Case 2: $u$ is activated and not assigned $c^{\prime}$

Call this case $B_{2}$. We are interested in $\mathbf{Pr}(A|B_{2})$. We
introduce two new events: let $A_{1}$ be the event that $c^{\prime}$ remains
in $L_{i+1}(u)$ or is lost due to a conflict with $v$, and let $A_{2}$ be the
event that for at least one neighbour $w$ of $u$, $w$ is activated and the
colour assigned to $w$ makes $u$ uncoloured. Note that $A=A_{1}\cap A_{2}$, so
our strategy for computing $\mathbf{Pr}(A|B_{2})$ is to compute
$\mathbf{Pr}(A_{1}|B_{2})\times\mathbf{Pr}(A_{2}|A_{1}\cap B_{2})$ instead.
The reader can easily verify that these two expressions are equal by using the
definition of conditional probabilities.
First we consider $\mathbf{Pr}(A_{1}|B_{2})$. Note that conditioning on $u$
being assigned a colour other than $c^{\prime}$ has no effect on the colours
assigned on vertices in $N(u)$. So by the same argument as (11) we have:

$\displaystyle\mathbf{Pr}(A_{1}|B_{2})\leq\mathrm{Keep}_{i}+L_{i}^{-1/2}.$
(12)

Now we consider $\mathbf{Pr}(A_{2}|A_{1}\cap B_{2})$. For $\gamma\in
L_{i}(u)-c^{\prime}$, define $B_{2,\gamma}$ to be the event that $u$ is
activated and assigned $\gamma$. I.e. $B_{2}=\bigcup_{\gamma}B_{2,\gamma}$ is
a union of disjoint events, each equally likely to occur with some
probability, say $p$. Also note that each $B_{2,\gamma}$ is independent from
$A_{1}$. From this we get the following:

$\displaystyle\mathbf{Pr}(A_{2}|A_{1}\cap
B_{2})=\frac{\sum_{\gamma}\mathbf{Pr}(A_{2}\cap A_{1}\cap
B_{2,\gamma})}{(L_{i}-1)p\times\mathbf{Pr}(A_{1})}\leq\frac{\max_{\gamma}\mathbf{Pr}(A_{2}\cap
A_{1}\cap
B_{2,\gamma})}{p\times\mathbf{Pr}(A_{1})}=\max_{\gamma}\mathbf{Pr}(A_{2}|A_{1}\cap
B_{2,\gamma}).$ (13)

I.e. it suffices to achieve a bound on $\mathbf{Pr}(A_{2}|A_{1}\cap
B_{2,\gamma})$. Fix $\gamma\in L_{i}(u)-c^{\prime}$. To achieve our bound, for
a neighbour $w$ of $u$ we define $A_{2,w}$ to be the event that $w$ is
activated and assigned a colour which makes $u$ lose $\gamma$. Then we have
the following:

$\displaystyle\mathbf{Pr}(A_{2}|A_{1}\cap B_{2,\gamma})=\bigg{(}1-\prod_{w\in
N(u)}(1-\mathbf{Pr}(A_{2,w}|A_{1}\cap B_{2,\gamma})\bigg{)}.$ (14)

We consider two subcases. When $w=v$, we have:

$\displaystyle\mathbf{Pr}(A_{2,v}|A_{1}\cap
B_{2,\gamma})=\frac{K}{\ln\Delta}\times\frac{t_{i}(u,v,\gamma)}{L_{i}}.$ (15)

For any other neighbour $w\in N(u)-v$, we should be more careful since a
colour assignment on $w$ could make $u$ lose $c^{\prime}$ thus violating event
$A_{1}$. Since the activations and colour assignments are independent over
different vertices, and since $\gamma\neq c^{\prime}$, we simply have:

$\mathbf{Pr}(A_{2,w}|A_{1}\cap B_{2,\gamma})=\mathbf{Pr}((w\textit{ is
activated and assigned a bad colour for }u,\gamma)|D_{w}),$

where $D_{w}$ is the event that $w$ is not assigned a colour which makes $u$
lose $c^{\prime}$. So we get:

$\displaystyle\mathbf{Pr}((w\textit{ is activated and assigned a bad colour
for }u,\gamma)\cap D_{w})/\mathbf{Pr}(D_{w})$ $\displaystyle\leq\ $
$\displaystyle\mathbf{Pr}(w\textit{ is activated and assigned a bad colour for
}u,\gamma)/\mathbf{Pr}(D_{w})$ $\displaystyle=\ $
$\displaystyle\Bigg{(}\frac{K}{\ln\Delta}\times\frac{t_{i}(u,w,\gamma)}{L_{i}}\Bigg{)}\times\frac{1}{\Big{(}1-\frac{K}{\ln\Delta}\times\frac{t_{i}(u,w,c^{\prime})}{L_{i}}\Big{)}}.$
(16)

Note that by (2), the second factor tends to $1$ from above. This means that
for $\Delta$ sufficiently large, it is at most $(1+\epsilon
e^{-\epsilon}/40)$. So continuing (16) we get:

$\displaystyle\mathbf{Pr}(A_{2,w}|A_{1}\cap B_{2,\gamma})$
$\displaystyle\leq\Bigg{(}\frac{K}{\ln\Delta}\times\frac{t_{i}(u,w,\gamma)}{L_{i}}\Bigg{)}\times\frac{1}{\Big{(}1-\frac{K}{\ln\Delta}\times\frac{t_{i}(u,w,c^{\prime})}{L_{i}}\Big{)}}$
$\displaystyle\leq(1+\epsilon
e^{-\epsilon}/40)\Bigg{(}\frac{K}{\ln\Delta}\times\frac{t_{i}(u,w,\gamma)}{L_{i}}\Bigg{)}.$
(17)

So by (15), (17) and (14) we get:

$\displaystyle\mathbf{Pr}(A_{2}|A_{1}\cap B_{2,\gamma})$ $\displaystyle\leq
1-\bigg{(}1-\frac{Kt_{i}(u,v,\gamma)}{L_{i}\ln\Delta}\bigg{)}\times\prod_{w\in
N(u)-v}\bigg{(}1-(1+\epsilon
e^{-\epsilon}/40)\frac{Kt_{i}(u,w,\gamma)}{L_{i}\ln\Delta}\bigg{)}$
$\displaystyle\leq 1-\prod_{w\in N(u)}\bigg{(}1-\frac{K(1+\epsilon
e^{-\epsilon}/40)t_{i}(u,w,\gamma)}{L_{i}\ln\Delta}\bigg{)}.$

Now using the same argument as in Claim 3.2 we can see that this is at most
$1-\mathrm{Keep}_{i}$. So by (13) we have:

$\displaystyle\mathbf{Pr}(A_{2}|A_{1}\cap B_{2})\leq 1-\mathrm{Keep}_{i}.$
(18)

Finally, by (12) and (18), we have:

$\displaystyle\mathbf{Pr}(A|B_{2})=(\mathrm{Keep}_{i}+L_{i}^{-1/2})(1-\mathrm{Keep}_{i}).$
(19)

Case 3: $u$ is activated and assigned $c^{\prime}$

Call this case $B_{3}$. We are interested in $\mathbf{Pr}(A|B_{3})$. The only
scenario where $u$ remains uncoloured and $c^{\prime}$ is either lost due to a
conflict with $v$ or remains in $L_{i+1}(u)$, is if $c^{\prime}$ is lost due
to a conflict with $v$. This happens with probability

$\displaystyle\mathbf{Pr}(A|B_{3})=\frac{K}{\ln\Delta}\frac{t_{i}(u,v,c^{\prime})}{L_{i}}<L_{i}^{-1/2}$
(20)

by (2).
Therefore, by the law of total probability and (11), (19), (20), we get that
the probability of the event $A$ occurring is:

$\displaystyle\
\mathbf{Pr}\big{(}B_{1}\big{)}\times\mathbf{Pr}\big{(}A|B_{1}\big{)}+\mathbf{Pr}\big{(}B_{2}\big{)}\times\mathbf{Pr}\big{(}A|B_{2}\big{)}+\mathbf{Pr}\big{(}B_{3}\big{)}\times\mathbf{Pr}\big{(}A|B_{3}\big{)}$
$\displaystyle\leq$ $\displaystyle\
\Bigg{(}1-\frac{K}{\ln\Delta}\Bigg{)}\times\Bigg{(}\mathrm{Keep}_{i}+L_{i}^{-1/2}\Bigg{)}+\frac{K}{\ln\Delta}\times\frac{L_{i}-1}{L_{i}}\times\Bigg{(}\mathrm{Keep}_{i}+L_{i}^{-1/2}\Bigg{)}\Bigg{(}1-\mathrm{Keep}_{i}\Bigg{)}+\frac{K}{\ln\Delta}\times\frac{L_{i}^{-1/2}}{L_{i}}$
$\displaystyle\leq$ $\displaystyle\
\Bigg{(}1-\frac{K}{\ln\Delta}\Bigg{)}\times\mathrm{Keep}_{i}+\frac{K}{\ln\Delta}\times\mathrm{Keep}_{i}\times\Bigg{(}1-\mathrm{Keep}_{i}\Bigg{)}+3L_{i}^{-1/2}$
$\displaystyle=$ $\displaystyle\
\mathrm{Keep}_{i}-\frac{K}{\ln\Delta}\mathrm{Keep}_{i}+\frac{K}{\ln\Delta}\mathrm{Keep}_{i}-\frac{K}{\ln\Delta}\mathrm{Keep}^{2}_{i}+3L_{i}^{-1/2}$
$\displaystyle\leq$ $\displaystyle\
\bigg{(}1-\frac{K}{\ln\Delta}\times\mathrm{Keep}_{i}\Bigg{)}\times\mathrm{Keep}_{i}+L_{i}^{-1/3}.$

for $\Delta$ sufficiently large.

Now by linearity of expectation we have

$\displaystyle\mathbf{E}(t^{\prime}_{i+1}(v,c))$ $\displaystyle\leq
t_{i}(v,c)\bigg{(}1-\frac{K}{\ln\Delta}\mathrm{Keep}_{i}\bigg{)}\times\mathrm{Keep}_{i}+t_{i}(v,c)L_{i}^{-1/3}$
$\displaystyle\leq
t_{i}(v,c)\bigg{(}1-\frac{K}{\ln\Delta}\mathrm{Keep}_{i}\bigg{)}\times\mathrm{Keep}_{i}+T_{i}L_{i}^{-1/3}$
by property $P(i)$
$\displaystyle=t_{i}(v,c)\bigg{(}1-\frac{K}{\ln\Delta}\mathrm{Keep}_{i}\bigg{)}\times\mathrm{Keep}_{i}+T_{i}^{2/3}\bigg{(}\frac{T_{i}}{L_{i}}\bigg{)}^{1/3}$
$\displaystyle\leq
t_{i}(v,c)\bigg{(}1-\frac{K}{\ln\Delta}\mathrm{Keep}_{i}\bigg{)}\times\mathrm{Keep}_{i}+T_{i}^{2/3}\big{(}\ln\Delta\big{)}^{1/3}$
$\displaystyle\leq
t_{i}(v,c)\bigg{(}1-\frac{K}{\ln\Delta}\mathrm{Keep}_{i}\bigg{)}\times\mathrm{Keep}_{i}+T_{i}^{3/4}$

for $\Delta$ sufficiently large.

∎

The next step is to show concentration results for our parameters.

######  Lemma 3.10.

If $P(i)$ holds, $T_{i}\geq\frac{1}{8}L_{i}$,and if
$T_{i},L_{i}\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$, then for
any uncoloured vertex $v$ and colour $c\in L_{i}(v)$,

  1. a)

$\mathbf{Pr}\Big{(}|\ell_{i+1}(v)-\mathbf{E}(\ell_{i+1}(v))|>L_{i}^{1-\beta/2}\Big{)}<\Delta^{-\ln\Delta}$;

  2. b)

$\mathbf{Pr}\Big{(}|t^{\prime}_{i+1}(v,c)-\mathbf{E}(t^{\prime}_{i+1}(v,c))|>\frac{1}{2}T_{i}^{1-\beta/2}\Big{)}<\Delta^{-\ln\Delta}$.

###### Proof.

To show that our parameters are strongly concentrated, we will make use of
Talagrand’s Inequality. Recall that Talagrand’s Inequality requires that a
random variable be determined by a set of independent trials.

The random choices made in an iteration are as follows. For each vertex we
choose whether or not to activate it. We assign a random colour to each
activated vertex. Finally, we conduct an equalizing coin flip for each $v$ and
$c$ in $v$’s list, removing $c$ from $v$’s list if it loses the coin flip. A
problem arises when applying Talagrand’s Inequality, since these choices are
not made independently of one another. For instance, the choice of whether to
assign a random colour to a vertex depends on the activation choice for that
vertex. Also, the choice of whether to conduct an equalizing coin flip for a
given colour and vertex $v$ depends on the fact that this colour was not
removed from $v$’s list earlier in the iteration, and this is determined by
the activation and colour assignments on $v$’s neighbours. We add a set of
dummy choices to fix this. We choose a colour for each unactivated vertex and
conduct an equalizing coin flip for each $v$ and $c$ not in $v$’s list. Of
course we do not assign the chosen colour to the unactivated vertex and there
is no need to remove $c$ from $v$’s list if it loses the coin flip, so these
dummy choices have no effect on the procedure. Their purpose is to make the
set of random choices independent from one another, and this will allow us to
apply Talagrand’s Inequality.

  1. $a)$

We focus on showing that the number of colours removed from $v^{\prime}s$ list
during iteration $i+1$, $\bar{\ell}$, is highly concentrated.
Changing the activation or colour assignment to any vertex $u\in N(v)$ can
affect $\bar{\ell}$ by at most the maximal value of $t_{i}(u,v,\gamma)$
realized by colour $\gamma$. By (2) this is at most $L_{i}^{1/2-\beta}$.
Changing the colour assignment to any other vertex cannot affect $\bar{\ell}$
at all. Changing the result of any equalizing flip can affect $\bar{\ell}$ by
at most 1.
Suppose $\bar{\ell}\geq s$. We consider the two possible ways a colour $c$
could leave $v$’s list. A neighbour $u$ of $v$ could have caused a conflict,
meaning that $u$ was assigned a colour $c^{\prime}$ such that
$(c,c^{\prime})\in\mathcal{T}(v,u)$. The other way a colour could be removed
is via an equalizing flip. Therefore, there must be $s_{1}$ neighbours of $v$
which were involved in conflicts and caused $v$ to lose $s_{1}$ distinct
colours. There must also be $s_{2}$ equalizing flips which resulted in $s_{2}$
distinct colours (disjoint from the $s_{1}$ previous colours) being removed
from $v^{\prime}s$ list, and we must have $s_{1}+s_{2}=s$. For the first set
of events we require two trials for each colour removed: the activation and
colour assigned to the neighbour. For the second set of events we require only
one trial, the equalizing flip. Therefore in total we require at most
$2s_{1}+s_{2}\leq 2s$ trials to certify that $\bar{\ell}\geq s$.
Let $t=L_{i}^{1-\beta/2}$, and note that $\mathbf{E}(\bar{\ell})$ =
$L_{i}-\mathbf{E}(\ell_{i+1}(v))=L_{i}-L_{i}\times\mathrm{Keep}_{i}$. So this
expectation is at most $L_{i}$. Therefore since $L_{i}$ grows with $\Delta$,
we have $t/2\geq 20q\sqrt{\smash[b]{r\mathbf{E}(\bar{\ell})}}+64q^{2}r$ for
any $q\leq L_{i}^{1/2-\beta}$ and any constant $r$, and for $\Delta$
sufficiently large. Using this fact, we have that

$\mathbf{Pr}\Big{(}|\bar{\ell}-\mathbf{E}(\bar{\ell})|>t\Big{)}\leq\mathbf{Pr}\Big{(}|\bar{\ell}-\mathbf{E}(\bar{\ell})|>\frac{t}{2}+20q\sqrt{r\mathbf{E}(\bar{\ell})}+64q^{2}r\Big{)}.$

So applying Talagrand’s Inequality with $q=L_{i}^{1/2-\beta}$ and $r=2$, we
get that

$\displaystyle\mathbf{Pr}\Big{(}|\bar{\ell}-\mathbf{E}(\bar{\ell})|>L_{i}^{1-\beta/2}\Big{)}$
$\displaystyle\leq
4\exp\Bigg{(}{-\frac{L_{i}^{2-\beta}}{64q^{2}\Big{(}\mathbf{E}(\bar{\ell})+L_{i}^{1-\beta/2}\Big{)}}}\Bigg{)}$
$\displaystyle\leq
4\exp\Bigg{(}{-\frac{L_{i}^{1-\beta}}{128L_{i}^{1-2\beta}}}\Bigg{)}$
$\displaystyle\leq 4\exp\Bigg{(}{-\frac{L_{i}^{\beta}}{128}}\Bigg{)}$
$\displaystyle\leq 4\exp\bigg{(}{-\frac{\ln^{3}\Delta}{128}}\bigg{)}$ since
$L_{i}\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$ by assumption
$\displaystyle<\Delta^{-\ln\Delta}$

for $\Delta$ sufficiently large.
Now by linearity of expectation,
$\mathbf{E}(\ell_{i+1}(v))=L_{i}-\mathbf{E}(\bar{\ell})$. So we have that

$\mathbf{Pr}\Big{(}|\ell_{i+1}(v)-\mathbf{E}(\ell_{i+1}(v))|>L_{i}^{1-\beta/2}\Big{)}=\mathbf{Pr}\Big{(}|\bar{\ell}-\mathbf{E}(\bar{\ell})|>L_{i}^{1-\beta/2}\Big{)}<\Delta^{-\ln\Delta}$

as desired.

  2. $b)$

Let $X$ be the random variable which counts the number of constraints
$(c,c^{\prime})\in N_{i}(v,c)$ with endpoints $v,u$ such that $u$ did not
retain a colour during iteration $i+1$. Let $Y$ be the number of constraints
$(c,c^{\prime})\in N_{i}(v,c)$ with endpoints $v,u$ such that during iteration
$i+1$ the following occurred:

     * •

$u$ did not retain a colour, and,

     * •

$c^{\prime}$ was removed from $u$’s list by either an equalizing flip or
because a neighbour of $u$ other than $v$ caused a conflict

Note that $t^{\prime}_{i+1}(v,c)=X-Y$, and so by linearity of expectation it
suffices to show that $X$ and $Y$ are both sufficiently concentrated.

First we focus on $X$. We prove concentration by splitting up $X$ into two
related variables, $X_{1}$ and $X_{2}$. Let $X_{1}$ denote the number of
constraints $(c,c^{\prime})\in N_{i}(v,c)$ with endpoints $v,u$ such that
during iteration $i+1$ one of the following occurred:

     * •

$u$ was not activated, or,

     * •

$u$ did not retain a colour because of a conflict with a neighbour other than
$v$

Let $X_{2}$ denote the number of constraints $(c,c^{\prime})\in N_{i}(v,c)$
with endpoints $v,u$ such that $u$ was activated and lost its colour because
of a conflict with $v$. Let us be clear about the definitions of $X_{1}$ and
$X_{2}$. Note that for a constraint $(c,c^{\prime})$ between $v$ and $u$ such
that $u$ lost its colour because of a conflict with $v$, this constraint could
still be counted by $X_{1}$ so long as there is some neighbour $w\neq v$ which
also conflicted with $u$. Similarly, if $u$ lost its colour because of a
conflict with a neighbour $w\neq v$, it could still be counted by $X_{2}$ so
long as $v$ also conflicted with $u$. Now note that $X_{1}\leq X\leq
X_{1}+X_{2}$.

First we consider $X_{1}$. Consider the effect on $X_{1}$ by changing a random
choice for a vertex. By triangle-freeness, there are no edges within $N(v)$,
and so for a vertex $u\in N(v)$, changing a random choice for $u$ only affects
whether or not $u$ remains uncoloured. Thus this affects $X_{1}$ by at most
$t_{i}(v,u,c)$. By (3), this is at most $T_{i}^{1/2-\beta}$. Because our graph
has no 4-cycles, if $w$ is a vertex outside the neighbourhood of $v$ and
$w\neq v$, then $w$ can have at most 1 neighbour in $N(v)$, say $u$. Therefore
changing a random choice for $w$ can at worst affect whether or not $u$
remains uncoloured, and therefore can affect $X_{1}$ again by at most
$t_{i}(v,u,c)\leq T_{i}^{1/2-\beta}$. Of course, changing a random choice for
$v$ has no effect on $X_{1}$.

If vertices $v$ and $u$ are constrained by $(c,c^{\prime})\in N_{i}(v,c)$ and
$u$ does not receive a colour, the activation choice for $u$ certifies this
fact. Otherwise if $u$ becomes uncoloured because of a conflict with a
neighbour $u^{\prime}$, then the activation and colour choices for both $u$
and $u^{\prime}$ certify this fact. Thus we require a set of at most $4s$
random choices to certify that $X_{1}\geq s$.

As $X_{1}\leq T_{i}$, we have $\mathbf{E}(X_{1})\leq T_{i}$. So similar to the
computation in part ($a$) which made use of Talagrand’s Inequality, this
implies that

$\mathbf{Pr}\big{(}|X_{1}-\mathbf{E}(X_{1})|>\frac{1}{4}T_{i}^{1-\beta/2}\big{)}<\frac{1}{4}\Delta^{-\ln\Delta}.$

Now we turn our attention to $X_{2}$. It’s not hard to verify that $X_{2}$ is
bounded above in distribution by the following random variable:

$t_{i}(v,u^{\ast},\gamma)BIN\Big{(}T_{i},\frac{K}{\ln\Delta}\times\frac{t_{i}(u^{\ast\ast},v,\gamma^{\prime})}{L_{i}}\Big{)},$

where $u^{\ast},\gamma$ and $u^{\ast\ast},\gamma^{\prime}$ are chosen to
maximize the values $t_{i}(v,u^{\ast},\gamma)$ and
$t_{i}(u^{\ast\ast},v,\gamma^{\prime})$ respectively (recall that by (3), both
of these values are at most $T_{i}^{1/2-\beta}$). Since
$T_{i}/L_{i}<\ln\Delta$ by Lemma 3.6, we have:

$\frac{K}{\ln\Delta}\times
T_{i}\times\frac{t_{i}(u^{\ast\ast},v,\gamma^{\prime})}{L_{i}}<Kt_{i}(u^{\ast\ast},v,\gamma)<\alpha$

for some $\alpha=O(T_{i}^{1/2-\beta})$. Rearranging terms, we get:

$\frac{K}{\ln\Delta}\times\frac{t_{i}(u^{\ast\ast},v,\gamma^{\prime})}{L_{i}}<\frac{\alpha}{T_{i}}.$

Since $T_{i}\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$ by
assumption, we can see that the Chernoff Bound implies:

$\displaystyle\mathbf{Pr}\big{(}X_{2}>\frac{1}{4}T_{i}^{1-\beta/2}\big{)}$
$\displaystyle<\mathbf{Pr}\big{(}|BIN(T_{i},\frac{\alpha}{T_{i}})-\alpha|>\frac{1}{4}\frac{T_{i}^{1-\beta/2}}{T_{i}^{1/2-\beta}}-\alpha\big{)}$
$\displaystyle<\mathbf{Pr}\big{(}|BIN(T_{i},\frac{\alpha}{T_{i}})-\alpha|>T_{i}^{1/2}\big{)}$
$\displaystyle<2e^{-\Big{(}\big{(}1+\frac{T_{i}^{1/2}}{\alpha}\big{)}\ln\big{(}1+\frac{T_{i}^{1/2}}{\alpha}\big{)}-\frac{T_{i}^{1/2}}{\alpha}\Big{)}\alpha}$
$\displaystyle=2e^{-\Big{(}\ln\big{(}1+\frac{T_{i}^{1/2}}{\alpha}\big{)}+\frac{T_{i}^{1/2}}{\alpha}\ln\big{(}1+\frac{T_{i}^{1/2}}{\alpha}\big{)}-\frac{T_{i}^{1/2}}{\alpha}\Big{)}\alpha}$
$\displaystyle<2e^{-\Big{(}\frac{T_{i}^{1/2}}{\alpha}\big{(}\ln\big{(}1+\frac{T_{i}^{1/2}}{\alpha}\big{)}-1\big{)}\Big{)}\alpha}$
$\displaystyle<2e^{-\Big{(}\frac{T_{i}^{1/2}}{\alpha}\big{(}\ln\big{(}1+\Omega(T_{i}^{\beta})\big{)}-1\big{)}\Big{)}\alpha}$
$\displaystyle<2e^{-T_{i}^{1/2}}$ since $\ln(1+\Omega(T_{i}^{\beta}))\gg 1$
$\displaystyle<2e^{-\ln^{3}\Delta}$
$\displaystyle<\frac{1}{4}\Delta^{-\ln\Delta}$

for $\Delta$ sufficiently large.

Since $X_{1}\leq X\leq X_{1}+X_{2}$, these two bounds together imply that

$\mathbf{Pr}\Big{(}|X-\mathbf{E}(X)|\geq\frac{1}{2}T_{i}^{1-\beta/2}\Big{)}<\frac{1}{2}\Delta^{-\ln\Delta}$

as desired.

Now we focus on $Y$. Analogously define $Y_{1}$ to be the number of
constraints $(c,c^{\prime})\in N_{i}(v,c)$ with endpoints $v,u$ such that
during iteration $i+1$ one of the following occurred:

     * •

$u$ was not activated, or,

     * •

$u$ did not retain a colour because of a conflict with a neighbour other than
$v$

and in addition:

     * •

$c^{\prime}$ was removed from $u$’s list because of an equalizing flip or
because a neighbour of $u$ other than $v$ caused a conflict

Define $Y_{2}$ to be the number of constraints $(c,c^{\prime})\in N_{i}(v,c)$
with endpoints $v,u$ such that during iteration $i+1$ the following occurred:

     * •

$u$ did not retain a colour because of a conflict with $v$, and,

     * •

$c^{\prime}$ was removed from $u$’s list because of an equalizing flip or
because a neighbour of $u$ other than $v$ caused a conflict

First we focus on $Y_{1}$, the same argument used for $X_{1}$ shows that
changing any activation or colour assignment can affect $Y_{1}$ by at most
$T_{i}^{1/2-\beta}$, and changing the result of an equalizing coin flip may
have an affect of at most 1.

If vertices $v$ and $u$ are constrained by $(c,c^{\prime})\in N_{i}(v,c)$ and
$u$ is not activated then the activation choice for $u$ certifies this fact.
Otherwise if $u$ is uncoloured because of a conflict with a neighbour $w\neq
v$, then the activation and colour choices for $u$ and $w$ certify this. In
addition, if $c^{\prime}$ is removed from $u$’s list because of a conflict
with a neighbour other than $v$ then the activation and colour choice for that
neighbour certifies this. So in total we require a set of at most $6s$ random
choices to certify that $Y_{1}\geq s$.

Therefore applying Talagrand’s Inequality, the same calculation from before
gives

$\mathbf{Pr}\big{(}|Y_{1}-\mathbf{E}(Y_{1})|>\frac{1}{4}T_{i}^{1-\beta/2}\big{)}<\frac{1}{4}\Delta^{-\ln\Delta}.$

Now $Y_{2}$ is again bounded above by the random variable
$T_{i}^{1/2-\beta}BIN\big{(}T_{i},\frac{K}{\ln\Delta}\times\frac{T_{i}^{1/2-\beta}}{L_{i}}\big{)}$.
So we have

$\mathbf{Pr}\big{(}Y_{2}>\frac{1}{4}T_{i}^{1-\beta/2}\big{)}<\frac{1}{4}\Delta^{-\ln\Delta},$

and this implies $Y$ is sufficiently concentrated as before, so the result
follows.

∎

Our next step is to show property $P(i)$ holds for all appropriate values of
$i$.

######  Lemma 3.11.

With positive probability, $P(i)$ holds for every $i$ such that for all
$j<i:L_{j},T_{j}\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$ and
$T_{j}\geq\frac{1}{8}L_{j}$.

###### Proof.

The proof is by induction. For the base case, we note that the bounds
$\ell_{0}(v)\geq L_{0}$ and $t_{0}(v,c)\leq T_{0}$ clearly hold by
Modification 1. So $P(0)$ holds.
For the induction step we assume $P(i)$ holds for some $i\in\mathbb{N}$, and
we will show that with positive probability $P(i+1)$ holds.
For every $v$, neighbour $u$ of $v$, and $c\in L_{i+1}(v)$ we define $A_{v}$
to be the event that $\ell_{i+1}(v)<L_{i+1}$, and $B_{v,c}$ be the event that
$t_{i+1}(v,c)>T_{i+1}$. If none of these events hold, then $P(i+1)$ holds.
If the event $A_{v}$ occurs, by Lemma 3.9 this implies that
$|\ell_{i+1}(v)-\mathbf{E}(\ell_{i+1}(v))|>L_{i}^{1-\beta/2}$, and by Lemma
3.10 this happens with probability at most $p=\Delta^{-\ln\Delta}$ (notice
that we’ve implicitly used the inductive hypothesis here when making use of
Lemma 3.9 and Lemma 3.10).

Also if the event $B_{v,c}$ occurs we have:

$\displaystyle t_{i+1}(v,c)$
$\displaystyle>T_{i}(1-\frac{K}{\ln\Delta}\mathrm{Keep}_{i})\times\mathrm{Keep}_{i}+T_{i}^{1-\beta/2}$
$\displaystyle\geq
t_{i}(v,c)\Big{(}1-\frac{K}{\ln\Delta}\mathrm{Keep}_{i}\Big{)}\times\mathrm{Keep}_{i}+T_{i}^{1-\beta/2}$
$\displaystyle\geq
t_{i}(v,c)\Big{(}1-\frac{K}{\ln\Delta}\mathrm{Keep}_{i}\Big{)}\times\mathrm{Keep}_{i}+T_{i}^{3/4}+\frac{1}{2}T_{i}^{1-\beta/2}$
$\displaystyle\geq\mathbf{E}(t^{\prime}_{i+1}(v,c))+\frac{1}{2}T_{i}^{1-\beta/2}$

and since $t_{i+1}(v,c)\leq t^{\prime}_{i+1}(v,c)$ we can see this implies
$|t^{\prime}_{i+1}(v,c)-\mathbf{E}(t^{\prime}_{i+1}(v,c))|>\frac{1}{2}T_{i}^{1-\beta/2}$.
Again by Lemma 3.10, this happens with probability at most $p$.
Moreover, each event corresponding to a vertex $v$ is determined by equalizing
coin flips and colours assigned to vertices of distance at most 2 from $v$.
Therefore, by the Mutual Independence Principle (see chapter 4 of [23]), each
event corresponding to a vertex $v$ is mutually independent of all events
except for those corresponding to vertices of distance at most 4 from $v$. So
every event can only be dependent on at most $d=\Delta^{4}\times
O\big{(}\sqrt{\Delta/\ln\Delta}\big{)}<\Delta^{5}$ other events. So
$pd<\Delta^{-\ln\Delta}\Delta^{5}<1/4$ for $\Delta$ sufficiently large and the
result follows from the Lovász Local Lemma. ∎

Our next lemma shows that the values for $L_{i+1}$ and $T_{i+1}$ defined in
(3) do not stray too far from the values $L_{i+1}^{\prime}$ and
$T_{i+1}^{\prime}$ defined in (3). As the recursive equations defined in (3)
have a much nicer structure, this will simplify our analysis significantly
moving forward.

######  Lemma 3.12.

If for all $j<i$ we have
$L_{j},T_{j}\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$ and
$T_{j}\geq\frac{1}{8}L_{j}$, then

  1. $a)$

$|L_{i}-L^{\prime}_{i}|\leq(L^{\prime}_{i})^{1-\beta/4}=o(L^{\prime}_{i})$;

  2. $b)$

$|T_{i}-T^{\prime}_{i}|\leq(T^{\prime}_{i})^{1-\beta/4}=o(T^{\prime}_{i})$.

###### Proof.

  1. $a)$

The proof is by induction. Since $L^{\prime}_{i}>L_{i}$, it suffices to show
that $L_{i}^{\prime}\leq L_{i}+(L^{\prime}_{i})^{1-\beta/4}$. Initially this
is clearly the case. Now suppose that for some $i>0$ we have
$L_{i}^{\prime}\leq L_{i}+(L^{\prime}_{i})^{1-\beta/4}$. It is easy to verify
that the function $f(x)=x^{1-\beta/4}-x$ has only one critical point in the
interval $(0,1)$, namely at $x=(1-\beta/4)^{4/\beta}<e^{-1}$. Therefore $f(x)$
is decreasing on the interval $[e^{-1},1]$. By Lemma 3.7 and Remark 3.8,
$\mathrm{Keep}_{i}$ is within this interval. Also by Lemma 3.7 we have
$\mathrm{Keep}_{i}\leq(1-{\color[rgb]{0,0,0}\frac{K}{10}\ln\Delta})$ and so
using the fact that $f$ is decreasing we have

$\displaystyle\mathrm{Keep}_{i}^{1-\beta/4}-\mathrm{Keep}_{i}\geq\Big{(}1-{\color[rgb]{0,0,0}\frac{K}{10\ln\Delta}}\Big{)}^{1-\beta/4}-\Big{(}1-{\color[rgb]{0,0,0}\frac{K}{10\ln\Delta}}\Big{)}.$
(21)

Now we use the Maclaurin Series expansion of the function
$g(x)=(1-x)^{1-\beta/4}=1-(1-\beta/4)x-\frac{\beta}{8}(1-\beta/4)x^{2}-\cdots$
to see that $(1-x)^{1-\beta/4}=1-(1-\beta/4)x-O(x^{2})$ for $x\in[0,1]$. So
for $x={\color[rgb]{0,0,0}\frac{K}{10\ln\Delta}}$ and for $\Delta$
sufficiently large,

$\Big{(}1-{\color[rgb]{0,0,0}\frac{K}{10\ln\Delta}}\Big{)}^{1-\beta/4}\geq
1-{\color[rgb]{0,0,0}(1-\beta/4)\frac{K}{10\ln\Delta}}-O\Big{(}\frac{1}{\ln^{2}\Delta}\Big{)}\geq
1-{\color[rgb]{0,0,0}(1-\beta/8)\frac{K}{10\ln\Delta}}$

So continuing (21) we see that

$\displaystyle\mathrm{Keep}_{i}^{1-\beta/4}-\mathrm{Keep}_{i}\geq
1-{\color[rgb]{0,0,0}(1-\beta/8)\frac{K}{10\ln\Delta}}-\Big{(}1-{\color[rgb]{0,0,0}\frac{K}{10\ln\Delta}}\Big{)}={\color[rgb]{0,0,0}\frac{\beta
K}{80\ln\Delta}}.$ (22)

Now we have:

$\displaystyle L^{\prime}_{i+1}$
$\displaystyle=\mathrm{Keep}_{i}L^{\prime}_{i}$ by definition (3)
$\displaystyle\leq\mathrm{Keep}_{i}(L_{i}+(L^{\prime}_{i})^{1-\beta/4})$ by
$IH$
$\displaystyle=\mathrm{Keep}_{i}L_{i}+\mathrm{Keep}_{i}(L^{\prime}_{i})^{1-\beta/4}$
$\displaystyle=L_{i+1}+L_{i}^{1-\beta/2}+\mathrm{Keep}_{i}(L^{\prime}_{i})^{1-\beta/4}$
using definition (3) $\displaystyle\leq
L_{i+1}+L^{1-\beta/2}_{i}+\mathrm{Keep}_{i}^{1-\beta/4}(L^{\prime}_{i})^{1-\beta/4}-{\color[rgb]{0,0,0}\frac{\beta
K}{80\ln\Delta}}(L^{\prime}_{i})^{1-\beta/4}$ by (22)
$\displaystyle=L_{i+1}+\mathrm{Keep}_{i}^{1-\beta/4}(L^{\prime}_{i})^{1-\beta/4}+L^{1-\beta/2}_{i}-{\color[rgb]{0,0,0}\frac{\beta
K}{80\ln\Delta}}(L^{\prime}_{i})^{1-\beta/4}$ $\displaystyle\leq
L_{i+1}+(L^{\prime}_{i+1})^{1-\beta/4}$ using definition (3)

where in the last bound we use the fact that the negative term dominates over
$L^{1-\beta/2}_{i}$ for $\Delta$ sufficiently large (since
$L_{i}\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$).

  2. $b)$

For this part we have $T^{\prime}_{i}<T_{i}$, and so it suffices to show that
$T^{\prime}_{i}\geq T_{i}-(T^{\prime}_{i})^{1-\beta/4}$. The proof uses the
same method as before, except this time we show that for
$x=\mathrm{Keep}_{i}(1-\frac{K}{\ln\Delta}\mathrm{Keep}_{i})$ we have
$x^{1-\beta/4}-x=\Omega\big{(}\frac{1}{\ln\Delta}\big{)}$, which allows us to
complete the proof in the same way.

∎

With the help of Lemma 3.12 we can finally show that our list sizes never
become too small, while on the other hand showing that $T_{i}$ eventually
becomes much smaller than $L_{i}$. This will allow us to apply Lemma 3.1.

######  Lemma 3.13.

There exists $i^{\ast}$ such that

  1. $a)$

For all
$i<i^{\ast},T_{i},L_{i}>\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$,
and $T_{i}\geq\frac{1}{8}L_{i}$;

  2. $b)$

$T_{i^{\ast}}<\frac{1}{8}L_{i^{\ast}}$.

###### Proof.

  1. $a)$

For this part we show that $T_{i}$ and $L_{i}$ are sufficiently large whenever
$T_{i}\geq\frac{1}{8}L_{i}$. The proof is by induction, $L_{0}$ and $T_{0}$
are clearly sufficiently large. We show that for some $i$, if $T_{i}$ and
$L_{i}$ are sufficiently large and $T_{i+1}\geq\frac{1}{8}L_{i+1}$, then
$T_{i+1}$ and $L_{i+1}$ are sufficiently large as well. If
$T_{i+1}<\frac{1}{8}L_{i+1}$ then there is no need to continue the procedure
for more than $i+1$ iterations and this implies the existence of $i^{\ast}$.
We show that this indeed happens in part ($b$).
First, recall the definitions of $L^{\prime}_{i+1}$ and $T^{\prime}_{i+1}$.
Initially, we have:

$\displaystyle\begin{aligned}
L^{\prime}_{0}&=L_{0}=(\sqrt{2}+\epsilon/2)\sqrt{\Delta/\ln\Delta}\\\ \\\
T^{\prime}_{0}&=T_{0}=\frac{1}{\sqrt{2}+\epsilon/2}\sqrt{\Delta\ln\Delta}\end{aligned}$

and we recursively define:

$\displaystyle\begin{aligned}
L^{\prime}_{i+1}&=L^{\prime}_{i}\times\mathrm{Keep}_{i}\\\ \\\
T^{\prime}_{i+1}&=T^{\prime}_{i}\Big{(}1-\frac{K}{\ln\Delta}\mathrm{Keep}_{i}\Big{)}\times\mathrm{Keep}_{i}\end{aligned}$

We focus on showing $L_{i+1}$ is large first, but rather than finding a lower
bound for $L_{i+1}$, Lemma 3.12 allows us to focus on $L^{\prime}_{i+1}$
instead. In particular, for each $j\leq i$ we focus on bounding
$\mathrm{Keep}_{j}$ which is closely related to the ratio
$r_{j}=T_{j}/L_{j}\approx r^{\prime}_{j}=T^{\prime}_{j}/L^{\prime}_{j}$.
Recall that we gave the following lower bound on $\mathrm{Keep}_{j}$ in the
proof of Lemma 3.7:

$\displaystyle\mathrm{Keep}_{j}>\exp\bigg{(}-K\frac{(1+\frac{1}{20}\epsilon
e^{-\epsilon})r_{j}}{\ln\Delta}\bigg{)}>\exp\bigg{(}-K\frac{(1+\frac{1}{20}\epsilon
e^{-\epsilon})}{(\sqrt{2}+\epsilon/2)^{2}}\bigg{)}$ (23)

Now by ($a)$) we have

$r^{\prime}_{i}=r_{0}\prod_{j=1}^{i-1}\Bigg{(}1-\frac{K}{\ln\Delta}\mathrm{Keep}_{j}\Bigg{)}.$

So by (23), and since $r_{0}=\frac{\ln\Delta}{(\sqrt{2}+\epsilon/2)^{2}}$ by
($a)$) we get:

$\displaystyle r^{\prime}_{i}$ $\displaystyle\leq
r_{0}\times\bigg{(}1-\frac{K}{\ln\Delta}\exp\Big{(}-K\frac{(1+\frac{1}{20}\epsilon
e^{-\epsilon})}{(\sqrt{2}+\epsilon/2)^{2}}\Big{)}\bigg{)}^{i-1}$
$\displaystyle=\frac{\ln\Delta}{(\sqrt{2}+\epsilon/2)^{2}}\bigg{(}1-\frac{K}{\ln\Delta}\exp\Big{(}-K\frac{(1+\frac{1}{20}\epsilon
e^{-\epsilon})}{(\sqrt{2}+\epsilon/2)^{2}}\Big{)}\bigg{)}^{i-1}$ (24)

Moreover, by Lemma 3.12 we have

$\displaystyle
r_{i}=\frac{T_{i}}{L_{i}}\leq\frac{T^{\prime}_{i}+(T^{\prime}_{i})^{1-\beta/4}}{L^{\prime}_{i}-(L^{\prime}_{i})^{1-\beta/4}}=r^{\prime}_{i}\times\frac{1+\frac{1}{(T^{\prime}_{i})^{\beta/4}}}{1-\frac{1}{(L^{\prime}_{i})^{\beta/4}}}=(1+o(1))r^{\prime}_{i}$
(25)

where in the last equality we use the fact that
$L^{\prime}_{i},T^{\prime}_{i}$ are close to $L_{i},T_{i}$ respectively by
Lemma 3.12, and the latter values satisfy
$L_{i},T_{i}\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$ by $IH$. So
by (25) we get $r_{i}\leq(1+\epsilon e^{-\epsilon}/30)r^{\prime}_{i}$ for
$\Delta$ sufficiently large. So now we have:

$\displaystyle r_{i}$ $\displaystyle\leq(1+\epsilon
e^{-\epsilon}/30)r^{\prime}_{i}$ $\displaystyle\leq\frac{(1+\epsilon
e^{-\epsilon}/30)\ln\Delta}{(\sqrt{2}+\epsilon/2)^{2}}\bigg{(}1-\frac{K}{\ln\Delta}\exp\Big{(}-K\frac{(1+\frac{1}{20}\epsilon
e^{-\epsilon})}{(\sqrt{2}+\epsilon/2)^{2}}\Big{)}\bigg{)}^{i-1}$ by (24)

which yields a better lower bound on $\mathrm{Keep}_{i}$:

$\displaystyle\mathrm{Keep}_{i}$ $\displaystyle>\exp\Bigg{(}-K(1+\epsilon
e^{-\epsilon}/20)r_{i}/\ln\Delta\Bigg{)}$ by (23)
$\displaystyle\geq\exp\Bigg{(}-\frac{K(1+\epsilon e^{-\epsilon}/20)(1+\epsilon
e^{-\epsilon}/30)\ln\Delta}{\ln\Delta(\sqrt{2}+\epsilon/2)^{2}}\Big{(}1-\frac{K}{\ln\Delta}e^{-\frac{K(1+\epsilon
e^{-\epsilon}/20)}{(\sqrt{2}+\epsilon/2)^{2}}}\Big{)}^{i-1}\Bigg{)}$
$\displaystyle=\exp\Bigg{(}-\frac{K(1+\epsilon e^{-\epsilon}/20)(1+\epsilon
e^{-\epsilon}/30)}{(\sqrt{2}+\epsilon/2)^{2}}\Big{(}1-\frac{K}{\ln\Delta}e^{-\frac{K(1+\epsilon
e^{-\epsilon}/20)}{(\sqrt{2}+\epsilon/2)^{2}}}\Big{)}^{i-1}\Bigg{)}$ (26)

It is straightforward to check that for any $\epsilon>0$, we have $(1+\epsilon
e^{-\epsilon}/20)(1+\epsilon e^{-\epsilon}/30)\leq(1+\epsilon
e^{-\epsilon}/10)$ in the above expressions. So now we can proceed with our
bound for $L^{\prime}_{i}$. We have:

$\displaystyle L^{\prime}_{i+1}$
$\displaystyle=L_{0}\prod_{j=1}^{i}\mathrm{Keep}_{j}$
$\displaystyle\geq(\sqrt{2}+\epsilon/2)\sqrt{\frac{\Delta}{\ln\Delta}}\exp\Bigg{(}-\frac{K(1+\epsilon
e^{-\epsilon}/10)}{(\sqrt{2}+\epsilon/2)^{2}}\sum_{j=1}^{i}\Big{(}1-\frac{K}{\ln\Delta}e^{-\frac{K(1+\epsilon
e^{-\epsilon}/20)}{(\sqrt{2}+\epsilon/2)^{2}}}\Big{)}^{j-1}\Bigg{)}$ by (26)
$\displaystyle\geq(\sqrt{2}+\epsilon/2)\sqrt{\frac{\Delta}{\ln\Delta}}\exp\Bigg{(}-\frac{(1+\epsilon
e^{-\epsilon}/10)\ln\Delta}{(\sqrt{2}+\epsilon/2)^{2}}e^{\frac{K(1+\epsilon
e^{-\epsilon}/20)}{(\sqrt{2}+\epsilon/2)^{2}}}\Bigg{)}$ by the geometric
series
$\displaystyle=(\sqrt{2}+\epsilon/2)\sqrt{\frac{\Delta}{\ln\Delta}}\times\Delta^{-\frac{(1+\epsilon
e^{-\epsilon}/10)}{(\sqrt{2}+\epsilon/2)^{2}}\exp\Big{(}\frac{K(1+\epsilon
e^{-\epsilon}/20)}{(\sqrt{2}+\epsilon/2)^{2}}\Big{)}}$ (27)

Now it suffices to obtain a bound on the exponent of $\Delta$ in (27). We
simply choose a value of $K$ which makes the exponent collapse to some value
strictly greater than $-\frac{1}{2}$. We take

$\displaystyle K=\frac{(\sqrt{2}+\epsilon/2)^{2}}{(1+\epsilon
e^{-\epsilon}/20)}\ln{(1+\epsilon e^{-\epsilon}/10)}.$ (28)

At this point the reader should verify that this definition is consistent with
remark 3.8. So we have:

$\frac{(1+\epsilon
e^{-\epsilon}/10)}{(\sqrt{2}+\epsilon/2)^{2}}\exp\Bigg{(}\frac{K(1+\epsilon
e^{-\epsilon}/20)}{(\sqrt{2}+\epsilon/2)^{2}}\Bigg{)}=\Bigg{(}\frac{1+\epsilon
e^{-\epsilon}/10}{\sqrt{2}+\epsilon/2}\Bigg{)}^{2}$

It is straightforward (although tedious) to verify that
$\frac{1}{2}-\Big{(}\frac{1+\epsilon
e^{-\epsilon}/10}{\sqrt{2}+\epsilon/2}\Big{)}^{2}>\frac{1}{2}\Big{(}\frac{\epsilon}{\epsilon+3}\Big{)}^{2}$.
So continuing (27) we obtain:

$\displaystyle L^{\prime}_{i+1}$
$\displaystyle\geq(\sqrt{2}+\epsilon/2)\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+3)^{2}}/\sqrt{\ln\Delta}$
$\displaystyle\geq\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+3.5)^{2}}$

for $\Delta$ sufficiently large.

Therefore
$L_{i+1}>L^{\prime}_{i+1}-(L^{\prime}_{i+1})^{1-\beta/4}>\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+3.75)^{2}}$
for $\Delta$ sufficiently large. Since $T_{i+1}\geq\frac{1}{8}L_{i+1}$ this
means $T_{i+1}>\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$, so both
$L_{i+1}$ and $T_{i+1}$ are at least
$\Delta^{\frac{1}{2}\epsilon^{2}/(\epsilon+4)^{2}}$ for $\Delta$ sufficiently
large.

  2. $b)$

Now we will show that the ratio $r_{i}=T_{i}/L_{i}$ eventually becomes smaller
than $\frac{1}{8}$.
We know by Lemma 3.7 that $\mathrm{Keep}_{0}\geq c$ for some positive constant
$c$. We also know by (25) that $r_{i}\leq(1+o(1))r^{\prime}_{i}\leq
2r^{\prime}_{i}$ for $\Delta$ sufficiently large. Now let
$\hat{i}=\frac{2}{Kc}\ln\Delta\ln\ln\Delta$. Recalling the value of
$r_{0}=\frac{\ln\Delta}{(\sqrt{2}+\epsilon/2)^{2}}$ we have:

$r_{\hat{i}}\leq
2r_{0}\Big{(}1-\frac{Kc}{\ln\Delta}\Big{)}^{\frac{2}{Kc}\ln\Delta\ln\ln\Delta}\leq\frac{2}{(\sqrt{2}+\epsilon/2)^{2}}\ln\Delta\times
e^{-2\ln\ln\Delta}<\frac{1}{8}.$

for sufficiently large $\Delta$. Let $S=\\{i\leq\hat{i}:r_{i}<\frac{1}{8}\\}$.
Clearly $S$ is non-empty, so we choose $i^{\ast}$ to be the minimum value in
$S$. Now the fact that $r_{i}$ is decreasing implies the lemma.

∎

Finally, we put it all together to prove the main theorem.

Proof of Theorem 1.5.

Let $i^{\ast}$ be the natural number guaranteed by Lemma 3.13. Firstly we can
carry out the wasteful colouring procedure for $i^{\ast}$ iterations. By Lemma
3.11 and Lemma 3.13, $P(i)$ holds with positive probability for each $i\leq
i^{\ast}$ so we do in fact perform $i^{\ast}$ iterations. Thus by property
$P(i^{\ast})$ and Lemma 3.13, we will have that for each $v$ and $c\in L(v)$,
$t_{i^{\ast}}(v,c)\leq T_{i^{\ast}}\leq\frac{1}{8}L_{i^{\ast}}$, and the
colouring can be completed by Lemma 3.1.

##  4 Concluding Remarks

In this paper we showed that for any $\epsilon>0$, there exists $\Delta_{0}$
such that any multigraph with maximum degree $\Delta>\Delta_{0}$, no cycles of
length 3 or 4 and an edge labelling $\tau$ with $D(\tau)$ at most
$\Delta^{\frac{1}{4}\epsilon^{2}/(\epsilon+5)^{2}}$ can be conflict coloured
with at most $\ell=(2\sqrt{2}+\epsilon)\sqrt{\Delta/\ln\Delta}$ colours.

Note that for large $\epsilon$, our result means that a bound on $D(\tau)$ of
$\Delta^{\frac{1}{4}-o(1)}$ is sufficient to complete the colouring with
$\ell$ colours (here $o(1)$ is a function of $\epsilon$). On the other hand,
Example 1.7 says that a bound of $\Delta^{\frac{1}{2}-o(1)}$ is necessary.
Closing this gap could be an interesting problem for future work.

For small $\epsilon$ the gap is more significant since when $\epsilon$ tends
to 0, theorem 1.5 gives a bound which tends to $\Delta^{0}$ while Example 1.7
says that a bound of $\ell^{15/16}\approx\Delta^{15/32}$ is necessary. Closing
this gap could be another interesting problem. A step in this direction is to
answer the following questions:

Question 1. Is there a constant $d\in(0,\frac{15}{32})$ such that any
multigraph with maximum degree $\Delta$, no cycles of length 3 or 4, and an
edge labelling with conflict degree at most $\Delta^{d}$ can be conflict
coloured with lists of size $(2\sqrt{2}+o(1))\sqrt{\Delta/\ln\Delta}$?

Question 2. If the answer to Question 1 is affirmative, what is the biggest
value of $d$ possible?

We conclude by pointing out that these questions cannot be resolved in the
affirmative with the analysis presented here. Recall Observation 1 and the
following discussion. There we showed that if our list sizes are sufficiently
large we have:

$t_{i}(v,u,c)\leq L_{i}^{1/2-\beta}.$

Recall that we required $t_{i}(v,u,c)$ to be quite small, and so this bound
was important for proving the concentration results (Lemma 3.10) of our main
parameters.

Now when we allow the conflict degree to be as large as $\Delta^{d}$ for come
absolute constant $d$, then initially $t_{i}(v,u,c)$ can also be this large.
This becomes a significant problem if $t_{i}(v,u,c)$ remains this large
throughout the procedure, since towards the end of the procedure our lists are
of size $L_{i}\approx\Delta^{\epsilon^{2}}$. In particular, when $\epsilon$ is
much smaller than $d$ it can be the case that $t_{i}(v,u,c)$ is as big as
$L_{i}$. I.e. assigning $c$ to $v$ in this case could eliminate $u$’s list
entirely.

A natural attempt to overcome this is to show that the parameter
$t_{i}(v,u,c)$ decreases quickly with each iteration. Unfortunately, there are
cases where this does not happen with high probability.

Nevertheless, as far as the authors know Questions 1 and 2 could conceivably
be answered in the affirmative via other methods.

##  5 Acknowledgements

The authors would like to thank Aleksandar Nikolov for his careful review and
valuable comments. This research is supported by an NSERC Discovery Grant.

## References

  * [1] A. F. Archer, On the upper chromatic numbers of the reals, Discrete Mathematics, 214 (2000), pp. 65–75.
  * [2] H. Chernoff et al., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, The Annals of Mathematical Statistics, 23 (1952), pp. 493–507.
  * [3] M. Cochand and P. Duchet, A few remarks on orientation of graphs and ramsey theory, in Irregularities of partitions, Springer, 1989, pp. 39–46.
  * [4] K. Dabrowski, V. Lozin, R. Raman, and B. Ries, Colouring vertices of triangle-free graphs, in International Workshop on Graph-Theoretic Concepts in Computer Science, Springer, 2010, pp. 184–195.
  * [5] Z. Dvořák, L. Esperet, R. J. Kang, and K. Ozeki, Least conflict choosability, (2018).
  * [6] Z. Dvořák and L. Postle, Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8, Journal of Combinatorial Theory, Series B, 129 (2018), pp. 38–54.
  * [7] P. Erdös and A. Gyárfás, Split and balanced colorings of complete graphs, Discrete Mathematics, 200 (1999), pp. 79–86.
  * [8] P. Erdős and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in COLLOQUIA MATHEMATICA SOCIETATIS JANOS BOLYAI 10. INFINITE AND FINITE SETS, KESZTHELY (HUNGARY), Citeseer, 1973.
  * [9] L. Esperet, M. Montassier, and X. Zhu, Adapted list coloring of planar graphs, Journal of Graph Theory, 62 (2009), pp. 127–138.
  * [10] T. Feder and P. Hell, Full constraint satisfaction problems, SIAM J. Comput., 36 (2006), pp. 230–246.
  * [11] T. Feder, P. Hell, S. Klein, and R. Motwani, List partitions, SIAM Journal on Discrete Mathematics, 16 (2003), pp. 449–478.
  * [12] T. Feder, P. Hell, and W. Xie, Matrix partitions with finitely many obstructions, Electronic Notes in Discrete Mathematics, 28 (2007), pp. 371–378.
  * [13] P. Fraigniaud, M. Heinrich, and A. Kosowski, Local conflict coloring, in Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, IEEE, 2016, pp. 625–634.
  * [14] A. M. Frieze and T. Łuczak, On the independence and chromatic numbers of random regular graphs, Journal of Combinatorial Theory, Series B, 54 (1992), pp. 123–132.
  * [15] J. Gimbel and C. Thomassen, Coloring triangle-free graphs with fixed size, Discrete Mathematics, 219 (2000), pp. 275–277.
  * [16] A. Guan and X. Zhu, Adaptable choosability of planar graphs with sparse short cycles, Discrete Mathematics, 309 (2009), pp. 6044–6047.
  * [17] T. P. Hayes, Randomly coloring graphs of girth at least five, in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, ACM, 2003, pp. 269–278.
  * [18] P. Hell, Z. Pan, T.-L. Wong, and X. Zhu, Adaptable chromatic number of graph products, Discrete Mathematics, 309 (2009), pp. 6153–6159.
  * [19] P. Hell and X. Zhu, On the adaptable chromatic number of graphs, European Journal of Combinatorics, 29 (2008), pp. 912–921.
  * [20] J. H. Kim, On brooks’ theorem for sparse graphs, Combinatorics, Probability and Computing, 4 (1995), pp. 97–132.
  * [21] A. V. Kostochka and X. Zhu, Adapted list coloring of graphs and hypergraphs, SIAM Journal on Discrete Mathematics, 22 (2008), pp. 398–408.
  * [22] M. Molloy, The adaptable chromatic number and the chromatic number, Journal of Graph Theory, 84 (2017), pp. 53–56.
  * [23] M. Molloy and B. Reed, Graph colouring and the probabilistic method, vol. 23, Springer Science & Business Media, 2013.
  * [24] , Colouring graphs when the number of colours is almost the maximum degree, Journal of Combinatorial Theory, Series B, 109 (2014), pp. 134 – 195.
  * [25] M. Molloy and G. Thron, The adaptable choosability number grows with the choosability number, Discrete Mathematics, 311 (2011), pp. 2268–2271.
  * [26] , An asymptotically tight bound on the adaptable chromatic number, Journal of Graph Theory, 71 (2012), pp. 331–351.
  * [27] M. Montassier, A. Raspaud, and X. Zhu, An upper bound on adaptable choosability of graphs, European Journal of Combinatorics, 30 (2009), pp. 351–355.
  * [28] B. Reed, The list colouring constants, Journal of Graph Theory, 31 (1999), pp. 149–153.
  * [29] B. Reed and B. Sudakov, Asymptotically the list colouring constants are 1, Journal of Combinatorial Theory, Series B, 86 (2002), pp. 27–37.
  * [30] M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, Publications Mathématiques de l’Institut des Hautes Etudes Scientifiques, 81 (1995), pp. 73–205.