# Low-Memory Algorithms for Online and W-Streaming Edge Coloring

Prantar Ghosh DIMACS, Rutgers University. Research supported in part by a
grant (820931) to DIMACS from the Simons Foundation. Manuel Stoeckl Department
of Computer Science, Dartmouth College. This work was supported in part by the
National Science Foundation under award 2006589.

###### Abstract

For edge coloring, the online and the W-streaming models seem somewhat
orthogonal: the former needs edges to be assigned colors immediately after
insertion, typically without any space restrictions, while the latter limits
memory to sublinear in the input size but allows an edge’s color to be
announced any time after its insertion. We aim for the best of both worlds by
designing small-space online algorithms for edge coloring. We study the
problem under both (adversarial) edge arrivals and vertex arrivals. Our
results significantly improve upon the memory used by prior online algorithms
while achieving an $O(1)$-competitive ratio. In particular, for $n$-node
graphs with maximum vertex-degree $\Delta$ under edge arrivals, we obtain an
online $O(\Delta)$-coloring in $\tilde{O}(n\sqrt{\Delta})$ space. This is also
the first W-streaming edge-coloring algorithm using $O(\Delta)$ colors (in
sublinear memory). All prior works either used linear memory or
$\omega(\Delta)$ colors. We also achieve a smooth color-space tradeoff: for
any $t=O(\Delta)$, we get an $O(\Delta t(\log^{2}\Delta))$-coloring in
$\tilde{O}(n\sqrt{\Delta/t})$ space, improving upon the state of the art that
used $\tilde{O}(n\Delta/t)$ space for the same number of colors (the
$\widetilde{O}(.)$ notation hides polylog$(n)$ factors). The improvements stem
from extensive use of random permutations that enable us to avoid previously
used colors. Most of our algorithms can be derandomized and extended to
multigraphs, where edge coloring is known to be considerably harder than for
simple graphs.

##  1 Introduction

A proper edge-coloring of a graph or a multigraph colors its edges such that
no two adjacent edges share the same color. The goal is to use as few colors
as possible. Any graph with maximum vertex-degree $\Delta$ trivially requires
$\Delta$ colors to be properly edge-colored. A celebrated theorem of Vizing
[Viz64] says that $\Delta+1$ colors suffice for any simple graph.111For
multigraphs, $3\Delta/2$ colors are necessary and sufficient. [Sha49] There
are constructive polynomial time algorithms that achieve a $(\Delta+1)$-edge-
coloring in the classical offline setting [MG92]. These algorithms are likely
to be optimal with respect to the number of colors: distinguishing between
whether the edge-chromatic number (i.e., the minimum number of colors needed
to edge-color a graph) of a simple graph is $\Delta$ or $\Delta+1$ is NP-hard
[Hol81].

The edge-coloring problem has several practical applications, including in
switch routing [AMSZ03], round-robin tournament scheduling [JURdW16], call
scheduling [EJ01], optical networks [RU94], and link scheduling in sensor
networks [GDP05]. In many of these applications, such as in switch routing,
the underlying graph is built gradually by a sequence of edge insertions and
the color assignments need to be done instantly and irrevocably. This is
modeled by the _online_ edge coloring problem. Due to its restrictions, an
online algorithm cannot obtain a $(\Delta+1)$-coloring [BMN92]. Consider,
however, the simple greedy algorithm that colors every edge with the first
available color that is not already assigned to any of its neighbors. Since
each edge can have at most $2\Delta-2$ adjacent edges, this algorithm achieves
a $(2\Delta-1)$-coloring, i.e., a competitive ratio of $2-o(1)$ (since the
optimum is $\Delta$ or $\Delta+1$). Bar-Noy, Motwani, and Naor [BMN92] showed
that no online algorithm can perform better than this greedy algorithm.
However, they proved this only for graphs with max-degree $\Delta=O(\log n)$.
They conjectured that for $\Delta=\omega(\log n)$, it is possible to get
better bounds, and that, in particular, a $(1+o(1))\Delta$-coloring is
possible. Several works [AMSZ03, BMM12, CPW19, BGW21, SW21, KLS+22, NSW23]
have studied online edge coloring with the aim of beating the greedy algorithm
and/or resolving the said conjecture. Other variants of the problem have also
been studied [FN03, Mik16, FM18]. However, all prior works assume that all
graph edges are always stored in the memory along with their colors.

With the ubiquity of big data in the modern world, this assumption often seems
fallacious. The graphs that motivate the study of edge coloring, such as
communication and internet routing networks, turn out to be large-scale or
massive graphs in today’s world, making it expensive for servers to store them
entirely in their memory. This has led to big graph processing models such as
_graph streaming_ that, similar to the online model, have sequential access to
the graph edges, but can only store a small summary of the input graph so as
to solve a problem related to it. There is an immediate barrier for the edge
coloring problem in this setting: the output size is as large as the input,
and hence an algorithm must use space linear in the input size to present the
output as a whole. To remedy this, one can consider the natural extension of
the model where the output is also reported in streaming fashion: in the
context of edge coloring, think of the algorithm having a limited working
memory to store information about both the input graph and the output
coloring; it periodically streams or announces the edge colors before deleting
them from its memory. This is the so called W-streaming model. Unlike the
online model, here we don’t need to assign a color to the incoming edge right
away, and can defer it to some later time. However, due to the space
restriction, we are not able to remember all the previously announced colors.
Note that this makes even the greedy $(2\Delta-1)$-coloring algorithm hard (or
maybe impossible) to implement in this model.

In this work, we aim to get the best of both worlds of the online and the
streaming models: we focus on designing _low-memory_ online algorithms for
edge coloring. This is motivated by modern practical scenarios that demand
immediate color assignment as well as space optimization. We succeed in
designing such algorithms and at the same time, the quality of our algorithms
is close to optimal: we achieve an $O(1)$-competitive ratio, i.e., a color
bound of $O(\Delta)$. Note that no prior work studying edge-coloring in the
sublinear-space setting could attain an $O(\Delta)$-coloring W-streaming
algorithm, let alone online. For adversarial edge-arrival streams, we get an
online $O(\Delta)$-coloring in $O(n\sqrt{\Delta})$ space, significantly
reducing the space used by prior online algorithms at the cost of only a
constant factor in the number of colors. We can smoothly tradeoff space with
colors to get an $O(\Delta t)$-coloring in $\widetilde{O}(n\sqrt{\Delta/t})$
space. This improves upon the state of the art [CL21, ASZZ22] which obtained
the same color bound using $\widetilde{O}(n\Delta/t)$ space. Furthermore, for
the natural and well-studied settings of vertex-arrival in general graphs and
one-sided vertex arrival in bipartite graphs, we can improve the space usage
to $O(n\text{ polylog }n)$, i.e., semi-streaming, which is the most popular
memory regime for graph streaming problems. Most of our algorithms generalize
to multigraphs and can be made deterministic.

###  1.1 Our Results and Contributions

We study edge-coloring in the online model with sublinear (i.e., $o(n\Delta)$)
memory as well as in the W-streaming model and improve upon the state of the
art. These results are summarized in Table 1 and Table 2. They also mention
the state of the art, for comparison.

Arrival | Algorithm | Colors | Space | Graph | Reference
---|---|---|---|---|---
Edge | Randomized | $\left(\frac{e}{e-1}+o(1)\right)\Delta$ | $\widetilde{O}(n\Delta)$ | Simple | [KLS+22]
Edge | Randomized | $O(\Delta)$ | $\widetilde{O}(n\sqrt{\Delta})$ | Simple | Theorem 1.1
Edge | Deterministic | $(2\Delta-1)t$ | $O(n\Delta/t)$ | Multigraph | [ASZZ22]
Edge | Deterministic | $\widetilde{O}(\Delta t)$ | $\widetilde{O}(n\sqrt{\Delta/t})\star$ | Multigraph | Theorem 1.3
Vertex | Randomized | $(1.9+o(1))\Delta$ | $\widetilde{O}(n\Delta)$ | Simple | [SW21]
Vertex | Randomized | $O(\Delta)$ | $\widetilde{O}(n)\star$ | Multigraph | Theorem 1.5
Vertex | Deterministic | $2\Delta-1$ | $O(n\Delta)$ | Multigraph | Greedy folklore
Vertex | Deterministic | $O(\Delta)$ | $\widetilde{O}(n)\star$ | Multigraph | Theorem 1.6
One-sided vertex | Randomized | $(1+o(1))\Delta$ | $\widetilde{O}(n\Delta)$ | Simple | [CPW19]
One-sided vertex | Randomized | $1.533\Delta$ | $\widetilde{O}(n\Delta)$ | Multigraph | [NSW23]
One-sided vertex | Randomized | $5\Delta$ | $\widetilde{O}(n)\star$ | Multigraph | Lemma 3.2
One-sided vertex | Deterministic | $2\Delta-1$ | $O(n\Delta)$ | Multigraph | Greedy folklore
One-sided vertex | Deterministic | $O(\Delta)$ | $\widetilde{O}(n)\star$ | Multigraph | Lemma 3.6
Table 1: Our results in the online model. Here, $t=O(\Delta)$ is any positive integer. Algorithms marked with a $\star$ require oracle randomness for randomized algorithms and advice computable in exponential time for deterministic. Algorithm | Colors | Space | Graph | Reference
---|---|---|---|---
Randomized | $O(\Delta^{2}/s)$ | $\widetilde{O}(ns)$ | Simple | [CL21]
Randomized | $O(\Delta^{2}/s)$ | $\widetilde{O}(n\sqrt{s})$ | Simple | Section 1.1
Randomized | $O(\Delta^{2}/s)$ | $\widetilde{O}(n\sqrt{s})\star$ | Multigraph | Theorem 1.2
Deterministic | $(1-o(1))\Delta^{2}/s$ | $O(ns)$ | Simple | [ASZZ22]
Deterministic | $\widetilde{O}(\Delta^{2}/s)$ | $\widetilde{O}(n\sqrt{s})\star$ | Multigraph | Section 1.1
Table 2: Our results in the W-streaming model. Here, $s\leq\Delta/2$ is any
positive integer. Results marked with $\star$ require oracle randomness for
randomized algorithms and advice computable in exponential time for
deterministic.

We consider the problem under (adversarial) edge-arrivals as well as vertex-
arrivals. We give an account of our results in each of these models below.

Edge-arrival model. Here we design both online and W-streaming algorithms.

######  Theorem 1.1 (Formalized in Theorem 4.4).

Given any adversarial edge-arrival stream of a simple graph, there is a
randomized algorithm for online $O(\Delta)$-edge-coloring using
$\widetilde{O}(n\sqrt{\Delta})$ bits of space.

Previously, there was no sublinear space online algorithm known for
$O(\Delta)$-coloring. As observed in Table 1, all prior algorithms need
$\Theta(n\Delta)$ space in the worst case to achieve a color bound of
$O(\Delta)$.

Note that Theorem 1.1 immediately implies a randomized W-streaming algorithm
with the same space and color bounds. Although immediate, we believe that it
is important to note it as a corollary.

######  Corollary 1.1.

Given an adversarially ordered edge stream of any simple graph, there is a
randomized W-streaming algorithm for $O(\Delta)$-edge-coloring using
$\widetilde{O}(n\sqrt{\Delta})$ bits of space.

The above result improves upon the state of the art algorithms of [CL21,
ASZZ22] which, as implied by Table 2, only obtain $\omega(\Delta)$-colorings
for $o(n\Delta)$ space (the non-trivial memory regime in W-streaming). In
fact, we improve upon them by a factor of $\Omega(\sqrt{\Delta})$ in space for
$O(\Delta)$-coloring.

We show that the above W-streaming algorithm can be made to work for
multigraphs and against adaptive adversaries at the cost of
$\widetilde{O}(n\Delta)$ bits of oracle randomness.

######  Theorem 1.2 (Formalized in Theorem 4.3).

Given an adversarially ordered edge stream of any multigraph, there is a
randomized W-streaming algorithm for $O(\Delta)$ edge-coloring using
$\widetilde{O}(n\sqrt{\Delta})$ bits of space and $\widetilde{O}(n\Delta)$
bits of oracle randomness. The algorithm works even against adaptive
adversaries.

Further, we prove that we can make the above algorithms deterministic at the
cost of only a polylogarithmic factor in space. Once again, the online
algorithm immediately implies a W-streaming algorithm.

######  Theorem 1.3 (Formalized in Theorem 4.7).

Given an adversarial edge-arrival stream of edges of any multigraph, there is
a deterministic algorithm for online $O(\Delta(\log^{2}\Delta))$-edge-coloring
using $\widetilde{O}(n\sqrt{\Delta})$ bits of space.

######  Corollary 1.3.

Given an adversarially ordered edge stream of any multigraph, there is a
deterministic W-streaming algorithm for $O(\Delta(\log^{2}\Delta))$-edge-
coloring using $\widetilde{O}(n\sqrt{\Delta})$ bits of space.

Furthermore, in each case, we can achieve a smooth tradeoff between the number
of colors and the memory used. This is implied by a framework captured in the
following lemma.

######  Lemma 1.4 (Formalized and generalized in Lemma 4.1).

Suppose that we are given an $f(n,\Delta)$-space streaming algorithm
$\mathcal{A}$ for $O(\Delta)$-coloring any $n$-node multigraph with max-degree
$\Delta$ under adversarial edge arrivals. Then, for any $s\geq 1$, there is a
streaming algorithm $\mathcal{B}$ for $O(s\Delta)$-coloring the same kind of
graphs under adversarial edge arrivals using $f(n/s,s\Delta)+\widetilde{O}(n)$
bits of space.

For the online model, the above lemma combined with Theorem 1.3 immediately
gives the tradeoff of $\widetilde{O}(\Delta t)$ colors and
$\widetilde{O}(n\sqrt{\Delta/t})$ space for any $t=O(\Delta)$, as claimed in
Table 1. In other words, combined with Section 1.1, it implies the W-streaming
bounds of $O(\Delta^{2}/s)$ colors and $O(n\sqrt{s})$ space for any
$s=O(\Delta)$, as claimed in Table 2. Note that our results match the tradeoff
obtained by the state of the art for $t=\Theta(\Delta)$ and $s=O(1)$, and
strictly improve upon them for $t=o(\Delta)$ and $s=\omega(1)$.

Vertex-Arrival Model. We now turn to the weaker vertex-arrival model. The
online edge-coloring problem has been widely studied in this setting as well
(see Section 1.2 for a detailed discussion). Our online algorithms obtain
significantly better space bounds than the edge-arrival setting.

######  Theorem 1.5 (Formalized in Theorem 3.3).

Given any adversarial vertex-arrival stream of a multigraph, there is a
randomized online $O(\Delta)$-edge coloring algorithm using $\widetilde{O}(n)$
bits of space. It works even against an adaptive adversary and uses
$\widetilde{O}(n\Delta)$ oracle random bits.

Thus, at the cost of only a constant factor in the number of colors, we can
improve the memory usage from $\widetilde{O}(n\Delta)$ to $\widetilde{O}(n)$
for vertex-arrival streams. Since this algorithm immediately implies a
W-streaming algorithm with the same bounds, we see that for vertex-arrival
streams, $O(\Delta)$-coloring can be achieved in semi-streaming space, the
most popular space regime for graph streaming. Behnezhad et al. [BDH+19]
mentioned that “a major open question is whether [the number of colors for
W-streaming edge-coloring] can be improved to $O(\Delta)$ while also keeping
the memory near-linear in $n$.” Our results answer the question in the
affirmative for vertex-arrival streams, which is a widely studied model in the
streaming literature as well.

Further, we show that the algorithm can be made deterministic using
$\widetilde{O}(n)$ bits of _advice_ instead of $\widetilde{O}(n\Delta)$ bits
of oracle randomness. By picking a uniformly random advice string, the same
algorithm can alternatively be used as a robust algorithm with
$1/\operatorname{poly}(n)$ error; the advice can also be computed in
exponential time.

######  Theorem 1.6 (Formalized in Theorem 3.7).

Given any adversarial vertex-arrival stream of a multigraph, there is a
deterministic online $O(\Delta)$-edge-coloring algorithm using
$\widetilde{O}(n)$ bits of space, using $\widetilde{O}(n)$ bits of advice.

An interesting special case of the vertex-arrival model is the one-sided
vertex-arrival setting for bipartite graphs. Here, the vertices on one side of
the bipartite graph are fixed, while the vertices on the other side arrive in
a sequence along with their incident edges. A couple of works [CPW19, NSW23]
have studied online edge-coloring specifically in this model. We design low-
memory online algorithms in this model (see Algorithms 3 and 4) and use them
as building blocks for our algorithms in the more general settings of vertex-
arrival and edge-arrival. These algorithms maybe of independent interest due
to practical applications of the one-sided vertex-arrival model; moreover, the
randomized algorithm in this model uses only $5\Delta$ colors (as opposed to
our algorithms where the hidden constant in $O(\Delta)$ is rather large).

Finally, we present a lower bound on the space requirement of a deterministic
online edge-coloring algorithm.

######  Theorem 1.7 (Formalized in Theorem 5.2).

For $\Delta\leq\varepsilon n$ for a sufficiently small constant $\varepsilon$,
any deterministic online algorithm that edge-colors a graph using
$(2-o(1))\Delta$ colors requires $\Omega(n)$ space.

To the best of our knowledge, this is the first non-trivial space lower bound
proven for an online edge-coloring algorithm.

An outline of how the several building blocks are put together to obtain the
above results is given in Figure 1.

Theorem 1.5 Theorem 1.6 Theorem 1.2 Theorem 1.1 Theorem 1.3 Lemma 1.4 Theorem
1.7 Lemma 3.2 Lemma 3.6 Lemma 3.5 Lemma 3.4 Lemma 6.1 Lemma 4.2 Section 3
Section 3 [SS96], as Section 6 Lemma 4.6 Lemma 6.2 Lemma 4.5 [Mor13] Lemma 5.1
Figure 1: Overview of how the results in this paper fit together. Primary
results are in red; main supporting lemmas in orange; and specific external
results in yellow.

###  1.2 Related Work

Online model. The edge-coloring problem has a rich literature in the online
model [AMSZ03, ASZZ22, BMN92, BMM12, BGW21, CPW19, FM18, FN03, Mik15, Mik16,
NSW23, KLS+22, SW21]. The seminal work of Bar-Noy, Motwani, and Naor [BMN92]
showed that no online algorithm can do better than the greedy algorithm that
obtains a $(2\Delta-1)$-coloring by assigning each edge the first available
color that’s not already used by any of its adjacent edges. However, this
lower bound applies only to graphs with $\Delta=O(\log n)$. They conjectured
that for $\Delta=\omega(\log n)$, there exist online $(1+o(1))\Delta$-coloring
algorithms. Although this conjecture remains unresolved, there has been
significant progress on it over the years. A number of works [AMSZ03, BMM12,
BGW21] considered the problem under _random-order_ edge arrivals: Aggarwal et
al. [AMSZ03] showed that if $\Delta=\omega(n^{2})$, then a
$(1+o(1))\Delta$-coloring is possible. For $\Delta=\omega(\log n)$ (the bound
in the said conjecture), Bahmani et al. [BMM12] obtained a
$1.26\Delta$-coloring. Bhattacharya et al. [BGW21] then attained the “best of
both worlds” by designing a $(1+o(1))\Delta$-coloring algorithm for
$\Delta=\omega(\log n)$, resolving the conjecture for random-order arrivals.

More relevant to our work is the setting of _adversarial-order_ edge arrivals.
Cohen et al. [CPW19] were the first to make progress on [BMN92]’s conjecture
in this setting: they obtained a $(1+o(1))\Delta$-coloring for bipartite
graphs under one-sided vertex arrivals (i.e., the nodes on one side are fixed,
and the nodes on the other side arrive one by one with all incident edges).
Their algorithm assumes a priori knowledge of the value of $\Delta$. For
unknown $\Delta$, they prove that no online algorithm can achieve better than
a $(e/(e-1))\Delta$-coloring, and also complement this result with a
$(e/(e-1)+o(1))\Delta$-coloring algorithm for unknown $\Delta$. For bipartite
_multigraphs_ with one-sided vertex arrivals, Naor et al. [NSW23] very
recently prove that $1.533\Delta$ colors suffice, while at least $1.207\Delta$
colors are necessary even for $\Delta=2$. Saberi and Wajc [SW21] showed that
it is possible to beat the greedy algorithm for $\Delta=\omega(\log n)$ under
vertex arrivals in general graphs: they design a $(1.9+o(1))\Delta$-coloring
algorithm. Recently, Kulkarni et al. [KLS+22] made the first progress on the
said conjecture in the general setting of adversarial edge arrivals: they
obtained a $(e/(e-1)+o(1))\Delta$-coloring in this model. Note that the focus
of all these works was on resolving [BMN92]’s conjecture without any space
limitations. Our focus is on designing low-memory online algorithms while
staying within a constant factor of the optimal number of colors. The only
prior sublinear-space online edge-coloring algorithm we know was given by
Ansari et al. [ASZZ22]: a (deterministic) online $2\Delta t$-coloring in
$O(n\Delta/t)$ space for any $t\leq\Delta$.

A number of works [FN03, EFKM10, FM18] have studied the variant of the problem
where given a fixed number of colors, the goal is to color as many edges as
possible. Mikkelsen [Mik15, Mik16] considered online edge-coloring with
limited advice for the future.

W-Streaming model. The W-streaming model [DFR06] is a natural extension of the
classical streaming model for the study of problems where the output size is
very large, possibly larger than our memory. While prior works have considered
several graph problems in this model [DFR06, DEMR10, LS11, GSS22], we are only
aware of three papers [BDH+19, CL21, ASZZ22] that have studied edge-coloring
here. Behnezhad et al. [BDH+19] initiated the study of W-streaming edge-
coloring algorithms. They considered the problem for both adversarial-order
and random-order streams: using $\widetilde{O}(n)$ bits of working memory,
they gave an $O(\Delta^{2})$-coloring in the former setting, and a
$(2e\Delta)$-coloring in the latter setting. Charikar and Liu [CL21] improved
these results: for adversarial-order streams, for any $s=\Omega(\log n)$, they
gave an $O(\Delta^{2}/s)$-coloring algorithm that uses $\widetilde{O}(ns)$
space; and for random-order streams, they gave a $(1+o(1))\Delta$-coloring
algorithm using $\widetilde{O}(n)$ space. Both of the aforementioned
algorithms for adversarial-order streams are, however, randomized. Ansari et
al. [ASZZ22] gave simple deterministic algorithms achieving the same bounds of
$O(\Delta^{2}/s)$ colors and $\widetilde{O}(ns)$ space. Their algorithm can
also be made online at the cost of a factor of $2$ in the number of colors.
Note that parameterizing our results in Table 2 appropriately, our algorithms
achieve $O(\Delta^{2}/s)$-colorings in $\widetilde{O}(n\sqrt{s})$ space,
matching the state of the art for $s=O(1)$, and strictly improving upon it for
$s=\omega(1)$.

Concurrent work. In an independent and parallel work, Behnezhad and Saneian
[BS23] have designed a randomized $\widetilde{O}(n\sqrt{\Delta})$-space
W-streaming algorithm for $O(\Delta)$-edge-coloring for edge-arrival streams
in simple general graphs. This matches our Section 1.1. Their result
generalizes to give, for any $s\in[\sqrt{\Delta}]$, an $O(\Delta^{1.5}/s)$
coloring algorithm in $\widetilde{O}(ns)$ space, while we achieve an
$O(\Delta^{2}/s)$-coloring in the same space. They also get an
$O(\Delta)$-edge-coloring algorithm for vertex-arrival streams using
$\widetilde{O}(n)$ space, similar to our Theorem 1.5. Note that some of our
edge-arrival algorithms have the additional strong feature of being online,
while it is not clear if their edge-arrival algorithm can also be implemented
in the online setting. In terms of techniques, while both works have some high
level ideas in common, e.g., using random offsets/permutations to keep track
of colors, or designing a one-sided vertex-arrival algorithm first and
building on it to obtain the edge-arrival algorithm, the final algorithms and
analyses in the two papers are fairly different.

Another independent work by Chechik, Mukhtar, and Zhang [CMZ23] obtains a
randomized W-streaming algorithm that edge-colors an edge-arrival stream on
general multi-graphs using $O(\Delta^{1.5}\log\Delta)$ colors in
expectation222While [CMZ23] does not claim this, one can prove their algorithm
uses $O(\Delta^{1.5}\log\Delta)$ colors with $\geq 1-1/\operatorname{poly}(n)$
probability., and $\widetilde{O}(n)$ bits of space in expectation. Unlike us,
they make no claims in the online model.

##  2 Preliminaries

###  2.1 Notation

Throughout the paper, logarithms are in base $2$. The notation $[t]$ indicates
the set of integers $\\{1,\ldots,t\\}$. The notation $\widetilde{O}(x)$
ignores $\operatorname{poly}(\log(n),\log(\Delta))$ factors in $x$. $A\sqcup
B$ gives the disjoint union of $A$ and $B$. $S_{t}$ is the set of permutations
over $[t]$, and for any permutation $\sigma\in S_{t}$ and $X\subseteq[t]$, we
denote $\sigma[X]:=\\{\sigma_{i}:i\in X\\}$. For any set $X$, $\binom{X}{k}$
denotes the set of all $k$-sized subsets of $X$.

If not otherwise stated, $n$ is the number of vertices in a graph $G$, $V$ the
set of vertices (or $A\sqcup B$ if the graph is bipartite), $E$ the
(multi-)set of edges, and $\Delta$ is the maximum degree of the graph.

###  2.2 Basic Definitions

######  Definition 2.0.

A random permutation $\sigma$ in $S_{n}$ is $k$-wise independent if, for all
distinct $a_{1},\ldots,a_{k}$ in $[n]$, and distinct $b_{1},\ldots,b_{k}$ in
$[n]$, we have:

$\displaystyle\Pr\left[\bigwedge_{i\in[k]}\\{\sigma(a_{i})=b_{i}\\}\right]=\frac{1}{\prod_{i\in[k]}(n-i+1)}$

A family of permutations is $k$-wise independent if the random variable for a
uniformly randomly chosen element of that family is $k$-wise independent.

Per [AL12], while it is not known if there are nontrivial $k$-wise independent
families of permutations for large $k$ and $n$, one can always construct
weighted distributions which have support of size $n^{O(k)}$ and provide
$k$-wise independence.

A random permutation $\sigma$ is $(\epsilon,k)$-wise independent if for all
distinct $a_{1},\ldots,a_{k}$ in $[n]$, the distribution of $\sigma$ on
$a_{1},\ldots,a_{k}$ has total variation distance $\leq\epsilon$ from uniform.
In other words,

$\displaystyle\frac{1}{2}\sum_{\text{distinct $b_{1},\ldots,b_{k}$ in
$[n]$}}\left|\Pr\left[\bigwedge_{i\in[k]}\\{\sigma(a_{i})=b_{i}\\}\right]-\frac{1}{\prod_{i\in[k]}(n-i+1)}\right|\leq\epsilon$

We say almost $k$-wise independent, when the random permutation is
$(\epsilon,k)$-wise independent for sufficiently small $\epsilon$.

###  2.3 Models

This paper will use the following models of presenting edges to an algorithm
to be colored. In all cases, the set of vertices for the graph is known in
advance. For general graphs, we call the set of vertices $V$; for bipartite
graphs, $V$ is partitioned into two disjoint sets, which we typically call $A$
and $B$. Let $G$ be the (multi-) graph formed by taking the union of all edges
in the stream.

We assume that the maximum degree $\Delta$ of $G$ is known in advance. An
edge-coloring algorithm for which $\Delta$ is not known in advance can be
converted to one which is, although one way to do this conversion (by running
a new $2\Delta$-coloring algorithm with a fresh set of colors whenever the
maximum degree of graph formed by the input stream doubles) increases the
total number of colors used by a constant factor, and requires
$O(n\log\Delta)$ bits of space to keep track of the maximum degree. Since the
algorithms in this paper already have large constant factors on number of
colors used, it is not worth it to optimize the algorithms for the case where
$\Delta$ is not known in advance.

######  Definition 2.0.

With an _edge arrival stream_ , the algorithm is given a sequence of edges in
the graph. Each edge is provided as an ordered pair $\\{x,y\\}$ of vertices in
$V$. In this paper, online algorithms processing edge arrival streams will
implement a method $\textsc{Process}(\\{x,y\\})$ which returns the color
assigned to the edge. For example, see Algorithm 1, an implementation of the
greedy edge coloring algorithm using $O(n\Delta)$ bits of space. W-streaming
algorithms may assign the color for an edge at any time, although all edges
must be given a color at the end of the stream.

######  Definition 2.0.

In a _vertex arrival stream_ , the algorithm is given a sequence of
(vertex,edge-set) pairs $(v,M_{v})$, where the edge set $M_{v}$ contains all
edges from $v$ to vertices that have been seen earlier in the stream. Online
algorithms should report colors for all edges in $M_{v}$ when $(v,M_{v})$ is
processed.

A _one-sided vertex arrival stream_ on a bipartite graph with parts $A,B$ is
like a vertex arrival stream, if which the vertices for one part ($B$) were
all presented first, and then all the (vertex,edge-set) pairs for the other
part ($A$) are given. For one-sided vertex arrival, we assume that the
algorithm knows parts $A$ and $B$ in advance, and receives the (vertex,edge-
set) pairs for $B$. The stream consists of pairs $(v,M_{v})$, where each $v\in
A$, and $M_{v}$ contains all edges from $v$ to $B$.

An algorithm is said to be robust if it works with $\geq 1-\delta$ probability
even when its input streams are adaptively generated. By "adaptively
generated", we mean that the input is produced by an adaptive adversary that
sees all outputs of the online (or W-streaming) algorithm, and repeatedly
chooses the next element of the stream based on what the algorithm has output
so far. See [BJWY20] for a more detailed explanation.

Algorithm 1 An implementation of a greedy $2\Delta-1$ online edge-coloring
algorithm using $O(n\Delta)$ bits of space

1:Input: Stream of edges in an $n$-vertex graph $G=(V,E)$

2:

3:Initialize:

4:for $v\in V$ do

5: $U_{v}\leftarrow\emptyset$ is a subset of $[2\Delta-1]$

6:

7:Process(edge $\\{x,y\\}$) $\rightarrow$ color

8:Let $c$ be arbitrary color in $[2\Delta-1]\setminus U_{x}\setminus U_{y}$

9:Add $c$ to $U_{x}$ and to $U_{y}$

10:return color $c$

##  3 Edge coloring on vertex arrival streams

######  Lemma 3.1 (Deterministic general-to-bipartite partitioning).

For sufficiently large $n$, there is a set of $t=4{\left\lceil{\log
n}\right\rceil}$ bipartite graphs $F_{1},\ldots,F_{t}$, and an online
algorithm $\mathcal{A}$, which processes a stream of edges and assigns each
edge to one of the $t$ graphs. The algorithm ensures that at each time, for
each vertex $v$, $\deg_{F_{i}}(v)\leq\frac{300}{\log n}\deg_{G}(x)+1$. It uses
$O(n(\log n)(\log\Delta))$ bits of space.

Using Lemma 3.1 to route edges to $O(\log n)$ instances of an algorithm that
$f(\hat{\Delta})$ colors bipartite graphs of max degree $\leq\hat{\Delta}$
implies the following corollary.

######  Corollary 3.1 (Of Lemma 3.1).

Say $f:\mathbb{N}\mapsto\mathbb{N}$ is a function for which $f(x)/x$ is
monotonically increasing. Then given an algorithm $\mathcal{A}$ for edge
coloring with $f(\Delta)$ colors on edge arrival streams over bipartite graphs
of max degree $\Delta$, which uses $g(n,\Delta)$ bits of space, one can
implement an algorithm $\mathcal{B}$ for edge coloring with $O(f(\Delta))$
colors on general graphs, using $O((g(n,\Delta)+n\log\Delta)\log n)$ space.

Combining the previous corollary with that fact that one can convert an
algorithm for one-sided vertex arrival streams on bipartite graphs to general
("two-sided") vertex arrival streams on bipartite graphs, only doubling the
number of colors used, gives the following:

######  Corollary 3.1 (Of Lemma 3.1).

Say $f:\mathbb{N}\mapsto\mathbb{N}$ is a function for which $f(x)/x$ is
monotonically increasing. Then given an algorithm $\mathcal{A}$ for edge
coloring with $f(\Delta)$ colors on one-sided vertex arrival streams over
bipartite graphs of max degree $\Delta$, which uses $g(n,\Delta)$ bits of
space, one can implement an algorithm $\mathcal{B}$ for edge coloring under
vertex arrivals of general graphs using $O(f(\Delta))$ colors and
$O((g(n,\Delta)+n\log\Delta)\log n)$ space.

###### Proof of Lemma 3.1.

We claim Algorithm 2 works for sufficiently large $n$.

Algorithm 2 Algorithm to partition general graph edges into bipartite graphs

1:Input: Stream of edges in an $n$-vertex graph $G=(V,E)$

2:

3:Initialize:

4:for $v\in V$ do

5: $\deg_{F_{i}}(v)\leftarrow 0$

6:Setup binary code $\mathcal{C}$ of length $t:=4{\left\lceil{\log
n}\right\rceil}$ from Section 6

7:for $i\in[t]$ do

8: Let $F_{i}$ be the bipartition with parts $A_{i}=\\{v\in
V:\mathcal{C}(v)_{i}=0\\}$ and $B_{i}=\\{v\in V:\mathcal{C}(v)_{i}=1\\}$

9:

10:Process(edge $\\{x,y\\}$)

11:Let $\deg(x)=\sum_{i\in[t]}\deg_{F_{i}}(x)$ and
$\deg(y)=\sum_{i\in[t]}\deg_{F_{i}}(y)$.

12:for $i\in[t]$ do

13: if $\mathcal{C}(x)_{i}\neq\mathcal{C}(y)_{i}$ and $\deg_{F_{i}}(x)\leq
1200\deg(x)/t$ and $\deg_{F_{i}}(y)\leq 1200\deg(y)/t$ then

14: Increase $\deg_{F_{i}}(x)$ and $\deg_{F_{i}}(y)$ by 1

15: Assign edge $\\{x,y\\}$ to $F_{i}$

16: return

17:unreachable

It is clear that at each point in time, for all $v\in V$ and $i\in[t]$, the
algorithm will have $\deg_{F_{i}}(v)$ be the number of edges assigned to
$F_{i}$ incident on $v$.

Line 13 of the algorithm ensures that before edge $\\{x,y\\}$ is assigned,
$\deg_{F_{i}}(x)\leq 1200\deg(x)/t$. Consequently, after the edge is assigned,
$\deg_{F_{i}}(x)\leq 1200\deg(x)/t+1\leq 300\deg(x)/\log(n)+1$. Similarly, we
will have $\deg_{F_{i}}(y)\leq 300\deg(y)/\log(n)+1$.

It remains to prove that the algorithm will always assign an edge, and that
Line 17 is never reached. When processing edge an $\\{x,y\\}$, define
$B_{v}:=\\{i\in[t]:\deg_{F_{i}}(v)>1200\deg(v)/t$. By Markov’s inequality,
since $\sum_{i\in[t]}\deg_{F_{i}}(v)=\deg(v)$, $|B_{v}|\leq t/1200$. Because
the code $\mathcal{C}$ has minimum distance $t/400$, the set
$K=\\{i:\mathcal{C}(x)_{i}\neq\mathcal{C}(y)_{i}\\}$ has size $\geq t/400$;
and the set of $i\in[t]$ for which Line 13 passes has size $|K\setminus
B_{x}\setminus B_{y}|\geq t/400-t/1200-t/1200=t/1200$, and hence is nonempty.
∎

######  Lemma 3.2.

Theorem 1.5 holds for one-sided vertex arrival streams on bipartite graphs.

###### Proof of Lemma 3.2.

Consider Algorithm 3. This algorithm will have the required properties if
$\Delta\geq 6\ln\frac{n}{\delta}$; if $\Delta$ is smaller, convert the vertex
arrival stream to an edge arrival stream and pass it to Algorithm 1, which
guarantees a $2\Delta-1$ coloring of the graph using
$O(n\Delta)=O(n\ln\frac{n}{\delta})$ bits of space.

Algorithm 3 Randomized algorithm for $5\Delta$ edge coloring for (adversarial)
one sided vertex arrival bipartite streams

1:Input: Stream of vertex arrivals $n$-vertex graph $G=(A\sqcup B,E)$

2:

3:Initialize:

4:Let $C=5\Delta$.

5:for $v\in B$ do

6: Let $\sigma_{v}$ be a uniformly random permutation over $[C]$
$\triangleright$ constructed on demand from random oracle bits.

7: $h_{v}\leftarrow 1$.

8:Process(vertex $x$ with multiset $M_{v}$ of edges to $B$)

9:Let $S\leftarrow\emptyset$ $\triangleright$ Set of colors $M_{x}$ will have
used so far

10:for $e=\\{x,y\\}$ in $M_{x}$, in arbitrary order do

11: while $h_{y}\leq C\land\sigma_{y}[h_{y}]\in S$ do

12: $h_{y}\leftarrow h_{y}+1$

13: if $h_{y}>C$ then

14: abort

15: Assign color $\sigma_{y}[h_{y}]$ to $e$

16: $S\leftarrow S\cup\\{\sigma_{y}[h_{y}]\\}$

17: $h_{y}\leftarrow h_{y}+1$

This algorithm will never assign the same color to any pair of edges adjacent
to the same vertex; at worst, it will abort. The condition on Line 11 ensures
that when a vertex $x$ is processed, no two edges will be assigned the same
color. On the other hand, after Line 15 assigns a color to an edge, Line 17
increases $h_{y}$; because $\sigma_{v}$ is a permutation, this prevents the
algorithm from ever assigning the same color twice to edges incident on some
vertex $y$ in $B$.

For the rest of the proof, we will argue that the algorithm never aborts;
equivalently, that $h_{y}\leq C$ always holds for all $y\in B$. In fact, we
shall prove the stronger claim, that $h_{y}\leq C-2\Delta$ holds with
probability $\geq 1-\delta/n$ for each individual $y\in B$. Consider a
specific vertex $y\in B$. For each $i\in[\Delta]$, let $V_{y,i}$ be the random
variable counting the number of times that the loop starting at Line 11 ran,
when the $i$th edge adjacent to $y$ was processed. If there was no $i$th edge
(or the algorithm already aborted), we set $V_{y,i}=0$; then at the end of the
stream, we will have $h_{y}\leq\Delta+\sum_{i\in\Delta}V_{y,i}$.

We now consider the distribution of $V_{y,i}$, conditioned on both the value
of the variable $S$ at the time the $i$th edge was processed, and on the parts
of the permutation $\sigma_{y}$ which the algorithm has read so far,
$\sigma_{y}[1..{h_{y}-1}]$.

$\displaystyle\Pr[V_{y,i}\geq k\mid S,\sigma_{y}[1..{h_{y}-1}]]$
$\displaystyle=\Pr[\sigma_{y}[h_{y},\ldots,h_{y}+k-1]\subseteq S\mid
S,\sigma_{y}[1..{h_{y}-1}]]$
$\displaystyle=\binom{|S\cap\sigma_{y}[h_{y},...,C]|}{k}/\binom{C-h_{y}-1}{k}$
$\displaystyle\leq\binom{\Delta}{k}/\binom{2\Delta}{k}\qquad\qquad\text{since
$|S|\leq\Delta$, $h_{y}\leq C-2\Delta$}$
$\displaystyle\leq\frac{\Delta\cdot(\Delta-1)\cdots(\Delta-k+1)}{2\Delta\cdot(2\Delta-1)\cdots(2\Delta-k+1)}\leq\frac{1}{2^{k}}$

Since this bound holds for all values of $S$ and all
$\sigma_{y}[1..{h_{y}-1}]$, in particular we have

$\displaystyle\Pr[V_{y,i}\geq
k|(V_{y,j})_{j<i}]=\operatorname{\mathbb{E}}_{\text{$S,\sigma_{y}[1..{h_{y}-1}]$
compat with $(V_{y,j})_{j<i}$}}\Pr[V_{y,i}\geq
k|S,\sigma_{y}[1..{h_{y}-1}]]\leq\frac{1}{2^{k}}$

By Lemma 6.1, for $e^{t}\in[1,2)$, we have
$\operatorname{\mathbb{E}}[e^{tV_{y,i}}\mid(V_{y,j})_{j<i}]\leq 1/(2-e^{t})$,
and $\operatorname{\mathbb{E}}[V_{y,i}\mid(V_{y,j})_{j<i}]\leq 1$.

By a slight variation on the Chernoff bound:

$\displaystyle\Pr[\sum_{i=1}^{\Delta}V_{y,i}\geq 2\Delta]$
$\displaystyle\leq\inf_{t\geq 0}\Pr\left[\prod_{i=1}^{\Delta}e^{tV_{y,i}}\geq
e^{2t\Delta}\right]$ $\displaystyle\leq\inf_{t\geq
0}\frac{1}{e^{2t\Delta}}\operatorname{\mathbb{E}}[e^{tV_{y,1}}\cdots\operatorname{\mathbb{E}}\left[e^{tV_{y,\Delta}}\mid(V_{y,j})_{j<\Delta}\right]\cdots]$
$\displaystyle\leq\min_{t:e^{t}\in[1,2)}\frac{1}{e^{2t\Delta}}\left(\frac{1}{2-e^{t}}\right)^{\Delta}=\left(\min_{t:e^{t}\in[1,2)}\frac{1}{e^{2t}(2-e^{t})}\right)^{\Delta}$
$\displaystyle=\left(\frac{1}{\max_{x\in[1,2)}x^{2}(2-x)}\right)^{\Delta}=\left(\frac{27}{32}\right)^{\Delta}\leq\exp(-\Delta/6)$

Since $h_{v}\leq\Delta+\sum_{i\in\Delta}V_{y,i}$, this implies that

$\displaystyle\Pr[h_{v}\geq C]\leq\Pr[h_{v}\geq C-2\Delta]=\Pr[h_{v}\geq
3\Delta]\leq\Pr[\sum_{i=1}^{\Delta}V_{y,i}\geq 2\Delta]\leq\exp(-\Delta/6)$

Thus, by a union bound, the probability that _any_ vertices $v\in B$ will have
$h_{v}>C$ at the end of the algorithm will be $\leq n\exp(-\Delta/6)$. In
particular, if $\Delta\geq 6\ln(n/\delta)$, the algorithm will the guaranteed
to abort with probability $\leq\delta$. ∎

Observe that Section 3 and Lemma 3.2 collectively imply Theorem 1.5.

######  Theorem 3.3 (Formal version of Theorem 1.5).

There is a randomized online $O(\Delta)$-edge coloring algorithm for vertex
arrival streams over multigraphs using $O(n\log(n\Delta/\delta))$ bits of
space, with error $\leq\delta$ against any adaptive adversary. It uses
$O(n\Delta\log\Delta)$ oracle random bits.

Let us now turn to the deterministic version of the problem. We will introduce
an a deterministic algorithm which uses advice, and show that if the advice is
chosen randomly, the algorithm will work with high probability. This algorithm
can also be used as a randomized algorithm, if we choose the advice uniformly
at random, and we use a somewhat complicated analysis to show that this can be
achieved using only $\widetilde{O}(n)$ (random) bits of advice.

######  Lemma 3.4.

Let $C,t,w$ be integers, with $C\geq t\geq 512$, and $8|C$. Let $\epsilon\leq
C^{-t-1}$. Say that $F_{1},\ldots,F_{w}$ are subsets of $[C]$, and define
$s_{i}=|F_{i}|$ for all $i\in[w]$. We furthermore require
$\min_{i\in[w]}s_{i}\geq\frac{1}{2}t$, and
$\min_{i\in[w]}s_{i}\geq\frac{1}{2}\max_{i\in[w]}s_{i}$. Let $X\subseteq[C]$
satisfy $|X|\leq\frac{1}{8}C$, and let $\sum_{i\in[w]}s_{i}\leq\frac{1}{2}C$.
Then if $\sigma_{1},\ldots,\sigma_{w}$ are $(\epsilon,t)$-wise independent
random permutations over $[C]$,

$\displaystyle\Pr\left[\left|\bigcup_{i\in[w]}\sigma_{i}[F_{i}]\setminus
X\right|<\frac{1}{8}\sum_{i\in[w]}s_{i}\right]\leq\exp(-\frac{1}{2^{9}}tw)\,.$

###### Proof of Lemma 3.4.

Since the $(\sigma_{i})_{i\in[w]}$ are $(\epsilon,t)$-wise independent, in
particular we have for any $i\in[w]$,$j\in[C]$, that
$\Pr\left[j\in\sigma_{i}[F_{i}]\right]\leq s_{i}/C+\epsilon$, and for any
$Q\subseteq[C]$ with $|Q|\leq t$, that

$\displaystyle\Pr[Q\subseteq\sigma_{i}[F_{i}]]=\frac{s_{i}\cdot(s_{i}-1)\cdots(s_{i}-|Q|+1)}{C\cdot(C-1)\cdots(C-|Q|+1)}+\epsilon\leq\left(\frac{s_{i}}{C}\right)^{|Q|}$
(1)

Let $U_{i}$ be a random subset of $[C]$ in which each element in $C$ is
included independently with probability $s_{i}/C$. Eq. 1 thus implies
$\Pr[Q\subseteq\sigma_{i}[F_{i}]]\leq\Pr[Q\subseteq U_{i}]$. Now, for any
fixed set $H\subseteq[C]$, let $Y_{H,i}:=|\sigma_{i}[F_{i}]\cap H|$, and
$W_{H,i}=|U_{i}\cap H|$. Then $\operatorname{\mathbb{E}}[Y_{H,i}]\leq
s_{i}|H|/C+\epsilon C=\operatorname{\mathbb{E}}[W_{H,i}]+\epsilon C$, and as a
consequence of Eq. 1, we have for all $k\leq t$, that
$\operatorname{\mathbb{E}}[Y_{H,i}^{k}]\leq\operatorname{\mathbb{E}}[W_{H,i}^{k}]+\epsilon
C$. This lets us bound the moment generating function of $Y_{H,i}$, for
nonnegative $z$:

$\displaystyle\operatorname{\mathbb{E}}e^{zY_{H,i}}$
$\displaystyle\leq\sum_{k=0}^{\infty}\frac{1}{k!}(\operatorname{\mathbb{E}}(zY_{H,i})^{k})$
$\displaystyle\leq\sum_{k=0}^{t}\frac{1}{k!}(\operatorname{\mathbb{E}}(zY_{H,i})^{k})+\sum_{k=t+1}^{\infty}\frac{1}{k!}(\operatorname{\mathbb{E}}(zY_{H,i})^{k})$
$\displaystyle\leq\sum_{k=0}^{t}\frac{1}{k!}(\operatorname{\mathbb{E}}(zW_{H,i})^{k})+\sum_{k=t+1}^{\infty}\frac{1}{(k-t-1)!(t+1)!}((zs_{i})^{k})+\epsilon
tC$
$\displaystyle\leq\operatorname{\mathbb{E}}e^{zW_{H,i}}+\frac{(zs_{i})^{t+1}}{(t+1)!}e^{zs_{i}}+\epsilon
tC$
$\displaystyle\leq\exp\left({\frac{s_{i}|H|}{C}(e^{z}-1)}\right)+\frac{(zs_{i})^{t+1}}{(t+1)!}e^{zs_{i}}+\epsilon
tC$ (2)

We will use this to upper bound the probability that a supermartingale, which
sums how many elements in each $\sigma_{i}[F_{i}]$ were present in
$\bigcup_{j<i}\sigma_{j}[F_{j}]$, grows too large. Let $B_{1}$ be an arbitrary
set of size $\frac{1}{8}C$ which contains $X$. (This definition will make the
following analysis simpler than if we had set $B_{1}=X$). For each
$i\in\\{2,\ldots,w\\}$, define $B_{i}=B_{i-1}\cup\sigma_{i-1}[F_{i-1}]$. Note
that $|B_{w}|\leq\frac{5}{8}C$. We have
$\operatorname{\mathbb{E}}[\sum_{i\in[w]}Y_{B_{i},i}]\leq\sum_{i\in[w]}{\left(\frac{|B_{i}|}{C}s_{i}+\epsilon
C\right)}\leq\frac{|B_{w}|}{C}\sum_{i\in[w]}s_{i}\leq\frac{5}{8}\sum_{i\in[w]}s_{i}$.

Note that

$\displaystyle\Pr\left[\left|\bigcup_{i\in[w]}\sigma_{i}[F_{i}]\setminus
X\right|<\frac{1}{8}\sum_{i\in[w]}s_{i}\right]$
$\displaystyle\leq\Pr\left[\sum_{i\in[w]}Y_{B_{i},i}\geq\frac{7}{8}\sum_{i\in[w]}s_{i}\right]$
(3)

Let
$\gamma=(\frac{7}{8}\sum_{i\in[w]}s_{i})/\operatorname{\mathbb{E}}[\sum_{i\in[w]}Y_{B_{i},i}]$;
this is $\geq 7/5$. Applying a modified proof of the Chernoff bound/Azuma’s
inequality to the right hand side of Eq. 3 gives:

$\displaystyle=\inf_{z>0}\Pr\left[\exp\left(z\sum_{i\in[w]}Y_{B_{i},i}\right)\geq\exp\left(\gamma
z\operatorname{\mathbb{E}}[\sum_{i\in[w]}Y_{B_{i},i}]\right)\right]$
$\displaystyle\leq\inf_{z>0}\frac{\exp\left(z\sum_{i\in[w]}Y_{B_{i},i}\right)}{\exp\left(\gamma
z\operatorname{\mathbb{E}}[\sum_{i\in[w]}Y_{B_{i},i}]\right)}\qquad\qquad\text{by
Markov's inequality}$
$\displaystyle=\inf_{z>0}\exp\left(z\sum_{i\in[w]}(Y_{B_{i},i}-\gamma\operatorname{\mathbb{E}}[Y_{B_{i},i}])\right)$
$\displaystyle=\inf_{z>0}\operatorname{\mathbb{E}}\left[\exp\left(z(Y_{B_{1},1}-\gamma\operatorname{\mathbb{E}}[Y_{B_{1},1}])\right)\cdots\operatorname{\mathbb{E}}\left[\exp\left(z(Y_{B_{w},w}-\gamma\operatorname{\mathbb{E}}[Y_{B_{w},w}])\right)\big{|}Y_{B_{1},1},\ldots,Y_{B_{w-1},w-1}\right]\cdots\right]$
$\displaystyle\leq\inf_{z>0}\prod_{i\in[w]}\max_{B:\frac{1}{8}C\leq|B|\leq\frac{5}{8}C}\operatorname{\mathbb{E}}\exp\left(z(Y_{B,i}-\gamma\operatorname{\mathbb{E}}[Y_{B,i}])\right)\qquad\qquad\text{bounding
terms from the inside out}$
$\displaystyle=\inf_{z>0}\prod_{i\in[w]}\max_{B:\frac{1}{8}C\leq|B|\leq\frac{5}{8}C}\frac{\operatorname{\mathbb{E}}\exp\left(zY_{B,i}\right)}{\exp\left(\gamma
z\operatorname{\mathbb{E}}[Y_{B,i}])\right)}$
$\displaystyle\leq\inf_{z>0}\prod_{i\in[w]}\max_{B:\frac{1}{8}C\leq|B|\leq\frac{5}{8}C}\frac{\exp\left({\frac{s_{i}|B|}{C}(e^{z}-1)}\right)+\frac{(zs_{i})^{t+1}}{(t+1)!}e^{zs_{i}}+\epsilon
tC}{\exp\left(\gamma
z\operatorname{\mathbb{E}}[Y_{B,i}])\right)}\qquad\qquad\text{by Eq.
\ref{eq:moment-bound} }$

Now set $z=\frac{t}{8\frac{1}{w}\sum_{i\in[w]}s_{i}}$. Since $t\leq
2\min_{i\in[w]}s_{i}$, it follows
$z\leq\frac{2\min_{i\in[w]}s_{i}}{8\min_{i\in[w]}s_{i}}\leq\frac{1}{4}$. Since
$\max_{i\in[w]}s_{i}\leq 2\min_{i\in[w]}s_{i}$, we have $z\leq t/(4s_{i})$ for
all $i\in[w]$. This implies
$(zs_{i})^{t+1}/(t+1)!e^{zs_{i}}\leq{(t/4)}^{t+1}e^{t/4}/(t+1)!\leq\frac{1}{2}$.
Since $\epsilon\leq C^{-t-1}$, we also have $\epsilon tC\leq\frac{1}{2}$.
Continuing the upper bound of Eq. 3:

$\displaystyle\leq\prod_{i\in[w]}\max_{B:\frac{1}{8}C\leq|B|\leq\frac{5}{8}C}\frac{\exp\left({\frac{s_{i}|B|}{C}(e^{z}-1)}\right)+1}{\exp\left(\gamma((zs_{i}|B|/C)-\epsilon)\right)}$
$\displaystyle\leq e^{\gamma
w\epsilon}\prod_{i\in[w]}\frac{\exp\left({\frac{s_{i}}{8}(e^{z}-1)}\right)+1}{\exp\left(\gamma
zs_{i}/8\right)}$ maximum occurs at $|B|=\frac{1}{8}C$ $\displaystyle\leq
e^{w(\ln(2)+\gamma\epsilon)}\prod_{i\in[w]}\exp((e^{z}-1-\gamma z)s_{i}/8)$
since $(x+1)/x^{\gamma}\leq 2/x^{\gamma-1}$ $\displaystyle\leq
e^{w(\ln(2)+\gamma\epsilon)}\prod_{i\in[w]}\exp\left(-\frac{1}{4}z\frac{s_{i}}{8}\right)$
since $z\leq\frac{1}{4}$ implies $\frac{1}{4}z\leq\frac{7}{5}z-(e^{z}-1)$
$\displaystyle=\exp\left(-\frac{1}{4}\frac{tw}{8\sum_{i\in[w]}s_{i}}\sum_{i\in[w]}\frac{s_{i}}{8}+w(\ln
2+\gamma\epsilon)\right)$ $\displaystyle\leq\exp(-\frac{tw}{2^{8}}+w(\ln
2+\gamma\epsilon))$ $\displaystyle\leq\exp(-\frac{tw}{2^{9}})$ since
$\frac{t}{2^{9}}\geq 1\geq\ln 2+\gamma\epsilon$

This completes the proof of the lemma. ∎

######  Lemma 3.5.

Let $C,s,w$ be integers, with $s\geq 4$. Let $\epsilon\leq C^{-s-1}$. Say that
$F_{1},\ldots,F_{w}$ are subsets of $[C]$, with each $|F_{i}|\leq s$,
$|F_{i}|\geq 2$ and $\sum_{i\in[w]}|F_{i}|\geq\frac{1}{2}C$. Furthermore, let
$X\subseteq[C]$ satisfy $|X|\leq\frac{1}{8}C$. Then if
$\sigma_{1},\ldots,\sigma_{w}$ are $(\epsilon,s)$-wise independent random
permutations over $[C]$,

$\displaystyle\Pr\left[\left|\bigcup_{i\in[w]}\sigma_{i}[F_{i}]\setminus
X\right|<\frac{1}{16}C\right]\leq\exp(-\frac{1}{2}\sum_{i\in[w]}|F_{i}|)\,.$

This lemma differs from Lemma 3.4 in that the sets
$(\sigma_{i}[F_{i}])_{i\in[w]}$ are now smaller, and $\sum_{i\in[w]}|F_{i}|$
is $\Omega(C)$.

###### Proof of Lemma 3.5.

Because the $(\sigma_{i})_{i\in[w]}$ are $(\epsilon,s)$-wise independent, for
each $i\in[w]$, the random variable $\sigma_{i}[F_{i}]$ has total variation
distance $\epsilon$ from being a uniform random subset of $[C]$ of size
$|F_{i}|$. Let $\tau={\left\lfloor{\frac{1}{16}C}\right\rfloor}$. We will
bound the probability that there exists any set $T\subseteq[C]$ of size $\tau$
for which $\bigcup_{i\in[w]}\sigma_{i}[F_{i}]\subseteq T\cup X$. Observe:

$\displaystyle\Pr$ $\displaystyle\left[\exists
T\in\binom{[C]}{\tau}:\bigcup_{i\in[w]}\sigma_{i}[F_{i}]\subseteq T\cup
X\right]$
$\displaystyle\leq\sum_{T\in\binom{[C]}{\tau}}\Pr\left[\bigcup_{i\in[w]}\sigma_{i}[F_{i}]\subseteq
T\cup X\right]$
$\displaystyle=\sum_{T\in\binom{[C]}{\tau}}\prod_{i\in[w]}\Pr\left[\sigma_{i}[F_{i}]\subseteq
T\cup X\right]$ since $\sigma_{i}$ are independent
$\displaystyle\leq\sum_{T\in\binom{[C]}{\tau}}\prod_{i\in[w]}\left(\frac{\binom{|T\cup
X|}{|F_{i}|}}{\binom{C}{|F_{i}|}}+\epsilon\right)$ since $F_{i}$ approximately
uniform
$\displaystyle=\sum_{T\in\binom{[C]}{\tau}}\prod_{i\in[w]}\left(\frac{|T\cup
X|\cdots(|T\cup X|-|F_{i}|+1)}{C\cdots(C-|F_{i}|+1)}+\epsilon\right)$
$\displaystyle\leq\sum_{T\in\binom{[C]}{\tau}}\prod_{i\in[w]}\left(\frac{|T\cup
X|}{C}\right)^{|F_{i}|}$ since $2\leq|F_{i}|\leq s$ and $\epsilon\leq
C^{-s-1}$ $\displaystyle\leq\binom{C}{\tau}\left(\frac{|T\cup
X|}{C}\right)^{\sum_{i\in[w]}|F_{i}|}$ $\displaystyle\leq
2^{0.338C}\left(\frac{3}{16}\right)^{\sum_{i\in[w]}|F_{i}|}$ using
$|T|+|X|\leq\left(\frac{1}{16}+\frac{1}{8}\right)C$ and $\tau\leq\frac{C}{16}$
$\displaystyle\leq\exp(0.235C-\ln(16/3)\sum_{i\in[w]}|F_{i}|)$
$\displaystyle\leq\exp(-\frac{1}{2}\sum_{i\in[w]}|F_{i}|)$ since
$\sum_{i\in[w]}|F_{i}|\geq C/2$

This completes the proof. ∎

######  Lemma 3.6.

Theorem 1.6 holds for one-sided vertex arrival streams on bipartite graphs.

###### Proof of Lemma 3.6.

$\delta\in(0,1)$ is a parameter governing the probability that the Algorithm 4
will fail to be a correct deterministic algorithm, if its advice is chosen
randomly; if one just wants a deterministic algorithm, setting $\delta=1/2$
suffices. If $\Delta\leq\log\frac{n\Delta}{\delta}$, use the simple greedy
algorithm (Algorithm 1). Otherwise, use Algorithm 4.

Algorithm 4 Deterministic algorithm for $O(\Delta)$ edge coloring for
(adversarial) one sided vertex arrival bipartite streams, using
$\widetilde{O}(n)$ bits of advice

1:Input: Stream of vertex arrivals for $n$-vertex graph $G=(A\sqcup B,E)$ of
max degree $\Delta$

2:

3:$\delta\in(0,1)$ is a parameter so that, if the advice is chosen randomly,
it will work for all inputs with probability $\geq 1-\delta$

4:

5:Initialize:

6:Let $C=2^{18}\Delta$.

7:Let $s={\left\lceil{2^{18}\log\frac{n\Delta}{\delta}}\right\rceil}$.

8:Advice: $(\sigma_{v})_{v\in B}$, where each $\sigma_{v}$ is a permutation
over $[C]$. If chosen randomly, each is $(\epsilon,s)$-wise independent for
$\epsilon\leq C^{-s-1}$

9:for $v\in B$ do

10: $b_{v}\leftarrow 1$.

11: $Q_{v}\leftarrow[s]$.

12:Process(vertex $x$ with multiset $M_{x}$ of edges to $B$)

13:Let $d_{x,y}$ be the number of times edge $\\{x,y\\}$ is in $M_{x}$

14:for each $y\in B$ with $d_{x,y}>0$ do

15: if $d_{x,y}<\frac{1}{16}s$ then

16: Let $F_{y}=(b_{y}-1)s+Q_{y}$

17: else

18: Let
$F_{y}=((b_{y}-1)s+Q_{y})\sqcup[b_{y}s,b_{y}+{\left\lceil{\frac{64d_{a,b}}{s}}\right\rceil}s]$

19:Construct bipartite graph $H$ from $M_{x}$ to $[C]$, edge $e\in M_{x}$ is
linked to all $c\in\sigma_{y}[F_{y}]$.

20:Compute an $M_{x}$-saturating matching $P$ of $H$.

21:for each $e\in M_{x}$ do

22: Assign color $P(e)$ to $e$

23: if $d_{x,y}<\frac{1}{16}s$ then

24: Remove $\sigma_{y}^{-1}-(b_{y}-1)s$ from $Q_{y}$

25:for each $y\in B$ with $d_{x,y}>0$ do

26: if $d_{x,y}<\frac{1}{16}s$ then

27: if $|Q_{y}|\leq s-\frac{1}{2^{17}}s$ then

28: $b_{y}\leftarrow b_{y}+1$

29: $Q_{y}\leftarrow[s]$

30: else

31: $Q_{y}\leftarrow[s]$

32: $b_{y}\leftarrow b_{y}+{\left\lceil{\frac{2d_{x,y}}{s}}\right\rceil}+1$

This algorithm maintains, for each vertex $v\in B$, two variables $b_{v}$ and
$Q_{v}$ that indicate which colors in $[C]$ are certainly available for that
vertex. It ensures that that none of the colors in the set
$\Xi_{v}=\\{\sigma_{v}[(b_{v}-1)s)]:i\in
Q_{v}\\}\sqcup\\{\sigma_{v}[j]:j>b_{v}s\\}$ have been used. When a new vertex
$x$ in $A$ arrives, along with the multiset $M_{x}$ of edges adjacent to it,
the algorithm selects a set $F_{y}$ indicating candidate colors
$\sigma_{y}[F_{y}]$ for each $y$ adjacent to $x$, and computes a matching
between the edges in $M_{x}$ and the set of all colors, allowing each edge in
$M_{x}$ only the colors corresponding to the edges endpoint in $B$. This
matching ensures that all edges incident to $x$ receive different colors; and
for all $y\in B$, the use of the set $F_{y}$ to constrain the set of candidate
colors to a subset of $\Xi_{v}$ ensures that all incident to $y$ receive
different colors.

For a given vertex $y$, as the algorithm runs, $b_{y}$ will be increased, by
either Line 28 or 32. Line 28 only triggers when $|Q_{y}|\leq
s-\frac{1}{2^{17}}s$, which requires that vertex $y$ has received
$\geq\frac{1}{2^{17}}s$ incident edges since the last time $b_{y}$ was
increased. Since there will be at most $\Delta$ edges incident to $y$, the
total increase to $b_{y}$ from this line over the course of the algorithm will
be $\leq\Delta/(\frac{1}{2^{17}}s)=2^{17}\Delta/s$. On the other hand, Line 28
only triggers when $d_{x,y}\geq\frac{1}{16}s$, and then increases $b_{y}$ by
${\left\lceil{64d_{x,y}/s}\right\rceil}+1$. Since $\sum_{x\in
A}d_{x,y}\leq\Delta$,

$\displaystyle\sum_{x\in
A:d_{x,y}>\frac{1}{16}s}\left({\left\lceil{\frac{64d_{x,y}}{s}}\right\rceil}+1\right)\leq\sum_{x\in
A:d_{x,y}>\frac{1}{16}s}\left(\frac{64d_{x,y}}{s}+2\right)\leq\sum_{x\in
A:d_{x,y}>\frac{1}{16}s}\frac{96d_{x,y}}{s}\leq\frac{96\Delta}{s}$

Thus, the total increase in $b_{y}$ will be $\leq(2^{17}+96)\Delta/s$, and
$b_{y}$ will always be $\leq(2^{17}+97)\Delta/s$. Looking at the construction
of the set $F_{y}$ on Lines 16 and 18, we see that it will only ever contain
elements which are $\leq(2^{17}+98)\Delta$. Since
$C=2^{18}\Delta\geq(2^{17}+98)\Delta$, it follows that computing
$\sigma_{y}[F_{y}]$ will never index out of range.

The only remaining way this algorithm could fail is if Line 20 were to report
that no $M_{x}$-saturating matching exists. We will show that, if the
$(\sigma_{v})_{v\in B}$ are drawn from $(\epsilon,s)$-wise independent
distributions, then probability $\geq 1-\delta$, for all possible sets $M_{x}$
and combinations of "free slots", $(F_{y})_{y:d_{x,y}>0}$, Hall’s condition
will hold on the graph $H$ constructed on Line 19.

Since whether the constructed graph $H$ has a matching does not depend on the
value of $x$, only on the number of edges arriving at a given $y\in B$, we do
not need to take a union bound over all possible sets $M_{x}$. Instead, define
a configuration by a tuple $(S,(d_{y})_{y\in S},(b_{y})_{y\in S},(Q_{y})_{y\in
S})$. The set $S$ gives the neighborhood of $x$, and for each $y\in S$ we set
$d_{y}=d_{x,y}$. The values $b_{y},Q_{y}$ match the values from the algorithm
at the time $M_{x}$ arrives. Note that the set $F_{y}$ is a function of
$b_{y}$, $Q_{y}$, and $d_{y}$, and for fixed $b_{y},Q_{y}$ is monotone
increasing as a function of $d_{y}$. We do _not_ need any extra cases to
handle Hall’s condition for subsets of $M_{x}$; consider any subset
$M_{x}^{\prime}\subseteq M_{x}$, and let
$S^{\prime},d_{y}^{\prime},F_{y}^{\prime}$ correspond to $M_{x}^{\prime}$.
Then because $F_{y}^{\prime}\subseteq F_{y}$ for each $y\in S^{\prime}$, if
Hall’s condition holds for the configuration
$(S^{\prime},(d_{y}^{\prime})_{y\in S^{\prime}},(b_{y})_{y\in
S^{\prime}},(Q_{y})_{y\in S^{\prime}})$, then

$\displaystyle\left|\bigcup_{y\in
S^{\prime}}F_{y}\right|\geq\left|\bigcup_{y\in
S^{\prime}}F_{y}^{\prime}\right|\geq\sum_{y\in S^{\prime}}d_{y}^{\prime}$

which implies that Hall’s condition also holds for the subset $M_{x}^{\prime}$
within the bipartite graph $H$ constructed for $M_{x}$.

Let $d=\sum_{y\in S}d_{y}$. If the permutations $(\sigma_{y})_{y\in B}$ were
each chosen uniformly at random, it would be straightforward to prove that
Hall’s condition fails for each configuration $(S,(d_{y})_{y\in
S},(b_{y})_{y\in S},(Q_{y})_{y\in S}$ with probability $\leq
e^{d}(d/C)^{\Theta(|S|s+d)}$, after which a union bound over configurations
gives a $\leq\delta$ total failure probability. However, because we assume the
$(\sigma_{y})_{y\in B}$ are only $(\epsilon,s)$-wise independent, we will need
a more precise argument.

Each configuration $(S,(d_{y})_{y\in S},(b_{y})_{y\in S},(Q_{y})_{y\in S}$ can
be split into $O(\log\Delta)$ different "level configurations". Let
$\tau=s/16$; then for each vertex $y$, if $d_{y}<\tau$, the algorithm will
choose $F_{y}$ using Line 16 to be a subset of size $\leq s$ and $\geq
s(1-2^{-17})\geq s/2$; and if $d_{y}\geq\tau$, the algorithm will choose
$F_{y}$ using Line 18, to be a subset of size $\geq 64d_{y}$. Define
$L_{0}=\\{y\in S:d_{y}<\tau\\}$. For each $\ell\in\\{1,\ldots,\lambda\\}$, for
$\lambda={\left\lceil{\log{\Delta}}\right\rceil}$ let $L_{\ell}=\\{y\in
S:2^{\ell-1}\tau\leq d_{y}<2^{\ell}\tau\\}$. Also write
$L_{>\ell}=\bigcup_{j>\ell}L_{j}$. Within each "level", the values of $d_{y}$
are either all small ($<\tau$), or all within a factor $2$ of each other. We
will show that with high probability, the following two conditions hold:

$\displaystyle\forall\ell\geq 1,\forall(L_{\lambda},\ldots,L_{\ell+1})\text{
where }\max_{i>\ell}{(3/2)^{i-\ell}|L_{i}|}\leq|L_{\ell}|,$
$\displaystyle\forall{d_{y},b_{y},Q_{y}\text{ for
}y\in\bigsqcup_{j\geq\ell}L_{\ell}}:$ $\displaystyle\left|\left(\bigcup_{y\in
L_{\ell}}\sigma_{y}[F_{y}]\right)\setminus\left(\bigcup_{y\in
L_{>\ell}}\sigma_{y}[F_{y}]\right)\right|\geq 8\sum_{y\in L_{0}}d_{y}$ (4)
$\displaystyle\forall(L_{\lambda},\ldots,L_{1})\text{ where
}\max_{i>0}{(3/2)^{i}|L_{i}|}\leq|L_{0}|,$
$\displaystyle\forall{d_{y},b_{y},Q_{y}\text{ for }y\in\bigsqcup_{j\geq
0}L_{\ell}}:$ $\displaystyle\left|\left(\bigcup_{y\in
L_{0}}\sigma_{y}[F_{y}]\right)\setminus\left(\bigcup_{y\in
L_{>0}}\sigma_{y}[F_{y}]\right)\right|\geq\sum_{y\in L_{0}}d_{y}$ (5)

Then for the specific configuration $(S,(d_{y})_{y\in S},(b_{y})_{y\in
S},(Q_{y})_{y\in S})$, let $A\subseteq\\{0,\ldots,\lambda\\}$ contain all
$\ell$ for which $|L_{\ell}|\geq\max_{i>\ell}(3/2)^{i-\ell}|L_{i}|$. Because
the condition of Eq. 4 holds for all $i\in A$ with $i>0$, these "levels" of
the configuration are associated with enough entries of $C$ that they "pay
for" all levels with smaller degrees that also do not have many more vertices.
Level $L_{0}$ pays for itself if $0\in A$, by Eq. 5. Formally, we have:

$\displaystyle|\bigcup_{y\in S}\sigma_{y}[F_{y}]|$
$\displaystyle=\sum_{i\in\\{0,\ldots,\lambda\\}}|(\bigcup_{y\in
L_{i}}\sigma_{y}[F_{y}])\setminus(\bigcup_{y\in L_{>i}}\sigma_{y}[F_{y}])|$
$\displaystyle\geq\sum_{i\in A}|(\bigcup_{y\in
L_{i}}\sigma_{y}[F_{y}])\setminus(\bigcup_{y\in L_{>i}}\sigma_{y}[F_{y}])|$
$\displaystyle\geq 1_{0\in A}\left(\sum_{y\in L_{0}}d_{y}\right)+\sum_{i\in
A\setminus\\{0\\}}8\sum_{y\in L_{i}}d_{y}$ $\displaystyle\geq 1_{0\in
A}\left(\sum_{y\in L_{0}}d_{y}\right)+\sum_{i\in A\setminus\\{0\\}}8\cdot
2^{i-1}\tau|L_{i}|$ $\displaystyle=1_{0\in A}\left(\sum_{y\in
L_{0}}d_{y}\right)+\sum_{i\in A\setminus\\{0\\}}4\cdot 2^{i}\tau|L_{i}|$
$\displaystyle\geq 1_{0\in A}\left(\sum_{y\in L_{0}}d_{y}\right)+\sum_{i\in
A\setminus\\{0\\}}\sum_{j\leq
i}\left(\frac{3}{4}\right)^{i-j}\left(2^{i}\tau|L_{i}|\right)$
$\displaystyle\geq 1_{0\in A}\left(\sum_{y\in L_{0}}d_{y}\right)+\sum_{i\in
A\setminus\\{0\\}}\sum_{j\leq
i:|L_{j}|\leq(3/2)^{i-j}|L_{i}|}2^{j}\tau\left(\frac{3}{2}\right)^{i-j}|L_{i}|$
$\displaystyle\geq 1_{0\in A}\left(\sum_{y\in L_{0}}d_{y}\right)+\sum_{i\in
A\setminus\\{0\\}}\sum_{j\leq
i:|L_{j}|\leq(3/2)^{i-j}|L_{i}|}2^{j}\tau|L_{j}|$ $\displaystyle\geq 1_{0\in
A}\left(\sum_{y\in L_{0}}d_{y}\right)+\sum_{i\in A\setminus\\{0\\}}\sum_{j\leq
i:|L_{j}|\leq(3/2)^{i-j}|L_{i}|}\sum_{y\in L_{j}}d_{y}$
$\displaystyle=\sum_{i\in\\{0,\ldots,\lambda\\}}\sum_{y\in
L_{j}}d_{y}=\sum_{y\in S}d_{y}$

We first observe that Eq. 4 matches the conditions for Lemma 3.4.
Specifically, if $y\in L_{\ell}$ for $\ell>1$, then $d_{y}\geq s/16$, and we
have both $|F_{y}|\geq s$ and $|F_{y}|\geq 64d_{y}$. Also, since the
$d_{y}\in[2^{\ell-1}\tau,2^{\ell}\tau)$, we will have $\max_{y\in
L_{\ell}}|F_{y}|\leq 2\min_{y\in L_{\ell}}F_{y}$. Letting $X=\bigcup_{y\in
L_{>i}}\sigma_{y}[F_{y}]$, we have $|X|\leq\sum_{y\in
L_{>i}}|F_{y}|\leq\sum_{y\in L_{>\ell}}(2s+64d_{y})\leq
96\Delta\leq\frac{1}{8}C$ . Similarly, $\sum_{y\in
L_{\ell}}\sigma_{y}[F_{y}]\leq 96\Delta\leq\frac{1}{2}C$. Thus, Lemma 3.4
applies, and gives an $\exp(-O(s|L_{\ell}|))$ upper bound on the probability
that $|\bigcup_{y\in L_{\ell}}\sigma_{y}[F_{y}]\setminus X|\geq 4\sum_{y\in
L_{0}}d_{y}$.

For Eq. 5, if $\sum_{y\in L_{0}}{|F_{y}|}\geq\frac{1}{2}C$, we apply Lemma
3.5. As argued above, the set $X=\bigcup_{y\in L_{>0}}\sigma_{y}[F_{y}]$ will
have size $\leq\frac{1}{8}C$. If the bad event in Lemma 3.5 does not hold,
then the condition in Eq. 5 will, since $\sum_{y\in
L_{0}}d_{y}\leq\Delta\leq\frac{1}{16}C$. On the other hand, if $\sum_{y\in
L_{0}}{|F_{y}|}<\frac{1}{2}C$, we apply Lemma 3.4; this works because we have
$|F_{y}|\geq(1-2^{-17})s\geq\frac{1}{2}s$.

Since Lemma 3.4 and Lemma 3.5 both ensure a $\exp(-\Omega(s|L_{i}|))$ type
upper bound for the probability of conditions from Eqs. 4 and 5, we can bound
the probability that none of the individual event fails in a single sum. Since
for each $y$, $Q_{y}$ is refreshed after at least $s/2^{17}$ elements are
removed from it, there are only
$\sum_{i=0}^{{\left\lceil{s/2^{17}}\right\rceil}}\binom{s}{i}\leq
2^{sH(1/2^{16})}\leq\exp(s/2^{11})$ possible values for $Q_{y}$; here $H$ is
the binary entropy function.

$\displaystyle\Pr$ $\displaystyle[\text{Eqs. \ref{eq:hall-abundant} and
\ref{eq:hall-end-ok} hold}]$
$\displaystyle\leq\sum_{\ell\in\\{0,\ldots,\lambda\\}}\sum_{\underset{\text{where
$|L_{\ell}|=w$}}{w\in\\{1,\ldots,\Delta\\}}}\sum_{\underset{\text{all
$|L_{j}|\leq(2/3)^{j-\ell}w$}}{L_{\lambda},\ldots,L_{\ell}}}\sum_{(d_{y},b_{y},Q_{y})_{y\in\bigsqcup_{j\geq\ell}L_{j}}}\exp(-sw/2^{9})$
$\displaystyle\leq\sum_{\ell\in\\{0,\ldots,\lambda\\}}\sum_{\underset{\text{where
$|L_{\ell}|=w$}}{w\in\\{1,\ldots,\Delta\\}}}\prod_{j\geq\ell}\left((n+1)C^{2}\exp(s/2^{11})\right)^{(2/3)^{j-\ell}w}\exp(-sw/2^{9})$
$\displaystyle\leq\sum_{\ell\in\\{0,\ldots,\lambda\\}}\sum_{\underset{\text{where
$|L_{\ell}|=w$}}{w\in\\{1,\ldots,\Delta\\}}}\left((n+1)C^{2}\exp(s/2^{11})\right)^{3w}\exp(-sw/2^{9})$
$\displaystyle\leq\sum_{\ell\in\\{0,\ldots,\lambda\\}}\sum_{\underset{\text{where
$|L_{\ell}|=w$}}{w\in\\{1,\ldots,\Delta\\}}}\left(nC\right)^{6w}\exp(-sw/2^{11})\qquad\text{since
$(n+1)\leq n^{2}$ and $2^{-9}-3\cdot 2^{-11}=2^{-11}$}$
$\displaystyle\leq\sum_{\ell\in\\{0,\ldots,\lambda\\}}\sum_{\underset{\text{where
$|L_{\ell}|=w$}}{w\in\\{1,\ldots,\Delta\\}}}\exp(-sw/2^{12})\qquad\text{since
$s\geq 6\cdot 2^{12}(18+\log(n\Delta))\geq 6\cdot 2^{12}\ln(nC)$}$
$\displaystyle\leq(\lambda+1)\Delta\exp(-s/2^{12})\leq\delta\qquad\text{since
$s\geq 2^{13}\log(\Delta/\delta)\geq 2^{13}\ln(\Delta/\delta)$}$

Thus,

$\displaystyle\Pr[\text{any configuration fails Hall's
condition}]\leq\delta\,.$

∎

If the $(\epsilon,s)$-wise random permutations over $[C]$ are constructed
using Lemma 6.2 (assuming $\Delta$ is a power of two), then the total number
of bits of randomness needed to sample advice for the algorithm will be
$O(ns(\log C)^{4}\log\frac{1}{\epsilon})=O(ns^{2}(\log
C)^{5})=O\left(n\left(\log\frac{n\Delta}{\delta}\right)^{2}(\log\Delta)^{5}\right)$.

Combining Section 3 with Lemma 3.6, we immediately get the following theorem.

######  Theorem 3.7 (Formal version of Theorem 1.6).

There is a deterministic online $O(\Delta)$-edge coloring algorithm for vertex
arrival streams over multigraphs using $O(n\log(n\Delta))$ bits of space,
using $\widetilde{O}(n)$ bits of advice. (By picking a uniformly random advice
string, the same algorithm can alternatively be used as a robust algorithm
with $1/\operatorname{poly}(n)$ error; the advice can also be computed in
exponential time.)

##  4 Edge coloring on edge arrival streams

First we prove the general version of Lemma 1.4.

######  Lemma 4.1 (Generalized Lemma 1.4).

Let $f,g$ be functions from $\mathbb{N}\mapsto\mathbb{N}$. Given a streaming
algorithm $\mathcal{A}$ for $g(\Delta)$-coloring over edge arrival streams on
multigraphs of max degree $\Delta$, using $f(N,\Delta)$ bits of space, for any
positive integer $s$, there is a streaming algorithm $\mathcal{B}$ for
$(g(s\Delta)+s\Delta)$-coloring edge arrival streams for multigraphs of max
degree $\Delta$, using $f(N/s,s\Delta)+O(n\log\Delta)$ bits of space.

###### Proof.

Pseudocode for algorithm $\mathcal{B}$ is given by Algorithm 5.

Algorithm 5 Adapting edge coloring algorithm $\mathcal{B}$ to use more colors
and less space, with parameter $s$

1:Input: Stream of edge arrivals for $n$-vertex graph $G=(V,E)$

2:Assume $V=[n]$

3:

4:Initialize:

5:Let $\chi:K_{s}\mapsto[s]$ give an $s$-edge coloring of $K_{s}$.333While it
is possible to implement this more efficiently, this function can also be
evaluated by running the Misra-Gries algorithm in $O(s^{3})$ time..[MG92]

6:$A\leftarrow$ instance of $\mathcal{A}({\left\lceil{n/s}\right\rceil},\Delta
s)$.

7:for $v\in[n]$ do

8: $d_{v}\leftarrow 0$

9:Process(edge $\\{x,y\\}$) $\rightarrow$ color

10:$d_{x}\leftarrow d_{x}+1$

11:$d_{y}\leftarrow d_{y}+1$

12:if ${\left\lceil{x/s}\right\rceil}={\left\lceil{y/s}\right\rceil}$ then

13: Let $c\leftarrow\Delta\cdot(\chi(\\{x\bmod s,y\bmod
s\\})-1)+d_{\min(x,y)}$

14: return color $(0,c)$

15:Let $c\leftarrow
A.\textsc{Process}({{\left\lceil{x/s}\right\rceil},{\left\lceil{y/s}\right\rceil}})$

16:return color $(1,c)$

This algorithm partitions the set of all vertices into sets
$S_{1},\ldots,S_{{\left\lceil{n/\delta}\right\rceil}}$, where set $S_{i}$
contains the $s$ vertices $\\{s(i-1)+1,\ldots,si-1,si\\}$.It provides the
nested algorithm instance $A$ with the (non-loop) edges in the graph $H$
formed by contracting these sets. Edges entirely inside one of the $S_{i}$ are
colored using a separate set of $\Delta s$ colors.

As the total number of edges incident on a set of $s$ vertices in $G$ is
$\leq\Delta s$, the maximum degree of $H$ will also be $\leq\Delta s$. Since
instance $A$ is guaranteed to correctly edge color all multigraphs on
$[{\left\lceil{n/s}\right\rceil}]$ of maximum degree $\leq\Delta s$, no two
edges adjacent to a vertex in $H$ will be assigned the same color.
Consequently, the edges from each individual vertex $v\in S_{i}$ to vertices
outside $S-I$ will all be given different colors.

Consider one of the vertex sets $S_{i}$; a given edge $\\{x,y\\}$ with $x,y\in
S_{i}$ will be assigned a color which, due to the use of $\chi$ to partition
edges, will differ from the colors assigned to all other edge types between
vertices in $S_{i}$; and if the edge $\\{x,y\\}$ was processed in the past,
this time will assign a different color since $d_{\min(x,y)}$ has been
increased since then.

The algorithm will require $f({\left\lceil{N/s}\right\rceil},\Delta s)$ bits
of space to store $A$, and $n\log\Delta$ bits of state to keep track of all
vertex degrees. The total number of colors used will be $g(s\Delta)+s\Delta$;
if $g(x)=O(x)$, this will be $O(s\Delta)$.

∎

######  Lemma 4.2.

Given a streaming algorithm $\mathcal{A}$ for $O(\Delta)$ edge coloring for
one-sided vertex arrival streams over bipartite multigraphs using $\leq
f(n,\Delta)$ space, we can construct a streaming algorithm $\mathcal{B}$ for
$O(\Delta)$ edge coloring of edge arrival streams over bipartite multigraphs
using $O(\sqrt{\Delta}f(n,O(\sqrt{\Delta}))+n\sqrt{\Delta}(\log
n\Delta)\log(n/\delta))$ bits of space. The new streaming algorithm
$\mathcal{B}$ is randomized, runs in polynomial time, and has additional
$\leq\delta$ probability of error, even if the input stream is adaptively
generated.

###### Proof of Lemma 4.2.

The W-streaming edge-arrival algorithm is given by Algorithm 6. The algorithm
uses $s=O(\sqrt{\Delta})$ instances of $\mathcal{A}$. This algorithm maintains
a pool $P$ of edges, and whenever it receives a new edge it adds it to the
pool. Edges with high multiplicity
($\widetilde{\Omega}(\sqrt{\Delta}/\log(n^{2}/\delta))$ in $P$ are moved to a
different pool $L$; since there are not many of this type, they can be stored
using only $\widetilde{O}(n\sqrt{\Delta})$ space. When a vertex $v$ reaches a
high degree ($\geq\sqrt{\Delta}$) in the pool, it and its incident edges are
removed from $P$ and assigned to a random instance of $\mathcal{A}$ which has
not yet received $v$. At the end of the stream, all edges still stored in
either $P$ or $L$ are colored.

Algorithm 6 W-streaming algorithm for $O(\Delta)$ edge coloring on edge-
arrival stream given black-box access to algorithm $\mathcal{A}$ for $C\Delta$
edge coloring on vertex-arrival stream

1:Input: Stream of edge arrivals for $n$-vertex graph $G=(A\sqcup B,E)$

2:

3:Initialize:

4:Let $s=2{\left\lceil{\sqrt{\Delta}}\right\rceil}$

5:Let $\tau={\left\lfloor{\frac{\sqrt{\Delta}}{9\ln(n/\delta)}}\right\rfloor}$

6:$P\leftarrow\emptyset$ is a multiset of edges – used to cache all arriving
edges

7:$L\leftarrow\emptyset$ is a multiset of edges – used to efficiently store
certain edge types which have high multiplicity

8:for $i\in[s]$ do

9: $\mathcal{I}^{(i)}\leftarrow$ instance of algorithm $\mathcal{A}$ for
graphs of max degree ${\left\lceil{4\Delta/s}\right\rceil}$; this will use
$C{\left\lceil{4\Delta/s}\right\rceil}$ colors

10: $x^{(i)}\leftarrow[0,\ldots,0]\in\\{0,1\\}^{A}$, tracks for which vertices
$w$ in $A$ the instance $\mathcal{I}^{(i)}$ has received $(w,M_{w})$

11:Process(edge $\\{x,y\\}$)

12:$P\leftarrow P\cup\\{\\{x,y\\}\\}$.

13:if edge $\\{x,y\\}$ has multiplicity > $\tau$ in $P$ then

14: Remove all copies of $\\{x,y\\}$ from $P$, and add them to $L$

15: return

16:if $\exists v\in A$ with degree
$\geq{\left\lceil{\sqrt{\Delta}}\right\rceil}$ in $P$ then

17: Pick random $i$ from $\\{j\in[s]:x^{(j)}_{v}=0\\}$

18: $x^{(i)}_{v}\leftarrow 1$

19: Let $M_{v}$ be edges incident on $v$ in $P$

20: Send $(v,M_{v})$ to $\mathcal{I}^{(i)}$ to be colored

21: Remove $M_{v}$ from $P$

22:End of Stream

23:Color edges in $P\cup L$ greedily using an independent set of $2\Delta-1$
colors

Algorithm 6 requires $sf(n)$ bits of space to store the instances
$\mathcal{I}^{(1)},\ldots,\mathcal{I}^{(s)}$, and $sn$ bits to keep track of
the vectors $x^{(1)},\ldots,x^{(s)}$. Since the edges adjacent to a vertex in
$A$ are removed from $P$ as soon as it reaches degree
${\left\lceil{\sqrt{\Delta}}\right\rceil}$, the total number of edges in $P$,
counting multiplicity, will be
$\leq|A|({\left\lceil{\sqrt{\Delta}}\right\rceil}-1)=O(n\sqrt{\Delta})$. Thus,
$P$ can be stored using $O(n\sqrt{\Delta}\log(n^{2}/\delta))$ bits of space.
Finally, since $L$ receives only edges whose multiplicity was at least
$\sqrt{\Delta}/\log n$, it will contain at most
$(n\Delta/2)/(\sqrt{\Delta}/\log n)=n\sqrt{\Delta}/(2\log n)$ distinct edges;
keeping track of them and their multiplicity can be done in
$O(n\sqrt{\Delta}\log(n\Delta)/\log n)$ space. In total, Algorithm 6 will
require $O(\sqrt{\Delta}(f(n)+n(\log(n\Delta))\log(n/\delta)))$ bits of space
in total.

The total number of colors used is
$2{\left\lceil{\sqrt{\Delta}}\right\rceil}\cdot
C{\left\lceil{4\Delta/s}\right\rceil}+(2\Delta-1)=O(\Delta)$.

Because Algorithm 6 only sends a star around a vertex $v$ to an instance
$\mathcal{I}^{(i)}$ (Line 20) when the vertex $v$ has degree
$={\left\lceil{\sqrt{\Delta}}\right\rceil}$ in $P$, the maximum degree of
arriving vertices that any instance of $\mathcal{A}$ will process will be
${\left\lceil{\sqrt{\Delta}}\right\rceil}$. However, it is still possible that
for some sketch $\mathcal{I}^{(i)}$, a vertex $v\in B$ will receive a too many
edges from vertices in $A$ that the sketch $\mathcal{I}^{(i)}$ receives later.

For some pair $i\in[s]$, $z\in B$, we will show that sketch
$\mathcal{I}^{(i)}$ receives $\leq 4\Delta/s$ edges (counting multiplicity)
for $z$, with $\geq\frac{\delta}{n^{2}}$ probability. Let
$X_{1},\ldots,X_{\Delta}$ be random variables, where $X_{i}$ is the number of
edges that are sent to $\mathcal{I}^{(i)}$ when the $j$th star adjacent to $z$
is removed. If the stream ends before an $j$th star is removed, then
$X_{j}=0$. Because Line 14 removes all edges with multiplicity $>\tau$ in $P$,
$z$ will have at most $\tau$ edges between it and the center of the $j$th
star, so $X_{j}\leq\tau$. Furthermore, at the time the $j$th star is selected,
the algorithm makes a random decision on Line 17 to choose which sketch will
receive it. Because $s=2{\left\lceil{\sqrt{\Delta}}\right\rceil}$, and each
star has root degree only ${\left\lceil{\sqrt{\Delta}}\right\rceil}$, there
will always be $\geq s/2$ instances that have not received a given vertex as
the root of a star, so the probability that $\mathcal{I}^{(i)}$ will receive
the $j$th star is $\leq\frac{2}{s}$. Thus
$\operatorname{\mathbb{E}}[X_{j}|X_{1},\ldots,X_{j-1}]\leq 2\tau/s$. This
bound holds even if the input stream is produced by an adaptive adversary.
Since the degree of $z$ will be less than $\leq\Delta$ at the end of the
stream, we also have $\operatorname{\mathbb{E}}[\sum_{j\in\Delta}X_{j}]\leq
2\Delta/s$.

We now apply the multiplicative (Chernoff-like) form of Azuma’s inequality, on
the $[0,1]$ random variables $Y_{1},\ldots,Y_{\Delta}$, defined by
$Y_{j}:=X_{j}/\tau$. Let
$\alpha=\operatorname{\mathbb{E}}[\sum_{j\in\Delta}Y_{j}]$.

$\displaystyle\Pr\left[\sum_{i\in[\Delta]}X_{j}\geq 4\Delta/s\right]$
$\displaystyle=\Pr\left[\sum_{i\in[\Delta]}Y_{j}\geq\frac{4\Delta}{s\tau}\right]=\Pr\left[\sum_{i\in[\Delta]}Y_{j}\geq\left(1+\left(\frac{4\Delta}{s\tau\alpha}-1\right)\right)\alpha\right]$
$\displaystyle\leq\exp\left(-\frac{1}{3}\left(\frac{4\Delta}{s\tau\alpha}-1\right)\cdot\alpha\right)\qquad\qquad\text{since
$\frac{4\Delta}{s\tau\alpha}-1>1$}$
$\displaystyle\leq\exp\left(-\frac{1}{3}\frac{2\Delta}{s\tau\alpha}\cdot\alpha\right)=\exp\left(-\frac{2}{3}\frac{\Delta}{s\tau}\right)$
$\displaystyle=\exp\left(-\frac{2\Delta}{3\cdot
2{\left\lceil{\sqrt{\Delta}}\right\rceil}{\left\lfloor{\sqrt{\Delta}/(9\ln(n/\delta))}\right\rfloor}}\right)$
$\displaystyle\leq\exp\left(-2\ln(n/\delta)\right)\leq\frac{\delta}{n^{2}}\qquad\qquad\text{since
$2{\left\lceil{\sqrt{\Delta}}\right\rceil}\leq 3\sqrt{\Delta}$ and
$1/{\left\lfloor{x}\right\rfloor}\geq 1/x$}$

By a union bound over all $\leq n$ vertices $v\in B$, and all $\leq n$
instances in $\\{\mathcal{I}^{(j)}\\}_{j\in[s]}$, we have that the total
probability of any vertex $v$ in an instance $\mathcal{I}^{(i)}$ receiving
more than $4\Delta/s$ edges is $\leq\delta$. ∎

Combining Lemma 4.2 with Lemma 3.2, and then applying Section 3 proves the
following.

######  Theorem 4.3 (Formal version of Theorem 1.2).

There is a randomized W-streaming algorithm for $O(\Delta)$ edge coloring on
edge arrival streams for multigraphs which uses
$O(n\sqrt{\Delta}(\log(n\Delta))^{2})$ bits of space, with error $\leq
1/\operatorname{poly}(n)$ against any adaptive adversary. The algorithm also
requires $\widetilde{O}(n\Delta)$ bits of oracle randomness.

The following online edge coloring algorithms will both use the same core
primitive; a pool of random colors, which is periodically refreshed, along
with data to keep track of which colors in the pool have been used so far. The
times at which the pool are refreshed only depend on the number of colors that
were used, and not which colors where used; this property makes the primitive
easier to handle in proofs.

Algorithm 7 Storing free regions from a permutation

1:$F\leftarrow$InitFreeTracker($C$,$s$,$\Delta$,$\sigma$): $\triangleright$
Assume $C$,$s$,$\Delta$ are powers of two, and $\sigma$ permutation of $[C]$,
and $C\geq\Delta$

2:$H\leftarrow[s]$ be a subset of $[s]$

3:$b\leftarrow 1$ be a counter between $1$ and $C/s$

4:Optional: $Q\leftarrow\emptyset$ is a set of references to objects

5:

6:Interpreting $F$ as subset of $[C]$

7:return $\sigma[H+(b-1)s]$

8:

9:$F$.RemoveAndUpdate($c$, optional: $o$) $\triangleright$ Requires $c\in
F_{v}$

10:$H\leftarrow H\setminus\\{\sigma^{-1}(c)\\}$

11:Optional: Add a reference to $o$, and store it in $Q$

12:if $|H|\leq s-s\Delta/C$ then $\triangleright$ Switch to next block

13: $H\leftarrow[s]$

14: $b\leftarrow b+1$

15: Optional: Drop all references in $Q$ and set $Q\leftarrow\emptyset$

We are now ready to state and prove the formal version of Theorem 1.1.

######  Theorem 4.4 (Formal version of Theorem 1.1).

Given any adversarial edge-arrival stream of a simple graph, there is a
randomized algorithm for online $O(\Delta)$-edge-coloring using
$O(n\sqrt{\Delta\log n})$ bits of space and $\widetilde{O}(n\sqrt{\Delta})$
oracle random bits.

###### Proof.

We will show that Algorithm 8 satisfies the claims of the lemma, if
$\Delta=\Omega(\log(n/\delta))$. (For smaller values of $\Delta$, fall back to
Algorithm 1.) In the following argument, we shall assume that the permutations
$(\sigma_{v})_{v\in S}$ are $s$-wise independent. The pseudocode states
$(\epsilon,s)$-wise independence, since that is attainable per Lemma 6.2 using
only $O(s\operatorname{poly}(\log 1/\epsilon,\log s))$ bits of randomness per
permutation. This will not affect the validity of the proof, since it at most
increases the probabilities of events $H_{\\{u,v\\}}$ and $J_{u,v}$ defined
later by $\epsilon$, which is polynomially smaller than the losses in the
argument due to bounding the number of events by $n^{2}$ instead of
$\binom{n}{2}$ or $n^{2}-n$. We also assume that $\Delta$ is a power of two;
if not, we can increase $\Delta$ to the nearest power of two, and the
algorithm will still give an $O(\Delta)$ coloring.

Each color tracker $F_{v}$ can be stored using $O(\log\Delta)$ bits for $b$,
and $O(s)$ bits for $H$; thus Algorithm 8 will use
$O(n(s+\log\Delta))=O(n\sqrt{\Delta\log(n/\delta)})$ bits in total. For
$\Delta=O(\log(n/\delta))$, the Algorithm 1 uses $O(n\Delta)$ bits, which is
also $O(n\sqrt{\Delta\log(n/\delta)})$.

Algorithm 8 Randomized algorithm for $O(\Delta)$ edge coloring for simple
graph edge arrival streams

1:Input: Stream of vertex arrivals $n$-vertex graph $G=(A\sqcup B,E)$

2:Assume $\Delta$ is a power of two, and $\Delta=\Omega(\log(n/\delta))$

3:

4:Initialize:

5:Let $C=128\Delta$

6:Let $s$ be the least power of two which is $\geq
128\sqrt{\Delta\log(n/\delta)}$

7:Let $\mathcal{H}$ be an ($\epsilon,s$)-wise independent distribution of
permutations on $[C]$, with $\epsilon\leq\exp(-s^{2}/C)\leq(\delta/n)^{128}$

8:for $v\in B$ do

9: Let $\sigma_{v}$ be a random permutation from $\mathcal{H}$

10: $F_{v}\leftarrow\textsc{InitFreeTracker}(C,s,\Delta,\sigma_{v})$, without
reference count tracking

11:

12:

13:Process(edge $\\{x,y\\}$) $\rightarrow$ color

14:if $F_{x}\cap F_{y}=\emptyset$ then

15: abort

16:Let $c$ be chosen uniformly at random from $F_{x}\cap F_{y}$.

17:$F_{x}.\textsc{RemoveAndUpdate(c)}$

18:$F_{y}.\textsc{RemoveAndUpdate(c)}$

19:return color $c$

For each $v\in V$, $i\in[C/s]$, write $P_{v,i}$ for the set
$\sigma[[s]+(i-1)s]$ of the free region tracker $F_{v}$ for vertex $v$. (See
Algorithm 7.) Since we are assuming the $\sigma_{v}$ are $s$-wise independent,
the set $P_{v,i}$ will be uniformly distributed over over $\binom{[C]}{s}$.

Consider a fixed input stream $e_{1},e_{2},\ldots$, where the edges of the
stream together form the simple graph $G$. Write $b_{x,\\{u,v\\}}$ for the
value of the counter $b$ inside $F_{x}$ just before the algorithm processed
edge $\\{u,v\\}$. Let $D_{\\{u,v\\}}:=P_{u,b_{u,\\{u,v\\}}}\cap
P_{v,b_{v,\\{u,v\\}}}$. Also define $M_{u,v}:=\\{x:\\{x,u\\}\in G\land
b_{u,\\{x,u\\}}=b_{u,\\{u,v\\}}\land\\{x,u\\}\prec\\{u,v\\}\\}$; this is the
set of vertices which were adjacent to $u$, for which the edge $\\{x,u\\}$ was
added before $\\{u,v\\}$, and while the value of the counter $b$ inside
$F_{u}$ for vertex $u$ was the same as it was at the time $\\{u,v\\}$ was
added. This is the set of vertices whose color choices _might_ reduce the size
of $F_{u}\cap F_{v}$ at the time $\\{u,v\\}$ is added.

We will first show that of the following two classes of $m$ events, the
probability that any of the events is true is $\leq\delta/2$.

$\displaystyle\forall\\{u,v\\}\in G:H_{\\{u,v\\}}$
$\displaystyle:=\left\\{D_{\\{u,v\\}}\leq\frac{1}{2}s^{2}/C\right\\}$
$\displaystyle\forall(u,v)\text{ where }\\{u,v\\}\in G:J_{u,v}$
$\displaystyle:=\left\\{\sum_{x\in M_{u,v}}|D_{\\{u,v\\}}\cap
P_{x,b_{x,\\{x,u\\}}}|\geq 2\cdot\frac{3}{2}\frac{s^{3}}{C^{2}}\frac{\Delta
s}{C}\right\\}$

To bound the probability of $H_{\\{u,v\\}}$, we let $X_{1},\ldots,X_{C}$ be
indicator random variables where $X_{i}=1$ iff $i\in P_{u,b_{u,\\{u,v\\}}}$.
Since the $X_{i}$ are negatively associated[JP83], the proof of the Chernoff
bound holds, and

$\displaystyle\Pr[|D_{\\{u,v\\}}|\leq\frac{1}{2}s^{2}/C]$
$\displaystyle=\Pr[D_{\\{u,v\\}}\leq\frac{1}{2}\operatorname{\mathbb{E}}[D_{\\{u,v\\}}]]$
$\displaystyle=\Pr[\sum_{i\in[P_{v,b_{v,\\{u,v\\}}}]}X_{i}\leq\frac{1}{2}\operatorname{\mathbb{E}}[D_{\\{u,v\\}}]]$
$\displaystyle\leq\exp(-\frac{1}{8}\operatorname{\mathbb{E}}[D_{\\{u,v\\}}])=\exp(-\frac{s^{2}}{8C})$
$\displaystyle\leq\exp(-16\log\frac{n}{\delta})\leq\frac{\delta}{2n^{2}}$

To bound the probability of the events $\\{J_{u,v}\\}$, we will show that
$|D_{u,v}|$ is not too large w.h.p, and conditioned on that, the sum
$\sum_{x\in M_{u,v}}|D_{\\{u,v\\}}\cap P_{x,b_{x,\\{x,u\\}}}|$ is not too
large w.h.p. With $\\{X_{i}\\}_{i\in[C]}$ as defined above:

$\displaystyle\Pr[|D_{\\{u,v\\}}|\geq\frac{3}{2}s^{2}/C]$
$\displaystyle=\Pr[D_{\\{u,v\\}}\geq\frac{3}{2}\operatorname{\mathbb{E}}[D_{\\{u,v\\}}]]$
$\displaystyle\leq\Pr[\sum_{i\in[P_{v,b_{v,\\{u,v\\}}}]}X_{i}\geq\frac{3}{2}\operatorname{\mathbb{E}}[D_{\\{u,v\\}}]]$
$\displaystyle\leq\exp(-\frac{1}{10}\operatorname{\mathbb{E}}[D_{\\{u,v\\}}])=\exp(-\frac{s^{2}}{10C})$
$\displaystyle\leq\exp(-\frac{128}{10}\log\frac{n}{\delta})\leq\frac{\delta}{4n^{2}}$

The permutations $\\{\sigma_{x}\\}_{x\in M_{u,v}}$ are independent of
$\sigma_{u}$ and $\sigma_{v}$. For each $x\in M_{u,v}$, let
$Y_{1,x},\ldots,Y_{C,x}$ be indicator random variables where $Y_{i,x}$ is 1
iff $i\in P_{x,b_{x,\\{x,u\\}}}$, and zero otherwise. Due to the frequency of
free color buffer refreshing, $|M_{u,v}|\leq s\Delta/C$; and since
$|P_{x,b_{x,\\{x,u\\}}}|=s$, $\operatorname{\mathbb{E}}Y_{i,x}=s/C$. Since the
$\\{Y_{i,x}\\}_{i\in D_{\\{u,v\\}},x\in M_{u,v}}$ are negatively associated,
we can apply a Chernoff bound. If we assume that
$|D_{\\{u,v\\}}|\leq\frac{3s^{2}}{2C}$, then we have:

$\displaystyle\Pr\left[\sum_{x\in M_{u,v}}|D_{\\{u,v\\}}\cap
P_{x,b_{x,\\{x,u\\}}}|\geq 2\frac{\Delta
s^{2}}{C^{2}}\frac{3s^{2}}{2C}\right]$ $\displaystyle=\Pr\left[\sum_{i\in
D_{\\{u,v\\}},x\in M_{u,v}}Y_{i,x}\geq 2\frac{\Delta
s^{2}}{C^{2}}\frac{3s^{2}}{2C}\right]$
$\displaystyle\leq\exp\left(-\frac{1}{8}\frac{\Delta
s^{2}}{C^{2}}\frac{3s^{2}}{2C}\right)$
$\displaystyle\leq\exp(-12(\log(n/\delta))^{2})\leq\frac{\delta}{4n^{2}}$

Thus, the probability that either $|D_{\\{u,v\\}}|\geq\frac{3s^{2}}{2C}$ or
event $J_{u,v}$ does not hold is $\frac{\delta}{2n^{2}}$.

For the rest of the proof, we will consider the case where none of the events
$J_{u,v}$ or $H_{\\{u,v\\}}$ holds; this happens with probability $\geq
1-\delta/2$. Fix values of the $(\sigma_{v})_{v\in V}$ satisfying none of the
events. The only other random decisions made by the algorithm are the choices
made on Line 16, randomly choosing the edge color $\chi_{\\{u,v\\}}$ for
$\\{u,v\\}$ from $F_{u}\cap F_{v}$. We will prove by induction on the number
of edges processed that the probability of $|F_{u}\cap
F_{v}|\leq\frac{1}{4}s^{2}/C$ holding at the time Line 16 is executed, in
total over all $t$ edges so far is, $\leq\delta\cdot t/(2n^{2})$.

To do this, we will use the following lower bound:

$\displaystyle|F_{u}\cap F_{v}|\geq|D_{\\{u,v\\}}|-\sum_{x\in
M_{u,v}}W_{x,u}-\sum_{x\in M_{u,v}}W_{x,v}$ (6)

Here $W_{x,u}$ is the indicator random variable for the event that the color
chosen for $\\{x,u\\}$ was in $D_{\\{u,v\\}}$. The lower bound overcounts the
number of colors in $D_{\\{u,v\\}}$ that have been removed from $F_{u}\cap
F_{v}$.

The base case of the induction (0 edges) is immediate. Assume that we are
processing edge $\\{u,v\\}$, and that all edges $\\{x,y\\}$ earlier in the
stream, when they were processed, had $|F_{x}\cap F_{y}|\geq\frac{s^{2}}{4C}$.
For each $x\in M_{u,v}$, the color $\chi_{\\{x,u\\}}$ was drawn uniformly at
random from _some_ set $F_{x}\cap F_{u}$, which we assume satisfies
$|F_{x}\cap F_{u}|\geq\frac{s^{2}}{4C}$. For any subset $H$ of $D_{\\{x,u\\}}$
of size $\frac{s^{2}}{4C}$, if $\hat{\chi}$ is chosen u.a.r. from $H$, then

$\displaystyle\Pr[\hat{\chi}\in D_{\\{u,v\\}}]\leq\frac{|H\cap
D_{\\{u,v\\}}|}{|H|}\leq\frac{4C}{s^{2}}|P_{x,b_{x,\\{x,u\\}}}\cap
D_{\\{u,v\\}}|$

Conditioned on the color choices of all earlier edges, we thus have
$\operatorname{\mathbb{E}}W_{x,u}\leq\frac{4C}{s^{2}}|P_{x,b_{x,\\{x,u\\}}}\cap
D_{\\{u,v\\}}|$. Thus

$\displaystyle\operatorname{\mathbb{E}}\left[\sum_{x\in
M_{u,v}}W_{x,u}+\sum_{x\in M_{v,u}}W_{x,v}\right]$
$\displaystyle\leq\frac{4C}{s^{2}}\left(\sum_{x\in
M_{u,v}}|P_{x,b_{x,\\{x,u\\}}}\cap D_{\\{u,v\\}}|+\sum_{x\in
M_{v,u}}|P_{x,b_{x,\\{x,v\\}}}\cap D_{\\{u,v\\}}|\right)$
$\displaystyle\leq\frac{4C}{s^{2}}\cdot 2\frac{\Delta
s^{2}}{C^{2}}\frac{3s^{2}}{2C}=12\frac{\Delta}{C}\frac{s^{2}}{C}<\frac{s^{2}}{8C}$
since $\Delta\leq C/128$

By the multiplicative/Chernoff-like formulation of Azuma’s inequality,

$\displaystyle\Pr$ $\displaystyle\left[\sum_{x\in M_{u,v}}W_{x,u}+\sum_{x\in
M_{v,u}}W_{x,v}\geq\frac{s^{2}}{4C}\right]$
$\displaystyle\leq\exp(-\frac{1}{3}\frac{s^{2}}{4C})\leq\exp\left(-\frac{32}{3}\log\frac{n}{\delta}\right)\leq\frac{\delta}{2n^{2}}$

By a union bound over all edges, the probability that any edge $\\{u,v\\}$ has
$|F_{u}\cap F_{v}|\leq\frac{s^{2}}{4C}$ is $\leq\delta/2$.

We have shown that, in total, the probability of the algorithm aborting
because $F_{u}\cap F_{v}=\emptyset$ is $\leq\delta$. ∎

Algorithm 8 can be generalized to produce $O(\Delta^{2}/t)$ edge colorings
using $\widetilde{O}(n\sqrt{t})$ bits of space, by increasing the parameters
$C$ and $s$ while ensuring that $s^{2}/C=\Omega(\log(n/\delta))$. Then as at
most $s\Delta/C$ colors are removed from each free color tracker, it will be
possible to store each free color tracker using $\widetilde{O}(s\Delta/C)$
bits of space. However, further adjustment would be necessary to make the
algorithm use $\widetilde{O}(n\sqrt{t})$ random bits. We suspect that picking
$(\epsilon,O(s^{2}/C))$-wise independent distributions will be sufficient. As
proving this would be tedious, and the following Theorem 1.3 already provides
a color-space tradeoff for the edge arrival setting, we do not do so.

We now introduce a technical lemma which will be useful in the proof of
Theorem 1.3

######  Lemma 4.5.

Let $V$ be a set of size $n$, $\delta\in(0,1)$, and let $\Delta$ be a power of
two, satisfying $\Delta\geq 256\log\frac{n}{\delta}$. Define $C=32\Delta$, and
let $s$ be the least power of two which is $\geq
512\sqrt{\Delta\log\frac{n}{\delta}}$. Let $(\sigma_{v})_{v\in V}$ be randomly
chosen permutations from an $(\epsilon,s)$-wise independent family, where
$\epsilon\leq\exp(-s^{2}/C)\leq(\delta/n)^{1024}$. For $i\in[C/s]$, $v\in V$,
let $P_{v,i}:=\sigma[s(i-1)+[s]]$.

We say that the permutations $(\sigma_{v})_{v\in V}$ are _good_ if, for all
simple graphs $H$ on $V\times[C/s]$ for which, for any $u,w\in V$ and
$i\in[C/s]$, there is at most one $j$ for which edge $\\{(u,i),(v,j)\\}$ is in
$H$, and the max degree of $H$ is $\leq s\Delta/C$; that the graph $H$ can be
list-edge colored where edge $\\{(u,i),(v,j)\\}$ may only use colors in
$P_{u,i}\cap P_{v,j}$.

The probability that the $(\sigma_{v})_{v\in V}$ are _good_ is $\geq
1-\delta$.

###### Proof of Lemma 4.5.

We will prove this in two steps. First, define a specific property U that the
$(\sigma_{v})_{v\in V}$ should satisfy with probability $\geq 1-\delta$;
second, prove that if this property holds, then any graph $H$ can be colored.

The permutations $(\sigma_{v})_{v\in V}$ satisfy property U if:

  * •

For all pairs $(u,i),(v,j)\in V\times[C/s]$, with $u\neq v$, we have
$|P_{u,i}\cap P_{v,i}|\geq\frac{s^{2}}{2C}$.

  * •

For each $(u,i)\in V\times[C/s]$, $S\subseteq(V\setminus\\{s\\})\times[C/s]$
where $|S|\leq s\Delta/C$ and $S$ includes no two vertices $(v,i),(u,j)$ with
$v=u$, and all $T\in\binom{P_{u,i}}{|S|-1}$, there exists some $(x,j)\in S$
for which $|P_{x,j}\cap T|<\frac{1}{10}|P_{x,j}\cap P_{u,i}|$. (This is, in
effect, a stronger version of Hall’s condition).

For the first part of property $U$, it is straightforward to bound the
probability that it does not hold. For a given pair $(u,i),(v,j)\in
V\times[C/s]$, $u\neq v$, because the permutations are $(\epsilon,s)$-wise
independent, the sets $P_{u,i}$ and $P_{v,j}$ are within $\epsilon$-total-
variation distance of being uniformly random subsets of $[C]$ of size $s$, we
can apply a Chernoff bound for the number of elements in $P_{u,i}$ that lie in
$P_{v,j}$:

$\displaystyle\Pr[P_{u,i}\cap
P_{v,j}\leq\frac{1}{2}\frac{s^{2}}{C}]\leq\exp(-\frac{1}{8}\frac{s^{2}}{C})+\epsilon\leq\exp(-2^{10}\log(n/\delta))+\epsilon\leq\frac{\delta}{2n^{2}}$
(7)

(The additive factor $\epsilon$ accounts for the maximum difference in
probabilities for this event between the case where $P_{u,i}$ is exactly
uniform and the case where it is $\epsilon$-far from such.)

For the second part, consider a specific combination $(u,i,S,T)$, and fix
$P_{u,i}$. Then the probability that this combination violates property U is:

$\displaystyle\Pr\left[\bigwedge_{(x,j)\in S}\left\\{|P_{x,j}\cap
T|\geq\frac{1}{10}|P_{x,j}\cap P_{u,i}\right\\}\right]\leq\prod_{(x,j)\in
S}\Pr_{P_{x,j}}\left[|P_{x,j}\cap T|\geq\frac{1}{10}|P_{x,j}\cap
P_{u,i}|\right]$ (8)

since the $P_{x,j}\in S$ are all independent, since $S$ contains at most one
entry for each $v\in V$. Since $P_{x,j}$ is a uniformly random subset $[C]$,
$P_{x,j}\cap P_{u,i}$ is symmetrically distributed over $P_{u,i}$. Now let
$\hat{T}$ be a uniformly random element of $\binom{P_{u,i}}{s}$, and define
indicator random variables $\\{Y_{k}\\}_{k\in P_{u,i}}$ so that $Y_{k}=1$ iff
$k\in\hat{T}$; these are negatively associated and
$\operatorname{\mathbb{E}}[Y_{k}]=\frac{|S|-1}{s}$. Thus, if we assume
$|P_{x,j}\cap P_{u,i}|=h$:

$\displaystyle\Pr_{P_{x,j}}$ $\displaystyle\left[|P_{x,j}\cap
T|\geq\frac{1}{10}|P_{x,j}\cap P_{u,i}|\Big{|}|P_{x,j}\cap P_{u,i}|=h\right]$
$\displaystyle\leq\Pr_{\hat{T}}\left[|P_{x,j}\cap\hat{T}|\geq\frac{1}{10}h\Big{|}|P_{x,j}\cap
P_{u,i}|=h\right]+\epsilon$ $\displaystyle=\Pr_{\\{Y_{k}\\}_{k\in
P_{u,i}}}\left[\sum_{k\in P_{u,i}}Y_{k}\geq\frac{1}{10}h\Big{|}|P_{x,j}\cap
P_{u,i}|=h|\right]+\epsilon$
$\displaystyle\leq\exp\left(-2\left(\frac{1}{10}-\frac{|S|-1}{s}\right)^{2}h\right)+\epsilon$
$\displaystyle\leq\exp\left(-2\left(\frac{1}{10}-\frac{\Delta}{C}\right)^{2}h\right)+\epsilon\leq\exp\left(-h/200\right)+\epsilon\qquad\text{since
$C=32\Delta$}$

This bound is useful only if $h$ is large enough. By the law of total
probability, and using the bound from Eq. 7 to handle the case where $h$ is
small:

$\displaystyle\Pr_{P_{x,j}}$ $\displaystyle\left[|P_{x,j}\cap
T|\geq\frac{1}{10}|P_{x,j}\cap P_{u,i}|\right]$
$\displaystyle\leq\Pr_{P_{x,j}}\left[|P_{x,j}\cap
T|\geq\frac{1}{10}|P_{x,j}\cap P_{u,i}|\Big{|}|P_{x,j}\cap
P_{u,i}|\geq\frac{s^{2}}{2C}\right]\Pr\left[|P_{x,j}\cap
P_{u,i}|\geq\frac{s^{2}}{2C}\right]+\Pr\left[|P_{x,j}\cap
P_{u,i}|\leq\frac{s^{2}}{2C}\right]$
$\displaystyle\leq(\exp\left(-\frac{s^{2}}{400C}\right)+\epsilon)\cdot
1+(\exp(-\frac{s^{2}}{8C})+\epsilon)\leq
2\exp\left(-\frac{s^{2}}{400C}\right)\,.$

Substituting this result into Eq. 8 gives:

$\displaystyle\Pr\left[\bigwedge_{(x,j)\in S}\left\\{|P_{x,j}\cap
T|\geq\frac{1}{10}|P_{x,j}\cap P_{u,i}\right\\}\right]\leq
2^{|S|}\exp\left(-|S|\frac{s^{2}}{400C}\right)\,.$

Taking a union bound over all $(u,i,S,T)$ tuples gives:

$\displaystyle\Pr$ $\displaystyle[\text{second part of Property U fails}]$
$\displaystyle\leq\sum_{(u,i)\in
V\times[C/s]}\sum_{k=1}^{s\Delta/C}\sum_{\text{valid $S$ with
$|S|=k$}}\sum_{T\subseteq\binom{P_{u,i}}{k-1}}2^{k}\exp\left(-k\frac{s^{2}}{400C}\right)$
$\displaystyle\leq
n\cdot\sum_{k=1}^{s\Delta/C}\cdot\binom{n-1}{k}\left(\frac{C}{s}\right)^{k}\cdot\binom{s}{k-1}\cdot
2^{k}\exp\left(-k\frac{s^{2}}{400C}\right)$ $\displaystyle\leq
n\sum_{k=1}^{s\Delta/C}\left(2nCs\exp\left(-\frac{s^{2}}{400C}\right)\right)^{k}$
$\displaystyle\leq 2n\cdot
2nCs\exp\left(-\frac{s^{2}}{400C}\right)\qquad\qquad\text{for large enough
$s^{2}/C$}$ $\displaystyle\leq
4n^{2}\cdot(32n)^{2}\exp(-\frac{2048}{100}\log(n/\delta))\leq\frac{\delta}{2}\qquad\qquad\text{since
$s\leq C=32\Delta$}$

Combining this with a union bound over Eq. 7 implies that property U fails to
hold with probability $\leq\delta$.

For the second stage of the proof, we consider the following iterative process
to color any graph $H$ satisfying the given conditions. Consider an arbitrary
ordering $v_{1},\ldots,v_{n}$ of the vertices in $V\times[C/s]$. For a given
vertex $v_{t}$, let $A(v_{t})$ be the set of vertices in
$\\{v_{1},\ldots,v_{t-1}\\}$ which are adjacent to $(v_{t},i)$, and let
$B(v_{t},i)$ be the set of vertices in $\\{v_{t+1},\ldots,v_{n}\\}$ which are
adjacent to $(v_{t},i)$. For each $z\in A(v_{t})\cup B(v_{t})$, define
$U_{t,v_{t},z}$ to be the set of colors in $P_{v_{t}}\cap P_{z}$ that were
already used by edges to vertices in $A(v_{t})$ just _after_ step $t$. The
color assignment chosen will maintain the invariant W that
$|U_{t,z,(v_{t^{\prime}})}|\leq\frac{1}{3}|P_{z}\cap P_{v_{t^{\prime}}}|$ for
all $t^{\prime}>t$ and $z\in A(v_{t^{\prime}})$. In other words, that when it
is time to color the edges from a future vertex $(v_{t^{\prime}})$ to
$A(v_{t^{\prime}}$, only a $\leq 1/3$ fraction of the initially possible color
options will have been used.

Invariant W automatically holds when $t=0$, since no edges have been colored.
Say the invariant holds at time $t-1$. Then we are guaranteed that
$|U_{t-1,z,v_{t}}|\leq\frac{1}{3}|P_{z}\cap P_{v_{t}}|$ for all $z\in
A(v_{t})$, and want to find color assignments for the edges from $A(v_{t})$ to
$z$ so that $|U_{t,z,v_{t}}|\leq\frac{1}{3}|P_{z}\cap P_{v_{t}}|$ for all
$z\in B(v_{t})$. To do this, we will first pick a set $F\subseteq P_{v_{t}}$
that satisfies:

$\displaystyle\forall x\in A(v_{t}):$ $\displaystyle\quad|P_{x}\cap
P_{v_{t}}\setminus U_{t-1,x,v_{t}}\setminus F|\geq\frac{1}{10}|P_{x}\cap
P_{v_{t}}|$ (9) $\displaystyle\forall x\in B(v_{t}):$
$\displaystyle\quad|(P_{y}\cap P_{v_{t}})\setminus F|\leq\frac{1}{3}|P_{y}\cap
P_{v_{t}}|$ (10)

That such a set $F$ exists follows by the probabilistic method; say $F$ were
chosen so that each element of $P_{v_{t}}$ is included u.a.r with probability
$\frac{7}{10}$. For $i\in P_{v,t}$, let $X_{i}$ be the indicator random
variable for the event that $i\in F$. Then the probability of Eq. 9 is bounded
by:

$\displaystyle\Pr$ $\displaystyle\left[|(P_{x}\cap P_{v_{t}})\setminus
U_{t-1,x,v_{t}}\setminus F|\geq\frac{1}{10}|P_{x}\cap P_{v_{t}}|\right]$
$\displaystyle\leq\Pr\left[|(P_{x}\cap P_{v_{t}})\setminus
U_{t-1,x,v_{t}}\setminus F|\geq\frac{3}{20}|(P_{x}\cap P_{v_{t}})\setminus
U_{t-1,x,v_{t}}|\right]\quad\text{ since $|(P_{x}\cap P_{v_{t}})\setminus
U_{x,v}|\geq\frac{2}{3}|P_{x}\cap P_{v_{t}}|$ }$
$\displaystyle\leq\Pr\left[\sum_{i\in(P_{x}\cap P_{v_{t}})\setminus
U_{t-1,x,v_{t}}}X_{i}\geq\frac{17}{20}|(P_{x}\cap P_{v_{t}})\setminus
U_{t-1,x,v_{t}}|\right]$ $\displaystyle\leq\exp\left(-\frac{9}{200}|P_{x}\cap
P_{v_{t}}\setminus U_{t-1,x,v_{t}}|\right)\qquad\text{by Chernoff bound, since
$\operatorname{\mathbb{E}}$ of LHS is $\frac{14}{20}|(P_{x}\cap
P_{v_{t}})\setminus U_{t-1,x,v_{t}}|$}$
$\displaystyle\leq\exp\left(-\frac{3}{100}|P_{x}\cap
P_{v_{t}}|\right)\qquad\text{since $|(P_{x}\cap P_{v_{t}})\setminus
U_{t-1,x,v_{t}}|\geq\frac{2}{3}|P_{x}\cap P_{v_{t}}|$}$
$\displaystyle\leq\exp\left(-\frac{3s^{2}}{200C}\right)=\exp\left(-\frac{3072}{25}\log(n/\delta)\right)<\frac{1}{2n}$

And for Eq. 10:

$\displaystyle\Pr\left[|(P_{x}\cap P_{v_{t}})\setminus
F|\geq\frac{1}{3}|P_{x}\cap P_{v_{t}}|\right]$
$\displaystyle=\Pr\left[\sum_{i\in(P_{x}\cap
P_{v_{t}})}X_{i}\leq\frac{2}{3}|P_{x}\cap P_{v,t}|\right]$
$\displaystyle\leq\exp\left(-2\left(\frac{7}{10}-\frac{2}{3}\right)^{2}|P_{x}\cap
P_{v,t}|\right)$ $\displaystyle\leq\exp\left(-\frac{1}{450}|P_{y}\cap
P_{v}|\right)=\exp\left(-\frac{s^{2}}{900C}\right)=\exp\left(-\frac{2048}{225}\log(n/\delta)\right)<\frac{1}{2n}$

Applying a union bound for the complements of Eq. 10 and Eq. 9 over all
applicable $z$, we find that both conditions hold with positive probability,
so a suitable $F$ exists.

Now that $F$ has been chosen, we will select the colors for the edges from
$v_{t}$ to each $x\in A(v_{t})$ from the set $(P_{x}\cap P_{v_{t}})\setminus
U_{t-1,x,v_{t}}\setminus F$. Since no colors in $F$ are chosen, for any $z\in
B(v_{t})$, $U_{t,z,v_{t}}$ will not contain any element of $F$; thus
$|U_{t,z,v_{t}}|\leq|(P_{x}\cap P_{v_{t}})\setminus
F|\leq\frac{1}{3}|P_{x}\cap P_{v_{t}}|$.

Construct the bipartite graph $J$ between $A(v_{t})$ and $P_{v_{t}}$, where
$x\in A(v_{t})$ has an edge to each of the colors in $(P_{x}\cap
P_{v_{t}})\setminus U_{t-1,x,v_{t}}\setminus F$. We claim there is an an
$A(v_{t})$-saturating matching $M$ of $J$; given this matching, we assign to
edge $\\{x,v_{t}\\}$ its matched color $M(x)$. For all $x\in A(v_{t})$, we
will have $M(x)\in(P_{x}\cap P_{v_{t}})\setminus U_{t-1,x,v_{t}}\setminus F$;
since $M(x)\notin U_{t-1,x,v_{t}}$, the edge color for $\\{x,v_{t}\\}$ will
not have been used before by any edge adjacent to $x$. As the matching assigns
a unique color to each edge, the edge coloring constraint will also be
satisfied for $v_{t}$.

To prove there exists a matching $M$ in $J$, we verify that Hall’s condition
holds. For any subset $S$ of the vertices in $A(v_{t})$, we want to show that

$\displaystyle\left|\bigcup_{x\in S}((P_{x}\cap P_{v_{t}})\setminus
U_{t-1,x,v_{t}}\setminus F)\right|\geq|S|$

The construction of $H$ ensures that $A(v_{t})$ and all subsets thereof
satisfy the conditions for the second part of Property U (Specifically,
$|A(v_{t})|\leq s\Delta/C$, and that for any $b\in V$ there is at most one $j$
for which $(b,j)\in A(v,t)$.) By this property, we are guaranteed that for all
$T\subseteq P_{v_{t}}$ of size $k-1$, that there exists some $x\in S$ for
which $|P_{x}\cap T|\leq\frac{1}{10}|P_{x}\cap P_{v_{t}}$. If Hall’s condition
does not hold for $S$, then there must exist some $T\subseteq P_{v,t}$ for
which:

$\displaystyle\bigcup_{x\in S}((P_{x}\cap P_{v_{t}})\setminus
U_{t-1,x,v_{t}}\setminus F)\subseteq T$ $\displaystyle\implies\quad\forall
x\in S:\quad$ $\displaystyle(P_{x}\cap P_{v_{t}})\setminus
U_{t-1,x,v_{t}}\setminus F\subseteq T$ $\displaystyle\implies\quad\forall x\in
S:\quad$ $\displaystyle(P_{x}\cap P_{v_{t}})\setminus U_{t-1,x,v_{t}}\setminus
F\subseteq T\cap P_{x}$ $\displaystyle\implies\quad\forall x\in S:\quad$
$\displaystyle|(P_{x}\cap P_{v_{t}})\setminus U_{t-1,x,v_{t}}\setminus
F|\leq|T\cap P_{x}|$ $\displaystyle\implies\quad\forall x\in S:\quad$
$\displaystyle\frac{1}{10}|P_{x}\cap P_{v_{t}}|\leq|T\cap P_{x}|\qquad\text{by
Eq. \ref{eq:F-backward}}$

But by the second part of Property U, there must exist an $x\in S$ for which
$\frac{1}{10}|P_{x}\cap P_{v_{t}}|>|T\cap P_{x}|$; this is a contradiction, so
it follows that Hall’s condition does hold for $S$. Since Hall’s condition
holds for all $S\subseteq A(v_{t})$, $J$ will contain a matching, and step $t$
will ensure invariant W holds for step $t+1$.

By induction, it follows that invariant W holds for all $t\in[n]$, and thus
that the process to color the edges of the graph will always work. ∎

At the core of the algorithm used by Theorem 1.3 will be an algorithm for
partial coloring of input streams. We will prove that this inner algorithm
Algorithm 9 works for a specific class of edge arrival streams. These are
categorized by a Property Z, which is closely linked to the way the free color
tracker (Algorithm 7) refreshes its pool of colors.

######  Definition 4.5.

For each edge $\\{u,v\\}$ that arrives at time $t$, let $d_{u,t}$ and
$d_{v,t}$ be the degrees of $u$ and $v$ respectively in the multigraph formed
by all stream edges up to $t$. The edges adjacent to each $x\in V$ are
assigned to blocks depending on the degree of $x$ after they were added; thus
edge $\\{x,y\\}$ arriving at time $t$ is assigned to block number
$b_{x,t}:={\left\lceil{d_{x,t}\cdot\frac{C}{s\Delta}}\right\rceil}$. Note that
$b_{x,t}\in[C/s]$. The stream satisfies Property Z when, for all $v\in V$,
$i\in[C/s]$, and $w\in V\setminus\\{v\\}$, the stream contains at most one
edge $\\{v,w\\}$, added at time $t$, for which $b_{v,t}=i$.

Algorithm 9 Partial coloring algorithm: $(1/3)$-partial $O(\Delta)$ edge
coloring for graph edge arrival streams satisfying Property Z, plus reference
counting

1:Input: Stream of edge arrivals $n$-vertex graph $G=(V,E)$.

2:Assume $\Delta$ is a power of two

3:

4:Initialize($\ell$,$\xi$,$\Delta$,$C$,$(\sigma_{v})_{v\in V}$, $s$, $R$):

5:Input $\Delta$ is the maximum degree of the input graph stream

6:Input $C$ the number of colors this sketch will use

7:Input $s$ is block size parameter, and $(\sigma_{v})_{v\in V}$ are $s$-wise
almost independent permutations

8:Input $R$ is a reference counted pool of edges

9:Each edge $e\in R$ will have associated counter
$M^{(\ell)}_{e}\in[2^{\ell}]$ and color class
$\chi^{(\ell)}_{e}\in\\{0,\ldots,{\left\lceil{\log_{3/2}{\Delta^{(\ell)}}}\right\rceil}\\}\times[C^{(\ell)}]$

10:for $v\in V$ do

11: $F_{v}\leftarrow\textsc{InitFreeTracker}(C,s,\Delta,\sigma_{v})$.
$\triangleright$ Also referred to as: $F^{(\ell,\xi)}_{v}$

12:

13:Process(edge $\\{x,y\\}$) $\rightarrow$ Option<color>
$\in\\{\bot\\}\cup[C]$

14:if $F_{x}\cap F_{y}\neq\emptyset$ then

15: Choose $c\in F_{x}\cap F_{y}$ arbitrarily

16: $F_{x}.\textsc{RemoveAndUpdate(c, $\\{x,y\\}$)}$ $\triangleright$ This
will increase $\\{x,y\\}$’s refcount in $R$

17: $F_{y}.\textsc{RemoveAndUpdate(c, $\\{x,y\\}$)}$

18: $\chi^{(\ell)}_{\\{x,y\\}}\leftarrow(\xi,c)$

19: $M^{(\ell)}_{\\{x,y\\}}\leftarrow 1$

20: return color $c$

21:else

22: return $\bot$

######  Lemma 4.6.

Algorithm 9 properly edge-colors a $\geq 1/3$ fraction of the edges in its
input stream, if the permutations it is given are good according to Lemma 4.5,
and the input stream satisfies Property Z.

###### Proof of Lemma 4.6.

Say that the input stream for Algorithm 9 satisfies Property Z. To each edge
$\\{x,y\\}$, arriving at time $t$, we can associate a set of possible colors
$P_{x,b_{x,t}}\cap P_{y,b_{y,t}}$, where $P_{x,i}:=\sigma_{x}[(i-1)s+[s]$
indicates the $i$th set of colors used by the free color tracker $F_{x}$. Of
course, as the algorithm progresses some of the colors in $P_{x,b_{x,t}}\cap
P_{y,b_{y,t}}$ may be used by other edges adjacent to $x$ and $y$; the color
trackers $F_{x}$ and $F_{y}$ precisely record these.

Let $H$ be the simple graph on $V\times[C/s]$ formed by mapping each edge
$\\{x,y\\}$ arriving in the input stream at time $t$ to the edge
$\\{(x,b_{x,t}),(y,b_{y,t})\\}$. Because the stream satisfies Property Z, for
any $u,i,v$, there is at most one $j$ for which $\\{(u,i),(v,j)\\}$ is in $H$.
Thus, by Lemma 4.5, with probability $\geq 1-\delta$ over randomly chosen
advice, the permutations $(\sigma_{v})_{v\in V}$ are good, and there exists an
edge coloring $\chi$ of $H$ where each edge $\\{(x,i),(y,j)\\}$ is given a
color from $P_{x,i}\cap P_{y,j}$. This implies that, _if_ the color chosen at
Line 15 were to exactly match the color from $\chi$ at each step, it would be
possible to for the first layer to assign a color to every edge.

However, Line 15, when processing edge $\\{x,y\\}$ at time $t$, chooses a
color arbitrarily from the set of available colors in $P_{x,b_{x,t}}\cap
P_{y,b_{y,t}}$. As a result, the algorithm may select colors so that at some
point, a given edge has $F_{x}\cap F_{y}=\emptyset$ on Line 14, and cannot be
colored. We claim that nevertheless, it will color a $\geq\frac{1}{3}$
fraction of all input edges. Consider any fixed input graph stream of length
$T$ for Algorithm 9, whose edges form multiset $E$. Consider a run of this
algorithm on the stream. At each time $t$, let
$\rho_{t}:E\mapsto[C]\cup\\{\bot\\}$ indicate the partial coloring produced by
the stream after $t$ edges were processed. Let $\chi:E\mapsto[C]$ be the
coloring produced by Lemma 4.5. Call an edge $e$ "good" at time $t$ if
$\rho_{t}(e)=\bot$ and it is possible to assign color $\chi(e)$ to $e$. (In
other words, there is no edge $f$ incident on one of $e$’s endpoints for which
$\rho_{t-1}(f)=\chi(e)$.) Initially, all edges in $E$ are good. Each time $t$
that the algorithm processes an edge $\\{u,v\\}$, it will either fail to color
the edge, or set $\rho_{t}(\\{u,v\\})=c$ for some color $c$. If
$c=\chi(\\{u,v\\}$, then the number of "good" edges will be reduced by 1,
because $\chi$ is a valid edge coloring. If $c\neq\chi(\\{u,v\\}$, then the
number of "good" edges will be reduced by 3; $\\{u,v\\}$ will no longer be
good, and there are at most two edges $f$ that are incident to either $u$ or
$v$ and have $\chi(f)=c$. If the algorithm fails to color edge $\\{u,v\\}$,
then this means $\chi(\\{u,v\\})$ was not available (because some edge
incident on $u$ or $v$ used that color); so in all cases, after the algorithm
processes an edge, it will no longer be "good". Thus, at the end of the
stream, there will be no "good" edges remaining; and since the number of
"good" edges is reduced by at most 3 per edge that was colored, the number of
colored edges must be at least $|E|/3$. ∎

Finally, we state and prove the formal version of Theorem 1.3.

######  Theorem 4.7 (Formal version of Theorem 1.3).

There is a deterministic algorithm for online $O(\Delta(\log\Delta)^{2})$ edge
coloring in edge arrival streams for multigraphs, using $O(n\sqrt{\Delta}(\log
n)^{2.5}(\log\Delta)^{3})$ bits of space, and $\widetilde{O}(n\sqrt{\Delta})$
bits of advice. (By picking a uniformly random advice string, the same
algorithm can alternatively be used as a robust algorithm with
$1/\operatorname{poly}(n)$ error; the advice can also be verified and computed
in exponential time.)

###### Proof.

We claim that Algorithm 11 satisfies the conditions of the theorem. This
algorithm uses $O(n\sqrt{\Delta})$ bits of advice, for which we do not know of
an efficient polynomial time construction. $\delta\in(0,1)$ is a parameter
which gives, if the advice string is chosen uniformly at random, an upper
bound on the probability that the advice string does not work for all possible
inputs. If we ran this algorithm with a random advice string, it would be
robust to adversarially generated inputs, with failure probability
$\leq\delta$.

Algorithm 11 runs $O(\log\Delta)$ instances of an inner algorithm, Algorithm
10, which is designed to give correct edge colorings for graph streams with a
specific low-repetition guarantee: that for any vertex $v\in V$, if one
considers the sequence of edges adjacent to $v$ in stream order, and splits
them into $O(\sqrt{\Delta/\log n})$ contiguous lists, that no lists will
include a given edge more than once. To handle edges that are more commonly
repeated, Algorithm 11 will keep track of all edges which, if added, might
violate the guarantee, and send them to another instance of Algorithm 10 which
handles graph streams where no contiguous lists of edges adjacent to a vertex
includes a given edge twice; and if an edge in the stream might violate that
condition, the algorithm sends it to another copy of Algorithm 10, and so on.

Algorithm 10 Inner algorithm: $O(\Delta\log\Delta)$ edge coloring for graph
edge arrival streams which have certain substreams satisfying Property Z, plus
reference counting

1:Input: Stream of edge arrivals $n$-vertex graph $G=(V,E)$.

2:Assume $\Delta$ is a power of two

3:Superscript $\cdot^{(\ell)}$ indicates _level_ of algorithm

4:

5:Initialize($\ell$, $\Delta^{(\ell)}$, $R$):

6:Input $\Delta^{(\ell)}$ is the maximum degree of the input graph

7:Let $C^{(\ell)}=32\Delta^{(\ell)}$

8:$D^{(\ell)}\leftarrow\emptyset$ be a set of $O(n\log n)$ "overflow" edges

9:if $\Delta^{(\ell)}\geq 256\log(n/\delta))$ then $\triangleright$ Condition
for Lemma 4.5 to apply

10: Let $s^{(\ell)}$ satisfy constraints of Lemma 4.5

11: Advice: $\\{\sigma_{v}^{(\ell)}\\}_{v\in V}$ are permutations over
$[C^{(\ell)}]$, "good" for Lemma 4.5

12: for each _layer_
$\xi\in[{\left\lceil{\log_{3/2}{\Delta^{(\ell)}}}\right\rceil}]$ do

13: $\mathfrak{I}^{(\ell,\xi)}\leftarrow$
Initialize($\ell$,$\xi$,$\Delta$,$C$,$s$,$\\{\sigma_{v}^{(\ell)}\\}_{v\in
V}$,$R$) from Algorithm 9

14:

15:Process(edge $\\{x,y\\}$) $\rightarrow$ color
$\in\left[{\left\lceil{\log_{3/2}{\Delta^{(\ell)}}}\right\rceil}\right]\times\left[C^{(\ell)}\right]$

16:if $\Delta^{(\ell)}\geq 256\log(n/\delta))$ then

17: for
$\xi\in\left[{\left\lceil{\log_{3/2}{\Delta^{(\ell)}}}\right\rceil}\right]$ do

18: Let $c\leftarrow\mathfrak{I}^{(\ell,\xi)}.\textsc{Process}(\\{x,y\\})$
from Algorithm 9

19: if $c\neq\bot$ then

20: return color $(\xi,c)$

21:$D^{(\ell)}\leftarrow D^{(\ell)}\cup\\{\\{x,y\\}\\}$

22:Increase reference count for $\\{x,y\\}$ in $R$

23:Greedily pick a color class $c\in[C^{(\ell)}]$ not used by any edge in
$D^{(\ell)}$ adjacent to $x$ or $y$

24:$\chi^{(\ell)}_{\\{x,y\\}}\leftarrow(0,c)$

25:$M^{(\ell)}_{\\{x,y\\}}\leftarrow 1$

26:return color $(0,c)$

We will first prove that the inner algorithm, Algorithm 10, works. This
algorithm runs a number of instances of Algorithm 9, which perform a greedy
partial coloring of the input stream, with constraints on the set of colors
that it can use for any edge, as per Lemma 4.5. This greedy-coloring can be
performed in $O(n\sqrt{\Delta})$ space, and by Lemma 4.6 is guaranteed to
color at least $1/3$ of the edges in the input stream. By sending all edges
which the greedy procedure did not color to an independent greedy coloring
instance, the number of uncolored edges can be reduced further; after
$O(\log\Delta)$ iterations of this, an $O(1/\Delta)$ fraction of the input
stream has not been colored; this part of the stream can be stored entirely
and colored with $2\Delta-1$ colors.

In Algorithm 10, the for loop at Line 17 sends the edge $\\{x,y\\}$ being
processed to each of the
${\left\lceil{\log_{3/2}\Delta^{(\ell)}}\right\rceil}$ instances of Algorithm
9, until either one of them assigns a color to the edge, or all the instances
fail to color the edge. Since each instance is guaranteed to color a $\geq
1/3$ fraction of the edges it processes, only a
$(2/3)^{\left\lceil{\log_{3/2}\Delta^{(\ell)}}\right\rceil}\leq\frac{1}{\Delta^{(\ell)}}$
fraction of the edges received by Algorithm 10 will reach Line 21 of the
algorithm and be stored in $D^{(\ell)}$; since there are only $O(n)$ such
edges, storing them does not significantly affect the space usage of the
algorithm. These edges will be greedily colored using a fresh set of colors.

Algorithm 11 Deterministic algorithm for $O(\Delta(\log\Delta)^{2})$ edge
coloring for multigraph edge arrival streams

1:Input: Stream of edge arrivals $n$-vertex graph $G=(V,E)$

2:Assume $\Delta$ is a power of two

3:

4:Initialize:

5:Let $R\leftarrow\emptyset$ be a reference counted pool of edges. (This will
be a set of "recent" edges for each layer in each level, including edges that
are either in $D^{(\ell)}$ or have a reference from one of the
$F_{x}^{(\ell,\xi)}$

6:Each edge $e\in R$ will have, per level $\ell$, one associated counter
$M^{(\ell)}_{e}\in[0,2^{\ell}]$ and color class
$\chi^{(\ell)}_{e}\in\\{0,\ldots,{\left\lceil{\log_{3/2}{\Delta^{(\ell)}}}\right\rceil}\\}\times[C^{(\ell)}]$.
When an edge is added to the pool, $M^{(\ell)}_{e}=0$ for all layers.

7:for each _level_ $\ell$ in $0,\ldots,\log\Delta$ do

8: Define $\Delta^{(\ell)}=\Delta/2^{\ell}$

9: $\mathfrak{K}^{(\ell)}\leftarrow$ Initialize($\ell$,$\Delta^{(\ell)}$) from
Algorithm 10

10:

11:Process(edge $\\{x,y\\}$) $\rightarrow$ color

12:for $\ell$ in $0,\ldots,\log\Delta$ do

13: if $\\{x,y\\}$ is in $R$ and $M^{(\ell)}_{\\{x,y\\}}>0$ then

14: if $M^{(\ell)}_{\\{x,y\\}}=2^{\ell}$ then

15: continue

16: else

17: $M^{(\ell)}_{\\{x,y\\}}\leftarrow M^{(\ell)}_{\\{x,y\\}}+1$

18: Let $(i,j)\leftarrow\chi^{(\ell)}_{\\{x,y\\}}$

19: return color $\left(\ell,i,(j-1)2^{\ell}+M^{(\ell)}_{\\{x,y\\}}\right)$

20: else

21: Let $(\xi,c)\leftarrow\mathfrak{K}^{(\ell)}.\textsc{Process}$($\\{x,y\\}$)
for level $\ell$ algorithm

22: return color $\left(\ell,\xi,(c-1)2^{\ell}+1\right)$

To handle general multigraphs, Algorithm 11 divides the stream into a series
of levels, for $\ell$ from $0$ to $\log\Delta$. The higher levels process very
common edges, which are assigned blocks of $2^{\ell}$ colors for layer $\ell$.
Each level uses an instance of Algorithm 10 to assign color blocks for the
edges it receives. If a copy $e$ of a given edge $\\{u,v\\}$ arrives, and the
color block for $\\{u,v\\}$ is not full, then the $e$ will be assigned the
next available color in the block. The specific scheme, as we shall show,
ensures that every edge is either colored from an existing color block, or
passed to an instance of Algorithm 10; and in the latter case, ensures that
property Z holds for the stream sent to Algorithm 10.

Algorithm 11 maintains a global reference counted pool $R$, which keeps track
of every edge $\\{x,y\\}$ that arrives for some amount of time. Each level
$\ell$ can provide references for the edge; $\\{x,y\\}$ will only be dropped
from $R$ if no levels have a reference. At level $\ell$, we have two cases,
depending on how $\\{x,y\\}$ was processed by Algorithm 10. If $\\{x,y\\}$ was
not colored by any layer $\xi$, it will be stored in $D^{(\ell)}$ for the rest
of the stream, and any further copies of that edge will not be sent by
Algorithm 11 to the level $\ell$ instance of Algorithm 10. If $\\{x,y\\}$ was
successfully colored by layer $\xi$, the edge will be recorded until both of
the free color trackers $F_{x}^{(\ell,\xi)}$ and $F_{y}^{(\ell,\xi)}$ have
been refreshed. This only happens if the block numbers $b_{x,t}$ and $b_{y,t}$
of $\\{x,y\\}$ with respect to the substream received by the layer $\xi$
instance of Algorithm 9 have increased. Consequently, that substream will
satisfy Property Z – if Algorithm 11 receives a second copy of edge
$\\{x,y\\}$ at time $t^{\prime}$ while either $b_{x,t^{\prime}}=b_{x,t}$ or
$b_{y,t}=b_{y,t}$, because $\\{x,y\\}$ will be still be in $R$, Algorithm 11
will not send the second copy to the level $\ell$ instance of Algorithm 10.

We now check that the level $\ell$ instance of Algorithm 10 does not receive a
graph stream of degree more than $\Delta^{(\ell)}$. When a copy of an edge
$\\{u,v\\}$ arrives, the loop at Line 12 only continues from level $\ell$ to
to level $\ell+1$ if $M_{\\{u,v\\}}^{(\ell)}=2^{\ell}$ was true. Thus, for an
edge $e$ to be processed by the level $\ell$ instance of Algorithm 10, the
edge $e$ must have arrived at least $2^{0}+2^{1}\ldots+2^{\ell-1}=2^{\ell}-1$
times before in the stream, and $2^{\ell}$ times in total, since the last time
$e$ was dropped from $R$. Since the maximum degree of the graph is $\Delta$,
and an edge must be added $\geq 2^{\ell}$ times for each time that it is sent
to the level $\ell$ instance of Algorithm 10, the level $\ell$ instance will
receive at most $\Delta/2^{\ell}$ edges adjacent to any given vertex.

When $\ell=\log\Delta$ in the for loop, Line 15 will not be executed; because
for $M_{\\{x,y\\}}^{(\ell)}$ to equal $2^{\ell}=\Delta$, this must be the
$\Delta+1$st copy of edge $\\{x,y\\}$ to arrive. Thus Algorithm 11 will assign
a color to every edge in the stream.

The total space usage of Algorithm 11 is dominated by the sets $D^{(\ell)}$,
free color trackers $F^{(\ell,\xi)}_{v}$, and the pool $R$ (along with its
linked properties $\chi^{(\ell)}_{e},M^{(\ell)}_{e}$, for each
$\ell\in\\{0,\ldots,\log\Delta\\}$.) Over all levels $\ell$, layers $\xi$, and
vertices in $V$, there are $O((\log\Delta)^{2}n)$ color trackers, each of
which uses $O(s^{(\ell)}\log n+\log\Delta)=O(\sqrt{\Delta\log(n/\delta)}\log
n)$ bits of space to store colors and $O(\log n)$-bit references to edges.
Each $D^{(\ell)}$ is guaranteed to contain $O(n\log n)$ edges, at most, and
needs $O(n(\log n)^{2})$ bits of space. Finally, the $\ell$th level references
at most $|D^{(\ell)}|+O(ns^{(\ell)}\log\Delta)$ edges in $R$, so in total $R$
will have $O(n\log n+n\sqrt{\Delta\log(n/\delta)}\log\Delta)$ edges. Each each
needs $O(\log n)$ bits to identify, and there are $O((\log\Delta)^{2})$ bits
of associated information in the $(\chi^{(\ell)}_{e},M^{(\ell)}_{e})_{\ell}$.
Thus, in total, Algorithm 11 uses:

$\displaystyle O(n\sqrt{\Delta\log(n/\delta)}(\log\Delta)^{2}\log
n\log(n\Delta))$

bits of space.

If the advice $(\sigma_{v}^{(\ell)})_{v\in
V,\ell\in\\{0,\ldots,\log\Delta\\}}$ was chosen randomly using Lemma 6.2, then
$O(s\operatorname{poly}(\log\Delta,\log n))$ truly random bits per permutation
would be needed for a level of accuracy ($\leq 1/\operatorname{poly}(n)$ total
variation variation distance from uniformity) under which the proof of Lemma
4.5 works. At $\delta=1/2$, this is
$O(n\sqrt{\Delta}\operatorname{poly}(\log\Delta,\log n)$ bits. Given
exponential time, the advice can also be computed on demand, since checking
that Property U from the proof of Lemma 4.5 can be done in exponential time.

∎

##  5 Lower bounds for deterministic edge coloring

######  Lemma 5.1.

Let $B$ be a set of $n$ vertices; let $\Delta$ be an integer, and let
$C\in[\Delta,2\Delta-1]$ be another integer. Define $\beta:=C/\Delta$.
Consider the case where $(2-\beta)n\geq 32C$.

For each $v\in B$, say we have a nonempty set $S_{v}\subseteq[C]$ of possible
colors, where $\sum_{i\in B}|S_{i}|\leq\beta n$. If $G$ is a uniformly random
bipartite graph between a set $A$ of size
${\left\lfloor{n/\Delta}\right\rfloor}$, then the probability
$p(n,\Delta,\beta)$ that $G$ has a valid edge coloring where each edge $(a,b)$
is given a color from $S_{b}$ is:

$\displaystyle p(n,\Delta,\beta)\leq\exp(-\frac{1}{2^{13}}(2-\beta)^{3}n)$
(11)

###### Proof of Lemma 5.1.

The graph $G$ can be interpreted as a random partition of $B$ into sets
$P_{1},\ldots,P_{{\left\lfloor{n/\Delta}\right\rfloor}}$, plus a possible
$P_{\text{remainder}}$ set, where all sets $P_{i}$ except for the remainder
have size $\Delta$. Note that $P_{1}$ is a uniformly random subset of size
$\Delta$ in $B$, $P_{2}$ is a uniformly random subset of size $\Delta$ in
$B\setminus P_{1}$, and so on. For each
$i\in{\left\lfloor{n/\Delta}\right\rfloor}$, let $C_{i}$ be the event that
there is a $P_{i}$-saturating matching in the bipartite graph between $P_{i}$
and $[C]$, where each $v\in P$ is adjacent to all $c\in S_{v}$. Let
$\gamma=2-\beta$. Then we have:

$\displaystyle
p(n,\Delta,\beta)\leq\prod_{i=1}^{{\left\lceil{\frac{1}{2}\gamma
n/\Delta}\right\rceil}}\Pr[C_{i}|C_{1},\ldots,C_{i-1}]$ (12)

We will prove Eq. 11 by proving a upper bounds on
$\Pr[C_{i}|C_{1},\ldots,C_{i-1}]$, for all
$i\in[{\left\lceil{\frac{1}{2}\gamma n/\Delta}\right\rceil}]$, and then
applying Eq. 12.

By Markov’s inequality, the fraction of vertices in $B$ for which
$|S_{v}|-1\geq 1$ is $\leq\beta-1=1-\gamma$, so $\Pr_{v\sim
B}[|S_{v}|=1]\geq\gamma$. For each
$i\in[{\left\lfloor{n/\Delta}\right\rfloor}]$, let
$T_{i}=B\setminus\bigcup_{j<i}P_{j}$. Then for all
$i\leq{\left\lceil{\frac{1}{2}\gamma n/\Delta}\right\rceil}$:

$\displaystyle\frac{|\\{v\in T_{i}:|S_{v}|=1\\}|}{|T_{i}|}\geq\frac{|\\{v\in
B:|S_{v}|=1\\}|-\Delta(i-1)}{|B|-\Delta i}\geq\frac{\gamma
n-(i-1)\Delta}{n-\Delta(i-1)}\geq\frac{\gamma n-\frac{1}{2}\gamma
n}{n-\frac{1}{2}\gamma n}\geq\frac{1}{2}\gamma$

Consequently, conditioned on $P_{1},\ldots,P_{i-1}$, the set $P_{i}$ will be
drawn uniformly at random from a set $T_{i}$ of vertices for which at least a
$\gamma/2$ fraction have singleton color sets (have $|S_{v}|=1$).

For a given $i$, we remark that if $P_{i}$ contains two vertices $v,w$ for
which $|S_{v}|=|S_{w}|=1$ and $S_{v}=S_{w}$, then it is not possible to match
the vertices in $P_{i}$ to colors, as $v$ and $w$ would conflict. Let us bound
the probability that this occurs. Let $\hat{n}=|T_{i}|$; note that this is
$\geq n/2$. To make the distribution of singleton sets drawn from
$\\{S_{v}\\}_{v\in T_{i}}$ appear more uniform, we construct $C$ disjoint sets
$L_{1},\ldots,L_{C}$ in $T_{i}$, so that for each $L_{i}$, the associated
color sets are all a singleton $|\bigcup_{j\in L_{i}}S_{j}|=1$; and for which
$|L_{i}|\geq\gamma\hat{n}/4C$. (If each singleton color set were equally
likely, we could get $|L_{i}|\geq\gamma\hat{n}/2C$ – but it is possible that
$\\{1\\}$ is rare, while $\\{2\\}$ more common than average. One way to
construct the $L_{1},\ldots,L_{C}$ is by iteratively removing sets of
$\gamma\hat{n}/4C$ vertices from $T_{i}$ whose associated color sets are all
the same singleton set.)

For each $j\in T_{i}$, let $X_{j}$ be the indicator random variable for the
event that $j\in P_{i}$. For each $k\in[C]$, let $Y_{k}=\sum_{j\in
L_{k}}X_{j}$. Since the random variables $\\{X_{j}\\}_{j\in T_{i}}$ are
negatively associated, sums of disjoint sets of them, the
$\\{Y_{k}\\}_{k\in[C]}$, are also negatively associated. (See [JP83].) We
have:

$\displaystyle\Pr$ $\displaystyle[P_{i}\text{ has no two elements from same
$L_{k}$}]$ $\displaystyle\leq\Pr[\bigwedge_{k\in[C]}\\{Y_{k}\leq 1\\}]$
$\displaystyle\leq\prod_{k\in[C]}\Pr[Y_{k}\leq 1]\qquad\text{since negative
association $\implies$ negative orthant dependence}$

We calculate $\Pr[Y_{k}\leq 1]$ exactly, and then prove an upper bound on it.

$\displaystyle\Pr[Y_{k}\leq 1]$
$\displaystyle=\frac{\binom{\hat{n}-|L_{k}|}{\Delta}+|L_{k}|\binom{\hat{n}-|L_{k}|}{\Delta-1}}{\binom{\hat{n}}{\Delta}}$
$\displaystyle=\frac{\frac{\hat{n}-|L_{k}|-\Delta+1}{\Delta}\binom{\hat{n}-|L_{k}|}{\Delta-1}+|L_{k}|\binom{\hat{n}-|L_{k}|}{\Delta-1}}{\frac{\hat{n}}{\Delta}\binom{\hat{n}-1}{\Delta-1}}$
$\displaystyle=\frac{\frac{\hat{n}-|L_{k}|-\Delta+1}{\Delta}+|L_{k}|}{\hat{n}/\Delta}\cdot\frac{\binom{\hat{n}-|L_{k}|}{\Delta-1}}{\binom{\hat{n}-1}{\Delta-1}}$
$\displaystyle\leq\frac{\frac{\hat{n}-|L_{k}|-\Delta+1}{\Delta}+|L_{k}|}{\hat{n}/\Delta}\cdot\left(\frac{\hat{n}-|L_{k}|}{\hat{n}-1}\right)^{\Delta-1}\qquad\text{since
$\binom{a}{c}/\binom{b}{c}\leq(a/b)^{c}$ if $c\leq a\leq b$}$
$\displaystyle=\left(1+\frac{|L_{k}|-1}{\hat{n}}(\Delta-1)\right)\left(1-\frac{|L_{k}|-1}{\hat{n}-1}\right)^{\Delta-1}$
$\displaystyle\leq\exp\left(\ln\left(1+\frac{|L_{k}|-1}{\hat{n}}(\Delta-1)\right)-\frac{|L_{k}|-1}{\hat{n}-1}(\Delta-1)\right)\qquad\text{since
$1-x\leq\exp(x)$}$
$\displaystyle\leq\exp\left(\frac{|L_{k}|-1}{\hat{n}}(\Delta-1)-\frac{1}{4}\left(\frac{|L_{k}|-1}{\hat{n}}(\Delta-1)\right)^{2}-\frac{|L_{k}|-1}{\hat{n}-1}(\Delta-1)\right)\qquad\text{since
$\ln(1+x)\leq x-x^{2}/4$ for $x\leq 1$}$
$\displaystyle\leq\exp\left(-\frac{(|L_{k}|-1)(\Delta-1)}{\hat{n}(\hat{n}-1)}-\frac{1}{4}\left(\frac{|L_{k}|-1}{\hat{n}}(\Delta-1)\right)^{2}\right)$
$\displaystyle\leq\exp\left(-\frac{1}{4}\frac{\gamma^{2}}{2^{10}}\right)=\exp(-\gamma^{2}/2^{12})$

In the last inequality, we used the fact that
$(|L_{k}|-1)(\Delta-1)/\hat{n}\geq(\gamma\hat{n}/4C-1)(\Delta-1)/\hat{n}\geq\gamma/32C$.

Having bounded $\Pr[Y_{k}\leq 1]$, it follows that:

$\displaystyle p(n,\Delta,\beta)$
$\displaystyle\leq\prod_{i=1}^{{\left\lceil{\frac{1}{2}\gamma
n/\Delta}\right\rceil}}\Pr[C_{i}|C_{1},\ldots,C_{i-1}]\leq\left(\exp\left(-\gamma^{2}/2^{12}\right)^{C}\right)^{{\left\lceil{\frac{1}{2}\gamma
n/\Delta}\right\rceil}}$ $\displaystyle\leq\exp\left(-\gamma^{2}/2^{12}\cdot
C\cdot{\left\lceil{\frac{1}{2}\gamma
n/\Delta}\right\rceil}\right)\leq\exp(-\gamma^{3}n/2^{13})$

∎

We now formally restate Theorem 1.7 and prove it.

######  Theorem 5.2 (Formal version of Theorem 1.7).

For all $\beta\in(1,2)$, and integers $n,\Delta$ satisfying $\Delta\leq
n(2-\beta)/(32\beta)$, every deterministic online streaming algorithm for
edge-coloring that uses $\beta\Delta$ colors requires $\Omega((2-\beta)^{3}n)$
bits of space.

###### Proof.

Say we have an algorithm $\mathcal{A}$ to provide an online $(\beta\Delta)$
edge-coloring of an input stream, presented in one-sided vertex arrival order,
using $S$ bits of space. We assume that $\Delta|n$; if this is not the case,
we can reduce $n$ to the nearest multiple of $\Delta$, weakening our final
lower bound by at most a factor of $2$. With the algorithm, we can implement a
protocol for a $\Delta$-player one-way communication game in which each
message uses $\leq S$ bits. We will then prove a communication lower bound for
this game.

Specifically, let $P_{1},\ldots,P_{\Delta}$ be the players of the game. Let
$A_{1},\ldots,A_{\Delta}$ and $B$ be sets of vertices, where for each
$i\in[\Delta]$, $|A_{i}|=n/\Delta$, and $|B|=n$. For each $i\in[\Delta]$, the
player $P_{i}$ is given a regular bipartite graph $G_{i}$ from $A_{i}$ to $B$,
in which each vertex in $A_{i}$ has degree $\Delta$, and each vertex in
$B_{i}$ has degree $1$. Player $P_{1}$ starts the communication game by
outputing an edge coloring $\chi_{1}$ of $G_{1}$, using colors in
$[\beta\Delta]$; and then it sends a message $m_{1}$ to Player $P_{2}$. For
each $i\in\\{2,\ldots,\Delta\\}$, the player $P_{i}$ will receive a message
$m_{i-1}$ from its predecessor, output an edge coloring $\chi_{i}$ of $G_{1}$
which is compatible with the edge colorings $\chi_{1},\ldots,\chi_{i-1}$ made
by the earlier players, and then (if $i<\Delta$) send a message $m_{i}$ to the
next player.

The conversion from an algorithm $\mathcal{A}$ to a protocol for this game is
straightforward; $P_{1}$ initializes an instance $A$ of $\mathcal{A}$, uses it
to process $G_{1}$ in arbitrary order, and reports the colors the algorithm
output; then it encodes the state of the instance $A$ as an $S$-bit message
$m_{1}$. $P_{2}$ receives this message, and uses it to continue running the
instance $A$, this time having it process $G_{2}$; $P_{2}$ outputs the
results, and sends the new state of $A$ to $P_{3}$ as $m_{2}$. The players
continue in this way until $P_{\Delta}$ produces output.

For each $i\in\\{1,\ldots,\Delta-1\\}$, and message $m_{i}$, we define
$\mathcal{S}_{m_{i}}=(S_{m_{i},v})_{v\in B}$. Here $S_{m_{i},v}$ is the set of
all colors which players $P_{1},\ldots,P_{i}$ could have assigned to edges
incident on $v$ for executions of the protocol in which $P_{i}$ sent message
$m_{i}$. If player $P_{i+1}$ receives message $m_{i}$, the coloring
$\chi_{i+1}$ that it outputs must be disjoint from $\mathcal{S}_{m_{i}}$;
specifically, if we view $\chi_{i+1}$ as a vector in $[\beta\Delta]^{B}$ whose
$v$th entry gives the color assigned to the edge incident to vertex $v$, then
$\forall v\in B:\chi_{i+1,v}\notin S_{m_{i},v}$. If this were not the case,
and there was a vertex $x$ for which $\chi_{i+1,x}\in S_{m_{i},x}$, then there
would be an execution of the protocol on which some player $P_{j}$ output
color $\chi_{i+1,x}$ for an edge incident on $x$, later $P_{i}$ sent message
$m_{i}$, and now $P_{i+1}$’s assignment of $\chi_{i+1,x}$ to the edge incident
on $x$ violates the edge coloring constraint.

Let $p(n,\Delta,\beta)$ be the probability from Lemma 5.1. We claim that there
exists an input for which some player must send a message with more than $\log
1/p(n,\Delta,\beta)$ bits. If this is not the case, then we shall construct an
input on which the protocol must give an incorrect output, a contradiction.

Let $M_{1}$ be the set of all messages that player $P_{1}$ can send. Let $H$
be chosen uniformly at random from the set of $(\Delta,1)$-regular bipartite
graphs from $A_{1}$ to $B$, and let $m_{1}(H)$ be the message $P_{1}$ would
send if $G_{1}=H$. Then, if for all $m\in M_{1}$, we were to have $\sum_{v\in
B}|S_{m_{i},v}|\leq\beta n$,

$\displaystyle 1=\sum_{m\in M_{1}}\Pr[m=m_{1}(H)]\leq|M_{1}|p(n,\Delta,\beta)$

But since we have assumed messages in $M_{1}$ need $<\log 1/p(n,\Delta,\beta)$
bits, and hence $|M_{1}|<1/p(n,\Delta,\beta)$, the above equation would imply