# Large rainbow matchings in edge-colored graphs

Debsoumya Chakraborti Supported by the Institute for Basic Science
(IBS-R029-C1). Discrete Mathematics Group, Institute for Basic Science (IBS),
Daejeon, South Korea Po-Shen Loh Supported in part by National Science
Foundation CAREER Grant DMS-1455125. Department of Mathematical Sciences,
Carnegie Mellon University, Pittsburgh, USA

###### Abstract

There has been much research on the topic of finding a large rainbow matching
(with no two edges having the same color) in a properly edge-colored graph,
where a proper edge coloring is a coloring of the edge set such that no same-
colored edges are incident. Recently, Gao, Ramadurai, Wanless, and Wormald
proved that in every proper edge coloring of a graph with $q$ colors where
each color appears at least $q+o(q)$ times, there is always a rainbow matching
using every color. We strengthen this result by simultaneously relaxing two
conditions: (i) we lift the condition on the number of colors and allow any
finite number of colors and instead, put a weaker condition requiring the
maximum degree of the graph to be at most $q$, and (ii) we also relax the
proper coloring condition and require that the graph induced by each of the
colors have bounded degree. This strengthening resolves a natural question
inspired by the remarks made by Gao, Ramadurai, Wanless, and Wormald.

As an application of this result, we show that for every proper edge coloring
of a graph with $2q+o(q)$ colors where each color appears at least $q$ times,
there is always a rainbow matching of size $q$. This can be seen as an
asymptotic version of a conjecture of Barát, Gyárfás, and Sárközy restricted
on simple graphs. We also provide a construction showing that having $q+1$
colors is not enough, disproving a conjecture of Aharoni and Berger. As a by-
product of our techniques, we obtain a new asymptotic version of the
Brualdi–Ryser–Stein Conjecture, which is one of the central open questions in
combinatorics.

##  1 Introduction

###  1.1 State of the art

Transversals in Latin squares have been a central topic of study in
combinatorics, dating back to the work of Euler [19] in the 18th century, who
studied conditions on when Latin squares can be decomposed into transversals.
For a survey of transversals in Latin squares, see, e.g., [34]. One of the
central and long-standing conjectures in this field is the following, which is
attributed to Brualdi, Ryser, and Stein.

######  Conjecture 1.1 (Brualdi and Ryser [14], Ryser [32], and Stein [33]).

Every $n\times n$ Latin square has a partial transversal of size $n-1$.

This conjecture translates into the graph-theoretic statement: “In any proper
edge-coloring of the complete bipartite graph $K_{n,n}$ with $n$ colors, there
is a rainbow matching of size $n-1$”. To see this connection, refer to [28] or
[34]. Hatami and Shor [24] proved an asymptotic version of Conjecture 1.1, and
the error term was further improved in a recent result of Keevash, Pokrovskiy,
Sudakov, and Yepremyan [25].

######  Theorem 1.2 (Keevash, Pokrovskiy, Sudakov, and Yepremyan [25]).

Every proper edge-coloring of the complete bipartite graph $K_{n,n}$ with $n$
colors contains a rainbow matching of size $n-O\left(\frac{\log n}{\log\log
n}\right)$.

In this paper, we study generalizations (in many different aspects) of
Conjecture 1.1 in the setting of rainbow matchings in edge-colored (but not
only properly edge-colored) graphs. We advise the interested readers to see
[5] for a recent survey on various extensions of this conjecture. Aharoni and
Berger conjectured the following generalization of Conjecture 1.1 in [3].

######  Conjecture 1.3 (Aharoni and Berger [3]).

Let $G$ be a properly edge-colored bipartite multigraph with $n$ colors,
having at least $n+1$ edges of each color. Then $G$ has a rainbow matching
using every color.

In this paper, multigraphs permit parallel edges but not loops. After
subsequent efforts by several authors (see, e.g., [7, 11, 15, 23, 27, 29]), an
asymptotic version of Conjecture 1.3 is established in [16] and [28], where
the conclusion of the conjecture is shown to hold if there are at least
$n+o(n)$ edges of each color. It is very natural to generalize Conjecture 1.3
for non-bipartite graphs. Gao, Ramadurai, Wanless, and Wormald [20] mentioned
the following conjecture, which was also suggested by Aharoni, Berger,
Chudnovsky, Howard, and Seymour [4].

######  Conjecture 1.4 (Gao, Ramadurai, Wanless, and Wormald [20]).

Let $G$ be a properly edge-colored multigraph with $n$ colors having at least
$n+2$ edges of each color. Then $G$ has a rainbow matching using every color.

We remark here that one cannot replace $n+2$ by $n+1$ in Conjecture 1.4 (to
see this, refer to [16] or [20]). After a couple of notable works progressing
towards Conjecture 1.4 by Gao, Ramadurai, Wanless, and Wormald [20], and by
Keevash and Yepremyan [26], recently Correia, Pokrovskiy, and Sudakov [16]
established an asymptotic version of Conjecture 1.4. Gao, Ramadurai, Wanless,
and Wormald proved the following asymptotic version of Conjecture 1.4 for
simple graphs.

######  Theorem 1.5 (Gao, Ramadurai, Wanless, and Wormald [20]).

For every $\epsilon>0$, there exists $N=N(\epsilon)$ such that whenever $n\geq
N$, for any graph $G$ that is properly edge-colored with $n$ colors such that
there are at least $(1+\epsilon)n$ edges of each color, there is a rainbow
matching of $G$ using every color.

In this paper, we provide a generalization of this result of [20], where we
allow non-proper edge-colorings and relax the condition of having only $n$
colors (see Theorem 1.9 in the next section). Yet another motivation for such
generalization comes from the following conjecture by Aharoni and Berger [3],
which allows the edge-coloring to be non-proper.

######  Conjecture 1.6 (Aharoni and Berger [3]).

Let G be a bipartite multigraph, with maximum degree $\Delta$, whose edges are
(not necessarily properly) colored. If every color appears on at least
$\Delta+1$ edges, then $G$ has a rainbow matching using every color.

Gao, Ramadurai, Wanless, and Wormald refuted Conjecture 1.6 in [20] by
constructing an example where $\Delta$ is linear in terms of the number of
colors used. In this context, it will be interesting to check if such a
statement holds for edge-coloring with the additional assumption of bounded
(perhaps in terms of $\Delta$) maximum degree in each color class (color class
refers to the subgraph formed by the edges of that color). Note that if the
maximum degree of a color class is one, that color appears as a matching. So,
this will be yet another generalization of Conjecture 1.3. Our generalization
(Theorem 1.9) of Theorem 1.5 implies the asymptotic version of Conjecture 1.6
for edge-coloring of not-necessarily-bipartite simple graphs with only a
bounded degree assumption on each color class.

We now move on to a related but slightly different problem. All the problems
discussed so far focused on the minimum number of edges in each color class to
ensure a rainbow matching using all the colors. Alternatively, we can insist
that each color class has size exactly $n$ and discuss how many colors we need
to ensure a rainbow matching of size $n$. In this context, the first result
appeared by Drisko [17] in 1998, which some authors later revisited (see,
e.g., [3, 9, 10]). On this topic, Barát, Gyárfás, and Sárközy [13] suggested
the following conjecture:

######  Conjecture 1.7 (Barát, Gyárfás, and Sárközy [13]).

Let $G$ be a properly edge-colored multigraph with $2n-t_{n}$ colors and
exactly $n$ edges of each color, where $t_{n}=0$ for even $n$ and $t_{n}=1$
for odd $n$. Then $G$ has a rainbow matching using $n$ colors.

For the best-known results on this conjecture, the readers are advised to
refer to [4] and [6]. Aharoni and Berger considered Conjecture 1.7 in a simple
graph, and made the following general conjecture (Conjecture 3.2 in [3]) for
simple hypergraphs.

######  Conjecture 1.8 (Aharoni and Berger [3]).

Let $G$ be an properly edge-colored $r$-uniform hypergraph with
$2^{r-2}(s-1)+2$ colors and $t$ edges of each color. Then, $G$ has a matching
with $t$ edges on which at least $s$ colors appear.

In this paper, we disprove this conjecture when $r=2$ and $s=t$ and progress
on the upper bound on the required number of matchings, which will be
discussed in Section 1.2. To be more precise, this upper bound is obtained by
establishing an asymptotic version of Conjecture 1.7 when we restrict
ourselves to simple graphs $G$ (see Theorem 1.11 in the next section).

###  1.2 Main results

We start with our first result, which generalizes Theorem 1.5.

######  Theorem 1.9.

There exists $N$ such that whenever $q\geq N$ and
$1\leq\Delta\leq\frac{\sqrt{q}}{\left(\log q\right)^{9}}$, the following
holds. Suppose $G$ is a graph with maximum degree at most $q$ that is edge-
colored such that there are at least
$\left(1+\left(\frac{\Delta^{2}}{q}\right)^{\frac{1}{6}}\left(\log
q\right)^{2}\right)q$ edges of each color. Suppose that at most $\Delta$ edges
of the same color are incident to any vertex (thus, this is not necessarily a
proper coloring). Then, there is a rainbow matching in $G$, which uses every
color.

In contrast to the result in Theorem 1.5, we do not need any bound on the
number of colors; instead, we require a weaker condition that the graph has
maximum degree at most $q$ (note that in Theorem 1.5, a proper-edge coloring
of $G$ with $n$ colors ensures the maximum degree to be at most $n$).
Furthermore, Theorem 1.9 does not require the color classes to be matchings,
but the subgraph formed by each color still must have bounded degree. To prove
Theorem 1.9, we use a natural randomized algorithm similar to the one used by
Gao, Ramadurai, Wanless, and Wormald [20]. However, we make a few subtle
changes in their algorithm to facilitate the analysis of the algorithm in our
general setting. We analyze our algorithm by differential equation technique
combined with the local lemma. Our argument also gives us a slightly better
error term in the required number of edges in each color in the case when the
edge-coloring is proper (i.e., when $\Delta=1$) compared to the one obtained
in [20]. Incidentally, this had the least error term among the known results
progressing towards Conjecture 1.4.

In this paper, we disprove Conjecture 1.8. As mentioned in [3], the $r=2$ and
$s=t$ case of Conjecture 1.8 would have given us a generalization of
Conjecture 1.1. But unfortunately, we have found a counterexample to this.

######  Proposition 1.10.

For all even $t$, there exists a graph that is properly edge-colored with
$t+1$ colors such that there are $t$ edges of each color, but no rainbow
matching of size $t$.

Thus, it is natural to find the maximum number $f(t)$ that can be written
instead of $t+1$ in the above proposition. Proposition 1.10 proves that
$f(t)\geq t+1$ for all even $t$. We make progress in the upper bound and
establish that $f(t)\leq 2t+o(t)$. This provides an asymptotic version of
Conjecture 1.7 in the case of simple graphs. Although we believe that the
lower bound on $f(t)$ is closer to the truth, there is a natural barrier to
improving the upper bound of $2t+o(t)$, which we elaborate on in the
concluding remarks. Our next result is the following:

######  Theorem 1.11.

For every $\epsilon>0$, there exists $N=N(\epsilon)$ such that whenever $q\geq
N$, for any graph $G$ that is properly edge-colored with at least
$2(1+\epsilon)q$ colors such that there are at least $q$ edges of each color,
there is a rainbow matching of $G$ using $q$ colors.

We next show that Theorem 1.11 is the best possible with respect to the number
of edges in each color class. We need each color to appear at least $q$ times
because it is possible to have no matching on $q$ edges when each color
appears $q-1$ times, even if we have any number $n$ of colors. To see this,
consider the graph that is a disjoint union of $q-1$ copies of $K_{1,n}$ and
color each $K_{1,n}$ using all the colors exactly once. Although each color
appears as a matching with $q-1$ edges, the graph does not contain any
matching with $q$ edges. It turns out that this rigid behavior concerning the
number of colors in each color class poses some difficulty in approaching this
problem with probabilistic methods. Nevertheless, we overcome this difficulty
by proving and using the following statement, which is also of independent
interest.

######  Theorem 1.12.

For every $\epsilon>0$, there exists $N=N(\epsilon)$ such that whenever $q\geq
N$ the following holds. Suppose $G$ is a bipartite graph on the vertex set
with bipartition $A\cup B$, where $|A|=q$ and every vertex in $A$ has degree
at least $(1+\epsilon)q$. Suppose the edges are properly colored. Then, there
always is a rainbow matching in $G$, which uses every vertex in $A$.

The constant 1 in $(1+\epsilon)q$ of this result is optimal in the above
result, because it is easy to construct examples showing that $\epsilon=0$
does not work (to see such an example, check the first part of Section 2). As
a straightforward corollary of Theorem 1.12, we next obtain the following
asymptotic version of Conjecture 1.1 (the Brualdi–Ryser–Stein conjecture),
which is also best possible up to the small error term.

######  Corollary 1.13.

Every proper edge-coloring of the complete bipartite graph $K_{q,q+o(q)}$
contains a rainbow matching of size $q$.

In comparison with Theorem 1.2, we relax one of the parts of the bipartite
graph to be slightly larger, but obtain a rainbow matching using every vertex
of the smaller part. However, our error term of $o(q)$ in Corollary 1.13 is
larger than the error term in Theorem 1.2 and thus, it will be interesting to
investigate whether one can obtain a polylogarithmic error term instead.

We use the differential equation method (also known as the dynamic
concentration method) to prove Theorem 1.11 and Theorem 1.12. Although our
method is motivated by the probabilistic approach in [20] by Gao, Ramadurai,
Wanless, and Wormald, due to the nature of the statements of our results, it
is required to keep track of more parameters compared to them, which in turn
makes the analysis inevitably complicated. To keep the analysis reasonably
concise, we take extra care in processing the underlying graph while executing
our algorithms.

Organization. This paper is organized as follows. We disprove Conjecture 1.8
in the next section by proving Proposition 1.10. We mention some standard
probabilistic tools in Section 3, which we use throughout this paper. For the
next few subsequent sections, we concentrate on Theorem 1.9. Section 4
contains the randomized algorithm we use to prove Theorem 1.9, which is
referred to as Algorithm everywhere. Later, we consider several similar
randomized algorithms with many subtle changes to prove Theorem 1.11 and
Theorem 1.12. In Section 5, we give an intuitive analysis to explain why the
algorithm in Section 4 is expected to work. In a subsequent couple of
sections, we prove Theorem 1.9 rigorously. Then, Theorem 1.12 is proved in
Section 8. In Section 9, we establish a weaker version of Theorem 1.11, which
we need later to prove it. Section 10 contains the proof of Theorem 1.11. We
finish with a few concluding remarks, which include a discussion on why the
required number of colors in Theorem 1.11 might be hard to improve using
arguments based on only probabilistic methods.

Throughout this paper, for brevity, we systematically avoid the floor and
ceiling signs because they do not affect the underlying analysis.

##  2 Construction for Proposition 1.10

We prove Proposition 1.10 in this section. Fix an even $t$. Consider a graph
$G$ on the vertex set $A\cup B$, where $A$ and $B$ have $t$ vertices each, and
recognize each of $A$ and $B$ by the group $\mathbb{Z}_{t}$. For each
$j\in\mathbb{Z}_{t}$, introduce a color $j$ with $t$ edges, where each $a\in
A$ is adjacent to $a+j\in B$. Thus, we have $t$ colors, each of which is a
matching of size $t$. First, we prove that there is no rainbow matching using
all of these $t$ colors. For the sake of contradiction, assume that we have
such a rainbow matching and fix such a matching. All colors and vertices of
$G$ have to participate in such a matching. Let $a_{j}b_{j}$ denote the edge
in color $j\in\mathbb{Z}_{t}$ in the rainbow matching, where $a_{j}\in A$ and
$b_{j}\in B$. Clearly, we have the following:

$\sum_{j\in\mathbb{Z}_{t}}a_{j}=\sum_{j\in\mathbb{Z}_{t}}b_{j}=\sum_{j\in\mathbb{Z}_{t}}j=\frac{t(t-1)}{2}.$

But by the definition of each color class $E_{j}$, we should have
$\sum_{j\in\mathbb{Z}_{t}}(b_{j}-a_{j})=\sum_{j\in\mathbb{Z}_{t}}j$, which is
a contradiction for even $t$.

Now let us introduce an extra $(t+1)$-st color in $G$, whose edges are the
union of an arbitrary perfect matching in $A$ and arbitrary perfect matching
in $B$. This clearly has $t$ edges. Note that all the matchings are still
disjoint because any matching considered before contains edges between $A$ and
$B$ only. We claim that even after introducing this extra color, we still
cannot have a rainbow matching of size $t$. For the sake of contradiction,
assume that we have such a rainbow $t$-matching. Clearly, the extra color has
to participate in that because we could not do it before. Without loss of
generality, the extra color edge in the rainbow matching is between two
vertices $u,v\in A$. Now it is impossible to have a rainbow matching of size
$t-1$ on $G\setminus\\{u,v\\}$ using the rest of the colors because each edge
uses a distinct vertex from each of $A$ and $B$. Hence, we have a
contradiction.

##  3 Preliminaries

We state some standard probabilistic tools, including a few large-deviation
inequalities, which will be used throughout the paper.

######  Theorem 3.1 (Chernoff bound, see [22]).

Let $X=\sum_{i=1}^{n}X_{i}$, where $X_{i}=1$ with probability $p_{i}$ and
$X_{i}=0$ with probability $1-p_{i}$, and all $X_{i}$ are independent. Let
$\mu=\mathbb{E}(X)=\sum_{i=1}^{n}p_{i}$. Then for any $0<\lambda<\mu$, we have
that $\mathbb{P}\left[|X-\mu|\geq\lambda\right]\leq
2e^{-\frac{\lambda^{2}}{3\mu}}$.

We need Azuma-Hoeffding inequality (see, e.g., [2] and [22]) to prove
concentration bounds to keep track of the behavior of certain parameters in
our randomized algorithms. More specifically, we use applications of Azuma-
Hoeffding inequality in the following general setting from Chapter 7 of [12].

For finite sets $A$ and $B$, let $\Omega=A^{B}$ denote the set of functions
$g:B\rightarrow A$. Now define a probability measure by setting
$\mathbb{P}[g(b)=a]$ where the values of $g(b)$ are independent for different
$b$. Fix a gradation $\emptyset=B_{0}\subset B_{1}\subset\cdots\subset
B_{N}=B$. Let $L:A^{B}\rightarrow\mathbb{R}$ be a functional. Now define a
martingale $X_{0},X_{1},\ldots,X_{N}$ as the following:

$X_{j}(h)=\mathbb{E}\left(L(g)\mid g(b)=h(b)\text{ for all }b\in
B_{j}\right).$

Clearly, $X_{0}$ is the deterministic expected value of $L$, and $X_{N}$ is
the random variable $L$. The values of $X_{j}(g)$ approach $L(g)$ as the
values of $g(b)$ are exposed. We say that the functional $L$ is $l$-Lipschitz
relative to the given gradation if for all $0\leq j<m$:

$h,h^{\prime}\text{ only differ on }B_{j+1}\setminus
B_{j}\;\;\;\;\;\;\;\;\;\;\;\;\Rightarrow\;\;\;\;\;\;\;\;\;\;\;\;|L(h)-L(h^{\prime})|\leq
l.$ (3.1)

######  Theorem 3.2.

Let $L$ satisfies the Lipschitz condition (3.1) relative to a gradation of
length $m$, and let $\mu=\mathbb{E}(L(g))$. Then for all $\lambda>0$,

$\mathbb{P}[|L(g)-\mu|\geq\lambda]\leq 2e^{-\frac{\lambda^{2}}{2ml^{2}}}$
(3.2)

To keep track of the evolution of certain parameters (in the proof of Theorem
1.9), we will sometimes need to use Talagrand’s inequality. We need a couple
of definitions to state it. For a random variable
$X:\Omega\rightarrow\mathbb{R}$ with $\Omega=\prod_{i=1}^{n}\Omega_{i}$ being
a product probability space, we say:

  * •

$X$ is $C$-Lipschitz, if for every $\omega\in\Omega$, changing $\omega$ in any
single coordinate affects the value of $X(\omega)$ by at most $C$.

  * •

$X$ is $r$-certifiable, if for every $\omega\in\Omega$ and $s\in\mathbb{R}$
such that $X(\omega)\geq s$, the following holds. There exists a set
$I\subseteq\\{1,\ldots,n\\}$ of size at most $rs$ such that every
$\omega^{\prime}\in\Omega$ that agrees with $\omega$ on the coordinates
indexed by $I$ also satisfies that $X(\omega^{\prime})\geq s$.

######  Theorem 3.3 (Talagrand’s inequality, see [12]).

Suppose that $X$ is a $C$-Lipschitz and $r$-certifiable random variable. Then,

$\mathbb{P}\left[|X-\mathbb{E}(X)|>t+60C\sqrt{r\mathbb{E}(X)}\right]\leq
4e^{-\frac{t^{2}}{8C^{2}r\mathbb{E}(X)}}.$

Since the number of colors in Theorem 1.9 can be arbitrarily large, simple
union bounds often do not work (e.g., to control the number of edges in every
color class). Thus, we need the Lovász local lemma to prove this result. We
next mention the symmetric version of the standard local lemma.

######  Theorem 3.4 (Lovász local lemma, see [12]).

Let $A_{1},\ldots,A_{n}$ be events in a probability space. Suppose that there
exist constants $p$ and $d$ such that all $\mathbb{P}[A_{i}]\leq p$, and each
event $A_{j}$ is mutually independent of all the other events $\\{A_{i}\\}$
except at most $d$ of them. If $ep(d+1)\leq 1$, then
$\mathbb{P}[\cap\overline{A_{i}}]>0$.

We next give a weaker bound for Theorem 1.9, which will be used in its proof.

######  Proposition 3.5.

Suppose $G$ is a graph with maximum degree at most $q$ that is edge-colored,
with at least $4eq$ edges of each color. Then, there is a rainbow matching in
$G$, which uses every color.

To prove Proposition 3.5, we use the following result of Alon [1] (see [21]
for the best possible result), which can be easily proved using the local
lemma (i.e., Theorem 3.4).

######  Proposition 3.6 (See [1]).

let $G$ be a multipartite graph with maximum degree $\Delta$, whose parts
$V_{1},\ldots,V_{r}$ all have size $|V_{i}|\geq 2e\Delta$. Then, $G$ has an
independent transversal.

###### Proof of Proposition 3.5.

Let $r$ be the number of colors in $G$, and $E_{i}$ denote the edge set of
$i$-th color. Consider the $r$-partite graph $\Gamma$ where the $i$-th part is
$E_{i}$ (the edges in $G$ are vertices of $\Gamma$). Two vertices in $\Gamma$
are considered adjacent if the corresponding edges in $G$ are incident to each
other. Thus, the maximum degree of $\Gamma$ is at most $2q$, and each part
contains at least $2e\cdot 2q$ vertices. Thus, by Proposition 3.6, the graph
$\Gamma$ has an independent transversal. Observe that an independent
transversal in $\Gamma$ corresponds with a rainbow matching in $G$ using every
color. This completes the proof of Proposition 3.5. ∎

##  4 Algorithm

In this section, we give a randomized algorithm that will be primarily used
for Theorem 1.9. Since we use some variants of this algorithm for proving
Theorems 1.11 and 1.12, this algorithm will be referred to as Algorithm
throughout the paper. Assume that we are given a graph $G$ with maximum degree
at most $q$ that is edge-colored such that there are $(1+\epsilon)q$ edges of
each color and at most $\Delta$ edges of the same color can be incident to any
vertex. We will provide a randomized algorithm, which constructs a rainbow
matching using almost all the colors in several iterations. Each iteration is
a random procedure, where we can show that we get to the desired state with
some positive probability. Then we fix that choice of desirable state to
analyze the next iteration. A single step of our algorithm will look like the
following.

This algorithm is in terms of some parameter $\delta>0$, which will be
specified later. Define $\tau=\frac{1}{\delta}$. We follow the algorithm below
for $\eta\tau$ steps, for some $\eta<1$ to be specified later. For $1\leq
t\leq\eta\tau$, the $t$-th iteration of the algorithm is given below.

  1. 1.

Activate each color class independently with probability
$\theta_{t}=\frac{\delta}{1-(t-1)\delta}$ (this probability is picked to
ensure that roughly $\delta m$ colors get activated in each iteration).

  2. 2.

Select independently one edge from each activated color class uniformly at
random. Denote by $T$ the set of all selected edges.

  3. 3.

Delete all the vertices corresponding to the edges in $T$ from $G$. Deleting
vertices always also deletes all incident edges.

  4. 4.

With some probability (to be specified later), independently delete each
vertex in $G$. This will ensure that among Steps 3 and 4 combined, every
vertex in $G$ gets deleted with the same probability.

  5. 5.

For each edge $e\in T$, add it to the rainbow matching if $e$ is not incident
to any edge $e^{\prime}\in T$ with $e^{\prime}\neq e$.

  6. 6.

For each edge $e$ added to the rainbow matching in Step 5, delete all the
edges of the same color as $e$ from $G$.

We next provide a heuristic on what we can expect from the above algorithm.
Thus, it is possible to skip the next section if the reader is only interested
in a formal proof of Theorem 1.9.

##  5 Intuitive analysis

We aim to show that if we run this randomized algorithm until we have picked
almost all the colors we need, then near the end, each remaining color still
has so many edges left (relative to the maximum degree of $G$) that we can
complete the rainbow matching using every color via a straightforward
application of Proposition 3.5. To this end, tracking the evolution of the
color class sizes and the degrees of the vertices is useful. We do that by
modeling the remaining color class size and vertex degrees using a system of
differential equations.

Define $d_{0,v}$ to be the initial degree of $v$ in $G$. We will define two
functions $s(x)$ and $g(x)$ such that after the $t$-th iteration of Algorithm,
we have the following:

  1. 1.

Each remaining color class has size around $s_{t}\approx
s(t\delta)(1+\epsilon)q$.

  2. 2.

Each surviving vertex $v$ has degree,
$d_{t,v}\approx(1-t\delta)g(t\delta)d_{0,v}$.

Clearly, $s(0)=1$ and $g(0)=1$. Assume that the $t$-th iteration is done, and
the properties 1 and 2 are true. We outline a rough analysis of the $(t+1)$-st
iteration of Algorithm to determine the functions $s$ and $g$.

Because of Step 4, every vertex of $G$ is deleted with the same probability
among Steps 3 and 4 combined. This is done only for convenience in our
analysis; thus, we should set that probability (denote it by $a_{t}$) as low
as possible. In other words, we need to find the maximum probability a vertex
$v$ can be deleted in Step 3 and set $a_{t}$ to be that maximum probability.
At the $(t+1)$-st iteration, for every edge $e$ of $G$, the probability
(denote by $p_{e}$) that $e$ will be picked in $T$ is exactly $\theta_{t+1}$
divided by the total number of edges of $G$ with the same color as $e$, which
is about $\frac{\theta_{t+1}}{s_{t}}$. Thus, by a simple union bound, the
probability that $v$ is deleted in Step 3 is at most $\sum_{e\ni
v}p_{e}\approx d_{t,v}\cdot\frac{\theta_{t+1}}{s_{t}}\approx\frac{\delta
g(t\delta)d_{0,v}}{s(t\delta)(1+\epsilon)q}$. Thus, we can define $a_{t}$ to
be about $\frac{\delta
g(t\delta)q}{s(t\delta)(1+\epsilon)q}=\gamma\frac{\delta
g(t\delta)}{s(t\delta)}$ (note that $d_{0,v}\leq q$), where
$\gamma=\frac{1}{1+\epsilon}$.

The probability that a single vertex gets deleted among Steps 3 and 4 is
$a_{t}$; thus, the probability that a pair of vertices gets deleted is about
$a_{t}^{2}$, which we ignore in this intuitive analysis as it is a strictly
lower-order term. Hence, the expected number of edges deleted in each color
class among Steps 3 and 4 is approximately $2a_{t}s_{t}$. This suggests the
following behavior:

$s^{\prime}(x)=-2\gamma g(x).$ (5.1)

Next, let us estimate the change in $d_{t,v}$ to get a differential equation
for $g$. We know that each neighbor of $v$ is deleted among Steps 3 and 4 with
probability $a_{t}$. On the other hand, any edge $e$ incident to $v$ will be
deleted in Step 6 by probability $\approx\theta_{t+1}$ because the color class
containing $e$ is activated with this probability in Step 1, and there is a
relatively low chance of conflicts in Step 5. Thus, neglecting small error
terms due to lack of independence, we expect to have the following:

$\displaystyle d_{t+1,v}-d_{t,v}$
$\displaystyle\approx-\left[a_{t}+(1-a_{t})\theta_{t+1}\right]d_{t,v}$
$\displaystyle(\tau-t-1)\delta g((t+1)\delta)d_{0,v}-(\tau-t)\delta
g(t\delta)d_{0,v}$ $\displaystyle\approx-\delta
g(t\delta)d_{0,v}-(\tau-t-1)\delta g(t\delta)d_{0,v}a_{t}$
$\displaystyle\frac{g((t+1)\delta)-g(t\delta)}{\delta}$
$\displaystyle\approx-\gamma\cdot\frac{g(t\delta)^{2}}{s(t\delta)}.$

The above suggests:

$g^{\prime}(x)=-\gamma\frac{g(x)^{2}}{s(x)}.$ (5.2)

By Equations (5.1) and (5.2), we have that $\frac{dg}{ds}=\frac{g}{2s}$, whose
solution is $s=cg^{2}$ for some constant $c$. By the initial conditions that
$g(0)=s(0)=1$, we get that $s=g^{2}$. Now, Equation (5.2) implies that
$g^{\prime}(x)=-\gamma$. Solving this with the initial condition $g(0)=1$, we
obtain that $g(x)=1-\gamma x$. Hence, $s(x)=(1-\gamma x)^{2}$ because
$s=g^{2}$.

We show in the next section that the degrees of vertices and the sizes of
color classes are concentrated throughout the process, implying that we can
not get stuck as long as $t\leq\eta\tau$. Moreover, after $\eta\tau$-th
iteration, the number of edges in any color class
$\approx(1-\gamma\eta)^{2}(1+\epsilon)q$, and the maximum degree of $G$ is at
most about $(1-\eta)(1-\gamma\eta)q$. As long as
$(1-\gamma\eta)^{2}(1+\epsilon)q\gg 4e(1-\eta)(1-\gamma\eta)q$, we can finish
the rainbow matching by including an edge from the remaining colors by using
Proposition 3.5. This inequality can be made true by choosing $\eta$ so that
$1-\eta$ is small enough compared to $1-\gamma$.

##  6 Formal analysis

Throughout this section (also in the remaining sections), we assume that $q$
is sufficiently large whenever needed. The previous section motivates us to
define $s(x)=(1-\gamma x)^{2}$ and $g(x)=1-\gamma x$, where
$\gamma=\frac{1}{1+\epsilon}$. From now on, we introduce error terms
$\alpha_{t}$ and $\beta_{t}$ (which will be explicitly specified in the next
section and much less than $\frac{1}{100}$), which will accumulate as we run
the process (i.e., as $t$ increases). Thus, throughout this section, we use
the inequalities that $\alpha_{t}<\frac{1}{100}$ and $\beta_{t}<\frac{1}{100}$
for every $t\leq\eta\tau$.

It will be easier to analyze Algorithm if all colors have the same number of
edges at the start of an iteration. We will add now a 7th step in Algorithm to
ensure that all the remaining color classes have same number of edges,
$s_{t}=(1-\alpha_{t})s(t\delta)(1+\epsilon)q$.

  * 7.

For each remaining color class, if the number of edges in that color class is
more than $s_{t}$ after Step 6, then delete arbitrary edges of that color
class to ensure that it has exactly $s_{t}$ edges.

We will make sure the following two happen after the $t$-th iteration for
$1\leq t\leq\eta\tau$:

  1. 1.

The remaining color classes have size exactly:

$s_{t}=(1-\alpha_{t})s(t\delta)(1+\epsilon)q.$ (6.1)

  2. 2.

The degree of each survived vertex is at most:

$d_{t}=(1+\beta_{t})(1-t\delta)g(t\delta)q.$ (6.2)

We fix some $t$ with $0\leq t<\eta\tau$ for this and the next section and
assume that (6.1) and (6.2) hold for $t$ (note that before starting the 1st
iteration of Algorithm, we can run Step 7 with $t=0$ and make sure that (6.1)
and (6.2) hold). Our goal is to show that after the $(t+1)$-st iteration of
Algorithm, with positive probability, (6.1) and (6.2) will hold (for $t+1$).
In this section, we show certain concentration bounds that hold in the
$(t+1)$-st iteration, and in the subsequent section, these bounds will be used
to achieve our goal. We next wish to specify probabilities for Step 4 for the
$(t+1)$-st iteration, which requires us to estimate the probability a vertex
gets deleted in Step 3.

In the $(t+1)$-st iteration of Algorithm, the probability that a fixed edge
will be selected in Step 2 is exactly $\frac{\theta_{t+1}}{s_{t}}$ because the
corresponding color gets activated with probability $\theta_{t+1}$ and if a
color is activated then each of the $s_{t}$ edges of this color gets selected
with the same probability. Let $\mathscr{C}$ denote the set of all colors and
for all $\mathcal{C}\in\mathscr{C}$, denote the number of edges incident to a
vertex $v$ that are of color $\mathcal{C}$ by $d_{\mathcal{C}}(v)$. Thus, for
a fixed vertex $v$, the probability that $v$ is deleted in Step 3 is given by
$p^{\prime}_{v}=1-\prod_{\mathcal{C}\in\mathscr{C}}\left(1-d_{\mathcal{C}}(v)\cdot\frac{\theta_{t+1}}{s_{t}}\right)$.
Since $\sum_{\mathcal{C}\in\mathscr{C}}d_{\mathcal{C}}(v)$ is equal to the
degree $d_{t,v}$ of $v$ after the $t$-th iteration, it is easy to see the
following:

$p^{\prime}_{v}\leq\frac{d_{t,v}\theta_{t+1}}{s_{t}}.$ (6.3)

This together with $d_{t,v}\leq d_{t}$ implies that $p^{\prime}_{v}\leq
d_{t}\cdot\frac{\theta_{t+1}}{s_{t}}=\frac{\delta\cdot(1+\beta_{t})(1-t\delta)g(t\delta)q}{(1-t\delta)\cdot(1-\alpha_{t})s(t\delta)(1+\epsilon)q}=\gamma\frac{\delta
g(t\delta)(1+\beta_{t})}{s(t\delta)(1-\alpha_{t})}$ (recall that
$\gamma=\frac{1}{1+\epsilon}$). Thus, define $a_{t}$ as follows:

$a_{t}=\gamma\cdot\frac{\delta
g(t\delta)(1+\beta_{t})}{s(t\delta)(1-\alpha_{t})}.$ (6.4)

Next, we specify a probability for Step 4. For a fixed $t$, at the $(t+1)$-st
iteration we delete each vertex $v$ independently with probability $p_{v}$
such that $p^{\prime}_{v}+(1-p^{\prime}_{v})p_{v}=a_{t}$. Thus, $a_{t}$ is the
total probability by which each vertex gets deleted in Steps 3 and 4.

We next give certain values to the parameters $\epsilon$, $\delta$, and $\eta$
in terms of $q$ and $\Delta$, which will be used in this and the next section.
Recall that $\Delta\leq\frac{\sqrt{q}}{\left(\log q\right)^{9}}$. Define the
following:

$\epsilon=\left(\frac{\Delta^{2}}{q}\right)^{\frac{1}{6}}\left(\log
q\right)^{2},\;\;\;\;\;\;\eta=1-\left(\frac{\Delta^{2}}{q}\right)^{\frac{1}{6}}\log
q,\;\;\;\;\;\;\delta=2\left(\frac{\Delta^{2}}{q}\right)^{\frac{1}{3}}.$ (6.5)

Our analysis is inspired by the “nibble” technique introduced in Rödl’s
pioneering work [31], which was later developed by various authors. Our goal
is to show that we can make some deterministic choices by some probabilistic
arguments so that (6.1) and (6.2) hold after the $(t+1)$-st iteration. Next,
we state a few lemmas showing that such deterministic choices can be made.

For the convenience of writing, we define a notion “with very high
probability” (in short, w.v.h.p.). We say an event $A_{q}$ happens w.v.h.p. to
mean that the probability that $A_{q}$ occurs with probability at least
$1-e^{-\omega(\log q)}$, where $\omega(n)$ is any function whose ratio with
$n$ tends to infinity as $n$ tends to infinity.

######  Lemma 6.1.

In the $(t+1)$-st iteration, the number of edges deleted from a single color
class in Steps 3 and 4 combined is at most $2a_{t}s_{t}+2\Delta\sqrt{\delta
q}\log q$ w.v.h.p.

###### Proof.

Fix a color remaining at the start of the $(t+1)$-st iteration. Remember that
by assumption, the number of edges in that color class before starting the
$(t+1)$-st iteration is $s_{t}$. Let $S_{t+1}$ be the random variable denoting
the number of edges of that color right after Step 4 in the $(t+1)$-st
iteration. Thus, $L=s_{t}-S_{t+1}$ denotes the number of edges of the fixed
color that are removed because of Steps 3 and 4. Recall that every vertex gets
deleted with probability $a_{t}$ in Steps 3 and 4. For convenience, let
$\mathcal{H}$ denote the set of edges in the fixed color class before starting
the $(t+1)$-st iteration.

Observe that $\mathbb{E}(L)\leq\sum_{e\in\mathcal{H}}2a_{t}=2a_{t}s_{t}$. To
show concentration of $L$, we use Talagrand’s inequality (i.e., Theorem 3.3).
The random variable $L$ can be seen as a function with domain $\Omega$, where
$\Omega=\prod_{\mathcal{C}\in\mathscr{C}}\Omega_{\mathcal{C}}\times\prod_{v\in
V(G)}\Omega_{v}$ with $\mathscr{C}$ being the set of colors and
$\Omega_{\mathcal{C}}$ (and $\Omega_{v}$) denoting the probability space for
the decision made for the color $\mathcal{C}$ in Steps 1 and 2 (and the vertex
$v$ in Step 4). If the decision for one of the $\Omega_{\mathcal{C}}$’s or
$\Omega_{v}$’s is altered, then $L$ will be affected by at most $2\Delta$.
Thus, $L$ is $2\Delta$-Lipschitz. Furthermore, observe that $L$ is
1-certifiable. Indeed, for any edge $e$ removed with the fixed color, there
must either be another edge incident to $e$ in $T$ or one of the vertices in
$e$ is deleted in Step 4, and these events certify the removal of $e$. Hence,
using Theorem 3.3, we can conclude that the probability that $L$ deviates from
its mean by $\lambda=\Delta\sqrt{a_{t}s_{t}}\log
q\geq\frac{\lambda}{2}+60\cdot(2\Delta)\cdot\sqrt{\mathbb{E}(L)}$ is at most
$4e^{-\frac{(\lambda/2)^{2}}{8(2\Delta)^{2}a_{t}s_{t}}}=e^{-\omega(\log q)}$.

Now, Lemma 6.1 follows by noting the following inequality:

$a_{t}s_{t}=\gamma\frac{\delta
g(t\delta)(1+\beta_{t})}{s(t\delta)(1-\alpha_{t})}\cdot(1-\alpha_{t})s(t\delta)(1+\epsilon)q\leq
2\delta q.$

∎

######  Lemma 6.2.

At the end of $(t+1)$-st iteration, for each reamaining vertex $v$, w.v.h.p.
the degree of $v$ is at most
$d_{t}(1-a_{t})\left(1-\theta_{t+1}\right)+2d_{t}\theta_{t+1}^{2}\log^{2}q+4\Delta\sqrt{\delta
q}\log q$.

###### Proof.

First of all, Step 7 can only decrease the degrees of any vertex; thus, it is
enough to prove Lemma 6.2 before Step 7. For each remaining vertex $v$ after
the $t$-th iteration, we define $D_{t+1,v}$ to be the random variable denoting
the degree of $v$ after Step 6 in the $(t+1)$-st iteration. Throughout the
proof of this lemma, for a simpler analysis, we use an alternative way to
execute Algorithm that produces exactly the same outcomes (more precisely, the
outcome space has the same probability distribution for both processes). We
will do the first four steps in a different order, namely Steps 2, 4, 1, and
then 3 (this can be done because these steps can essentially be done
independently). We next elaborate on the exact process in the $(t+1)$-st
iteration executed in this way.

  1. $1^{\prime}$.

Select independently one edge from each remaining color class (instead of just
the activated ones as originally described in Algorithm) uniformly at random.
Denote by $H$ the set of all selected edges.

  2. $2^{\prime}$.

Independently select each vertices $v$ with probability $p_{v}$. Denote by $V$
the set of all selected vertices.

  3. $3^{\prime}$.

Activate each color class independently with probability
$\theta_{t+1}=\frac{\delta}{1-t\delta}$. For each activated color class, pick
the edge from $H$, which has this color. Denote by $T$ the set of all picked
edges.

  4. $4^{\prime}$.

Delete all the vertices of $V$ and all the vertices corresponding to the edges
in $T$. Remember that deleting vertices also deletes all incident edges.

Then, Steps 5 and 6 are done as described in the original Algorithm. The added
benefit to performing the steps in the above way is that, typically, the edge-
set $H$ in Step $1^{\prime}$ induces a graph with small degree. Appropriately
conditioned on this, when we activate color classes in Step $3^{\prime}$, we
obtain a much better certifiability constant for the application of
Talagrand’s inequality.

Fix a vertex $v$ throughout the proof of this lemma. Let $d$ denote the degree
of $v$ after the $t$-th iteration of Algorithm. By our assumption, we have
$d\leq d_{t}$. Let $X$ be the random variable denoting the number of neighbors
of $v$ selected in $V$ in Step $2^{\prime}$, and $L$ be the random variable
denoting the number of edges $uv$ adjacent to $v$ deleted in Steps
$4^{\prime}$ and 6 and $u$ is not selected in $V$ in Step $2^{\prime}$.
Clearly, $D_{t+1,v}=d-(X+L)$. Thus, we are interested in a good lower bound on
the random variable $X+L$.

We start by collecting a few w.v.h.p. events that will be helpful to prove
Lemma 6.2. For convenience, we say a vertex $u$ meets a color $\mathcal{C}$ if
there is an edge incident to $u$ that is colored with $\mathcal{C}$. Define
$U$ as the set of vertices $u$ such that $u$ and $v$ meet some common color
(notice that $N(v)\subseteq U$). Denote by $d_{H}(u)$ the number of edges in
$H$ that are incident to $u$. Define $Z$ as the number of neighbors $u\in
N(v)$ such that the edge in $H$ with the same color as $uv$ is incident to
$u$. To facilitate the analysis of the random variable $L$, we will consider
the random variable $X^{\prime}=\theta_{t+1}\sum_{u\in N}d_{H}(u)$, where $N$
denotes the (random) subset of $N(v)$ containing all the vertices which are
not selected in Step $2^{\prime}$. In the proof of the following claim, we
often use the observation that $d_{t}\leq 2s_{t}$.

######  Claim 6.3.

The following events hold w.v.h.p.

  1. $F_{1}:$

every vertex $u\in U$ satisfies that $d_{H}(u)\leq\log q$, and $\sum_{u\in
N(v)}d_{H}(u)\leq 3d_{t}$.

  2. $F_{2}:$

$Z\leq\Delta\log q$.

  3. $F_{3}:$

$X\geq\sum_{u\in N(v)}p_{u}-\sqrt{\delta q}\log q$.

  4. $F_{4}:$

$X^{\prime}\geq\left(\theta_{t+1}\sum_{u\in
N(v)}\frac{d_{t,u}}{s_{t}}(1-p_{u})\right)-\sqrt{\delta q}\log q$, where
$d_{t,u}$ denotes the degree of $u$ after the $t$-th iteration.

###### Proof.

Clearly, $|U|\leq 2(1+\epsilon)q^{2}$. To see that $F_{1}$ holds w.v.h.p.,
observe that each edge is selected in Step $1^{\prime}$ with probability
exactly $\frac{1}{s_{t}}$. Thus, for each vertex $u$, we have
$\mathbb{E}(d_{H}(u))\leq\frac{d_{t}}{s_{t}}\leq 2$. Clearly, $d_{H}(u)$ is a
random variable with domain
$\Omega=\prod_{\mathcal{C}\in\mathscr{C}}\Omega_{\mathcal{C}}$ where
$\Omega_{\mathcal{C}}$ denotes the probability space for the random edge
chosen from the color class $\mathcal{C}$. It is straightforward to check that
$d_{H}(u)$ is 1-Lipschitz and 1-certifiable. Thus, using Theorem 3.3, we have
that $\mathbb{P}[d_{H}(u)\geq\log q]=e^{-\omega(\log q)}$. Now, by a simple
union bound over all vertices in $U$, we conclude that the first part of
$F_{1}$ holds w.v.h.p.

Define the random variable $Y^{\prime}=\sum_{u\in N(v)}d_{H}(u)$. Note that
$\mathbb{E}(Y^{\prime})\leq 2d_{t}$. Clearly, $Y^{\prime}$ is a random
variable with domain
$\Omega=\prod_{\mathcal{C}\in\mathscr{C}}\Omega_{\mathcal{C}}$. It is easy to
check that $Y^{\prime}$ is 2-Lipschitz and 1-certifiable. Thus, apply Theorem
3.3 to conclude that $Y^{\prime}$ deviates from its expectation by at least
$d_{t}\geq\frac{d_{t}}{2}+60\cdot 2\cdot\sqrt{\mathbb{E}(Y^{\prime})}$ is at
most $4e^{-\frac{d_{t}^{2}}{4\cdot 8\cdot 4\cdot 2d_{t}}}=e^{-\omega(\log
q)}$. This proves that the second part of $F_{1}$ holds w.v.h.p.

Note that $\mathbb{E}(Z)\leq\sum_{u\in
N(v)}\frac{\Delta}{s_{t}}\leq\Delta\cdot\frac{d_{t}}{s_{t}}\leq 2\Delta$.
Clearly, $Z$ is a random variable with domain
$\Omega=\prod_{\mathcal{C}\in\mathscr{C}}\Omega_{\mathcal{C}}$. It is again
easy to check that $Z$ is 1-Lipschitz and 1-certifiable. Thus, apply Theorem
3.3 to conclude that $Z$ deviates from its expectation by at least
$\frac{1}{2}\Delta\log q\geq\frac{1}{4}\Delta\log q+60\sqrt{\mathbb{E}(Z)}$ is
at most $4e^{-\frac{\Delta^{2}\log^{2}q}{16\cdot 8\cdot
2\Delta}}=e^{-\omega(\log q)}$. Thus, w.v.h.p. it holds that $|Z|\leq
2\Delta+\frac{1}{2}\Delta\log q\leq\Delta\log q$.

Next, observe that $\mathbb{E}(X)=\sum_{u\in N(v)}p_{u}\leq a_{t}d_{t}$.
Observe that $X$ is the sum of at most $d_{t}$ Bernoulli random variables with
probability at most $a_{t}$. So, by using standard Chernoff bound (Theorem
3.1), the probability that $X$ deviates by more than
$\frac{1}{2}\sqrt{a_{t}d_{t}}\log q\leq\sqrt{\delta q}\log q$ from its
expectation is at most $e^{-\omega(\log q)}$, where we use the following
inequality:

$a_{t}d_{t}=\gamma\frac{\delta
g(t\delta)(1+\beta_{t})}{s(t\delta)(1-\alpha_{t})}\cdot(1+\beta_{t})(1-t\delta)g(t\delta)q\leq
2\delta q.$

To show that the event $F_{4}$ holds w.v.h.p, we condition on the events
$F_{1}$ and $F^{\prime}$, where $F^{\prime}$ denotes the event that the random
variable $Y=\sum_{u\in N(v)}d_{H}(u)(1-p_{u})$ satisfies the following:

$Y\geq\left(\sum_{u\in
N(v)}\frac{d_{t,u}}{s_{t}}(1-p_{u})\right)-\sqrt{d_{t}}\log q.$

Note that $\mathbb{E}(Y)=\sum_{u\in N(v)}\frac{d_{t,u}}{s_{t}}(1-p_{u})\leq
d_{t}^{2}/s_{t}\leq 2d_{t}$. Clearly, $Y$ is a random variable with domain
$\Omega=\prod_{\mathcal{C}\in\mathscr{C}}\Omega_{\mathcal{C}}$. It is easy to
check that $Y$ is 2-Lipschitz and 1-certifiable. Thus, apply Theorem 3.3 to
conclude that $Y$ deviates from its expectation by at least $\sqrt{d_{t}}\log
q\geq\frac{1}{2}\sqrt{d_{t}}\log q+60\cdot 2\cdot\sqrt{\mathbb{E}(Y)}$ is at
most $4e^{-\frac{d_{t}\log^{2}q}{4\cdot 8\cdot 4\cdot 2d_{t}}}=e^{-\omega(\log
q)}$.

Since the events $F_{1}$ and $F^{\prime}$ hold w.v.h.p., it is enough to prove
that $F_{4}$ occurs w.v.h.p. conditioned on $F_{1}\wedge F^{\prime}$. Fix any
choice of $H=H^{\prime}$ in Step $1^{\prime}$ such that $F_{1}$ and
$F^{\prime}$ hold. For each $u\in N(v)$, let the number of edges in
$H^{\prime}$ incident to $u$ be $l(u)$. Thus, we have the following two
inequalities:

  1. 1.

Every vertex $u\in N(v)$ satisfies that $l(u)\leq\log q$.

  2. 2.

$\sum_{u\in N(v)}l(u)(1-p_{u})\geq\left(\sum_{u\in
N(v)}\frac{d_{t,u}}{s_{t}}(1-p_{u})\right)-\sqrt{d_{t}}\log q$.

Observe that $\mathbb{E}(X^{\prime}|H^{\prime})=\theta_{t+1}\sum_{u\in
N(v)}l(u)(1-p_{u})$. Furthermore, conditioning on $H^{\prime}$, we can prove a
concentration bound on $X^{\prime}$ using Theorem 3.3. Consider the random
variable $X^{\prime\prime}=\sum_{u\in N}l(u)$, which is basically same as
$\frac{X^{\prime}}{\theta_{t+1}}$ conditioned on $H^{\prime}$. By 1, we have
$\mathbb{E}(X^{\prime\prime})=\sum_{u\in N(v)}l(u)(1-p_{u})\leq d_{t}\log q$.
The random variable $X^{\prime\prime}$ can be seen as a function with domain
$\Omega=\prod_{u\in N(v)}\Omega_{u}$ with $\Omega_{u}$ denoting the
probability space for the decision made for the vertex $u$ in Step
$2^{\prime}$. If the decision for one of the $\Omega_{u}$’s is altered, then
$X^{\prime\prime}$ will be affected by at most $\log q$ because of 1. Thus,
$X^{\prime\prime}$ is $(\log q)$-Lipschitz. Furthermore, it is easy to see
that $X^{\prime\prime}$ is 1-certifiable. Hence, using Theorem 3.3, we can
conclude that the probability that $X^{\prime\prime}$ deviates from its mean
by $\lambda=\sqrt{d_{t}}\log^{2}q\geq\frac{\lambda}{2}+60\cdot\log
q\cdot\sqrt{\mathbb{E}(X^{\prime\prime})}$ is at most
$4e^{-\frac{(\lambda/2)^{2}}{8(\log
q)^{2}\mathbb{E}(X^{\prime\prime})}}=e^{-\omega(\log q)}$. This implies that
w.v.h.p. the following holds conditioned on $H^{\prime}$:

$X^{\prime}\geq\theta_{t+1}\sum_{u\in
N(v)}l(u)(1-p_{u})-\theta_{t+1}\sqrt{d_{t}}\log^{2}q.$

This, together with 2, gives us the following:

$\displaystyle\mathbb{P}\left[X^{\prime}\leq\left(\theta_{t+1}\sum_{u\in
N(v)}\frac{d_{t,u}}{s_{t}}(1-p_{u})\right)-2\theta_{t+1}\sqrt{d_{t}}\log^{2}q\;\bigg{|}H^{\prime}\right]=e^{-\omega(\log
q)}.$ (6.6)

Note the following:

$\theta_{t+1}\sqrt{d_{t}}=\frac{\delta}{1-t\delta}\sqrt{(1+\beta_{t})(1-t\delta)g(t\delta)q}\leq\frac{2\delta\sqrt{q}}{\sqrt{1-\eta}}\leq\frac{\sqrt{\delta
q}}{2\log q},$ (6.7)

where the last inequality can be checked by plugging in the values of the
parameters set in (6.5). Using (6.7) and the fact that the bound in (6.6)
holds for any choice of $H^{\prime}$ satisfying $F_{1}$ and $F^{\prime}$, we
have the following conditioned on $F_{1}\wedge F^{\prime}$:

$\displaystyle\mathbb{P}\left[X^{\prime}\leq\left(\theta_{t+1}\sum_{u\in
N(v)}\frac{d_{t,u}}{s_{t}}(1-p_{u})\right)-\sqrt{\delta q}\log
q\right]=e^{-\omega(\log q)}.$

This finishes the proof of Claim 6.3. ∎

We next show the concentration of $L$ conditioned on all the w.v.h.p. events
in Claim 6.3. Formally, let $F$ denote the event that the events $F_{1}$,
$F_{2}$, $F_{3}$, and $F_{4}$ hold. Next, we show the concentration bound on
$L$ conditioning on this event $F$, which holds w.v.h.p. Lemma 6.2 follows
from the following claim.

######  Claim 6.4.

Conditioned on $F$, at the end of Step 6 of the $(t+1)$-st iteration, w.v.h.p.
the degree of the vertex $v$ after $t$-th iteration is at most
$d_{t}(1-a_{t})\left(1-\theta_{t+1}\right)+2d_{t}\theta_{t+1}^{2}\log^{2}q+4\Delta\sqrt{\delta
q}\log q$.

###### Proof.

Fix any choice of $H^{\prime}$ in Step $1^{\prime}$ and $V^{\prime}$ in Step
$2^{\prime}$ such that $F$ holds. For each $u\in N(v)$, let the number of
edges in $H^{\prime}$ incident to $u$ be $l(u)$. Suppose that $Z^{\prime}$ is
the set of neighbors $u\in N(v)$ such that the edge in $H^{\prime}$ with the
same color as $uv$ is incident to $u$. Let $N=N(v)\setminus V^{\prime}$ and
$N^{\prime}=N(v)\setminus(V^{\prime}\cup Z^{\prime})$.

Fix a neighbor $u\in N^{\prime}$. The probability that one of the edges
incident to $u$ is picked in Step $3^{\prime}$ is exactly
$1-\left(1-\theta_{t+1}\right)^{l(u)}\geq
l(u)\theta_{t+1}-l(u)^{2}\theta_{t+1}^{2}$. Thus, the next task remaining is
to calculate the probability that the edge $uv$ will be deleted in Step 6, and
simultaneously no edge incident to the vertex $u$ gets picked in Step
$3^{\prime}$. For the convenience of writing, let $A$ denote the event that an
edge of the same color as $uv$ is picked in the partial rainbow matching from
$T$ in Step 5. Let $B$ denote the event that none of the edges incident to $u$
gets deleted in Step $3^{\prime}$. We are interested in getting a good lower
bound on $\mathbb{P}\left[A\cap B\right]$.

Let $e$ denote edge in $H^{\prime}$ that has the same color as $uv$ (clearly
$e$ is not incident to $u$ since $u\notin Z^{\prime}$. The event $A\cap B$ is
equivalent to the following event:

  1. (i)

the color of $uv$ is activated in Step $3^{\prime}$ and

  2. (ii)

none of the colors corresponding to the edges in $H^{\prime}$ incident to $u$
or $e$ is activated in Step $3^{\prime}$.

Observe that the event of (i) and the event that none of the edges adjacent to
$e$ is picked in Step $3^{\prime}$ ensures that $e$ is added to the rainbow
matching in Step 5; hence the edge $uv$ is deleted in Step 6. Thus, we have
$\mathbb{P}\left[A\cap
B\right]\geq\theta_{t+1}\left(1-\theta_{t+1}\right)^{3\log q}$, because the
number of edges in $H^{\prime}$ that are incident to $u$ or $e$ is at most
$3\log q$.

Hence, conditioned on $H^{\prime}$ and $V^{\prime}$, we have the following:

$\displaystyle\mathbb{E}(L\;|H^{\prime},V^{\prime})$
$\displaystyle\geq\sum_{u\in
N^{\prime}}\left(l(u)\theta_{t+1}-l(u)^{2}\theta_{t+1}^{2}+\theta_{t+1}\left(1-\theta_{t+1}\right)^{3\log
q}\right)$ $\displaystyle\geq\sum_{u\in
N}\left(l(u)\theta_{t+1}-\log^{2}q\cdot\theta_{t+1}^{2}+\theta_{t+1}-3\log
q\cdot\theta_{t+1}^{2}\right)-\sum_{u\in Z^{\prime}}1$ (6.8)
$\displaystyle\geq\sum_{u\in
N}\left(\theta_{t+1}+l(u)\theta_{t+1}\right)-d_{t}\theta_{t+1}^{2}(\log^{2}q+3\log
q)-\Delta\log q$ (6.9) $\displaystyle\geq\sum_{u\in
N}\left(\theta_{t+1}+l(u)\theta_{t+1}\right)-2d_{t}\theta_{t+1}^{2}\log^{2}q-\sqrt{\delta
q}\log q,$ (6.10)

where (6.8) holds because $l(u)\leq\Delta\log q$ (since the event $F_{1}$ from
Claim 6.3 holds). In (6.9), we use $|Z^{\prime}|\leq\Delta\log q$ (since the
event $F_{2}$ from Claim 6.3 holds). In (6.10), we use the fact that
$\Delta\leq\sqrt{\delta q}$.

Furthermore, conditioning on $H^{\prime},V^{\prime}$, we can prove a
concentration bound on $L$ using Theorem 3.3. Note that the probability of a
vertex $u$ is deleted in Step $4^{\prime}$ is at most $l(u)\theta_{t+1}$ and
the probability that an edge with a fixed color is picked in Step 5 is most
$\theta_{t+1}$. Thus, using the fact that $\sum_{u\in N(v)}l(u)\leq 3d_{t}$
(since $H^{\prime}$ satisfies $F_{1}$ from Claim 6.3), we have:

$\mathbb{E}(L\;|H^{\prime},V^{\prime})\leq\sum_{u\in
N(v)}\left(l(u)\theta_{t+1}+\theta_{t+1}\right)\leq 4d_{t}\theta_{t+1}\leq
5\delta q.$

The random variable $L$ conditioned on $H^{\prime},V^{\prime}$ can be seen as
a function with domain
$\Omega=\prod_{\mathcal{C}\in\mathscr{C}}\Omega_{\mathcal{C}}$ with
$\Omega_{\mathcal{C}}$ denoting the probability space for the decision made
for color $\mathcal{C}$. If the decision for one of the
$\Omega_{\mathcal{C}}$’s is altered, then $L$ will be affected by at most
$\Delta+2\leq 3\Delta$. Thus, $L$ is $3\Delta$-Lipschitz. Furthermore, we
claim that $L$ is $(2\log q)$-certifiable. Indeed, for any vertex $u\in N$
removed in Step $4^{\prime}$, there must be an edge $e\in H^{\prime}$ incident
to $u$ whose color is activated in Step $3^{\prime}$, and none of the colors
(less than $2\log q$) corresponding to the edges in $H^{\prime}$ incident to
$e$ is picked. Thus, fixing the choices for these colors along with the color
of $e$ certifies the deletion of $u$ in Step $4^{\prime}$. Also, for any edge
$uv$ removed in Step $6$, the color of $uv$ is activated in Step $3^{\prime}$
and none of the colors (less than $2\log q$) corresponding to the edges in
$H^{\prime}$ incident to $e$ is picked, where $e$ is the edge in $H^{\prime}$
with the same color as $uv$. Thus, fixing the choices for these colors along
with the color of $uv$ certifies the deletion of $uv$ in Step $6$. This
establishes that $L$ is $(2\log q)$-certifiable. Hence, using Theorem 3.3, we
can conclude that the probability that $L$ deviates from its mean by
$\lambda=\Delta\sqrt{\delta q}\log q\geq\frac{\lambda}{2}+60\cdot
3\Delta\cdot\sqrt{2\log q\cdot\mathbb{E}(L\;|H^{\prime},V^{\prime})}$ is at
most $4e^{-\frac{(\lambda/2)^{2}}{8(3\Delta)^{2}\cdot 2\log
q\cdot\mathbb{E}(L\;|H^{\prime},V^{\prime})}}=e^{-\omega(\log q)}$. Thus, we
have the following:

$\displaystyle\mathbb{P}\left[L\geq\mathbb{E}(L\;|H^{\prime},V^{\prime})-\Delta\sqrt{\delta
q}\log q\;\bigg{|}H^{\prime},V^{\prime}\right]=1-e^{-\omega(\log q)}.$ (6.11)

Conditioning on $H^{\prime},V^{\prime}$ and assuming that the event in (6.11)
holds, by (6.10) we have the following:

$\displaystyle D_{t+1,v}=|N|-L\leq\sum_{u\in
N}\left(1-\theta_{t+1}-l(u)\theta_{t+1}\right)+2d_{t}\theta_{t+1}^{2}\log^{2}q+\sqrt{\delta
q}\log q+\Delta\sqrt{\delta q}\log q.$ (6.12)

Note that $\sum_{u\in
N}\left(1-\theta_{t+1}-l(u)\theta_{t+1}\right)=\left(1-\theta_{t+1}\right)|N|-\theta_{t+1}\sum_{u\in
N}l(u)$. Thus, we have:

$\displaystyle D_{t+1,v}$
$\displaystyle\leq\left(1-\theta_{t+1}\right)\sum_{u\in
N(v)}(1-p_{u})-\theta_{t+1}\sum_{u\in
N(v)}\frac{d_{t,u}}{s_{t}}\cdot(1-p_{u})+2d_{t}\theta_{t+1}^{2}\log^{2}q+(3+\Delta)\sqrt{\delta
q}\log q$ (6.13) $\displaystyle=\sum_{u\in
N(v)}(1-p_{u})\left(1-\theta_{t+1}-\frac{d_{t,u}\theta_{t+1}}{s_{t}}\right)+2d_{t}\theta_{t+1}^{2}\log^{2}q+(3+\Delta)\sqrt{\delta
q}\log q$ $\displaystyle\leq\sum_{u\in
N(v)}(1-p_{u})\left(1-\frac{d_{t,u}\theta_{t+1}}{s_{t}}\right)\left(1-\theta_{t+1}\right)+2d_{t}\theta_{t+1}^{2}\log^{2}q+4\Delta\sqrt{\delta
q}\log q$ $\displaystyle\leq\sum_{u\in
N(v)}(1-p_{u})\left(1-p^{\prime}_{u}\right)\left(1-\theta_{t+1}\right)+2d_{t}\theta_{t+1}^{2}\log^{2}q+4\Delta\sqrt{\delta
q}\log q$ (6.14) $\displaystyle=\sum_{u\in
N(v)}(1-a_{t})\left(1-\theta_{t+1}\right)+2d_{t}\theta_{t+1}^{2}\log^{2}q+4\Delta\sqrt{\delta
q}\log q,$ (6.15)

where in (6.13), we use the fact that the choices of $H^{\prime}$ and
$V^{\prime}$ satisfy the events $F_{3}$ and $F_{4}$ from Claim 6.3. In (6.14)
and (6.15), we use the inequality at 6.3 and the definition of $p_{u}$
(mentioned after 6.3) respectively.

Since the bounds in (6.11), (6.12), and (6.15) hold for any choices of
$H^{\prime}$ and $V^{\prime}$ satisfying $F$, we have the following
conditioned on $F$:

$\displaystyle\mathbb{P}\left[D_{t+1,v}\leq
d_{t}(1-a_{t})\left(1-\theta_{t+1}\right)+2d_{t}\theta_{t+1}^{2}\log^{2}q+4\Delta\sqrt{\delta
q}\log q\right]=1-e^{-\omega(\log q)}.$

This finishes the proof of Claim 6.4 and Lemma 6.2. ∎

∎

Recall our assumption that after the $t$-th iteration, the bounds in (6.1) and
(6.2) hold. As long as for the $(t+1)$-st iteration, there is a positive
probability by which the conclusions of Lemma 6.1 for each color class and
Lemma 6.2 for each vertex hold, then we can choose a particular possible
output satisfying these. Using a simple union bound to show this is impossible
since we do not assume any bound on the number of colors or vertices in the
graph. However, utilizing the local lemma, we can show that with positive
probability, Lemma 6.1 holds for every color, and Lemma 6.2 holds for every
vertex simultaneously.

######  Lemma 6.5.

The following happens with positive probability in the $(t+1)$-st iteration.

  1. 1.

The number of edges deleted from each of the color classes in Steps 3 and 4
combined is at most $2a_{t}s_{t}+2\Delta\sqrt{\delta q}\log q$.

  2. 2.

The degree of each remaining vertex is at most
$d_{t}(1-a_{t})\left(1-\theta_{t+1}\right)+2d_{t}\theta_{t+1}^{2}\log^{2}q+4\Delta\sqrt{\delta
q}\log q$.

###### Proof.

Let $\Gamma$ be the graph on $\mathscr{C}$, the set of all colors, where two
colors are joined if a vertex in $G$ meets both colors. For each
$\mathcal{C}\in\mathscr{C}$, define the ‘bad events’ $B_{\mathcal{C}}$ to be
the event that at least one of the following events happens:

  * •

for the color class $\mathcal{C}$ the assertion of (1) does not hold,

  * •

there is a vertex $v$ that meets the color class $\mathcal{C}$ such that $v$
violates the assertion of (2).

It is straightforward to see that to prove Lemma 6.5, it is enough to show
that with positive probability, none of the events $B_{\mathcal{C}}$ happen.
Note that For each $\mathcal{C}\in\mathscr{C}$, the event $B_{\mathcal{C}}$ is
determined by the random choices involving the color classes
$\mathcal{C}^{\prime}$ with $d_{\Gamma}(\mathcal{C},\mathcal{C}^{\prime})\leq
2$ (where $d_{\Gamma}(\mathcal{C},\mathcal{C}^{\prime})$ denotes the distance
between $\mathcal{C}$ and $\mathcal{C}^{\prime}$ in the graph $\Gamma$, i.e.,
the length of the shortest path in between $\mathcal{C}$ and
$\mathcal{C}^{\prime}$). We claim that the graph $\Gamma^{4}$, defined by the
graph on $\mathscr{C}$ with edges between $\mathcal{C}$ and
$\mathcal{C}^{\prime}$ if and only if
$d_{\Gamma}(\mathcal{C},\mathcal{C}^{\prime})\leq 4$, is a dependency graph
for the events $\\{B_{\mathcal{C}}\\}_{C\in\mathscr{C}}$. This is because if
$\mathcal{C}\mathcal{C}^{\prime}\notin\Gamma^{4}$, then the events
$B_{\mathcal{C}}$ and $B_{\mathcal{C}^{\prime}}$ are determined by disjoint
random choices. Observe that the maximum degree of $\Gamma$ is at most
$4q^{2}$, and consequently, the maximum degree of $\Gamma^{4}$ is at most
$256q^{8}$. By Lemmas 6.1 and 6.2 and a simple union bound, for all
$\mathcal{C}\in\mathscr{C}$, we have
$\mathbb{P}[B_{\mathcal{C}}]=e^{-\omega(\log q)}$. Thus, by a simple
application of Lemma 3.4, we conclude that with positive probability, none of
the events $B_{\mathcal{C}}$ happen, which is what we desired to show to
finish the proof of Lemma 6.5. ∎

Lemma 6.5 implies that there is an output of the $(t+1)$-st iteration of
Algorithm satisfying (1) and (2). Thus, we fix such an outcome and assume (1)
and (2) throughout the next section.

##  7 Estimating the error terms and greedy completion

To estimate the error terms in the parameters throughout Algorithm, let us
first estimate the error terms in the ideal expressions from the intuitive
analysis. Define the following parameters, which essentially ignore the error
terms $\alpha_{t}$ and $\beta_{t}$ in the expressions in (6.1), (6.2), and
(6.4).

$\tilde{s}_{t}=s(t\delta)(1+\epsilon)q\;\;\;\;\text{and}\;\;\;\;\tilde{d}_{t}=(1-t\delta)g(t\delta)q\;\;\;\;\text{and}\;\;\;\;\tilde{a}_{t}=\gamma\frac{\delta
g(t\delta)}{s(t\delta)}.$

We have the following couple of lemmas concerning the relations between these
three ideal functions.

######  Lemma 7.1.

We have that
$(1-2\tilde{a}_{t})\tilde{s}_{t}=\tilde{s}_{t+1}-\gamma^{2}\delta^{2}(1+\epsilon)q$.

###### Proof.

A routine calculation shows:

$\displaystyle(1-2\tilde{a}_{t})\tilde{s}_{t}$
$\displaystyle=\left(1-\frac{2\gamma\delta
g(t\delta)}{s(t\delta)}\right)s(t\delta)(1+\epsilon)q$
$\displaystyle=\left((1-\gamma t\delta)^{2}-2\gamma\delta(1-\gamma
t\delta)\right)(1+\epsilon)q$
$\displaystyle=\left((1-\gamma\delta(t+1))^{2}-\gamma^{2}\delta^{2}\right)(1+\epsilon)q$
$\displaystyle=\tilde{s}_{t+1}-\gamma^{2}\delta^{2}(1+\epsilon)q.$

∎

######  Lemma 7.2.

We have that
$\left(1-\tilde{a}_{t}\right)\left(1-\frac{\delta}{1-t\delta}\right)\tilde{d}_{t}=\tilde{d}_{t+1}$.

###### Proof.

A routine calculation shows:

$\displaystyle\left(1-\tilde{a}_{t}\right)\left(1-\frac{\delta}{1-t\delta}\right)\tilde{d}_{t}$
$\displaystyle=\left(1-\frac{\gamma\delta(1-\gamma t\delta)}{(1-\gamma
t\delta)^{2}}\right)\left(1-\frac{\delta}{1-t\delta}\right)(1-t\delta)g(t\delta)q$
$\displaystyle=(1-(t+1)\gamma\delta)(1-(t+1)\delta)q$
$\displaystyle=\tilde{d}_{t+1}.$

∎

Now we mention a couple of lemmas relating the error terms $\alpha_{t}$ and
$\beta_{t}$ we accumulate for estimating $d_{t}$ and $s_{t}$ as the process
goes. In other words, we will specify $y_{t}$ and $z_{t}$ such that
$d_{t}\leq\tilde{d}_{t}+y_{t}$ and $s_{t}\geq\tilde{s}_{t}-z_{t}$. We will
then define that $\alpha_{t}=\frac{z_{t}}{\tilde{s}_{t}}$ and
$\beta_{t}=\frac{y_{t}}{\tilde{d}_{t}}$.

Define $y_{0}=z_{0}=0$ and recursively define the following sequences for each
$0\leq t<\eta\tau$.

$\displaystyle y_{t+1}=y_{t}+2\delta^{2}q\log^{2}q\cdot\frac{1-\gamma
t\delta}{1-t\delta}+4\Delta\sqrt{\delta q}\log
q\;\;\;\text{and}\;\;\;z_{t+1}=z_{t}+\delta^{2}q+2\Delta\sqrt{\delta q}\log
q+\frac{2\delta}{1-t\delta}\cdot y_{t}.$

Furthermore, define $\alpha_{t}=\frac{z_{t}}{\tilde{s}_{t}}$ and
$\beta_{t}=\frac{y_{t}}{\tilde{d}_{t}}$ for each $t$. The following lemma
finally shows the validity of (6.1) and (6.2) for the $(t+1)$-st iteration,
which is what we needed to show that we can choose a desirable output from
Algorithm for each $t\leq\eta\tau$.

######  Lemma 7.3.

At the end of the $(t+1)$-st iteration, the following two holds:

  1. 1.

the degree of each survived vertex is at most $d_{t+1}$.

  2. 2.

the remaining color classes have size exactly $s_{t+1}$.

###### Proof.

Starting with the conclusion of (2) from Lemma 6.5 and noting that
$a_{t}=\tilde{a}_{t}\cdot\frac{1+\beta_{t}}{1-\alpha_{t}}\geq\tilde{a}_{t}$, a
routine calculation shows the following bound on the degree $d_{t+1,v}$ of $v$
after the $(t+1)$-st iteration.

$\displaystyle d_{t+1,v}$ $\displaystyle\leq
d_{t}\cdot(1-\tilde{a}_{t})\left(1-\theta_{t+1}\right)+2d_{t}\theta_{t+1}^{2}\log^{2}q+4\Delta\sqrt{\delta
q}\log q$
$\displaystyle=\left(\tilde{d}_{t}+y_{t}\right)\left((1-\tilde{a}_{t})\left(1-\theta_{t+1}\right)+2\theta_{t+1}^{2}\log^{2}q\right)+4\Delta\sqrt{\delta
q}\log q$
$\displaystyle\leq\tilde{d}_{t}(1-\tilde{a}_{t})\left(1-\theta_{t+1}\right)+2\tilde{d}_{t}\theta_{t+1}^{2}\log^{2}q+y_{t}+4\Delta\sqrt{\delta
q}\log q$ (7.1)
$\displaystyle=\tilde{d}_{t+1}+y_{t}+2\delta^{2}q\log^{2}q\cdot\frac{1-\gamma
t\delta}{1-t\delta}+4\Delta\sqrt{\delta q}\log q$
$\displaystyle=\tilde{d}_{t+1}+y_{t+1}=(1+\beta_{t+1})\tilde{d}_{t+1}=d_{t+1},$

where in (7.1), we use the following:

$\displaystyle(1-\tilde{a}_{t})\left(1-\theta_{t+1}\right)+2\theta_{t+1}^{2}\log^{2}q\leq
1-\theta_{t+1}+2\theta_{t+1}^{2}\log^{2}q$
$\displaystyle=1-\theta_{t+1}\left(1-2\theta_{t+1}\log^{2}q\right)$
$\displaystyle=1-\theta_{t+1}\left(1-\frac{2\delta\log^{2}q}{1-t\delta}\right)$
$\displaystyle\leq
1-\theta_{t+1}\left(1-\frac{2\delta\log^{2}q}{1-\eta}\right)\leq 1.$

Next, starting with the conclusion of (1) from Lemma 6.5, the size of each
remaining color class after Step 4 of the $(t+1)$-st iteration is at least the
following:

$\displaystyle(1-2a_{t})s_{t}-2\Delta\sqrt{\delta q}\log q$
$\displaystyle=\left(1-2\tilde{a}_{t}\frac{1+\beta_{t}}{1-\alpha_{t}}\right)(1-\alpha_{t})\tilde{s}_{t}-2\Delta\sqrt{\delta
q}\log q$
$\displaystyle=(1-2\tilde{a}_{t})\tilde{s}_{t}-\alpha_{t}\tilde{s}_{t}-2\tilde{a}_{t}\beta_{t}\tilde{s}_{t}-2\Delta\sqrt{\delta
q}\log q$
$\displaystyle=\tilde{s}_{t+1}-\gamma^{2}\delta^{2}(1+\epsilon)q-z_{t}-\frac{2\gamma\delta(1+\epsilon)}{1-t\delta}\cdot
y_{t}-2\Delta\sqrt{\delta q}\log q$
$\displaystyle\geq\tilde{s}_{t+1}-\delta^{2}q-z_{t}-\frac{2\delta}{1-t\delta}\cdot
y_{t}-2\Delta\sqrt{\delta q}\log q$
$\displaystyle=\tilde{s}_{t+1}-z_{t+1}=(1-\alpha_{t+1})\tilde{s}_{t+1}=s_{t+1}.$

Thus, after Step 7 of the $(t+1)$-st iteration each remaining color class must
have exactly $s_{t+1}$ edges. ∎

Next, as we promised, we will find that the accumulated error terms are
negligible compared to the ideal parameter values, i.e.,
$y_{t}\ll\tilde{d}_{t}$ and $z_{t}\ll\tilde{s}_{t}$. This, in other words,
shows that $\beta_{t}<1/100$ and $\alpha_{t}<1/100$, which were used several
times in the previous section.

######  Lemma 7.4.

For each $t\leq\frac{\eta}{\delta}$, we have that
$y_{t}=o\left(\tilde{d}_{t}\right)$.

###### Proof.

We have the following:

$\displaystyle
y_{t}=\sum_{i=0}^{t-1}\left(2\delta^{2}q\log^{2}q\cdot\frac{1-\gamma
i\delta}{1-t\delta}+4\Delta\sqrt{\delta q}\log q\right)$ $\displaystyle\leq
2\delta q\log^{2}q\int_{0}^{t\delta}\frac{1-\gamma
x}{1-x}dx+4t\Delta\sqrt{\delta q}\log q$ $\displaystyle=2\delta
q\log^{2}q\left((1-\gamma)\log\left(\frac{1}{1-t\delta}\right)+\gamma
t\delta\right)+4t\Delta\sqrt{\delta q}\log q$ $\displaystyle\leq
2\delta\epsilon
q\log^{2}q\cdot\left(\log\left(\frac{1}{1-\eta}\right)\right)+2t\delta^{2}q\log^{2}q+4t\Delta\sqrt{\delta
q}\log q.$

Plugging in the parameter values in the above inequality, we get the
following:

$y_{t}\leq y_{\frac{\eta}{\delta}}\leq(\Delta q)^{\frac{2}{3}}\left(\log
q\right)^{5/2}.$ (7.2)

Plugging in the parameters in the expression for $\tilde{d}_{t}$, we have the
following:

$\tilde{d}_{t}\geq\tilde{d}_{\frac{\eta}{\delta}}=(1-\eta)(1-\gamma\eta)q\geq\frac{1}{2}(\Delta
q)^{\frac{2}{3}}\left(\log q\right)^{3}.$ (7.3)

By Equations (7.2) and (7.3), we conclude that Lemma 7.4 holds. ∎

######  Lemma 7.5.

For each $t\leq\frac{\eta}{\delta}$, we have that
$z_{t}=o\left(\tilde{s}_{t}\right)$.

###### Proof.

We have the following:

$\displaystyle z_{t}=\sum_{i=0}^{t-1}\left(\delta^{2}q+2\Delta\sqrt{\delta
q}\log q+\frac{2\delta}{1-i\delta}\cdot y_{i}\right)$ $\displaystyle\leq
t\delta^{2}q+2t\Delta\sqrt{\delta q}\log
q+2y_{t}\int_{0}^{t\delta}\frac{dx}{1-x}$ $\displaystyle\leq
t\delta^{2}q+2t\Delta\sqrt{\delta q}\log
q+2y_{t}\log\left(\frac{1}{1-\eta}\right).$

Similar to before, plugging in the parameter values in the above and using
(7.2), we get the following:

$z_{t}\leq z_{\frac{\eta}{\delta}}\leq(\Delta q)^{\frac{2}{3}}\left(\log
q\right)^{15/4}.$ (7.4)

Now, Lemma 7.5 can be seen to be true by noting the following:

$\tilde{s}_{t}\geq\tilde{s}_{\frac{\eta}{\delta}}=(1-\gamma\eta)^{2}(1+\epsilon)q\geq\frac{1}{2}(\Delta
q)^{\frac{2}{3}}\left(\log q\right)^{4}.$

∎

Finally, from (6.1) and (6.2), at the end of the $\frac{\eta}{\delta}$-th
iteration, the number of edges in any remaining color is at least
$s_{\frac{\eta}{\delta}}\geq\frac{1}{2}(\Delta q)^{\frac{2}{3}}\left(\log
q\right)^{4}$, and the maximum degree of the graph is at most
$d_{\frac{\eta}{\delta}}\leq 2(\Delta q)^{\frac{2}{3}}\left(\log
q\right)^{3}$. Now, it is easy to check that
$s_{\frac{\eta}{\delta}}>4ed_{\frac{\eta}{\delta}}$. Hence, at this point, we
invoke Proposition 3.5 to find a rainbow matching using the remaining colors
not yet picked in the partial matching built by Algorithm. This finishes the
proof of Theorem 1.9.

##  8 Proof of Theorem 1.12

In this section, we prove Theorem 1.12. We need to adjust Algorithm of Section
4 to apply for this theorem. In this entire section, we will work with the
algorithm given below and refer to it.

###  8.1 Algorithm

Assume that we are given a bipartite graph $G$ with the vertex set partition
$A\cup B$, $|A|=q$, and all the vertices in $A$ have degree at least
$(1+\epsilon)q$. Furthermore, $G$ is edge-colored with some colors such that
no two edges of the same color are incident to each other. We will provide a
randomized algorithm, which constructs a rainbow matching using almost all the
vertices in $A$ in several iterations. For the convenience of analyzing the
algorithm, we ensure that throughout the algorithm, the degree of each of the
remaining vertices in $A$ is the same at the start of each iteration. Thus, we
start with deleting arbitrary edges from $G$ to ensure that every vertex in
$A$ has degree exactly $(1+\epsilon)q$.

This algorithm is in terms of some parameter $\delta>0$, which will be
specified later. Define $\tau=\frac{1}{\delta}$. We follow the algorithm below
for $\eta\tau$ steps, for some $\eta<1$ to be specified later. For $1\leq
t\leq\eta\tau$, the $t$-th iteration of the algorithm is given below.

  1. 1.

Select independently $\delta q$ edges $e_{1},e_{2},\ldots,e_{\delta q}$
uniformly at random with replacement from among the remaining edges. Denote by
$T$ the set of all selected edges.

  2. 2.

For each edge $e_{i}\in T$, add it to the rainbow matching if $e_{i}$ is not
incident to any edge $e_{j}\in T$ for $j<i$ and $e_{i}$ does not have same
color as any edge $e_{j}\in T$ for $j<i$.

  3. 3.

Delete all the vertices in $A$ that are incident to the edges added in the
rainbow matching in the last step. Additionally, delete all the vertices in
$B$ that are incident to some edge in $T$. Deleting vertices always also
deletes all incident edges.

  4. 4.

With some probability (to be specified later), independently delete each
vertex in $B$. This will ensure that among Steps 3 and 4 combined, every
vertex in $B$ gets deleted with the same probability.

  5. 5.

For each edge $e\in T$, delete its color class from $G$. Here, deleting a
color class means deleting all the remaining edges of that color.

  6. 6.

With some probability (to be specified later), independently delete each color
class. This will ensure that among Steps 5 and 6 combined, every remaining
color class gets deleted with the same probability.

  7. 7.

At this point, every remaining vertex in $A$ will have degree at least
$s_{t}$, where $s_{t}$ will be specified later. For each remaining vertex $v$
in $A$ after Step 6, delete arbitrary edges incident to $v$ to ensure that $v$
has exactly $s_{t}$ edges incident to it.

We remark here that we do not have the flexibility of throwing vertices from
$A$ without using them because we need to use all of them at the end. As a
result, we needed to shift Step 5 of Algorithm in Section 4 to Step 2 here.
Furthermore, we needed to change Step 3 to the above form, where we delete
vertices only after adding the edges to the rainbow matching in the current
iteration. This makes our analysis slightly more complicated than last time.

###  8.2 Intuitive analysis

As before, we aim to show that if we run this randomized algorithm until we
have used almost all the vertices in $A$, then near the end, each remaining
vertices still has so many edges incident to it (relative to the number of
remaining vertices in $A$) that we can conclude via a simple greedy algorithm.
Similar to Section 5, we track the evolution of the degrees of the vertices
and the color class sizes.

Define $d_{0,v}$ to be the initial degree of $v$ in $G$. Note that
$d_{0,v}=(1+\epsilon)q$ for $v\in A$ and $d_{0,v}\leq q$ for $v\in B$. We will
define three functions $s(x)$, $g_{1}(x)$, and $g_{2}(x)$ such that after the
$t$-th iteration of the algorithm we have the following:

  1. 1.

Each surviving vertex in $A$ has degree exactly $s_{t}$111The readers would
expect to see $s_{t}$ (and analogously $d_{t}$) being used to track the
trajectory of size (and degree). Still, instead, we swap the roles because the
trajectory for the degree of vertices in $A$ (and size of color classes) in
this section turns out to be the same as ‘size’ (and ‘degree’) of Section 5.
This will be clear by the end of this subsection., which is approximately
$s(t\delta)(1+\epsilon)q$.

  2. 2.

Each surviving vertex $v\in B$ has degree $d_{t,v}$, which is approximately
$(1-t\delta)g_{1}(t\delta)d_{0,v}$.

  3. 3.

Each remaining color class has size is at most $d_{t}$, which is about
$(1-t\delta)g_{2}(t\delta)q$.

We outline a rough analysis below. Clearly $s(0)=1$, $g_{1}(0)=1$, and
$g_{2}(0)=1$. Assume that the $t$-th iteration is done, and the above three
properties are true after the $t$-th iteration. First, very few edges will be
discarded in Step 2 throughout the process. In other words, the number of
edges in the partial rainbow matching will be roughly $t\delta q$ after the
$t$-th round.

Because of Step 4, every vertex of $B$ is deleted with the same probability
among Steps 3 and 4 combined. This is done only for convenience in our
analysis; thus, we should set that probability (denote it by $b_{t}$) as low
as possible. In other words, we need to find the maximum probability a vertex
$v\in B$ can be deleted in Step 3 and set $b_{t}$ to be that maximum
probability. After the $t$-th iteration, the number of remaining vertices in
$A$ is at least $(1-t\delta)q$, so the number of remaining edges is at least
$(1-t\delta)qs_{t}$. Now if one picks an edge uniformly at random from $G$,
then the probability (denote by $p$) that one of the edges incident to $v\in
B$ will be picked is exactly $d_{t,v}$ divided by the total number of edges of
$G$, which is at most $\frac{d_{t,v}}{(1-t\delta)qs_{t}}$. Thus, the
probability that $v$ is not deleted in Step 3 is exactly $(1-p)^{\delta
q}\lesssim 1-\frac{\delta g_{1}(t\delta)d_{0,v}}{s(t\delta)(1+\epsilon)q}$.
Since $d_{0,v}\leq q$, we can define $b_{t}$ to be about $\frac{\delta
g_{1}(t\delta)q}{s(t\delta)(1+\epsilon)q}=\gamma\frac{\delta
g_{1}(t\delta)}{s(t\delta)}$, where $\gamma=\frac{1}{1+\epsilon}$.

Next, we similarly provide a probability (denote it by $a_{t}$) with which a
single color class will be deleted in Steps 5 and 6 combined. Any color class
will be deleted in Step 5 by probability $\leq\frac{\delta
qd_{t}}{(1-t\delta)qs_{t}}\approx\gamma\frac{\delta
g_{2}(t\delta)}{s(t\delta)}$, due to a simple union bound using the fact that
there are $\delta q$ edges picked in Step 1, relatively few conflicts in Step
2, and the number of edges remaining in the graph is at least
$(1-t\delta)qs_{t}$. Hence, we set $a_{t}$ to be about $\gamma\frac{\delta
g_{2}(t\delta)}{s(t\delta)}$.

We now analyze the change in $s_{t}$ to get a differential equation for the
function $s$. Any edge will be deleted in Steps 5 and 6 combined by
probability $a_{t}$. We also know that for every $v\in A$, each of its
neighbors gets deleted among Steps 3 and 4 with probability $b_{t}$. Thus,
neglecting small error terms due to lack of independence, we expect to have
the following:

$\displaystyle s_{t+1}-s_{t}$ $\displaystyle\approx-s_{t}(a_{t}+b_{t})$
$\displaystyle s^{\prime}(x)$
$\displaystyle=-\gamma\left(g_{1}(x)+g_{2}(x)\right).$ (8.1)

Next, let us estimate the change in $d_{t,v}$ to get a differential equation
for $g_{1}$. The probability that a single vertex in $A$ gets deleted in Step
3 is about $\frac{\delta q}{(1-t\delta)q}=\frac{\delta}{1-t\delta}$.
Furthermore, each edge will be deleted in Steps 5 and 6 by probability
$a_{t}$. Thus, neglecting small error terms due to lack of independence, the
degree of a vertex $v\in B$ is decreased by approximately
$\left[\frac{\delta}{1-t\delta}+\left(1-\frac{\delta}{1-t\delta}\right)a_{t}\right]d_{t,v}$.
This suggests the following behavior:

$\displaystyle d_{t+1,v}-d_{t,v}$
$\displaystyle\approx-\left[\frac{\delta}{1-t\delta}+\left(1-\frac{\delta}{1-t\delta}\right)a_{t}\right]d_{t,v}$
(8.2) $\displaystyle(\tau-t-1)\delta g_{1}((t+1)\delta)d_{0,v}-(\tau-t)\delta
g_{1}(t\delta)d_{0,v}$ $\displaystyle\approx-\delta
g_{1}(t\delta)d_{0,v}-(\tau-t-1)\delta\frac{\gamma\delta
g_{2}(t\delta)}{s(t\delta)}g_{1}(t\delta)d_{0,v}$
$\displaystyle\frac{g_{1}((t+1)\delta)-g_{1}(t\delta)}{\delta}$
$\displaystyle\approx-\gamma\cdot\frac{g_{1}(t\delta)g_{2}(t\delta)}{s(t\delta)}.$

The above suggests:

$g_{1}^{\prime}(x)=-\gamma\cdot\frac{g_{1}(x)g_{2}(x)}{s(x)}.$ (8.3)

We next estimate the change in $d_{t}$ to obtain a differential equation for
$g_{2}$. The probability that a single vertex $v\in A$ gets deleted in Step 3
is about $\frac{\delta q}{(1-t\delta)q}=\frac{\delta}{1-t\delta}$, and the
probability that a single vertex $v\in B$ gets deleted among Steps 3 and 4 is
$b_{t}$, and Thus, we can choose $d_{t+1}$ to be around
$\left(1-\left[\frac{\delta}{1-t\delta}+\left(1-\frac{\delta}{1-t\delta}\right)b_{t}\right]\right)d_{t}$,
where the expression is similar to (8.2). Hence, similarly, we expect the
following behavior:

$\displaystyle d_{t+1}-d_{t}$
$\displaystyle\approx-\left[\frac{\delta}{1-t\delta}+\left(1-\frac{\delta}{1-t\delta}\right)b_{t}\right]d_{t}$
$\displaystyle\frac{g_{2}((t+1)\delta)-g_{2}(t\delta)}{\delta}$
$\displaystyle\approx-\gamma\cdot\frac{g_{1}(t\delta)g_{2}(t\delta)}{s(t\delta)}.$

This, in turn, suggests:

$g_{2}^{\prime}(x)=-\gamma\frac{g_{1}(x)g_{2}(x)}{s(x)}.$ (8.4)

Equations (8.3) and (8.4) along with the initial conditions
$g_{1}(0)=g_{2}(0)$ imply that $g_{1}=g_{2}=g$. Combining with Equation (8.2),
we have the same equations and initial conditions as in Section 5. Thus, we
get $s(x)=(1-\gamma x)^{2}$ and $g_{1}(x)=g_{2}(x)=1-\gamma x$.

We show in the next section that the degrees of vertices and the sizes of
color classes are concentrated throughout the process, implying that we can
not get stuck as long as $t\leq\eta\tau$. Moreover, after the $\eta\tau$-th
iteration, the degree of any remaining vertex in $A$ is
$\approx(1-\gamma\eta)^{2}(1+\epsilon)q$, and the number of remaining vertices
in $A$ is about $q-\eta\tau\delta q=(1-\eta)q$. As long as
$(1-\gamma\eta)^{2}(1+\epsilon)q\gg 2(1-\eta)q$, we can finish the rainbow
matching greedily, which can be made true by choosing $1-\eta$ small enough
compared to $1-\gamma$.

###  8.3 Formal analysis

Throughout this section, we assume that $q$ is sufficiently large to support
our arguments. Similar to Section 6, we define $s(x)=(1-\gamma x)^{2}$ and
$g(x)=1-\gamma x$, where $\gamma=\frac{1}{1+\epsilon}$. Similar to Section 7,
the following are the ideal expressions from the intuitive analysis:

$\tilde{s}_{t}=s(t\delta)(1+\epsilon)q\;\;\;\;\text{and}\;\;\;\;\tilde{d}_{t}=(1-t\delta)g(t\delta)q\;\;\;\;\text{and}\;\;\;\;\tilde{a}_{t}=\gamma\frac{\delta
g(t\delta)}{s(t\delta)}.$

Similarly, Lemmas 7.1 and 7.2 continue to hold. We next introduce the
following error term:

$\alpha_{t}=\sqrt{\delta}\left(\left(1+\frac{10\delta}{(1-\gamma\eta)^{2}}\right)^{t}-1\right).$

We will make sure w.v.h.p. (recall the notion from Section 6) the following
events happen for $1\leq t\leq\eta\tau$:

  1. 1.

The survived vertices of $A$ have degree exactly:

$s_{t}=(1-\alpha_{t})\tilde{s}_{t}=(1-\alpha_{t})s(t\delta)(1+\epsilon)q.$
(8.5)

  2. 2.

The degree of each survived vertex in $B$ and the size of each remaining color
class both are at most:

$d_{t}=(1+\alpha_{t})\tilde{d}_{t}=(1+\alpha_{t})(1-t\delta)g(t\delta)q.$
(8.6)

We fix some $t$ with $0\leq t<\eta\tau$ for this subsection and assume that
(8.5) and (8.6) hold for $t$. Our goal is to show that after the $(t+1)$-st
iteration of the algorithm, w.v.h.p. (8.5) and (8.6) will continue to hold
(notice that by a simple union bound, this is enough to establish that
w.v.h.p. (8.5) and (8.6) hold for every $1\leq t\leq\eta\tau$). We will show
certain concentration bounds that hold in the $(t+1)$-st iteration that will
be used to achieve our goal. We start by specifying probabilities for Steps 4
and 6 for the $(t+1)$-st iteration.

In the $(t+1)$-st iteration, for a fixed remaining vertex $v\in B$, if one
picks an edge uniformly at random from $G$ in Step 1, then the probability
that one of the edges incident to $v$ will be picked is exactly the degree of
$v$ divided by the total number of edges of $G$, which is at most
$\frac{d_{t}}{(1-t\delta)qs_{t}}$. Thus, by a simple union bound, the
probability $p^{\prime}_{v}$ that the vertex $v$ is deleted in Step 3 is at
most $\delta q\cdot\frac{d_{t}}{(1-t\delta)qs_{t}}=\gamma\frac{\delta
g(t\delta)(1+\alpha_{t})}{s(t\delta)(1-\alpha_{t})}$. Define $a_{t}$ to be
$\gamma\frac{\delta g(t\delta)(1+\alpha_{t})}{s(t\delta)(1-\alpha_{t})}$. For
a fixed $t$, at the $(t+1)$-st iteration we delete each vertex $v\in B$ in
Step 4 independently with probability $p_{v}$ such that
$p^{\prime}_{v}+(1-p^{\prime}_{v})p_{v}=a_{t}$. Thus, $a_{t}$ is the total
probability by which each vertex in $B$ gets deleted in Steps 3 and 4.

In the $(t+1)$-st iteration, for a fixed remaining color class $\mathcal{C}$,
if one picks an edge uniformly at random from $G$ in Step 1, then the
probability that one of the edges of $\mathcal{C}$ will be picked is exactly
the number of edges of $\mathcal{C}$ divided by the total number of edges of
$G$, which is at most $\frac{d_{t}}{(1-t\delta)qs_{t}}$. Thus, by a simple
union bound, the probability $p^{\prime}_{\mathcal{C}}$ that the color class
$\mathcal{C}$ is deleted in Step 5 is at most $\delta
q\cdot\frac{d_{t}}{(1-t\delta)qs_{t}}=a_{t}$. For a fixed $t$, at the
$(t+1)$-st iteration we delete each color class $\mathcal{C}$ in Step 6
independently with probability $p_{\mathcal{C}}$ such that
$p^{\prime}_{\mathcal{C}}+(1-p^{\prime}_{\mathcal{C}})p_{\mathcal{C}}=a_{t}$.
Thus, each color class gets deleted by a total probability of $a_{t}$ in Steps
5 and 6.

We now fix the values of the parameters of this section. Let $\epsilon$ be a
fixed positive number less than $\frac{1}{10}$ (note that this can be assumed
in Theorem 1.12). Recall that $\gamma=\frac{1}{1+\epsilon}$ as mentioned
before. Let $\eta=1-\epsilon^{3}$ and $\delta=\frac{1}{\log q}$. Note that
$\epsilon$, $\theta$, $\gamma$, and $\eta$ are all fixed constants, where the
latter three constants are fixed once $\epsilon$ is fixed. On the other hand,
$\delta$ can be made arbitrarily small by picking sufficiently large $q$. As a
consequence, we have $\alpha_{t}\leq\frac{1}{100}$ for each $0\leq
t\leq\eta\tau$. This will be frequently used in this section.

We next have a few concentration bounds to control the degrees of vertices and
the sizes of color classes.

######  Lemma 8.1.

The number of edges discarded in Step 2 at the $(t+1)$-st iteration is at most
$\frac{3\delta^{2}q}{1-t\delta}$ w.v.h.p.

###### Proof.

For $i<j$, let $X_{i,j}$ be the indicator random variable for the event that
$e_{i}\in T$ and $e_{j}\in T$ are adjacent or have the same color. Clearly,
the total number of edges discarded in Step 2 is given by $X\leq\sum_{1\leq
i<j\leq\delta q}X_{i,j}$. Now for $i<j$, the probability of the event that
$X_{i,j}=1$ is at most $\max_{e\in G}f(e)$, where $f(e)$ is the probability
that a uniformly selected edge in $G$ is adjacent to $e$ or have the same
color as $e$. For any fixed edge $e$, the number of edges adjacent to $e$ is
at most $s_{t}+d_{t}$ and the number of edges which has the same color as $e$
is at most $d_{t}$. Thus, the probability that $X_{i,j}=1$ is at most
$\frac{s_{t}+2d_{t}}{(1-t\delta)qs_{t}}$. By using the linearity of
expectation, we get the following:

$\mathbb{E}(X)\leq\mathbb{E}\left(\sum_{1\leq i<j\leq\delta
q}X_{i,j}\right)=\sum_{1\leq i<j\leq\delta
q}\mathbb{P}[X_{i,j}=1]\leq\frac{(\delta
q)^{2}}{2}\cdot\frac{s_{t}+2d_{t}}{(1-t\delta)qs_{t}}.$ (8.7)

Observe the following:

$\frac{d_{t}}{s_{t}}=\frac{(1+\alpha_{t})(1-t\delta)g(t\delta)q}{(1-\alpha_{t})s(t\delta)(1+\epsilon)q}\leq\frac{3}{2}.$
(8.8)

Thus, from (8.7) and (8.8), we have
$\mathbb{E}(X)\leq\frac{2\delta^{2}q}{1-t\delta}$.

We now use Theorem 3.2 to show that the random variable $X$ is not much
greater than its expectation w.v.h.p. In the setting mentioned right before
Theorem 3.2, let $\mathcal{A}$ be the set of all remaining edges of $G$ at the
start of $(t+1)$-st iteration, $\mathcal{B}=\\{1,2,\ldots,\delta q\\}$, and
$\mathbb{P}[g(j)=e]$ is same for all edge $e$. The random variable $X$ is same
as the functional $L:\mathcal{A}^{\mathcal{B}}\rightarrow\mathbb{R}$ and the
corresponding martingale is $X_{0}=E(L),X_{1},\ldots,X_{\delta q}$, with
respect to the gradation $\emptyset\subset[1]\subset[2]\subset\ldots[\delta
q]$ (where $[n]$ denotes the set $\\{1,2,\ldots,n\\}$). If one edge is
replaced by some other edge in any one of the $\delta q$ coordinates, then $L$
will be affected by at most $4$; in other words, $4$ is an upper bound on the
Lipschitz constant of the martingale. By Theorem 3.2, we can conclude that the
probability that $L$ deviates from its mean by $\lambda=\delta^{2}q$ is at
most $2e^{-\frac{\lambda^{2}}{32\delta
q}}=2e^{-\frac{\delta^{3}q}{32}}=e^{-\omega(\log q)}$ (remember that
$\delta=\frac{1}{\log q}$). Thus, we conclude that w.v.h.p. it holds that
$X\leq\mathbb{E}(X)+\delta^{2}q\leq\frac{2\delta^{2}q}{1-t\delta}+\delta^{2}q\leq\frac{3\delta^{2}q}{1-t\delta}$.
∎

######  Corollary 8.2.

The total number of edges not added in the rainbow matching in Step 2
throughout the algorithm is at most $3\delta
q\log\left(\frac{1}{1-\eta}\right)$ w.v.h.p. Consequently, the number of
vertices left in $A$ after the $t$-th iteration is at most
$\left(1-t\delta+3\delta\log\left(\frac{1}{1-\eta}\right)\right)q$.

###### Proof.

By using Lemma 8.1, the total number is at most the following:

$\displaystyle\sum_{t=0}^{\frac{\eta}{\delta}-1}\frac{3\delta^{2}q}{1-t\delta}\leq
3\delta q\int_{0}^{\eta}\frac{dx}{1-x}=3\delta
q\log\left(\frac{1}{1-\eta}\right).$

∎

Next, we bound the degree of each survived vertex in $A$ throughout the
algorithm.

######  Lemma 8.3.

In the $(t+1)$-st iteration, the number of deleted edges incident to each
vertex in $A$ in Steps 3, 4, 5, and 6 combined is at most
$2a_{t}s_{t}+4\delta^{2}q$ w.v.h.p.

###### Proof.

Fix a vertex $v\in A$ at the start of the $(t+1)$-st iteration. By our
assumption, the number of edges incident to $v$ before starting the $(t+1)$-st
iteration is $s_{t}$. Let $S_{t+1}$ denote the number of edges right after
Step 6 in the $(t+1)$-st iteration. Thus, $s_{t}-S_{t+1}\leq L+X$, where $L$
is the random variable denoting the number of edges incident to $v$ that got
removed because of Steps 3 and 5, and $X$ is the same number because of Steps
4 and 6. We bound $L$ and $X$ separately.

For a fixed neighbor $w\in B$ of $v$, the probabilities that an edge $vw$ gets
removed due to the deletion of $w$ in Steps 3 and 4 are $p^{\prime}_{w}$ and
$p_{w}$, where $p^{\prime}_{w}+p_{w}=a_{t}+p^{\prime}_{w}p_{w}\leq
a_{t}+a_{t}^{2}$. Furthermore, for a fixed neighbor $w\in B$ of $v$, the
probabilities that an edge $vw$ gets deleted in Steps 5 and 6 are
$p^{\prime}_{\mathcal{C}(vw)}$ and $p_{\mathcal{C}(vw)}$, where
$\mathcal{C}(vw)$ denotes the color class containing the edge $vw$. We also
have
$p^{\prime}_{\mathcal{C}(vw)}+p_{\mathcal{C}(vw)}=a_{t}+p^{\prime}_{\mathcal{C}(vw)}p_{\mathcal{C}(vw)}\leq
a_{t}+a_{t}^{2}$.

Firstly, we have $\mathbb{E}(L)\leq\sum_{w\in
N(v)}\left(p^{\prime}_{w}+p^{\prime}_{\mathcal{C}(vw)}\right)$, because the
probability that an edge $vw$ gets deleted due to Steps 3 and 5 combined is at
most $p^{\prime}_{w}+p^{\prime}_{\mathcal{C}(vw)}$ by a simple union bound. To
show the concentration of $L$, we use the same sets $A$, $B$, and the same
distribution of $g$ as in the proof of Lemma 8.1. For the functional $L$, we
consider the martingale considered in Theorem 3.2. If one edge is replaced by
another in any of the $\delta q$ coordinates, then $L$ will be affected by at
most $2$. Thus, $2$ is an upper bound on the Lipschitz constant of the
underlying martingale. Hence, using Theorem 3.2, we can conclude that the
probability that $L$ deviates from its mean by $\lambda=\sqrt{\delta q}\log q$
is at most $2e^{-\frac{\lambda^{2}}{8\delta q}}=e^{-\omega(\log q)}$.

We analyze the behavior of $X$ by stochastically dominating it with a simpler
random variable which counts the number of edges incident to the vertex $v$
that are deleted in Steps 4 and 6 without deleting anything in Steps 3 and 5
(this is done to avoid conditioning on $L$). Clearly, $X$ is upper bounded by
$Y=\sum_{w\in N(v)}\left(Y_{w}+Y_{\mathcal{C}(vw)}\right)$, where $Y_{w}$ is
the indicator random variable of the event that the vertex $w$ gets deleted in
Step 4, and $Y_{\mathcal{C}(vw)}$ is the indicator random variable of the
event that the color class $\mathcal{C}(vw)$ gets deleted in Step 6. It is
clear that $\mathbb{E}(Y)=\sum_{w\in
N(v)}\left(p_{w}+p_{\mathcal{C}(vw)}\right)\leq 2a_{t}s_{t}$. Thus, by using
Theorem 3.1, the probability that $Y$ deviates by more than
$\lambda=\sqrt{a_{t}s_{t}}\log q$ from its expectation is less than
$e^{-\omega(\log q)}$.

Observe that $\mathbb{E}(L)+\mathbb{E}(Y)\leq\sum_{w\in
N(v)}(p^{\prime}_{w}+p_{w}+p^{\prime}_{\mathcal{C}(vw)}+p_{\mathcal{C}(vw)})\leq
2(a_{t}+a_{t}^{2})s_{t}$. Hence, using triangle inequality we conclude that
the random variable $L+X$ does not exceed from $2(a_{t}+a_{t}^{2})s_{t}$ by
more than $\sqrt{\delta q}\log q+\sqrt{a_{t}s_{t}}\log q$ w.v.h.p. Now, Lemma
6.1 follows by noting the following three inequalities:

$a_{t}s_{t}=\gamma\frac{\delta
g(t\delta)(1+\alpha_{t})}{s(t\delta)(1-\alpha_{t})}\cdot(1-\alpha_{t})s(t\delta)(1+\epsilon)q\leq
2\delta q.$

$\sqrt{\delta q}\log q+\sqrt{a_{t}s_{t}}\log q\leq 3\sqrt{\delta q}\log
q\leq\delta^{2}q.$

$a_{t}^{2}s_{t}=\gamma^{2}\frac{\delta^{2}g(t\delta)^{2}(1+\alpha_{t})^{2}}{s(t\delta)^{2}(1-\alpha_{t})^{2}}\cdot(1-\alpha_{t})s(t\delta)(1+\epsilon)q\leq\frac{3}{2}\delta^{2}q.$

∎

######  Corollary 8.4.

After the $(t+1)$-st iteration, the survived vertices of $A$ have degree
exactly $s_{t+1}$ w.v.h.p.

###### Proof.

By Lemma 8.3 and Lemma 7.1, after Step 6 of the $(t+1)$-st iteration, w.v.h.p.
every survived vertices of $A$ has degree has degree at least

$\displaystyle(1-2a_{t})s_{t}-4\delta^{2}q=\left(1-2\tilde{a}_{t}\frac{1+\alpha_{t}}{1-\alpha_{t}}\right)(1-\alpha_{t})\tilde{s}_{t}-4\delta^{2}q$
$\displaystyle=(1-\alpha_{t})(1-2\tilde{a}_{t})\tilde{s}_{t}-4\alpha_{t}\tilde{a}_{t}\tilde{s}_{t}-4\delta^{2}q$
$\displaystyle=(1-\alpha_{t})\left(\tilde{s}_{t+1}-\gamma^{2}\delta^{2}(1+\epsilon)q\right)-4\alpha_{t}\tilde{a}_{t}\tilde{s}_{t}-4\delta^{2}q$
$\displaystyle\geq(1-\alpha_{t})\tilde{s}_{t+1}-5\delta^{2}q-5\alpha_{t}\tilde{a}_{t}\tilde{s}_{t}.$
(8.9)

Next, note the following:

$\displaystyle
5\delta^{2}q+5\alpha_{t}\tilde{a}_{t}\tilde{s}_{t}=5\delta^{2}q+5\alpha_{t}\cdot\frac{\gamma\delta
g(t\delta)}{s(t\delta)}\cdot s(t\delta)(1+\epsilon)q$ $\displaystyle\leq
5\delta^{2}q+5\sqrt{\delta}\left(\left(1+\frac{10\delta}{(1-\gamma\eta)^{2}}\right)^{t}-1\right)\cdot\delta
q$ $\displaystyle\leq
10\delta^{3/2}q\left(1+\frac{10\delta}{(1-\gamma\eta)^{2}}\right)^{t}$
$\displaystyle=(\alpha_{t+1}-\alpha_{t})(1-\gamma\eta)^{2}q$
$\displaystyle\leq(\alpha_{t+1}-\alpha_{t})\tilde{s}_{t+1}.$ (8.10)

Thus, combining (8.9) and (8.10), we obtain that after Step 6 of the
$(t+1)$-st iteration, w.v.h.p. every survived vertices of $A$ has degree has
degree at least $(1-\alpha_{t+1})\tilde{s}_{t+1}=s_{t+1}$. Thus, after Step 7,
w.v.h.p. every survived vertices of $A$ has degree has degree exactly
$s_{t+1}$. ∎

Next, we bound the degree of each survived vertex in $B$ throughout the
algorithm.

######  Lemma 8.5.

At the end of $(t+1)$-st iteration, w.v.h.p. the degree of each remaining
vertex $v\in B$ is at most
$d_{t}(1-a_{t})\left(1-\frac{\delta}{1-t\delta}\right)+C^{\prime}\delta^{2}q$,
where $C^{\prime}$ is a constant depending on $\epsilon$.

###### Proof.

First, Step 7 can only decrease the degrees of any vertex in $B$; thus, it is
enough to prove Lemma 8.5 before Step 7. For each remaining vertex $v\in B$
after the $t$-th iteration, we define $D_{t+1,v}$ to be the random variable
denoting the degree of $v$ after Step 6 in the $(t+1)$-st iteration. To
simplify the analysis, we make a slight change in Step 6 which will not alter
the output of the original algorithm. Instead of the original Step 6, we
delete each color class $\mathcal{C}$ (even the ones which get deleted in Step
5) with the same probability $p_{\mathcal{C}}$ as desired in the algorithm.
Deleting a color class in Step 6 that was already deleted in Step 5 does not
do anything further. This alternative way essentially makes Step 6 independent
of every other step.

Fix a vertex $v\in B$. Let $d$ denote the degree of $v$ after the $t$-th
iteration of the algorithm. Clearly, $d\leq d_{t}$. Let $X$ be the random
variable denoting the number of neighbors of $v$ deleted in Step 6, and $L$ be
the random variable denoting the number of edges $uv$ adjacent to $v$ deleted
in Steps 3 and 5, and $uv$ is not deleted in Step 6. Clearly,
$D_{t+1,v}=d-(X+L)$. Thus, we are interested in a good lower bound on $X+L$.

Observe that $\mathbb{E}(X)=\sum_{u\in N(v)}p_{\mathcal{C}(uv)}$, where
$\mathcal{C}(uv)$ denotes the color class containing the edge $uv$. Clearly,
$X$ is the sum of at most $d_{t}$ independent Bernoulli random variables with
probability at most $a_{t}$. Thus, by using Chernoff bound (Theorem 3.1), the
probability that $X$ deviates by more than $\frac{1}{2}\sqrt{a_{t}d_{t}}\log
q\leq\sqrt{q}\log q$ from its expectation is at most $e^{-\omega(\log q)}$.

Now to facilitate the analysis of the random variable $L$, we introduce the
random variable $X^{\prime}=\sum_{u\in
N(v)}p^{\prime}_{\mathcal{C}(uv)}1_{u\in N^{\prime}}$, where $N^{\prime}$
denote the (random) subset of $N(v)$ containing all the vertices $u$ such that
the edge $uv$ is not deleted in Step 6. Clearly,
$\mathbb{E}(X^{\prime})=\sum_{u\in
N(v)}p^{\prime}_{\mathcal{C}(uv)}\left(1-p_{\mathcal{C}(uv)}\right)$. Again by
Chernoff bound (Theorem 3.1), the probability that $X^{\prime}$ deviates by
more than $\sqrt{q}\log q$ from its expectation is at most $e^{-\omega(\log
q)}$. Let $F$ denote the event that both $X$ and $X^{\prime}$ are within a gap
of $\sqrt{q}\log q$ from their corresponding expected values. Next, we show
the concentration bound on $L$ conditioning on this event $F$, which holds
w.v.h.p. Lemma 8.5 follows from the following claim.

######  Claim 8.6.

Conditioned on $F$, at the end of Step 6 of the $(t+1)$-st iteration, w.v.h.p.
the degree of each remaning vertex $v\in B$ is at most
$d_{t}\cdot(1-a_{t})\left(1-\frac{\delta}{1-t\delta}\right)+C^{\prime}\delta^{2}q$,
where $C^{\prime}$ is a constant depending on $\epsilon$.

###### Proof.

Fix a vertex $v\in B$ that survived after the $t$-th iteration. For any
neighbor $u\in A$ of $v$, the probability that the edge $uv$ is deleted in
Step 5 is exactly $p^{\prime}_{\mathcal{C}(uv)}$. Thus, the next task
remaining is to calculate the probability that the vertex $u$ is deleted in
Step 3, conditioned on the fact that the edge $uv$ does not get deleted in
Step 5. For the convenience of writing, let $Y$ denote the event that the
vertex $u$ is deleted in Step 3. Let $Z$ denote the event that the edge $uv$
does not get deleted in Step 5. We are interested in getting a good lower
bound on $\mathbb{P}\left[Y|Z\right]$.

The event $Z$ is the same as the event that none of the edges uniformly picked
in Step 1 has the same color as the edge $uv$. Hence, conditioning on the
event $Z$ essentially is equivalent to considering the uniform measure in Step
1, excluding the edges in the color class $\mathcal{C}(uv)$. Also, note that
the event $Y$ contains the event $Y^{\prime}$ that one edge $e$ incident to
the vertex $u$ is picked in Step 1, and no other edges incident to $e$ or with
the same color as $e$ is picked in Step 1. At this point, we can calculate
this probability for each fixed edge adjacent to $u$ and sum the probability.
So, we have the following:

$\mathbb{P}\left[Y|Z\right]\geq\mathbb{P}\left[Y^{\prime}|Z\right]\geq\frac{\delta
q(s_{t}-1)}{\left(1-t\delta+3\delta\log\left(\frac{1}{1-\eta}\right)\right)qs_{t}}\left(1-\frac{2d_{t}+s_{t}}{(1-t\delta)qs_{t}-d_{t}}\right)^{\delta
q-1},$

because, the probability to pick an edge $e$ incident to the vertex $u$ if we
choose an edge uniformly at random among the edges which are not in
$\mathcal{C}(uv)$ is at least
$\frac{s_{t}-1}{\left(1-t\delta+3\delta\log\left(\frac{1}{1-\eta}\right)\right)qs_{t}}$
(which follows from Corollary 8.2). Now, conditioning on the fact that such an
$e$ is picked, the probability that each of the remaining $\delta q-1$ edges
is not incident to $e$ and is not of the same color, is at least
$\left(1-\frac{2d_{t}+s_{t}}{(1-t\delta)qs_{t}-d_{t}}\right)^{\delta q-1}$.
Hence, we can write the following:

$\displaystyle\mathbb{P}\left[Y|Z\right]$ $\displaystyle\geq\frac{\delta
q(s_{t}-1)}{\left(1-t\delta+3\delta\log\left(\frac{1}{1-\eta}\right)\right)qs_{t}}\left(1-\frac{2d_{t}+s_{t}}{(1-t\delta)qs_{t}-d_{t}}\right)^{\delta
q}$
$\displaystyle\geq\frac{\delta}{1-t\delta+3\delta\log\left(\frac{1}{1-\eta}\right)}\cdot\frac{s_{t}-1}{s_{t}}\left(1-\frac{\delta
q\cdot 4s_{t}}{\frac{1}{2}(1-t\delta)qs_{t}}\right)$ (8.11)
$\displaystyle=\frac{\delta}{1-t\delta}\left(1-\frac{3\delta\log\left(\frac{1}{1-\eta}\right)}{1-t\delta}\right)\left(1-\frac{1}{s_{t}}\right)\left(1-\frac{8\delta}{1-t\delta}\right)$
$\displaystyle=\frac{\delta}{1-t\delta}-O_{\epsilon}(\delta^{2}).$ (8.12)

Clarification of (8.11), and (8.12): In (8.11), we have used
$d_{t}\leq\frac{3}{2}s_{t}$ from (8.8), and
$(1-t\delta)qs_{t}-d_{t}>\frac{1}{2}(1-t\delta)qs_{t}$ for all
$t\leq\eta\tau$, which we show below by plugging in the the values of the
parameters $\epsilon$, $\delta$, and $\eta$ assigned in the beginning of this
section. For $t\leq\eta\tau$, we have the following:

$\displaystyle\frac{1}{2}(1-t\delta)qs_{t}-d_{t}$
$\displaystyle=\frac{1}{2}(1-\alpha_{t})(1+\epsilon)(1-t\delta)(1-\gamma
t\delta)^{2}q^{2}-(1+\alpha_{t})(1-t\delta)(1-\gamma t\delta)q$
$\displaystyle\geq(1-t\delta)(1-\gamma t\delta)q\left(\frac{1}{4}(1-\gamma
t\delta)q-2\right)$
$\displaystyle\geq(1-\eta)(1-\gamma\eta)q\left(\frac{1}{4}(1-\gamma\eta)q-2\right)>0,$

which shows that $(1-t\delta)qs_{t}-d_{t}>\frac{1}{2}(1-t\delta)qs_{t}$ for
all $t\leq\eta\tau$, as we desired. In (8.12), we have used the fact that
$\frac{3\delta\log\left(\frac{1}{1-\eta}\right)}{1-t\delta}$,
$\frac{1}{s_{t}}$, and $\frac{7\delta}{1-t\delta}$ are all equal to
$O_{\epsilon}(\delta)$ for all $t\leq\eta\tau$, which can be verified by
plugging in the values of the parameters $\epsilon$, $\delta$, and $\eta$.
Hence, conditioned on $F$, we have the following:

$\mathbb{E}(D_{t+1,v})\leq\sum_{u\in
N^{\prime}}\left(1-p^{\prime}_{\mathcal{C}(uv)}\right)\left(1-\frac{\delta}{1-t\delta}+O_{\epsilon}(\delta^{2})\right).$
(8.13)

Note that $\sum_{u\in
N^{\prime}}p^{\prime}_{\mathcal{C}(uv)}=X^{\prime}\geq\sum_{u\in
N(v)}p^{\prime}_{\mathcal{C}(uv)}\left(1-p_{\mathcal{C}(uv)}\right)-\sqrt{q}\log
q$. Thus, we have the following:

$\displaystyle\sum_{u\in
N^{\prime}}\left(1-p^{\prime}_{\mathcal{C}(uv)}\right)=(d-X)-\sum_{u\in
N^{\prime}}p^{\prime}_{\mathcal{C}(uv)}$ $\displaystyle\leq\sum_{u\in
N(v)}\left(1-p_{\mathcal{C}(uv)}\right)+\sqrt{q}\log q-\sum_{u\in
N(v)}p^{\prime}_{\mathcal{C}(uv)}\left(1-p_{\mathcal{C}(uv)}\right)+\sqrt{q}\log
q$ $\displaystyle=\sum_{u\in
N(v)}\left(1-p^{\prime}_{\mathcal{C}(uv)}\right)\left(1-p_{\mathcal{C}(uv)}\right)+2\sqrt{q}\log
q$ $\displaystyle\leq d(1-a_{t})+\delta^{2}q,$

which we use in (8.13) to get the following conditioned on $F$:

$\mathbb{E}(D_{t+1,v})\leq
d_{t}(1-a_{t})\left(1-\frac{\delta}{1-t\delta}\right)+O_{\epsilon}(\delta^{2})\cdot
q.$ (8.14)

Furthermore, conditioning on $F$, we can prove a concentration bound on $L$
using Theorem 3.2. We use the same sets $A$, $B$, and the same probability
distribution as in the proof of Lemma 8.1. For the functional $L$, we consider
the martingale considered in Theorem 3.2. Suppose one edge is replaced by
another in any of the $\delta q$ coordinates. In that case, $L$ will be
affected by at most 2 because picking a different color in the partial rainbow
matching in Step 2 can change the number of neighbors deleted in Step 3 by at
most 1, and the number of deletions of edges incident to $v$ in Step 5 by at
most 1. Thus, 2 is a bound on the Lipschitz constant of the martingale. Hence,
using Theorem 3.2, we can conclude that the probability that $L$ deviates from
its mean by at least $\lambda=\delta^{2}q$ is at most
$2e^{-\frac{\lambda^{2}}{8\delta q}}=e^{-\omega(\log q)}$. This, together with
(8.14), finishes the proof of Claim 8.6, which in turn completes the proof of
Lemma 8.5. ∎

∎

######  Corollary 8.7.

After the $(t+1)$-st iteration, the survived vertices of $B$ have degree at
most $d_{t+1}$ w.v.h.p.

###### Proof.

By Lemma 8.5, Lemma 7.2, and the fact that $a_{t}\geq\tilde{a}_{t}$, after the
$(t+1)$-st iteration, w.v.h.p. every survived vertices of $B$ has degree has
degree at most

$\displaystyle
d_{t}\cdot(1-\tilde{a}_{t})\left(1-\frac{\delta}{1-t\delta}\right)+C^{\prime}\delta^{2}q$
$\displaystyle=\left(1+\alpha_{t}\right)\tilde{d}_{t}(1-\tilde{a}_{t})\left(1-\frac{\delta}{1-t\delta}\right)+C^{\prime}\delta^{2}q=(1+\alpha_{t})\tilde{d}_{t+1}+C^{\prime}\delta^{2}q.$
(8.15)

Recalling that $C^{\prime}$ is a constant depending only on $\epsilon$, we get
the following:

$\displaystyle C^{\prime}\delta^{2}q\leq
10\delta^{3/2}q\left(\frac{1-\eta}{1-\gamma\eta}\right)\left(1+\frac{10\delta}{(1-\gamma\eta)^{2}}\right)^{t}=(\alpha_{t+1}-\alpha_{t})\tilde{d}_{t+1}.$
(8.16)

Thus, combining (8.15) and (8.16), we obtain that after the $(t+1)$-st
iteration, w.v.h.p. every survived vertices of $B$ has degree has degree at
most $(1+\alpha_{t+1})\tilde{d}_{t+1}=d_{t+1}$. ∎

We next control the size of each color class throughout the algorithm. The
structure of the proof of the following lemma is very similar to the proof of
Lemma 8.5. Thus, we omit some details identical to the arguments used to prove
Lemma 8.5.

######  Lemma 8.8.

At the end of $(t+1)$-st iteration, w.v.h.p. the number of edges in each of
the remaining color class is at most
$d_{t}(1-a_{t})\left(1-\frac{\delta}{1-t\delta}\right)+C^{\prime}\delta^{2}q$,
where $C^{\prime}$ is a constant depending on $\epsilon$.

###### Proof.

First, Steps 5, 6, and 7 can only decrease the number of edges in a color
class; thus, it is enough to prove Lemma 8.8 before Step 5. For each remaining
color class $\mathcal{C}$ after the $t$-th iteration, we define
$S_{t+1,\mathcal{C}}$ to be the random variable denoting the number of edges
in $\mathcal{C}$ after Step 4 in the $(t+1)$-st iteration. To simplify the
analysis, we make a slight change in Step 4 which will not alter the output of
the original algorithm. Instead of the actual Step 4, we delete each vertex
$v\in B$ (even the ones which get deleted in Step 3) with the same probability
$p_{v}$ as desired in the algorithm. Deleting a vertex in Step 4, which was
already deleted in Step 3, does not do anything further. This alternative way
essentially makes Step 4 independent of every other step.

Fix a remaining color class $\mathcal{C}$. Let $s$ denote the number of edges
in $\mathcal{C}$ after the $t$-th iteration of the algorithm. Clearly, $s\leq
d_{t}$. Let $X$ be the random variable denoting the number of edges in
$\mathcal{C}$ deleted in Step 4, and $L$ be the random variable denoting the
number of edges $e$ in $\mathcal{C}$ deleted in Step 3, and $e$ is not deleted
in Step 4. Clearly, $S_{t+1,\mathcal{C}}=s-(X+L)$. Thus, we want a good lower
bound on $X+L$.

Observe that $\mathbb{E}(X)=\sum_{v\in B_{\mathcal{C}}}p_{v}$, where
$B_{\mathcal{C}}$ denotes the set of all vertices $v\in B$ that are incident
to an edge in $\mathcal{C}$. Clearly, $X$ is the sum of at most $d_{t}$
independent Bernoulli random variables with probability at most $a_{t}$. Thus,
by using standard Chernoff bound (Theorem 3.1), the probability that $X$
deviates by more than $\frac{1}{2}\sqrt{a_{t}d_{t}}\log q\leq\sqrt{q}\log q$
from its expectation is at most $e^{-\omega(\log q)}$.

Now to facilitate the analysis of the random variable $L$, we introduce the
random variable $X^{\prime}=\sum_{v\in B_{\mathcal{C}}}p^{\prime}_{v}1_{v\in
N^{\prime}}$, where $N^{\prime}$ denote the (random) subset of
$B_{\mathcal{C}}$ containing all the vertices $v$ that are not deleted in Step
4. Clearly, $\mathbb{E}(X^{\prime})=\sum_{v\in
B_{\mathcal{C}}}p^{\prime}_{v}\left(1-p_{v}\right)$. Again by Chernoff bound
(Theorem 3.1), the probability that $X^{\prime}$ deviates by more than
$\sqrt{q}\log q$ from its expectation is at most $e^{-\omega(\log q)}$. Let
$F$ denote the event that both $X$ and $X^{\prime}$ are within a gap of
$\sqrt{q}\log q$ from their corresponding expected values. Next, we show the
concentration bound on $L$ conditioning on this event $F$, which holds
w.v.h.p. Lemma 8.8 follows from the following claim.

######  Claim 8.9.

Conditioned on $F$, after Step 6 of the $(t+1)$-st iteration, w.v.h.p. the
number of edges in each of the remaning color class is at most
$d_{t}(1-a_{t})\left(1-\frac{\delta}{1-t\delta}\right)+C^{\prime}\delta^{2}q$,
where $C^{\prime}$ is a constant depending on $\epsilon$.

###### Proof.

Fix an edge $uv\in\mathcal{C}$ with $u\in A,v\in B$ that survived after the
$t$-th iteration. The probability that $v$ is deleted in Step 3 is exactly
$p^{\prime}_{v}$. Thus, the next task remaining is to calculate the
probability that the vertex $u$ is deleted in Step 3, conditioned on the fact
that the vertex $v$ does not get deleted in the same step. For the convenience
of writing, let $Y$ denote the event that the vertex $u$ gets deleted in Step
3. Let $Z$ denote the event that the vertex $v$ does not get deleted in Step
3. We want a good lower bound on $\mathbb{P}\left[Y|Z\right]$.

The event $Z$ is the same as the event that none of the edges uniformly picked
in Step 1 is incident to $v$. Hence, conditioning on the event $Z$ essentially
is equivalent to considering the uniform measure in Step 1, excluding the
edges incident to $v$. Also, note that the event $Y$ contains the event
$Y^{\prime}$ that one edge $e$ incident to the vertex $u$ is picked in Step 1,
and no other edges incident to $e$ or with the same color as $e$ is picked in
Step 1. By the same reasoning as in Claim 8.6, we can calculate this
probability for each fixed edge adjacent to $u$ and sum the probability. Thus,
we have the following:

$\mathbb{P}\left[Y|Z\right]\geq\mathbb{P}\left[Y^{\prime}|Z\right]\geq\frac{\delta
q(s_{t}-1)}{\left(1-t\delta+3\delta\log\left(\frac{1}{1-\eta}\right)\right)qs_{t}}\left(1-\frac{2d_{t}+s_{t}}{(1-t\delta)qs_{t}-d_{t}}\right)^{\delta
q-1}.$

Again by the same calculation as in Claim 8.6, we have the following:

$\displaystyle\mathbb{P}\left[Y|Z\right]\geq\frac{\delta}{1-t\delta}-O_{\epsilon}(\delta^{2}).$
(8.17)

Hence, conditioned on $F$, we have the following:

$\mathbb{E}(S_{t+1,\mathcal{C}})\leq\sum_{v\in
N^{\prime}}(1-p^{\prime}_{v})\left(1-\frac{\delta}{1-t\delta}+O_{\epsilon}(\delta^{2})\right).$
(8.18)

Note that $\sum_{v\in N^{\prime}}p^{\prime}_{v}=X^{\prime}\geq\sum_{v\in
B_{\mathcal{C}}}p^{\prime}_{v}(1-p_{v})-\sqrt{q}\log q$. Thus, we have the
following:

$\displaystyle\sum_{v\in N^{\prime}}(1-p^{\prime}_{v})=(d-X)-\sum_{v\in
N^{\prime}}p^{\prime}_{v}$ $\displaystyle\leq\sum_{v\in
B_{\mathcal{C}}}(1-p_{v})+\sqrt{q}\log q-\sum_{v\in
B_{\mathcal{C}}}p^{\prime}_{v}(1-p_{v})+\sqrt{q}\log q$
$\displaystyle=\sum_{v\in
B_{\mathcal{C}}}(1-p^{\prime}_{v})(1-p_{v})+2\sqrt{q}\log q$
$\displaystyle\leq d(1-a_{t})+\delta^{2}q,$

which we use in (8.18) to get the following conditioned on $F$:

$\mathbb{E}(S_{t+1,\mathcal{C}})\leq
d_{t}(1-a_{t})\left(1-\frac{\delta}{1-t\delta}\right)+O_{\epsilon}(\delta^{2})\cdot
q.$ (8.19)

Finally, we can finish the proof by showing the concentration of the random
variable $S_{t+1,\mathcal{C}}$ exactly as in the proof of Claim 8.6 using
Theorem 3.2.

∎

∎

The same calculations as in Corollary 8.7 obtains the following:

######  Corollary 8.10.

After the $(t+1)$-st iteration, the size of each remaning color class is at
most $d_{t+1}$ w.v.h.p.

Since the numbers of both colors and vertices in the graph are bounded by
$2q^{2}$, a simple union bound already shows that w.v.h.p. the conclusions of
Corollaries 8.2, 8.4, 8.7, and 8.10 hold simultaneously (note that we do not
need any local lemma like in the proof of Lemma 6.5). This proves that
w.v.h.p. (8.5) and (8.6) hold for every $1\leq t\leq\eta\tau$.

Hence, at the end of the $\eta\tau$-th iteration, by Corollary 8.4 the degree
of any remaining vertex in $A$ is at least
$\frac{1}{\sqrt{1+\epsilon}}(1-\gamma\eta)^{2}(1+\epsilon)q$ and by Corollary
8.2 the number of remaining vertices in $A$ is at most $q-\eta\tau\delta
q+3\delta q\log\left(\frac{1}{1-\eta}\right)\leq\sqrt{1+\epsilon}(1-\eta)q$
(here, any constant greater than 1 would work in the places of the
$\sqrt{1+\epsilon}$ factors, this particular choice was made to make the final
inequality easier). The straightforward greedy algorithm will work here as
long as
$\frac{1}{\sqrt{1+\epsilon}}(1-\gamma\eta)^{2}(1+\epsilon)q>2\sqrt{1+\epsilon}(1-\eta)q$,
which is equivalent to
$\left(1-\frac{1-\epsilon^{3}}{1+\epsilon}\right)^{2}>2\epsilon^{3}$ (remember
that $\eta=1-\epsilon^{3}$). This can be easily checked to be true for
$\epsilon<\frac{1}{10}$. Hence, the partial rainbow matching obtained from
running the algorithm can be completed to a rainbow matching using all
vertices in $A$, proving Theorem 1.12.

##  9 A weaker bound on Theorem 1.11

We need some easy upper bound on the number of colors required in Theorem 1.11
to prove the actual statement of it. We prove the following by a somewhat
direct application of 1.9.

######  Proposition 9.1.

There exists $N$ such that whenever $q\geq N$, for any graph $G$ that is
properly colored with at least $4q$ colors such that there are at least $q$
edges of each color, there is a rainbow matching of $G$ using $q$ colors.

###### Proof.

To prove this proposition, we start by showing an easy bound of $2q^{2}$
instead of $4q$. Suppose we have a properly colored graph $G$ with $2q^{2}$
colors where each color appears $q$ times. Consider the maximum size rainbow
matching $M=\\{e_{1},e_{2},\ldots,e_{m}\\}$ of $G$. Assume for the sake of
contradiction that $|M|=m\leq q-1$. Let $C$ denote all the colors used to
color the edges in any edge connecting two vertices participating in $M$.
Clearly, $|C|\leq\binom{2m}{2}<2q^{2}-2q$. So, there are $2q$ colors
$c_{1},c_{2},\ldots,c_{2q}$ which do not appear in any of the edges between
two vertices in $M$. If there is an edge with any of these $2q$ colors which
does not use any of the vertices used in $M$, then we are already done because
we can obtain a larger rainbow matching by adding that edge to $M$. So, all
the edges using colors from $\\{c_{1},c_{2},\ldots,c_{2q}\\}$ uses exactly one
vertex in $M$. By a simple application of pigeonhole principle, for every
color $c$ from $\\{c_{1},c_{2},\ldots,c_{2q}\\}$, there is an edge $e\in M$
such that there are two edges with color $c$, which are incident to $e$. By
another application of the pigeonhole principle, there exists an edge $e\in M$
such that there are three colors (without loss of generality, say $c_{1}$,
$c_{2}$, and $c_{3}$) with the property that there are two edges with each
color in $\\{c_{1},c_{2},c_{3}\\}$ such that all six of these edges are
incident to $e$. Now, it is easy to find two edges among these six edges such
that they are not incident to each other and have distinct colors. By
observing that one obtains a larger matching by adding these two edges and
subtracting $e$ from $M$, we estalish the desired upper bound of $2q^{2}$.

Next, we show that $4q$ colors suffice for all sufficiently large $q$, as
promised. Let $q$ be such that $q\geq N^{2}$, where $N$ comes from Theorem
1.9. We split the proof into two cases based on the degree sequence $d_{1}\geq
d_{2}\geq\cdots$ of $G$. Define $k$ to be the minimum integer such that
$d_{k}\leq 3(q-k)$, if it exists.

Case 1: If $k>q-\sqrt{q}$ or $k$ does not exist, then remove $q-\sqrt{q}$
highest degree-vertices from $G$. In the remaining graph there are at least
$\sqrt{q}$ edges of each color and the number of colors is $4q\geq
2\left(\sqrt{q}\right)^{2}$. Thus, using the bound proven in the last
paragraph, we can find a rainbow matching using $\sqrt{q}$ colors. Indeed, we
can greedily add an edge adjacent to each of the removed vertices to the
rainbow matching to get a rainbow matching of size $q$. This can be done in
the following way. Let $v_{i}$ denotes the vertex with degree $d_{i}$. The
number of colors used so far is $\sqrt{q}$, and the number of vertices used in
the rainbow matching is $2\sqrt{q}$. So, one can pick a neighbor of
$v_{q-\sqrt{q}}$ out of more than $3\sqrt{q}$ neighbors so that neither the
color of that edge nor the neighbor is used in the rainbow matching built yet.
We can continue this process greedily for $i=\sqrt{q},\sqrt{q}-1,\ldots,1$
respectively to find a rainbow matching of size $q$.

Case 2: If $k\leq q-\sqrt{q}$, then similarly remove $k$ highest degree-
vertices from $G$. Like last time, at least $q-k$ edges of each color are in
the remaining graph, and the maximum degree is at most $3(q-k)$. Now merge
four colors simultaneously to ensure that each color has $4(q-k)$ edges. Thus,
the total number of colors is now $q$, and each color class has maximum degree
at most four. Due to the choice of $N$, we can apply Theorem 1.9 on $G$ to
obtain a rainbow matching using these $q$ colors. ∎

##  10 Proof of Theorem 1.11

If we directly apply an appropriate randomized algorithm similar to the ones
of Sections 4 or 8, then we can only obtain a matching of size $q-o(q)$, which
is not enough for Theorem 1.11. As we have discussed in the introduction, the
rigid behavior in terms of the number of edges used in each color class is
somewhat responsible for this type of failure of the randomized algorithm used
before. It turns out that we need to be extra careful about the vertices with
small degree. To do so, we first need to show that there cannot be too many
vertices with degree close to the number of colors (note that the maximum
degree can be at most the number of colors because we have a proper coloring
this time).

To prove Theorem 1.11, without loss of generality, we assume that
$0<\epsilon<\frac{1}{10}$. We start with a simple graph $G$ that is properly
edge-colored with $2(1+\epsilon)q$ colors such that there are at least $q$
edges of each color, and $G$ does not have a rainbow matching of size $q$.
Define $\theta=\frac{\epsilon}{2}$. We first apply Theorem 1.12 to show that
the number of vertices with degree more than $2(1+\theta)q$ is at most
$(1-\theta)q$. If not, then select a set $A$ of size exactly $(1-\theta)q$
such that the degree of any vertex in $A$ is at least $2(1+\theta)q$. Let
$G^{\prime}$ denote the graph after deleting all the edges incident to $A$. We
have at least $\theta q$ edges in each color in $G^{\prime}$. Thus, by
applying Proposition 9.1 established in the last section, we can find a
rainbow matching $T$ of size $\theta q$ in $G^{\prime}$. Now in $G$, discard
all the vertices incident to $T$ and all the edges colored with a color used
in $T$. For a fixed $v\in A$, we discard at most $3\theta q$ edges incident to
$v$. Hence, $v$ still has at least $2(1+\theta)q-3\theta q-(1-\theta)q=q$
neighbors outside of $A$. Now, with a straightforward application of Theorem
1.12 on the graph $A\cup B$ (where $B=V(G)\setminus A$), we can find a rainbow
matching $T^{\prime}$ using all the vertices in $A$. As we have already
discarded the vertices and colors used in $T$, the edge set $T\cup T^{\prime}$
gives us a rainbow matching of size $q$. Hence, from now on, we assume that
the number of vertices with degree more than $2(1+\theta)q$ is at most
$(1-\theta)q$.

###  10.1 Algorithm

Assume that we are given a simple graph $G$ that is properly edge-colored with
$2(1+\epsilon)q$ colors such that there are $q$ edges of each color.
Additionally, assume that there exists $A\subseteq V(G)$ such that
$|A|\leq(1-\theta)q$ and the vertices outside $A$ have degree at most
$2(1+\theta)q$, where $\theta=\frac{\epsilon}{2}$. Like before, we will
provide a randomized algorithm, which constructs a rainbow matching using $q$
colors in several iterations.

This algorithm is in terms of some parameter $\delta>0$, which will be
specified later. Define $\tau=\frac{1}{\delta}$. We follow the algorithm below
for $\eta\tau$ steps, for some $\eta<\frac{1}{2}$ to be specified later.

  1. 1.

Select independently $\delta\cdot 2(1+\epsilon)q$ edges
$e_{1},e_{2},\ldots,e_{2\delta(1+\epsilon)q}$ uniformly at random with
replacement from among the remaining edges. Denote by $T$ the set of all
selected edges.

  2. 2.

Delete all the vertices corresponding to the edges in $T$ from $G$. Deleting
vertices always also deletes all incident edges.

  3. 3.

With some probability (to be specified later), independently delete each
vertex in $G$. This will make sure that among Steps 2 and 3 combined, every
vertex in $A$ gets deleted with the same probability, and every vertex outside
of $A$ gets deleted with the same probability (possibly different).

  4. 4.

For each edge $e_{i}\in T$, add it to the rainbow matching if $e_{i}$ is not
incident to any edge $e_{j}\in T$ for $j<i$ and $e_{i}$ does not have same
color as any edge $e_{j}\in T$ for $j<i$.

  5. 5.

For each edge $e$ added to the rainbow matching in Step 4, delete all the
edges of the same color as $e$ from $G$.

  6. 6.

For each remaining color class, if the number of edges in that color class is
more than $s_{t}$ after Step 5, then delete edges of that color class in the
following way to make sure that it has precisely $s_{t}$ edges, where $s_{t}$
will be specified later. If the number of edges that need to be deleted is at
most the number of edges containing at least one vertex from $A$, then delete
arbitrarily from those edges. Otherwise, delete all the edges with at least
one vertex from $A$, and then delete the rest arbitrarily from the rest of the
edges of the same color.

Compared to Algorithm of Section 4, we need to be more careful here in
deleting the vertices with smaller degree, and thus, we are treating the
vertices outside $A$ differently in Steps 3 and 6.

###  10.2 Intuitive analysis

We aim to show that if we run this randomized algorithm, we get a rainbow
matching with $q$ edges. Like last time, define $d_{0,v}$ to be the initial
degree of $v$ in $G$. We will define two functions $s(x)$ and $g(x)$ such that
after the $t$-th iteration of the algorithm, we have the following:

  1. 1.

Each remaining color class has size exactly $s_{t}$, which is at least about
$s(t\delta)q$.

  2. 2.

Each surviving vertex $v$ has degree at most $d_{t,v}$, which is approximately
$(1-t\delta)g(t\delta)d_{0,v}$.

  3. 3.

For each remaining color class, the fraction of number of vertices remaning in
$A$ is at most $\frac{1-\theta}{2}$ (i.e., for each color $c$, if $V_{c}$
denotes the set of all vertices incident to an edge of color $c$, then we have
$\frac{|V_{c}\cap A|}{|V_{c}|}\leq\frac{1-\theta}{2}$).

We outline a rough analysis below. Clearly $s(0)=1$ and $g(0)=1$. Assume that
the $t$-th iteration is done, and the above properties are true. First, very
few edges will be discarded in Step 4 throughout the process. In other words,
the number of edges in the partial rainbow matching will be roughly
$2(1+\epsilon)t\delta q$ after the $t$-th round.

Step 3 is there just to make the analysis more convenient. It ensures that
every vertex of $A$ is deleted with the same probability (call it $a_{t}$),
and every vertex outside of $A$ is also deleted with the same probability
(call it $b_{t}$). Like before, we need to find the maximum probability a
vertex $v$ can be deleted in Step 2 and set $a_{t}$ and $b_{t}$ accordingly.
After the $t$-th iteration, the number of remaining colors is at least
$2(1-t\delta)(1+\epsilon)q$, and thus the number of remaining edges is at
least $2(1-t\delta)(1+\epsilon)qs_{t}$. Now, if one picks an edge uniformly at
random from $G$, then the probability (denote by $p$) that one of the edges
incident to $v$ will be picked is exactly the degree of $v$ divided by the
total number of edges of $G$, which is at most
$\frac{d_{t,v}}{2(1-t\delta)(1+\epsilon)qs_{t}}$ (i.e.,
$p\leq\frac{d_{t,v}}{2(1-t\delta)(1+\epsilon)qs_{t}}$). As a result, the
probability that $v$ is not deleted in Step 2 is exactly
$(1-p)^{2\delta(1+\epsilon)q}$, which is at least about $1-\frac{\delta
g(t\delta)d_{0,v}}{s(t\delta)q}$. Thus, we can define $a_{t}$ to be about
$\frac{\delta g(t\delta)\cdot
2(1+\epsilon)q}{s(t\delta)q}=2(1+\epsilon)\delta\cdot\frac{g(t\delta)}{s(t\delta)}$
(note that $d_{0,v}\leq 2(1+\epsilon)q$). Similarly, we can define $b_{t}$ to
be about $2(1+\epsilon)\gamma\delta\cdot\frac{g(t\delta)}{s(t\delta)}$, where
$\gamma=\frac{1+\theta}{1+\epsilon}$.

The probability that a single vertex gets deleted among Steps 2 and 3 is
$a_{t}$ or $b_{t}$. Thus, by a simple union bound and using 3, the expected
number of edges deleted in each color class among Steps 2 and 3 is at most
$2s_{t}\left(\frac{1-\theta}{2}\cdot a_{t}+\frac{1+\theta}{2}\cdot
b_{t}\right)$. This suggests defining $s(x)$ with the following behavior:

$s^{\prime}(x)=-2(1+\epsilon)\left[(1-\theta)+(1+\theta)\gamma\right]g(x).$
(10.1)

Next, let us estimate the change in $d_{t,v}$ to get a differential equation
for $g$. We know that each neighbor of $v$ is deleted among Steps 2 and 3 with
probability $a_{t}$ or $b_{t}$, which is at least $b_{t}$. Moreover, any edge
incident to $v$ will be deleted in Step 5 by probability
$\approx\frac{\delta}{(1-t\delta)}$, because there are about
$2(1+\epsilon)\delta q$ colors picked in Step 1, relatively few conflicts in
Step 4, and the number of colors remaining is about
$2(1+\epsilon)(1-t\delta)q$. Thus, neglecting small error terms due to lack of
independence, we can choose to pick $d_{t,v}$ with the following behavior:

$\displaystyle d_{t+1,v}-d_{t,v}$
$\displaystyle\approx-\left[b_{t}+(1-b_{t})\frac{\delta}{1-t\delta}\right]d_{t,v}$
$\displaystyle(\tau-t-1)\delta g((t+1)\delta)d_{v}-(\tau-t)\delta
g(t\delta)d_{v}$ $\displaystyle\approx-\delta
g(t\delta)d_{v}-2(1+\epsilon)(\tau-t-1)\delta g(t\delta)d_{v}b_{t}$
$\displaystyle\frac{g((t+1)\delta)-g(t\delta)}{\delta}$
$\displaystyle\approx-2(1+\epsilon)\gamma\cdot\frac{g(t\delta)^{2}}{s(t\delta)}.$
(10.2)

Equation (10.2) suggests:
$g^{\prime}(x)=-2(1+\epsilon)\gamma\frac{g(x)^{2}}{s(x)}$. Combining with
Equation (10.1), we have that
$\frac{dg}{ds}=\frac{\gamma}{(1-\theta)+(1+\theta)\gamma}\cdot\frac{g}{s}$,
whose solution is $s=cg^{M}$ with
$M=\frac{(1-\theta)+(1+\theta)\gamma}{\gamma}$ for some constant $c$. Similar
to Section 5, by using the initial conditions that $g(0)=s(0)=1$, we get
$s(x)=(1-2(1+\epsilon)\cdot(1-\theta+\theta\gamma)x)^{\frac{M}{M-1}}$ and
$g(x)=(1-2(1+\epsilon)\cdot(1-\theta+\theta\gamma)x)^{\frac{1}{M-1}}$.

We show in the next section that the degrees of vertices and the sizes of
color classes are concentrated in some sense throughout the process, which
implies that we can not get stuck as long as $t\leq\eta\tau$ with
$\eta<\frac{1}{2(1+\epsilon)(1-\theta+\theta\gamma)}$ (note that we desire a
reasonable gap between $\eta$ and
$\frac{1}{2(1+\epsilon)(1-\theta+\theta\gamma)}$ to make room for the error
terms arising from concentration inequalities). Moreover, after $\eta\tau$-th
iteration for $\eta>\frac{1}{2(1+\epsilon)}$ (with a reasonable gap), the
number of edges in the rainbow matching will exceed $q$, even after accounting
for the discarded edges in Step 2 throughout the process. Thus, we need to
ensure that
$\frac{1}{2(1+\epsilon)}<\eta<\frac{1}{2(1+\epsilon)(1-\theta+\theta\gamma)}$.
It will turn out that, unlike before, we do not need to use any greedy
algorithm at the end to finish.

###  10.3 Formal analysis

Throughout this section, we assume $q$ to be sufficiently large to support our
arguments. Let $\gamma=\frac{1+\theta}{1+\epsilon}$ and
$M=\frac{(1-\theta)+(1+\theta)\gamma}{\gamma}$. Observe that $M>2$, which will
be used often in our analysis. Define the following two functions:

$s(x)=(1-2(1+\epsilon)\cdot(1-\theta+\theta\gamma)x)^{\frac{M}{M-1}}\;\;\;\text{and}\;\;\;g(x)=(1-2(1+\epsilon)\cdot(1-\theta+\theta\gamma)x)^{\frac{1}{M-1}}.$

Similar to Section 6, we introduce error terms $\alpha_{t}$ and $\beta_{t}$
which will be explicitly specified later and much less than $\frac{1}{100}$.
We will make sure that the following events happen after the $t$-th iteration
for $1\leq t\leq\eta\tau$:

  1. 1.

The remaining color classes have size exactly:

$s_{t}=(1-\alpha_{t})s(t\delta)q.$ (10.3)

  2. 2.

The degree of each survived vertex in $A$ is at most:

$d_{t}=2(1+\beta_{t})(1-t\delta)g(t\delta)(1+\epsilon)q.$ (10.4)

  3. 3.

The degree of each survived vertex outside $A$ is at most:

$d^{\prime}_{t}=2(1+\beta_{t})(1-t\delta)g(t\delta)(1+\theta)q.$ (10.5)

  4. 4.

For each color $\mathcal{C}$, if $V_{\mathcal{C}}$ denotes the set of all
vertices incident to an edge of color $\mathcal{C}$, then
$\frac{|V_{\mathcal{C}}\cap A|}{|V_{\mathcal{C}}|}\leq\frac{1-\theta}{2}$.

We fix some $t$ with $0\leq t<\eta\tau$ for this subsection and assume that
the above properties hold for $t$. Our goal is to show that after the
$(t+1)$-st iteration of the algorithm, w.v.h.p. the above properties will
continue to hold (notice that by a simple union bound, this is enough to
establish that w.v.h.p. these properties hold for every $1\leq
t\leq\eta\tau$). In this subsection, we show certain concentration bounds that
hold in the $(t+1)$-st iteration, and in the subsequent subsection, these
bounds will be used to achieve our goal.

Next, we explicitly define $a_{t}$ and $b_{t}$. The similar analysis as done
in Sections 6 or 8 leads us to define the following:

$a_{t}=2(1+\epsilon)\delta\cdot\frac{g(t\delta)(1+\beta_{t})}{s(t\delta)(1-\alpha_{t})}\;\;\;\;\;\;\text{and}\;\;\;\;\;\;b_{t}=2(1+\theta)\delta\cdot\frac{g(t\delta)(1+\beta_{t})}{s(t\delta)(1-\alpha_{t})}.$

Similar to before, we explicitly assign a probability for Step 3. For a fixed
$t$, at the $(t+1)$-st iteration we delete each vertex $v\in A$ independently
with probability $p_{v}$ such that
$p^{\prime}_{v}+(1-p^{\prime}_{v})p_{v}=a_{t}$, where $p^{\prime}_{v}$ is the
probability that $v$ gets deleted in Step 2. If $v\not\in A$, then we pick
$p_{v}$ such that $p^{\prime}_{v}+(1-p^{\prime}_{v})p_{v}=b_{t}$.

We now finally pick the values of the parameters. Recall that $\epsilon$ is a
fixed positive number less than $\frac{1}{10}$. Recall
$\theta=\frac{\epsilon}{2}$ and $\gamma=\frac{1+\theta}{1+\epsilon}$ as
introduced before. As mentioned in the intuitive analysis, we want $\eta$ such
that
$\frac{1}{2(1+\epsilon)}<\eta<\frac{1}{2(1+\epsilon)(1-\theta+\theta\gamma)}$.
Thus, explicitly let us define
$\eta=\frac{1}{2(1+\epsilon)}\cdot\frac{1-\frac{\theta}{2}+\frac{\theta\gamma}{2}}{1-\theta+\theta\gamma}$.
Let $\delta=\frac{1}{\log q}$. Note that $\epsilon$, $\theta$, $\gamma$, and
$\eta$ are all fixed constants, where the latter three constants are fixed
once $\epsilon$ is fixed. On the other hand, $\delta$ can be made arbitrarily
small by picking sufficiently large $q$.

Next, we have a few concentration bounds similar to the ones in Sections 6 and
8.

######  Lemma 10.1.

In Step 4 of the $(t+1)$-st iteration, at most
$\frac{8\delta^{2}q}{1-2(1+\epsilon)(1-\theta+\theta\gamma)t\delta}$ edges
aare discarded w.v.h.p.

###### Proof.

For $i<j$, let $X_{i,j}$ be the indicator random variable as defined in the
proof of Lemma 8.1. Clearly, the total number of edges discarded in Step 4 is
given by $X\leq\sum_{1\leq i<j\leq 2(1+\epsilon)\delta q}X_{i,j}$. By a
similar argument as in the proof of Lemma 8.1, the probability that
$X_{i,j}=1$ is at most $\frac{2d_{t}+s_{t}}{2(1+\epsilon)(1-t\delta)qs_{t}}$.
Hence, we have: