tcb@breakable lesson problem [rutgers,waterloo]Sepehr
<EMAIL_ADDRESS>[charles]Pankaj
<EMAIL_ADDRESS>[rutgers]Parth<EMAIL_ADDRESS>[rutgers]Department of Computer Science, Rutgers University, USA
[waterloo]Cheriton School of Computer Science, University of Waterloo, Canada
[charles]Department of Applied Mathematics, Faculty of Mathematics and
Physics, Charles University, Prague, Čzech Republic 2023 9 Sep 11, 2022 Apr
13, 2023 August 3, 2023 Semi-streaming algorithms, Graph coloring, Brooks’
theorem S. Assadi, P. Kumar, P. Mittal An extended abstract of this paper
appeared in ACM Symposium on Theory of Computing (STOC’22) [8]. Sepehr Assadi
was supported in part by an NSF CAREER Grant CCF-2047061, a Sloan Research
Fellowship, a Google Research gift, and a Fulcrum award from Rutgers Research
Council. Parth Mittal was supported in part by the NSF CAREER grant
CCF-2047061. Part of this research was carried out while Pankaj Kumar and
Parth Mittal participated in the 2020 DIMACS REU program, supported by CoSP, a
project funded by European Union’s Horizon 2020 research and innovation
program, grant agreement No. 823748. Brooks’ Theorem in Graph Streams

# Brooks’ Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for
$\Delta$-Coloring

###### Abstract

Every graph with maximum degree $\Delta$ can be colored with $(\Delta+1)$
colors using a simple greedy algorithm. Remarkably, recent work has shown that
one can find such a coloring even in the semi-streaming model: there exists a
randomized algorithm that with high probability finds a $(\Delta+1)$-coloring
of the input graph in only $O(n\cdot\mbox{\rm poly}\\!\log{n})$ _space_
assuming a single pass over the edges of the graph in any arbitrary order.
But, in reality, one almost never needs $(\Delta+1)$ colors to properly color
a graph. Indeed, the celebrated Brooks’ theorem states that every (connected)
graph beside cliques and odd cycles can be colored with $\Delta$ colors. Can
we find a $\Delta$-coloring in the semi-streaming model as well?

We settle this key question in the affirmative by designing a randomized semi-
streaming algorithm that given any graph, with high probability, either
correctly declares that the graph is not $\Delta$-colorable or outputs a
$\Delta$-coloring of the graph.

The proof of this result starts with a detour. We first (provably) identify
the extent to which the previous approaches for streaming coloring fail for
$\Delta$-coloring: for instance, all these prior approaches can handle streams
with repeated edges and they can run in $o(n^{2})$ time, whereas prove that
neither of these tasks is possible for $\Delta$-coloring. These impossibility
results however pinpoint exactly what is missing from prior approaches when it
comes to $\Delta$-coloring.

We build on these insights to design a semi-streaming algorithm that uses
$(i)$ a novel sparse-recovery approach based on sparse-dense decompositions to
(partially) recover the “problematic” subgraphs of the input—the ones that
form the basis of our impossibility results—and $(ii)$ a new coloring approach
for these subgraphs that allows for recoloring of other vertices in a
controlled way without relying on local explorations or finding “augmenting
paths” that are generally impossible for semi-streaming algorithms. We believe
both these techniques can be of independent interest.

###  1 Introduction

Graph coloring problems are ubiquitous in graph theory and computer science.
Given a graph $G=(V,E)$, a proper $c$-coloring of $G$ is any assignment of
colors from the palette $\left\\{1,\ldots,c\right\\}$ to the vertices so that
no edge receives the same color on both its endpoints. Recent years have
witnessed a flurry of results for graph coloring in the graph streaming model
[58, 15, 7, 13, 14, 4, 16, 6, 22, 39]. In this model, the edges of the input
graph arrive one by one in an arbitrarily ordered stream and the algorithm
needs to process these edges sequentially using a limited space, much smaller
than the input size. Of particular interest are _semi-streaming_ algorithms,
introduced by [32], that use only $\widetilde{O}(n):=O(n\cdot\mbox{\rm
poly}\\!\log{n})$ space111Throughout, we use
$\widetilde{O}(f):=O(f\cdot\mbox{\rm poly}\log{f})$ to suppress $\mbox{\rm
poly}\\!\log{(f)}$ factors. on $n$-vertex graphs which is proportional to the
output size. We focus on this model in this paper.

One of the simplest forms of graph coloring problems is $(\Delta+1)$-coloring
of graphs with maximum degree $\Delta$. Not only does every graph admits a
$(\Delta+1)$-coloring, one can in fact find one quite easily via a greedy
algorithm: iterate over the vertices and color each one from any of
$(\Delta+1)$ colors that has not appeared in any of its at most $\Delta$
colored neighbors. Yet, despite its utter simplicity, this algorithm does not
easily lend itself to a semi-streaming algorithm as the arbitrary arrival of
edges prohibits us from coloring vertices one at a time.

Nonetheless, a breakthrough of [7] showed that $(\Delta+1)$ coloring is still
possible in the semi-streaming model, albeit via a randomized algorithm that
employs a “non-greedy” approach. In particular, [7] proved the following
_palette sparsification theorem_ : if we sample $O(\log{n})$ colors from
$\left\\{1,\ldots,\Delta+1\right\\}$ for each vertex independently, then with
high probability, the entire graph can be colored by coloring each vertex from
its own sampled colors. This result immediately leads to a semi-streaming
algorithm for $(\Delta+1)$-coloring: sample these colors for each vertex and
store any edge in the stream that can potentially become monochromatic under
any coloring of vertices from their sampled list. A simple probabilistic
analysis bounds the number of stored edges by $O(n\log^{2}{n})$ with high
probability, and the palette sparsification theorem guarantees that one can
find a $(\Delta+1)$-coloring of the graph at the end of the stream.

Going back to existential results, it is easy to see that there are graphs
that do need $\Delta+1$ colors for proper coloring, for instance
$(\Delta+1)$-cliques or odd cycles (where $\Delta=2$). The celebrated Brooks’
theorem [19] states that these two are the only examples: any (connected)
graph besides cliques and odd cycles can be colored with $\Delta$ colors (see
also [49] and [47] for other classical proofs of this result by Melnikov and
Vizing, and by Lovász, respectively). Unlike existence of
$(\Delta+1)$-colorings which is rather a triviality, Brooks’ theorem turned
out to be a fundamental result in graph coloring [50, 63] with numerous proofs
discovered for it over the years; see, e.g., [63, 25, 56, 57] and references
therein. The algorithmic aspects of Brooks’ theorem have also been studied
extensively in classical algorithms [47, 62, 10], PRAM algorithms [44, 54, 43,
35], or LOCAL algorithms [53, 18, 34].

Given the key role Brooks’ theorem plays in graph coloring literature on one
hand, and the recent advances on streaming coloring algorithms on the other
hand, it is thus quite natural to ask:

> _Does there exist a “semi-streaming Brooks’ theorem”, namely, a semi-
> streaming algorithm that colors any given graph, besides cliques and odd
> cycles, with $\Delta$ colors?_

This is precisely the question addressed in this paper. We emphasize that our
interest in this question is not in “shaving off” a single color from
$(\Delta+1)$-coloring to $\Delta$-coloring in practice, but rather as a source
of insights and ideas (as is the case, say, in graph theory or classical
algorithms where $(\Delta+1)$-coloring is just a triviality). In fact,
$\Delta$-coloring appears to be just beyond the reach of our current
techniques. For instance, previous streaming coloring algorithms in [7, 14, 4]
can all be obtained via palette sparsification (see [4] for details). Yet, it
was already observed in [7] that palette sparsification cannot handle
$\Delta$-coloring (we elaborate on this later). More generally, while
$(\Delta+1)$-coloring has a strong “greedy nature”, all
existential/algorithmic proofs of $\Delta$-coloring are based on “exploring”
the graph for certain structures, say cut vertices or certain spanning trees
[47], Kempe Chains [49], Rubin’s Block Lemma [30, 5], or “augmenting paths”
[54] to name a few (we refer the interested reader to [63] for an excellent
overview of various proofs of Brooks’ theorem). These (local) exploration
tasks however tend to be generally impossible in the semi-streaming
model.222For instance, while computing all neighbors of a given vertex is
trivial via a semi-streaming algorithm (by storing edges of the vertex), it is
even impossible to discover the $2$-hop neighborhood of a given vertex [31].

####  1.1 Our Contributions

We start with studying the _limitations_ of the current approaches in
streaming graph coloring for solving $\Delta$-coloring. To do so, we focus on
two common characteristics of all prior algorithms in [7, 14, 4]: they all
also naturally lead to $(i)$ _sublinear-time_ algorithms for the corresponding
coloring problems that run in $(n^{3/2+o(1)})$ time, and $(ii)$ semi-streaming
algorithms that can handle _repeated-edge_ streams wherein the same edge may
appear more than once. We prove that obtaining either type of algorithms is
provably _impossible_ for $\Delta$-coloring:

>   * •
>
> Sublinear-time algorithms (Section A.1): Any algorithm that, given access to
> adjacency lists and adjacency matrix of a graph with known maximum degree
> $\Delta$, can output a $\Delta$-coloring with large constant probability
> requires $\Omega(n\Delta)$ queries to input and time.
>
>   * •
>
> Repeated-edge streams (Section A.2): Any algorithm that, given the edges of
> a graph with known maximum degree $\Delta$ in a _repeated-edge_ stream, can
> output a $\Delta$-coloring with large constant probability requires
> $\Omega(n\Delta)$ space.
>
>

These impossibility results already demonstrate how different
$\Delta$-coloring is compared to prior graph coloring problems studied in the
semi-streaming model. But, as we shall elaborate later, these results play a
much more important role for us: they pinpoint what is missing from prior
approaches when it comes to the $\Delta$-coloring problem and act as an
excellent guide for addressing our motivating question. This brings us to the
main contribution of our work.

######  Theorem 1.1 (Semi-Streaming Brooks’ Theorem).

There exists a randomized semi-streaming algorithm that given any connected
graph $G=(V,E)$ with maximum degree $\Delta$, which is not a clique nor an
odd-cycle, with high probability, outputs a $\Delta$-coloring of $G$.

Consequently, despite the fact that prior approaches inherently fail for
$\Delta$-coloring in fundamental ways and that $\Delta$-coloring is provably
intractable in closely related models, we can still obtain a semi-streaming
Brooks’ theorem and settle our motivating question in the affirmative. It is
also worth mentioning that randomness in Theorem 1.1 is crucial: a very recent
result of [6] shows that deterministic semi-streaming algorithms cannot even
find an $\exp\left(\Delta^{o(1)}\right)$-coloring. Our Theorem 1.1 thus fully
settles the complexity of the $\Delta$-coloring problem in the semi-streaming
model.

Theorem 1.1 can be stated more generally as an algorithm that either decides
whether the input graph is $\Delta$-colorable or not, and if yes, outputs the
coloring. This is because checking whether a graph is $\Delta$-colorable can
be done by simply storing a spanning forest of the input (see, e.g., [32]) and
maintaining the degrees of vertices; this allows us to check whether any of
the connected components in the graph is a $(\Delta+1)$-clique or an odd-
cycle. If not, applying Theorem 1.1 to each connected component of the graph
(in parallel in a single pass) gives us the desired $\Delta$-coloring (the
algorithm does not even require the prior knowledge of $\Delta$ using a
standard trick observed in [7]; see Remark 4.28). However, we find the
statement of Theorem 1.1 to best capture the most interesting part of the
result and thus opted to present it in this form.

###### Our Techniques.

We shall go over our techniques in detail in the streamlined overview of our
approach in Section 2. For now, we only mention the three main technical
ingredients of our work:

  1. $i).$

A thorough understanding of the powers and limitations of the palette
sparsification approach of [7] for $\Delta$-coloring via a rough
characterization of which (sub)graphs it still applies to;

  2. $ii).$

An algorithm for _implicitly_ identifying and storing “problematic” subgraphs
of the input graph—the ones that cannot be handled by palette sparsification
approach of previous step—via a novel sparse recovery approach that relies on
_algorithmic_ use of sparse-dense decompositions (see Section 3.1) in place of
their _analytic_ use in prior streaming algorithms [7, 4];

  3. $iii).$

A new coloring procedure that combines simple graph theoretic ideas with
probabilistic analysis of palette sparsification using a notion of _helper
structures_ ; these are simple subgraphs of the input that can be recovered
via our semi-streaming algorithms from the previous part and does not rely on
local exploration steps of prior proofs of Brooks’ theorem mentioned earlier.

###### Other Sublinear Algorithms Models.

Prior semi-streaming algorithms for graph coloring also naturally lead to a
series of algorithmic results for the respective problems in other models. Our
first impossibility result already rules out this possibility for
$\Delta$-coloring when it comes to _sublinear-time_ algorithms. Nevertheless,
our approach in Theorem 1.1 is still quite flexible and thus allows for
extension of this algorithm to many other models. In particular, the algorithm
is implemented via a _linear sketch_ (see [48]), which immediately implies the
following two results as well:

  * •

Dynamic streams: There exists a (single-pass) randomized semi-streaming
algorithm for $\Delta$-coloring on the streams that contain insertion and
deletion of edges.

  * •

Massively parallel computation (MPC): There exist a one round randomized MPC
algorithm for $\Delta$-coloring on machines of memory $\widetilde{O}(n)$ with
only $\widetilde{O}(n)$ extra global memory.

As this is not the focus of the paper, we omit the definition and details of
the models and instead refer the interested to [3, 48] and [45, 12] for each
model, respectively.

####  1.2 Related Work

Similar to the classical setting, it is known that approximating the minimum
number of colors for proper coloring, namely, the _chromatic number_ , is
intractable in the semi-streaming model [40, 2, 24]. Thus, recent work has
focused instead on “combinatorially optimal” bounds—termed by [37]—for
streaming coloring problems. On this front, we already discussed the
$(\Delta+1)$-coloring result of [7]. Independently and concurrently, [15]
obtained a semi-streaming algorithm for $O(\Delta)$ colorings. These results
were followed by semi-streaming algorithms for other coloring problems such as
degeneracy coloring [14], coloring locally sparse graphs and
$(\deg+1)$-coloring [4], $(\deg+1)$-list coloring [39], adversarially robust
coloring [22], edge-coloring (in W-streams) [13], deterministic lower bounds
and (multi-pass) algorithms [6], and coloring verification problems [16].
Moreover, [4] studied various aspects of palette sparsification technique of
[7] and showed that other semi-streaming coloring algorithms such as [15, 14]
can also be obtained via this technique.

Many of these work on streaming algorithms for graph coloring also extend to
other models such as sublinear-time and massively parallel computation (MPC)
algorithms. For instance, for $(\Delta+1)$-coloring, there are randomized
sublinear-time algorithms in $\widetilde{O}(n^{3/2})$ time [7] or
deterministic MPC algorithms with $O(1)$ rounds and $O(n)$ per-machine memory
[27] (see also [26]). Moreover, subsequent to the conference publication of
this paper in [8], some of the ideas in our work was also used in [33] in
designing distributed LOCAL algorithms for $\Delta$-coloring.

Numerous beautiful algorithmic results are known for $\Delta$-coloring problem
in various other models such as classical algorithms [47, 62, 10], PRAM
algorithms [44, 54, 43, 35], or LOCAL algorithms [53, 18, 34, 11]. For
instance, a remarkable “distributed Brooks’ theorem” of [54] proves that any
partial $\Delta$-coloring of all but one vertex of the graph, can be turned
into a proper $\Delta$-coloring of the entire graph by recoloring a single
“augmenting path” of $O(\log_{\Delta}{\\!n})$ length. Finally, it is worth
mentioning that Brooks’ theorem is part of a more general phenomenon in graph
theory: as the maximum clique size in $G$ moves further away from $\Delta+1$,
so does its chromatic number. For instance, [60] proves that for sufficiently
large $\Delta$, if a graph does not contain a $\Delta$-clique, then it is in
fact always $(\Delta-1)$-colorable; see, e.g., [17, 59, 60, 46, 50, 52] and
references therein for various other examples.

###  2 Technical Overview

We now give a streamlined overview of our approach. While Theorem 1.1 is by
far the main contribution of our work, we find it illuminating to first talk
about our impossibility results for $\Delta$-coloring as they, despite their
simplicity, played a crucial role for us in obtaining Theorem 1.1 and we
believe they can shed more light into different components of our final
algorithm.

####  2.1 A Detour: Impossibility Results, Barriers, and Lessons Along the Way

Palette sparsification. Let us start by reviewing the palette sparsification
theorem of [7]: if we sample $O(\log{n})$ colors from
$\left\\{1,\ldots,\Delta+1\right\\}$ for each vertex independently, then with
high probability, we can still color the graph by coloring each vertex from
its sampled palette. The proof of this result in [7] uses a variant of
_sparse-dense decomposition_ [59] that partitions the graph into _“(locally)
sparse”_ vertices and a collection of _“almost-clique”_ subgraphs that can be
turned into $(\Delta+1)$-cliques by changing $o(1)$ fraction of their vertices
and edges (Figure 1(a)). The sparse vertices are then colored _one at a time_
from their sampled lists using a standard greedy coloring argument originally
introduced in [51]. The main part of the proof is to handle almost-cliques by
going over them one by one and coloring each one _entirely_ , using the
sampled lists of _all_ its vertices at the same time, even assuming the
outside vertices are colored _adversarially_.

(a) Sparse-dense decomposition

(b) palette sparsification of $\Delta$-coloring

(c) query lower bound of $\Delta$-coloring

Figure 1:  A graph with maximum degree $\Delta=4$ and its sparse-dense
decomposition in (a) (each box denotes an almost-clique and remaining vertices
are sparse). Part (b) is an illustration of why palette sparsification fails
for $\Delta$-coloring: the only way to $\Delta$-color this graph is to color
the marked vertices the same, which cannot be done with these sampled lists.
Part (c) shows a similar construction can be used to prove a query lower bound
for $\Delta$-coloring. (The actual instance is obtained from
$\Theta(n/\Delta)$ copies of such pairs.)

As expected, the hard part in extending palette sparsification theorem of [7]
to $\Delta$-coloring involves the argument for almost-cliques. Indeed, this is
not just a matter of analysis; as already observed by [7], this theorem fails
for $\Delta$-coloring (Figure 1(b)): consider a $(\Delta+1)$-clique minus a
single edge $(u,v)$; the only way we can find a $\Delta$-coloring of this
graph is if we color both $u$ and $v$ the same, which requires their sampled
lists to intersect; by the birthday paradox this only happens when size of
each list is $\Omega(\sqrt{\Delta})$ which in turn implies that the algorithm
has to store $\Omega(n\Delta)$ edges from the stream—this is effectively the
same as storing the input itself!

###### Sublinear time (query) algorithms.

Consider a graph $G$ which is a collection of $\Theta(n/\Delta)$ _pairs_ of
$(\Delta+1)$-cliques. For each pair, randomly pick two vertices
$(u_{1},v_{1})$ and $(u_{2},v_{2})$ from its first and second clique,
respectively. Remove the edges $(u_{1},v_{1})$ and $(u_{2},v_{2})$ and instead
include the edges $(u_{1},v_{2})$ and $(u_{2},v_{1})$ in the graph. See Figure
1(c) for an illustration. It is easy to see that the only way to
$\Delta$-color this graph is to find the “switched” edges in each copy and
color their endpoints the same inside each (now) almost-clique. Yet, it is an
easy exercise to use the linear lower bound on the query complexity of or
function [20] to prove that this requires making $\Omega(\Delta^{2})$ queries
to the adjacency lists or matrix of the graph for each pair, and thus
$\Omega(n\Delta)$ queries overall. This lower bound now leaves us with the
following lesson.

Any semi-streaming algorithm for $\Delta$-coloring should explicitly _look at_
all but a tiny fraction of edges of the graph presented in the stream.

Section 2.1 may sound trivial at first. After all, the semi-streaming model
allows all algorithms to look at all edges of the graph. Yet, note that
numerous semi-streaming algorithms, say, sampling algorithms, including all
prior streaming coloring algorithms in [7, 14, 4, 39], do not use this
power—Section 2.1 implies that these algorithms cannot solve
$\Delta$-coloring.

###### Semi-streaming algorithms on repeated-edge streams.

What if we take Section 2.1 to the extreme and give the algorithm each edge
(potentially) multiple times in the stream—this should surely helps us even
more, no? It turns out however that this is not really the case.

$+$$=$

An illustration of the hard instances for the repeated-edge stream lower
bound—the actual instance is obtained from $\Theta(n/\Delta)$ copies of these
graphs. The only possible $\Delta$-coloring is to color both endpoints of
marked vertices the same.

Suppose that we have a graph $G$ on a collection of $\Theta(n/\Delta)$
disjoint sets of vertices of size $\Delta+1$ each. For each set of $\Delta+1$
vertices $U$, consider a stream of edges that in the first part, provides a
subset $E_{1}$ of edges over $U$ and in the second part, provides another
subset $E_{2}$—the repeated-edge stream allows these subsets to be overlapping
and we shall choose them so that $E_{1}\cup E_{2}$ leaves precisely one pair
of vertices $(u,v)$ among all pairs in $U$ without an edge. As before, the
only way to $\Delta$-color this graph is to color vertices $u$, $v$ in each of
the $\Theta(n/\Delta)$ pieces the same. But, given that the edges between
$E_{1}$ and $E_{2}$ may overlap, one can prove that finding all these pairs
requires $\Omega(n\Delta)$ space. This is by a reduction from communication
complexity lower bounds of the _Tribes_ function [42] (a slightly less well-
known cousin of the famous set disjointness problem). This brings us to the
next lesson.

Any semi-streaming algorithm for $\Delta$-coloring should crucially use the
fact that each edge of the graph arrives _exactly once_ in the stream.

Again, while the semi-streaming model only allows for presenting each edge
once in the stream, many algorithms are entirely oblivious to this feature.
This includes all previous semi-streaming coloring algorithms in [7, 15, 14,
4, 39], as well as various other ones for spanning trees [32], sparsifiers
[48], spanners [32, 31] and maximal matchings [32]. Section 2.1 says that any
potential $\Delta$-coloring algorithm cannot be of this type.

###### A natural algorithm or a barrier result?

Finally, let us conclude this part by considering a natural semi-streaming
algorithm for $\Delta$-coloring: Sample $O(n\log{n}/\Delta)$ vertices $S$
uniformly at random, and partition the input graph into two subgraphs $G_{S}$
consisting of all edges incident on $S$, and $G_{-S}$ consisting of all
remaining edges. We can easily detect, for each arriving edge in the stream,
which subgraph it belongs to. Moreover, it is easy to see that $G_{S}$
contains $O(n\log{n})$ edges and $G_{-S}$, with high probability, has maximum
degree at most $\Delta-1$. We can thus store $G_{S}$ explicitly via a semi-
streaming algorithm and run the algorithm of [7] on $G_{-S}$ to color it with
$(\Delta(G_{-S})+1)=\Delta$ colors. So, we have a $\Delta$-coloring of
$G_{-S}$ and all edges of $G_{S}$.

Surely, now that we know _all_ of $G_{S}$, we should be able to extend the
$\Delta$-coloring of $G_{-S}$ to $G_{S}$, no? The answer however turns out to
be _no_ : unlike the case of $(\Delta+1)$-coloring, not every partial coloring
of a graph can be extended directly to a proper $\Delta$-coloring of the
entire graph. But perhaps this is only an abstract worry and we should just
find the right way of analyzing this algorithm? The answer is yet again _no_ :
the algorithm we just proposed in fact neglects both Section 2.1 and Section
2.1 and thus is doomed to fail completely.333An added bonus of those
impossibility results is to allow for quickly checking viability of potential
algorithms. But this also leaves us with the following lesson.

Any semi-streaming algorithm for $\Delta$-coloring that colors the graph by
extending a partial coloring, subgraph by subgraph, should either provide a
_stronger guarantee_ than solely an arbitrary $\Delta$-coloring for each
subgraph, or allow for _recoloring_ of an already colored subgraph.

While perhaps less concrete than our two previous lessons, Section 2.1 has a
profound impact in the design of our semi-streaming algorithm that also colors
the graph one subgraph at a time; in particular, our algorithm is going to
adhere to _both_ restrictions imposed by Section 2.1 simultaneously.

####  2.2 The High-Level Overview of Our Algorithm

After this long detour, we are now ready to go over our algorithm in Theorem
1.1. As stated earlier, the three main ingredients of our algorithm are: $(i)$
a variant of palette sparsification for $\Delta$-coloring that can color all
but some problematic almost-cliques in the input (such as Figure 1(b)), $(ii)$
a sparse recovery approach for (partially) recovering these problematic
subgraphs, and $(iii)$ a new coloring procedure that allows for extending the
partial coloring of part $(i)$ to the remaining subgraphs partially recovered
in part $(ii)$ to obtain a proper $\Delta$-coloring of the entire graph. We
will go over each part separately in the following.

##### Part One: Powers and Limitations of Palette Sparsification for
$\Delta$-Coloring

While we already discussed in Section 2.1 that palette sparsification fails
for $\Delta$-coloring, we are still going to employ its ideas crucially in our
work. The goal of this step is to identify to what extent this approach fails
for $\Delta$-coloring. We develop a classification of almost-cliques (Section
4.1) based on the following three criteria:

  * •

Size—number of vertices: _small_ for $<\Delta+1$, _critical_ for $\Delta+1$,
and _large_ for $>\Delta+1$ vertices.

  * •

Inner density—number of non-edges inside the almost-clique: _holey_ for
$\Omega(\Delta)$ non-edges (or “holes” in the almost-clique), and _unholey_
otherwise.

  * •

Outer connections—a measure of how “tightly” the almost-clique is connected to
outside; we postpone the technical details of this part to the actual
definition in Section 4.1.

Among these, size and inner density are perhaps usual suspects. For instance,
we already saw in Section 2.1 that palette sparsification entirely fails for
almost-cliques of size $\Delta+1$ with exactly one non-edge—in our
classification, these correspond to critical unholey almost-cliques. The third
criterion is more technical and is motivated by Section 2.1; as we are still
going to color the graph one almost-clique at a time, we would like to be able
to reason about the partial coloring of outside vertices and possibility of
its extension to the almost-clique. This is particularly relevant for small
almost-cliques which can be actually a true clique inside and hence would
definitely be in trouble if the same exact set of colors is “blocked” for all
their vertices from outside. See Figure 2.

(a) “random” outside-coloring

(b) “adversarial” outside-coloring

(c) “adversarial” outside-coloring

Figure 2: An illustration of three possible types of outer connections on a
graph with maximum degree $\Delta=6$. The almost-clique in part (a) has a
“right” type of outside connection and is going to receive a more “random”
coloring on its neighbors, compared to the almost-clique in part (b) with
“few” outside neighbors and part (c) with “too many” ones. In particular, the
latter almost-cliques now cannot be $\Delta$-colored without changing the
color of outside vertices as the same colors are blocked for all vertices of
the inner (actual) cliques.

We then consider palette sparsification (on steroids!) wherein each vertex
samples $\mbox{\rm poly}\\!\log{(n)}$ colors from
$\left\\{1,\ldots,\Delta\right\\}$ and _characterize_ which families of
almost-cliques in our classification can still be colored using only the
sampled colors. We show that all holey almost-cliques (regardless of their
size or outer connections) can be still colored from their sampled colors
using a similar argument as in [7]. More interestingly, we show that even
unholey small almost-cliques that have the “right” type of outside connections
can be colored at this step. Our analysis in this part deviates significantly
from [7] and in particular crucially establishes certain _randomness_
properties on the coloring of vertices _outside_ of an almost-clique when
trying to color the almost-clique itself (recall Section 2.1). Thus, what
remains are unholey critical almost-cliques (regardless of their outer
connections) and unholey small almost-cliques with “problematic” outside
connections. We delegate coloring of these almost-cliques to the next steps of
the algorithm.

Let us now briefly discuss the effect of outer connections in coloring a small
almost-clique. As stated earlier, the main problem with small almost-cliques
occurs when exactly the same set of colors is used to color all outside
vertices, thus blocking these colors entirely for the almost-clique. While
this event is basically unavoidable for almost-cliques with only a couple of
outside neighbors (Figure 2(b)), it becomes less and less likely as the number
of outside neighbors increases (Figure 2(a)). After all, for a color to be
used on all these vertices, it should be sampled by every single one of them
in the first place. We will however run into problem again in cases when we
have “too many” outside neighbors for every single vertex of the almost-clique
(Figure 2(c)). The almost-cliques of Figure 2(c) are particularly problematic
as we have no knowledge of the neighborhood of their outside vertices (for
Figure 2(b), we at least know that each of them have many neighbors in the
almost-clique, which is used crucially by our latter algorithms). Thus, we
should basically avoid ending up in a situation that we have to color such
almost-cliques after having colored their outside neighbors.

Fortunately, the almost-cliques of Figure 2(c) can only happen for small
enough almost-cliques; this in turn makes the neighborhood of these almost-
cliques sufficiently sparse. Thus, we can instead handle them similar to
sparse vertices by _increasing_ the size of sampled palettes for vertices.
There is however a subtle issue with this approach. Increasing the size of
sampled palettes means that even a fewer number of outside vertices can make a
problem for us, hence requiring us to send even more almost-cliques to sparse
vertices to handle, leading to a chicken-and-egg problem. A key idea in this
part is a way to break this dependency cycle by careful sequencing the order
of processing of vertices in a way that ensures sufficient “randomness” exist
in the coloring of neighborhood of all small almost-cliques, except for the
ones with very few outside neighbors (the type in Figure 2(b)). We postpone
the discussion of this “dependency-breaking” step to Section 5 and Remark 5.6.

All in all, this step effectively establishes that palette sparsification
achieves a “weak” streaming Brooks’ theorem by $\Delta$-coloring graphs that
do not contain certain _forbidden_ subgraphs such as $(\Delta+1)$-cliques
minus few edges or $\Delta$-cliques that have few neighbors outside (for
Brooks’ theorem itself, the only forbidden subgraph is a $(\Delta+1)$-clique).

##### Part Two: Sparse Recovery for Remaining Almost-Cliques, and Helper
Structures

Our next step is a way of _finding edges of_ the almost-cliques left uncolored
by the previous step so that we can color them using a different approach. Let
us bring up an obvious point here: these left out almost-cliques are precisely
the same family of instances that were at the core of our impossibility
results in Section 2.1 (and their natural relaxations). Consequently, to
handle them, our algorithm needs to take into account the recipe put forward
by Section 2.1 and Section 2.1: it should look at _all_ edges of the stream
_exactly once_. This rather uniquely points us toward a canonical technique in
the streaming model: sparse recovery (via linear sketching).

123$\vec{N}(3):=[{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1},0,0,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1},0,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1}]$45$K$67
(a) neighbors-vector of $v=3$

123${\chi(K)}:=[0,0,1,1,1,1,1]$456$K$7 (b) characteristic-vector of $K$

123$\vec{N}(3)-{\chi(K)}:=[{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1},0,0,0,0,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}-1},0]$456$K$7
(c) recovery-vector for neighbors of 3

Figure 3:  An illustration of sparse-recovery on the neighborhood of each
vertex, plus an algorithm that finds the identity of vertices in each almost-
clique, allows for recovering all edges “highly-dense” almost-cliques. Our
actual algorithm is considerably more involved as it needs to _partially_
recover “not-too-dense” almost-cliques also.

Consider an almost-clique which is a $(\Delta+1)$-clique minus an edge (Figure
1(b)). On the surface, recovering all edges of this almost-clique is
problematic as these subgraphs are actually quite _dense_ ; for instance, if
the graph consists of only copies of such almost-cliques, we will need
$\Omega(n\Delta)$ space to store all of them. But what saves us at this stage
is the fact that these subgraphs are actually too dense! Informally speaking,
this reduces their “entropy” dramatically conditioned on our knowledge of the
sparse-dense decomposition. Thus, we can recover them _implicitly_ using a
novel sparse recovery approach that uses sparse-dense decompositions
algorithmically and not only analytically.444For the main results in [7] one
only needs to know the _existence_ of the decomposition and does not need to
compute it. That being said, [7] also gave algorithms for finding the
decomposition from the stream (which is needed to run their algorithms in
polynomial time)—we use an extension of their algorithm by [9] in this paper.

Although in the examples we discussed, we can hope to recover the entire
almost-clique in question implicitly, this will not be the case for all
almost-cliques left uncolored by the first part, e.g., for a
$(\Delta+1)$-clique minus a $\sqrt{\Delta}$-size inner clique (applying this
method to a graph consisting of only such almost-cliques requires
$\Omega(n\sqrt{\Delta})$ space). As a result, our semi-streaming algorithm
settles for recovering certain helper structures from these almost-cliques
instead. These are subgraphs of the input that are sufficiently simple to be
recoverable via a combination of sparse recovery, sampling, and some basic
graph theory arguments. At the same time, they are structured enough to give
us enough flexibility for the final coloring step. Given the technicality of
their definitions (Definitions 4.7 and 4.6 and Figure 6), we postpone further
details to Section 4.1.

We point out that sparse recovery and linear sketching have been a staple of
graph streaming algorithms since the seminal work of [3]. But, these tools
have been almost exclusively used to handle edge deletions in _dynamic_
streams. Their applications for us, on _insertion-only_ streams, as a way of
(implicitly) sparsifying a graph using outside information (i.e., the sparse-
dense decomposition), is quite different and can form a tool of independent
interest.

##### Part Three: The Final Coloring Procedure

The final step of our approach is then to color these remaining almost-
cliques, given the extra information we recovered for them in the previous
step. For intuition, let us consider two inherently different types of almost-
cliques left uncolored by the approach in the first part.

(a) a $(\Delta+1)$-clique minus an edge

(b) a $\Delta$-clique with few neighbors

Figure 4: Two problematic almost-cliques in a graph with maximum degree
$\Delta=4$. Both almost-cliques are _hard_ for palette sparsification. The
only way part (a) can be $\Delta$-colored is if the vertices incident on the
non-edge have intersecting lists. Part (b) is _not_ $\Delta$-colorable if the
outside (marked) vertices are all colored the same.

######  $(\Delta+1)$-clique minus an edge $(u,v)$ (Figure 4(a)):

Suppose we know all edges of such an almost-clique. We can color both $u$ and
$v$ the same using a color that does not appear in their outside neighbors
(which is possible because vertices of almost-cliques have few edges out); the
standard greedy algorithm now actually manages to $\Delta$-color this almost-
clique (recall that we assumed the knowledge of _all_ edges of the almost-
clique for now). The argument is simply the following: Pick a common neighbor
$z$ of $u$ and $v$, which will exist in an almost-clique, and greedily color
vertices from a color not used in their neighborhood, waiting for $z$ to be
colored last; at this point, since two neighbors of $z$ have the same color,
there is still a choice for $z$ to be colored with in the algorithm.

######  $\Delta$-clique with few neighbors (Figure 4(b)):

These are more problematic cases if we have ended up coloring all their
outside neighbors the same. Even if we know all edges of this almost-clique,
there is no way we can color a $\Delta$-clique with $(\Delta-1)$ colors (the
same one color is “blocked” for all vertices). So, the next ingredient of our
algorithm is a recoloring step that allows for handling these almost-cliques
(again, recall Section 2.1); we show that our strengthened palette
sparsification is flexible enough that, given the edges of a new almost-
clique, allows for altering some of its _past_ decisions on outside vertices
of this almost-clique. This step involves reasoning about a probabilistic
process (possibility of having a “good” color to change for an outside vertex)
_after_ already viewing the outcome of the process (having ended up with a
“blocked” color). This requires a careful analysis which is handled by
partitioning the randomness of the process into multiple _phases_ and using
our classification of almost-cliques to limit the amount of “fresh randomness”
we need for this step across these phases. We discuss this in more details in
Section 5.

The discussion above oversimplified many details. Most importantly, we
actually do not have such a “clean” picture as above for the remaining almost-
cliques we need to color. Instead, the algorithm needs to handle almost-
cliques that are not fully recoverable by sparse recovery (as they are not
sufficiently dense), using their helper structures described earlier.555For a
$(\Delta+1)$-clique minus an edge $(u,v)$, the helper structure is the
subgraph consisting of vertices $u$ and $v$, and all edges incident on at
least one of them. The helper structure of the other example is more tricky;
see Figure 6. This coloring is thus done via a combination of the greedy
arguments of the above type on the helper structures, combined with palette
sparsification ideas for the remaining vertices of the almost-clique. This in
turns requires using some out of (sampled) palette coloring of vertices, which
is in conflict with what the palette sparsification does and needs to be
handled carefully; see Sections 5.6 and 5.5.

###  3 Preliminaries

###### Notation.

For an integer $t\geqslant 1$, we define $[t]:=\left\\{1,2,\ldots,t\right\\}$.
For a graph $G=(V,E)$ and a vertex $v\in V$, we use $N_{G}(v)$ to denote the
neighbors of $v$ in $G$, and $N(v)$ when the graph is clear from the context.
Further, we define degree of $v$ by $\deg_{G}(v):=\left|{N_{G}(v)}\right|$
(and similarly $\deg(v)$). We refer to a pair $(u,v)$ of vertices in $V$ as a
non-edge when there is no edge between $u$ and $v$ in $G$. Similarly, we
sometimes say that $u$ is a non-neighbor of $v$ and vice versa.

For a graph $G=(V,E)$ and integer $q\geqslant 1$, we refer to any function
$C:V\rightarrow[q]$ as a $q$-coloring and call it a _proper_ coloring iff
there is no edge $(u,v)$ in $G$ with $C(u)=C(v)$. We further refer to a
function $C:V\rightarrow[q]\cup\left\\{\perp\right\\}$ as a partial
$q$-coloring and call the vertices $v\in V$ with $C(v)=\perp$ as uncolored
vertices by $C$. The edges $(u,v)$ in $G$ with $C(u)=C(v)=\perp$ are _not_
considered monochromatic, and thus we consider a partial $q$-coloring proper
iff there is no edge $(u,v)$ in $G$ with $C(u)=C(v)\neq\perp$. Finally, for
any proper partial $q$-coloring, and any vertex $v\in V$, we define:

  * •

$\mathsf{ColNei}_{C}(v):=\left\\{u\in N(v)\mid C(u)\neq\perp\right\\}$: the
neighbors of $v$ that are assigned a color by $C$; we further define
$\mathsf{coldeg}_{C}(v):=\left|{\mathsf{ColNei}_{C}(v)}\right|$.

  * •

$\mathsf{Avail}_{C}(v):=\left\\{c\in[q]\mid C(u)\neq c\text{~{}for all~{}}u\in
N(v)\right\\}$: the colors in $[q]$ that have not been assigned to any
neighbor of $v$ by $C$, i.e., are _available_ to $v$; we define
$\mathsf{avail}_{C}(v):=\left|{\mathsf{Avail}_{C}(v)}\right|$.

Finally, we say that a coloring $C_{1}$ is an extension of coloring $C_{2}$
iff for every $v\in V$ with $C_{2}(v)\neq\perp$, $C_{1}(v)=C_{2}(v)$; in other
words, only uncolored vertices in $C_{2}$ may receive a different color in
$C_{1}$.

For a bipartite graph $H=(L,R,E)$, a matching $M$ is any collection of
_vertex-disjoint_ edges. We say that a matching $M$ is an $L$-perfect matching
iff it matches all vertices in $L$. We use the following presentation of the
well-known Hall’s marriage theorem [36].

######  Fact 1 (cf. [36]).

Suppose $H=(L,R,E)$ is a bipartite graph such that for any set $A\subseteq L$,
we have $\left|{N(A)}\right|\geqslant\left|{A}\right|$; then $H$ has an
$L$-perfect matching.

###### Concentration results.

We use the following standard form of Chernoff bound in our proofs.

######  Proposition 3.1 (Chernoff bound; c.f. [29]).

Suppose $X_{1},\ldots,X_{m}$ are $m$ independent random variables with range
$[0,b]$ each. Let $X:=\sum_{i=1}^{m}X_{i}$ and
$\mu_{L}\leqslant\operatorname*{{\mathbb{E}}}\left[X\right]\leqslant\mu_{H}$.
Then, for any $\delta>0$,

$\operatorname*{\textnormal{Pr}}\left(X>(1+\delta)\cdot\mu_{H}\right)\leqslant\exp\left(-\frac{\delta^{2}\cdot\mu_{H}}{(3+\delta)\cdot
b}\right)\quad\textnormal{and}\quad\operatorname*{\textnormal{Pr}}\left(X<(1-\delta)\cdot\mu_{L}\right)\leqslant\exp\left(-\frac{\delta^{2}\cdot\mu_{L}}{(2+\delta)\cdot
b}\right).$

Throughout, we say that an event happens _“with high probability”_ , or
_“w.h.p.”_ for short, to mean that it happens with probability at least
$1-1/\mbox{\rm poly}{(n)}$ for some large polynomial (the degree can be
arbitrarily large without changing the asymptotic performance of the
algorithms). Moreover, we pick this degree to be large enough to allow us to
do a union bound over the polynomially many events considered and we do not
explicitly mention this union bound each time (but in certain places that we
need to do a union bound over exponentially many events, we will be more
explicit).

####  3.1 A Sparse-Dense Decomposition

We use a simple corollary of known streaming sparse-dense decompositions in
[7, 9], which have their origin in the classical work in graph theory [59, 50]
and have subsequently been used extensively in distributed algorithms as well
[41, 23, 55, 38].

The decomposition is based on partitioning the vertices into _“(locally)
sparse”_ vertices with many non-edges among their neighbors and _“almost-
clique”_ vertices that are part of a subgraph which is close to being a
clique. We formally define these as follows.

######  Definition 3.2.

For a graph $G=(V,E)$ and parameter $\varepsilon>0$, a vertex $v\in V$ is
$\varepsilon$-sparse iff there are at least $\varepsilon^{2}\cdot\Delta^{2}/2$
non-edges between the neighbors of $v$.

######  Definition 3.3.

For a graph $G=(V,E)$ and parameter $\varepsilon>0$, a subset of vertices
$K\subseteq V$ is an $\varepsilon$-almost-clique iff $K$ has the following
properties:

  1. $i)$.

Size of $K$ satisfies
$(1-5\varepsilon)\cdot\Delta\leqslant|K|\leqslant(1+5\varepsilon)\cdot\Delta$.

  2. $ii)$.

Every vertex $v\in K$ has $\leqslant 10\varepsilon\Delta$ _non-neighbors_
inside $K$;

  3. $iii)$.

Every vertex $v\in K$ has $\leqslant 10\varepsilon\Delta$ _neighbors_ outside
$K$;

  4. $iv)$.

Every vertex $u\notin K$ has $\geqslant 10\varepsilon\Delta$ _non-neighbors_
inside $K$.

We note that property $iv)$. of Definition 3.3 does not typically appear in
the definition of almost-cliques in prior work but it is crucial for our
proofs. However, this property follows immediately from the proof of [9]. We
have the following sparse-dense decomposition.

######  Proposition 3.4 (Sparse-Dense Decomposition; cf. [50, 7, 9]).

There is a constant $\varepsilon_{0}>0$ such that the following holds. For any
$0<\varepsilon<\varepsilon_{0}$, vertices of any graph $G=(V,E)$ can be
partitioned into sparse vertices $V_{\textnormal{sparse}}$ that are
$\varepsilon$-sparse (Definition 3.2) and dense vertices partitioned into a
collection of disjoint $\varepsilon$-almost-cliques $K_{1},\ldots,K_{k}$
(Definition 3.3).

Moreover, there is an absolute constant $\gamma>0$ and an algorithm that given
access to only the following information about $G$, with high probability,
computes this decomposition of $G$:

  * •

Random edge samples: A collection of sets $N_{\textnormal{sample}}(v)$ of
$(\gamma\cdot\varepsilon^{-2}\cdot\log{n})$ neighbors of every vertex $v\in V$
chosen independently and uniformly at random (with repetition);

  * •

Random vertex samples: A set SAMPLE of vertices wherein each $v\in V$ is
included independently with probability $(\gamma\cdot\log{n}/\Delta)$,
together with all the neighborhood $N(v)$ of each sampled vertex
$v\in\textnormal{{SAMPLE}}$.

We note that a dense vertex is _not_ necessarily not $\varepsilon$-sparse. Or
in other words, the set $V_{\textnormal{sparse}}$ may not include all the
$\varepsilon$-sparse vertices of $G$, as some $\varepsilon$-sparse vertices
may still be be included in some $\varepsilon$-almost-clique.

####  3.2 Sparse Recovery

We also use the following standard variant of sparse recovery in our proofs.
We note that the specific recovery matrix below, the Vandermonde matrix, is
not necessary for our proofs (i.e., can be replaced with any other standard
construction) and is only mentioned explicitly for concreteness.

######  Proposition 3.5 (cf. [28]).

Let $n,k\geqslant 1$ be arbitrary integers and $p\geqslant n$ be a prime
number. Consider the $(2k\times n)$-dimensional Vandermonde matrix over
$\mathbb{F}_{p}$:

$\Phi^{\textnormal{V}}:=\begin{bmatrix}1&1&1&\cdots&1\\\ 1&2&3&\cdots&n\\\
1&2^{2}&3^{2}&\cdots&n^{2}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
1&2^{2k-1}&3^{2k-1}&\cdots&n^{2k-1}\end{bmatrix},\quad\textnormal{or for all
$i\in[2k]$ and
$j\in[n]$:}\quad\Phi^{\textnormal{V}}_{i,j}=j^{i-1}\\!\\!\\!\\!\mod p.$

Then, for any $k$-sparse vector $x\in\mathbb{F}_{p}^{n}$, one can uniquely
recover $x$ from $\Phi^{\textnormal{V}}\cdot x$ in polynomial time.

The proof that a $k$-sparse vector $x$ can be recovered from
$\Phi^{\textnormal{V}}\cdot x$ is simply the following: for
$\Phi^{\textnormal{V}}\cdot x=\Phi^{\textnormal{V}}\cdot y$ for two $k$-sparse
vectors $x\neq y$ (i.e. recovery is impossible), we need
$\Phi^{\textnormal{V}}\cdot(x-y)=0$. But then this means that the (at most)
$2k$ columns in the matrix $\Phi^{\textnormal{V}}$ corresponding to the
support of $x-y$ have a non-trivial kernel; the latter is a contradiction as
any $2k$ columns of $\Phi^{\textnormal{V}}$ are independent (polynomial time
recovery also can be obtained via syndrome decoding from coding theory).

In order to safely use sparse recovery (in case when we mistakenly run it on a
non-sparse vector), we also need the following standard result that allows us
to test whether the output of the recovery is indeed correct or not. This
result is also standard and is proven for completeness.

######  Proposition 3.6.

Let $n,t\geqslant 1$ be arbitrary integers and $p\geqslant n$ be a prime
number. Consider the $(t\times n)$-dimensional random matrix
$\Phi^{\textnormal{R}}$ over $\mathbb{F}_{p}$ chosen uniformly from all
matrices in $\mathbb{F}_{p}^{t\times n}$. Then, for any two different vectors
$x\neq y\in\mathbb{F}_{p}^{n}$, we have,

$\operatorname*{\textnormal{Pr}}_{\Phi^{\textnormal{R}}}\left(\Phi^{\textnormal{R}}\cdot
x=\Phi^{\textnormal{R}}\cdot y\right)=p^{-t}.$

######  Proof 3.7.

Let $z:=x-y$ and note that there exists at least one index $i\in[n]$ with
$z_{i}\neq 0$. We need to calculate the probability of
$\Phi^{\textnormal{R}}\cdot z=0$. Let $r$ be any row of matrix
$\Phi^{\textnormal{R}}$. We have,

$\operatorname*{\textnormal{Pr}}\Big{(}\langle
r,z\rangle=0\Big{)}=\operatorname*{\textnormal{Pr}}\left(r_{i}\cdot
z_{i}=\sum_{j\neq i}r_{j}\cdot z_{j}\right)=p^{-1},$

because $r_{i}\cdot z_{i}$ is going to be any element of the field
$\mathbb{F}_{p}$ with equal probability (as $z_{i}$ is non-zero) and choice of
$r_{i}$ is independent of $\left\\{r_{j}\mid j\neq i\right\\}$. As all the $t$
rows of $\Phi^{\textnormal{R}}$ are independent, we get the final bound
immediately.

We can now combine Proposition 3.5 and Proposition 3.6 to have a “safe”
recovery w.h.p. as follows: For the (unknown) vector $x\in\mathbb{F}_{p}^{n}$,
we compute $\Phi^{\textnormal{V}}\cdot x$ and $\Phi^{\textnormal{R}}\cdot x$
in parallel. We first use $\Phi^{\textnormal{V}}\cdot x$ in Proposition 3.5 to
recover a vector $y\in\mathbb{F}_{p}^{n}$; then, since we know
$\Phi^{\textnormal{R}}$, we can also compute $\Phi^{\textnormal{R}}\cdot y$
and use Proposition 3.6 to check whether $\Phi^{\textnormal{R}}\cdot
y=\Phi^{\textnormal{R}}\cdot x$: if yes, we output $y$ and otherwise output
‘fail’. It is easy to see that if $x$ is indeed $k$-sparse, this scheme always
recovers $x$ correctly, and in any other case, w.h.p., it does not recover a
wrong vector (but may output ‘fail’).

####  3.3 Palette Graphs, Matching View of Coloring, and Random Graph Theory

We also borrow a key technique from [7] for coloring almost-cliques in the
decomposition. In the following, we shall follow the presentation of [7] as
specified in the notes by [1] which is conceptually identical but notation-
wise slightly different from the original presentation.

We note that this subsection might be rather too technical and not intuitive
enough at this stage and can be skipped by the reader on the first read of the
paper—we will get to these topics only starting from Section 5.2 of our
algorithm once we start with the final coloring step of our algorithm, and by
that time we have set the stage more for these definitions.

######  Definition 3.8.

Let $G=(V,E)$ be a graph, $q\geqslant 1$ be an integer, and $C$ be a proper
partial $q$-coloring of $G$. Let $K$ be any almost-clique in $G$. We define
the base palette graph of $K$ and $C$ as the following bipartite graph
$\mathcal{G}_{\textnormal{{Base}}}:=(\mathcal{L},\mathcal{R},\mathcal{E}_{\textnormal{{Base}}})$:

  * •

_Vertex-set:_ $\mathcal{L}$ consists of all vertices in $K$ that are uncolored
by $C$ and $\mathcal{R}$ consists of all the colors in $[q]$ that are not
assigned to any vertex in $K$. To avoid ambiguity, we use _nodes_ to refer to
elements of $\mathcal{L}$ and $\mathcal{R}$ (as opposed to vertices), and call
nodes in $\mathcal{L}$ as _vertex-nodes_ , and nodes in $\mathcal{R}$ as
_color-nodes_.

  * •

_Edge-set:_ there is an edge between any pair of vertex-node $v\in\mathcal{L}$
and color-node $c\in\mathcal{R}$ iff $c\in\mathsf{Avail}_{C}(v)$, i.e., $c$
does not appear in the neighborhood of $v$ in the partial coloring $C$.

Figure 5 gives an illustration of this definition.

The base palette graph gives us a different graph theoretic way of looking at
graph coloring. Suppose we start with a proper partial $q$-coloring $C$ of $G$
and manage to find an $\mathcal{L}$-perfect matching $\mathcal{M}$ in
$\mathcal{G}_{\textnormal{{Base}}}$;666Clearly, this will not be always
possible, for instance when size of $K$ is larger than $q$—in general, one
needs some preprocessing steps before being able to apply this idea. this will
allow us to find an extension of $C$ that colors all vertices of $K$: simply
color each vertex $v\in K$ with the color $c$ which corresponds to the matched
pair of $\mathcal{M}(v)$ (in $\mathcal{G}_{\textnormal{{Base}}}$). This
“matching view” of the coloring problem turns out to be quite helpful when
analyzing almost-cliques in [7], and we shall use and considerably generalize
this idea in this paper as well.

There is however an obvious obstacle in using
$\mathcal{G}_{\textnormal{{Base}}}$ when coloring the graph: we may not have
access to all of $\mathcal{G}_{\textnormal{{Base}}}$ (when using a semi-
streaming algorithm due to space limitations). This motivates the next
definition.

######  Definition 3.9.

Let $G=(V,E)$ be a graph, $q\geqslant 1$ be an integer, and $C$ be a proper
partial $q$-coloring of $G$. Let $K$ be any almost-clique in $G$ and
$\SS:=\left\\{S(v)\subseteq[q]\mid v\in K\right\\}$ be a collection of sampled
colors.777Think of $S(v)$ as being a small set of colors sampled for each
vertex. For instance, in the context of palette sparsification theorem of [7],
$S(v)$ is the set of $O(\log{n})$ colors sampled for each vertex. We define
the sampled palette graph of $K$, $C$, and $\SS$, denoted by
$\mathcal{G}_{\textnormal{{Sample}}}=(\mathcal{L},\mathcal{R},\mathcal{E}_{\textnormal{{Sample}}})$
as the spanning subgraph of the base palette graph
$\mathcal{G}_{\textnormal{{Base}}}$ obtained by letting
$\mathcal{E}_{\textnormal{{Sample}}}$ to be the edges $(v,c)$ from
$\mathcal{E}_{\textnormal{{Base}}}$ such that $c\in S(v)$.

1234511 (a) an almost-clique

235 (b) base palette graph (dashed lines are missing edges)

235 (c) sampled palette graph (dotted lines are not-sampled edges)

Figure 5: An illustration of base palette graphs (Definition 3.8) and sampled
palette graphs (Definition 3.9).

Let us again fix a small almost-clique $K$ and the partial coloring $C$.
Consider the sampled palette graph $\mathcal{G}_{\textnormal{{Sample}}}$ of
$K$, $C$, and $\SS:=\left\\{S(v)\mid v\in K\right\\}$ for $S(v)$ of size, say,
$\mbox{\rm poly}\\!\log{(n)}$, chosen randomly from $[q]$. This is now a much
sparser subgraph that is easier to maintain via a semi-streaming algorithm.
Similar to before, if we find an $\mathcal{L}$-perfect matching in
$\mathcal{G}_{\textnormal{{Sample}}}$ we will be done. The challenge now,
however, is to argue that not only $\mathcal{G}_{\textnormal{{Base}}}$, but
even $\mathcal{G}_{\textnormal{{Sample}}}$ (that has much fewer edges)
contains such a matching (with high probability over the choice of sampled
lists).

This challenge can be addressed using “random graph theory type” arguments: we
first establish several key properties of $\mathcal{G}_{\textnormal{{Base}}}$
itself that ensure that it has an $\mathcal{L}$-perfect matching; then, we
consider $\mathcal{G}_{\textnormal{{Sample}}}$ which is a random subgraph of
$\mathcal{G}_{\textnormal{{Base}}}$ and use simple tools in the analysis of
random graphs to prove that $\mathcal{G}_{\textnormal{{Sample}}}$ also w.h.p.
has an $\mathcal{L}$-perfect matching.888Note that if
$\mathcal{G}_{\textnormal{{Base}}}$ is indeed a bipartite clique, then
$\mathcal{G}_{\textnormal{{Sample}}}$ would become a standard random graph.
However, in general, $\mathcal{G}_{\textnormal{{Base}}}$ can be “sufficiently
far” from a bipartite clique, which requires a careful analysis of
$\mathcal{G}_{\textnormal{{Sample}}}$ beyond known results in random graph
theory. See Lemma 3.10 (and its proof in [7]) for an example. The following
lemma mentions one example of such a random graph theory type argument that
played a key role in [7] (we shall use this lemma and some news ones that we
establish throughout our proofs in this paper).

######  Lemma 3.10 ([7]).

Let $H=(L,R,E)$ be any bipartite graph with the following properties:

  1. $(i)$

$m:=\left|{L}\right|$ and $m\leqslant\left|{R}\right|\leqslant 2m$;

  2. $(ii)$

The minimum degree of vertices in $L$ is at least $(2/3)\cdot m$, i.e.,
$\min_{v\in L}\deg_{H}(v)\geqslant(2/3)\cdot m$;

  3. $(iii)$

For every set $A\subseteq L$ of size $\left|{A}\right|\geqslant m/2$, we have
$\sum_{v\in A}\deg_{H}(v)\geqslant(\left|{A}\right|\cdot m)-m/4$.

For any $\delta\in(0,1)$, a subgraph of $H$ obtained by sampling each edge
independently with probability at least
$(\frac{20}{m}\cdot(\log{m}+\log{(1/\delta)}))$ contains an $L$-perfect
matching with probability at least $1-\delta$.

As discussed earlier, the way one applies Lemma 3.10 is by setting $H$ to be
the base palette graph of a given almost-clique, in which case, sampled
palette graph has the same distribution as specified in Lemma 3.10 and thus
w.h.p. will have the desired matching. Also, while at this stage the
properties of $H$ in this lemma may sound rather arbitrary, as we shall see
later in our proofs, they appear naturally as properties of base graphs of
(certain) almost-cliques. Finally, we note that even though the proof of this
lemma is rather technical and so we do not repeat it here, it is not hard to
verify that at least the graph $H$ itself has an $L$-perfect matching using
Hall’s theorem (Fact 1), given the conditions imposed on it in Lemma 3.10.

###  4 The Semi-Streaming Algorithm

In this section we describe the algorithm that collects necessary information
for the $\Delta$-coloring from the stream. This will then be used in our main
coloring procedure in Section 5 to prove Theorem 1.1. The algorithm consists
of the following three main parts:

  * •

The palette-sampling algorithm (Algorithm 1): An algorithm, quite similar to
palette sparsification approach, that samples $\mbox{\rm poly}\\!\log{(n)}$
potential colors for each vertex and store all possibly monochromatic edges
during the stream.

  * •

The find-decomposition algorithm (Algorithm 2): An algorithm that recovers a
sparse-dense decomposition of the input graph as specified in Proposition 3.4
plus some extra useful information about the decomposition.

  * •

The sparse-recovery algorithm (Algorithm 3): An algorithm that uses sparse
recovery techniques to extract further “helper structures” about the almost-
cliques in the decomposition of the previous step.

We elaborate on each of these algorithms and their guarantees in the following
subsections. But we shall emphasize that they all run _in parallel_ in a
single pass over the stream. To continue, we start with setting up some
parameters and key definitions.

####  4.1 Parameters, Classification of Almost-Cliques, and Helper Structures

We use the following parameters for the design of our algorithms.

$\displaystyle\alpha=10^{3}:\quad$ a large constant used to simplify various
concentration inequalities $\displaystyle\beta=100\cdot\log{n}:$ used to bound
the size of certain palettes in palette-sampling
$\displaystyle\varepsilon=\frac{10^{-8}}{\log{n}}:$ $\displaystyle\text{used
as the parameter of sparse-dense decomposition
of~{}\lx@cref{creftypecap~refnum}{prop:decomposition}}.$ (1)

We also assume999This is used in the proof of Lemma 5.2. that
$\Delta=\Omega(\log^{5}{n})$ as otherwise we can simply store the graph
entirely and solve the problem offline, using any classical algorithm for
Brooks’ theorem.

Recall the notion of almost-cliques in Definition 3.3 used in our sparse-dense
decomposition. In the coloring phase of the algorithm, we make further
distinctions between almost-cliques based on their sizes as defined below—the
coloring algorithm will treat these classes separately and our algorithms in
this section provide further information about these different classes.

###### Classification of almost-cliques.

We start with the following simple definition that partitions almost-cliques
based on their size.

######  Definition 4.1.

Let $K$ be an almost-clique in the sparse-dense decomposition. We say that $K$
is small iff it has at most $\Delta$ vertices, critical iff it has exactly
$\Delta+1$ vertices, and large otherwise.

We have the following basic observation based on this definition. $(i)$ Any
critical almost-clique contains at least one non-edge, and $(ii)$ any large
almost-clique contains at least $(\Delta+2)/2$ non-edges.

######  Proof 4.2.

Property $(i)$ holds because there are no $(\Delta+1)$ cliques in our input as
otherwise the graph will not be $\Delta$-colorable, and $(ii)$ holds because
maximum degree of vertices is $\Delta$ and thus every vertex has at least one
non-edge in a large almost-clique.

A property that fundamentally affects how we color an almost-clique is the
number of non-edges inside it. Intuitively, if an almost-clique is very
“clique-like”, that is, it has very few non-edges inside, then it is more
difficult to color. This motivates the following definition.

######  Definition 4.3.

Let $K$ be an almost-clique in the sparse-dense decomposition. We say that $K$
is holey iff it has at least $10^{7}\cdot\varepsilon\Delta$ non-edges (or
“holes”) inside it. Otherwise, $K$ is unholey.

Another key property that governs our ability to color an almost-clique is how
it is connected to the outside and in particular, what we can expect from a
coloring of its neighbors outside: can we see those colors as being “random”
or are they “adversarial”? In the latter case, can we recolor some to make
them “less adversarial”? This motivates the following two definitions.

######  Definition 4.4.

Let $K$ be an almost-clique in the decomposition and $v$ be any vertex outside
$K$ that is neighbor to $K$. We say that:

  * •

$v$ is a friend of $K$ iff there are at least $2\Delta/\beta$ edges from $v$
to $K$, i.e., $\left|{N(v)\cap K}\right|\geqslant 2\Delta/\beta$;

  * •

$v$ is a stranger to $K$ iff there are less than $\Delta/\beta$ edges from $v$
to $K$, i.e., $\left|{N(v)\cap K}\right|<\Delta/\beta$;

We emphasize that there is a gap in the criteria between friend and stranger
vertices, and hence it is possible that a vertex is neither a friend of nor a
stranger to an almost-clique. Based on the notion of friend and stranger
vertices, we can further classify almost-cliques into these classes.

######  Definition 4.5.

Let $K$ be an almost-clique in the decomposition. We say that $K$ is:

  * •

friendly iff $K$ has at least one neighbor outside $K$ that is a friend of
$K$.

  * •

lonely iff all neighbors of $K$ outside $K$ are strangers.

  * •

social otherwise; that is, $K$ has at least one neighbor outside $K$ that is
_not_ a stranger, but at the same time, it has no friends.

We approach coloring friendly and lonely almost-cliques quite differently, but
both approaches can handle social almost-cliques. This will be crucial as we
can distinguish between friendly and lonely almost-cliques but our tester may
classify social almost-cliques in either of these groups.

###### Helper structures.

As stated earlier, the problematic almost-cliques to $\Delta$-color are
unholey ones. Some of these unholey almost-cliques can be handled by a
“global” argument that reason about the coloring of their neighbors outside.
But for the rest, we may need to consider recoloring some of their neighbors
outside and/or using some extra information about the graph. In the following,
we define two “helper structures” that provide this extra information for our
coloring approach. Our algorithms in this section then show how we can find
these subgraphs in the stream.

The first structure we have handles unholey almost-cliques which are critical.

######  Definition 4.6.

Let $K$ be an unholey almost-clique which is critical. We define a critical-
helper structure for $K$ as a tuple $(u,v,N(v))$ with the following
properties:

  1. $(i)$

$u,v$ are vertices of the graph and are both in $K$;

  2. $(ii)$

$u$ and $v$ are non-neighbor to each other;

  3. $(iii)$

$N(v)$ is the neighborhood of $v$ in the graph.

At a very high level, if we have a critical-helper structure of $K$ at hand,
we can color $u$ and $v$ the same (the crucial knowledge of $N(v)$ allows us
to do this) which “buys” us an extra color which will be sufficient for us to
color the entire almost-clique also.

The second structure we have handles unholey almost-cliques which are friendly
or even social.

######  Definition 4.7.

Let $K$ be an unholey almost-clique which is either friendly or social. We
define a friendly-helper structure for $K$ as a tuple $(u,v,w,N(v),N(w))$ with
the following properties:

  1. $(i)$

$u,v,w$ are vertices of the graph such that $u\notin K$ and is not a stranger
to $K$ and $v,w\in K$;

  2. $(ii)$

$u$ is neighbor to $v$ and non-neighbor to $w$, and $v$ and $w$ are themselves
neighbors;

  3. $(iii)$

$N(v)$ and $N(w)$ are the neighborhoods of $v$ and $w$ in the graph,
respectively.

Again, at a high level, if we have a friendly-helper structure of $K$ at hand,
we will be able to (re)color $u$ and $w$ the same, which “buys” us an extra
color for $v$ and gives us the required flexibility for coloring the entire
almost-clique (the knowledge of $N(v)$ and $N(w)$ crucially allows us to
choose the colors for these vertices without creating a conflict with their
neighbors in the graph).

$u$$v$$K$$N(v)$ (a) A critical helper: The vertices $u$ and $v$ can receive
the same color.

$v$$w$$u$$K$$N(v)\setminus K$$N(w)\setminus K$$\left|{N(u)\cap
K}\right|\geqslant\frac{\Delta}{\beta}$ (b) A friendly helper: The vertices
$u$ and $w$ can receive the same color.

Figure 6: The two types of helper structures in Definition 4.6 and Definition
4.7.

####  4.2 Palette Sampling

One key component of our algorithm is a color sampling procedure in the same
spirit as the palette sparsification theorem of [7].

Input: Graph $G=(V,E)$ with known vertices $V$ and streaming edges $E$.

  1. $(i)$

For every vertex $v\in V$, sample the following lists of colors:

     * •

$L_{1}(v)$: Sample a single color chosen uniformly at random from $[\Delta]$.

     * •

$L_{2}(v)$: Sample each color in $\left[\Delta\right]$ independently with
probability $\frac{\beta}{\Delta}$.

     * •

$L_{3}(v)$: Sample each color in $\left[\Delta\right]$ independently with
probability $\frac{100\cdot\alpha\cdot\log n}{\varepsilon^{2}\cdot\Delta}$.

     * •

$L_{4}(v):=(L^{*}_{4}(v)\text{~{}and~{}}{L_{4,i}(v)\textnormal{:
$i\in\left[\beta\right]$}})$: Independently, sample each color in
$\left[\Delta\right]$ with probability $\frac{\beta}{\Delta}$ in
$L_{4}^{*}(v)$ and with $q~{}:=~{}\frac{1}{100\sqrt{\varepsilon}\Delta}$ in
$L_{4,i}(v)$ for $i\in[\beta]$.

     * •

$L_{5}(v)$: Sample each color in $\left[\Delta\right]$ independently with
probability $\frac{\beta}{\Delta}$.

     * •

$L_{6}(v):=({L_{6,i}(v)\textnormal{: $i\in\left[2\beta\right]$}})$: Sample
each color in $\left[\Delta\right]$ independently with probability
$\beta^{2}/\Delta$.

  2. $(ii)$

Let $L(v):=\cup_{j\in[6]}L_{j}(v)$. Store any edge $({u,v})$ if $L(u)\cap
L(v)\neq\emptyset$ and let $H$ be the subgraph of $G$ on these stored edges,
referred to as the conflict graph.

Algorithm 1 The palette-sampling algorithm.

The main difference of this algorithm with that of [7] is that the number of
sampled colors per vertex is larger here ($\mbox{\rm poly}\\!\log{(n)}$ as
opposed to $O(\log{n})$) and that we explicitly partition these samples into
multiple lists instead of just one.

At this point, the choices of the lists $L_{1}(v)\ldots L_{6}(v)$ may seem
arbitrary:101010And indeed redundant; technically speaking, we could have just
sampled a single list of colors of proper size and postponed the partitioning
to the analysis (as in fact done in [7])—however, we find it more transparent
to consider these lists explicitly separate from each other due to various
dependency issues that this explicitly avoids. the (very) rough idea is that
we will use different lists at different stages of the coloring, and the sizes
are chosen to allow each stage to go through without causing too much
dependency for the next stage. In the rest of this subsection, we will bound
the space complexity of palette-sampling (Algorithm 1).

Recall that in the conflict graph $G$, we only keep an edge $({u,v})$ if
$L(u)\cap L(v)\neq\emptyset$—which makes sense, since if we restrict ourselves
to coloring vertices with a color from their lists $L(\cdot)$, then these are
the only edges that can be monochromatic. We have the following (standard)
lemma.

######  Lemma 4.8.

With high probability, conflict graph $H$ in palette-sampling has
$O(n\cdot\log^{6}n)$ edges.

######  Proof 4.9.

First, note that for any vertex $v\in V$, $L_{1}(v)$ has a single color. We
want to establish that the sizes of the other lists
$\left|{L_{2}(v)}\right|,\ldots,\left|{L_{6}(v)}\right|$ are bounded by
$O(\log^{3}n)$ with high probability.

For $L_{2}(v)$: We have that the expected size of $L_{2}(v)$ is
$\frac{\beta}{\Delta}\cdot\Delta=\beta$ by linearity of expectation. Since
each color is sampled into $L_{2}(v)$ independently, we have via an
application of Chernoff bound (Proposition 3.1, with $\delta=1$) that:

By union bound, we have that with high probability, $\left|{L_{2}(v)}\right|$
is bounded by $2\beta=O(\log n)$ for all $v\in V$. We can apply the same
argument on all lists with expected size $\Omega(\log n)$ to show that their
sizes are within a constant of their respective expected values with high
probability. In particular, $L_{3}(v)$, $L_{4}^{*}(v)$, $L_{5}(v)$, all have
expected sizes that are $\Omega(\log n)$ and also $O(\log^{3}n)$ (see Eq. 1),
and hence have size $O(\log^{3}n)$ for each one with high probability.
Further, since for each $i$, $L_{6,i}(v)$ has expected size $\beta^{2}$,
$\left|{L_{6}(v)}\right|$ is $O(\log^{3}n)$ as well, with high probability.

This leaves us with the lists $L_{4,i}(v)$: Note that their expected size is
$\frac{1}{100\sqrt{\varepsilon}}=100\sqrt{\log n}$. Since each color is
sampled into $L_{4,i}(v)$ independently, we can use a Chernoff bound with
$\delta=10\sqrt{\log n}$ to get:

And hence w.h.p., $\left|{L_{4}(v)}\right|$ is $O(\log^{2}n)$.

At this point, we have that there exist an absolute constant $\gamma>0$ such
that with high probability, $\left|{L(v)}\right|<\gamma\cdot\log^{3}{n}$ for
all $v\in V$. We condition on this event for the rest of this proof.

Our strategy is to bound $\deg_{H}(u)$ for each $u\in V$. Recall that an edge
$\\{u,v\\}$ is in $H$ if $L(v)$ samples a color from $L(u)$. An arbitrary
color $c\in\left[\Delta\right]$ is in $L(v)$ with probability at most
$\gamma\cdot\log^{3}(n)/\Delta$ (since each of the lists $L_{i}(v)$ is sampled
uniformly). Then for any choice of $L(u)$ (of size at most
$\gamma\cdot\log^{3}n$), we have by the union bound: where the randomness is
over the choice of $L(v)$.

Now we can bound the degree of an arbitrary vertex $u$ in the subgraph $H$
formed by the edges stored in Algorithm 1. First, fix the list $L(u)$—we
already conditioned on the event that it is small, but now we will “give up”
the remaining randomness in the choice of $L(u)$, and proceed by assuming an
arbitrary choice. Let $X_{u,v}$ be the indicator random variable that is $1$
iff the edge $\\{u,v\\}$ is in $H$. Then the expected degree of $u$ is
$(\gamma^{2}\cdot\log^{6}n)$ by the previous argument and linearity of
expectation. Finally, we observe that for $v\neq w$, $X_{u,v}$ and $X_{u,w}$
are independent, and via another application of Chernoff bound (Proposition
3.1, with $\delta=1$), we have:

Thus by union bound, each $u\in V$ has degree $O(\log^{6}n)$ in $H$ with high
probability. This immediately implies the bound on the number of edges stored
by Algorithm 1.

We can now bound the space used by palette-sampling. We have done all of the
heavy-lifting already, by bounding the number of edges stored in $H$. The only
new observation in the following lemma is that edges and colors can be stored
in $O(\log n)$ bits.

######  Lemma 4.10.

With high probability, palette-sampling uses $O(n\cdot\log^{7}n)$ bits of
space.

######  Proof 4.11.

We showed in the proof of Lemma 4.8 that with high probability,
$\left|{L(v)}\right|=O(\log^{3}n)$ for all $v\in V$. Since each color is from
$\left[\Delta\right]$, it can be represented by
${\left\lceil{\log\Delta}\right\rceil}$ bits, and hence storing the lists
$L(v)$ for all $v$ uses $O(n\log^{4}n)$ bits.

Further, each edge can be represented by $2\cdot{\left\lceil{\log
n}\right\rceil}$ bits, so by invoking Lemma 4.8, we have that we need
$O(n\cdot\log^{7}n)$ bits to store the conflict graph $H$.

####  4.3 Finding the Decomposition

We also work with the sparse-dense decomposition, but unlike [7], not only as
an analytical tool but in fact algorithmically (as will become evident from
the next subsection). We now describe an algorithm for finding the sparse-
dense decomposition of Proposition 3.4. In particular, we only need to provide
the random edge and vertex samples required by the proposition. But, in
addition to the samples required for the decomposition, we will also collect
independent random edge samples to allow us to distinguish friend vertices
from strangers (Definition 4.4).

Input: Graph $G=(V,E)$ with known vertices $V$ and streaming edges $E$.

  1. $(i)$

Let $\gamma$ be the constant from the statement of Proposition 3.4.

  2. $(ii)$

_Vertex samples:_ For each vertex $v$, sample $v$ into the set SAMPLE with
probability $(\gamma\cdot\log n/\Delta)$ independently. During the stream, for
each vertex $v$ in SAMPLE, store all edges incident on $v$.

  3. $(iii)$

_Edge samples:_ For each vertex $v$, use reservoir sampling on edges of $v$ to
pick a sample $N_{\textnormal{sample}}(v)$ of size
$\left(\gamma\cdot\varepsilon^{-2}\cdot\log n\right)$ from its neighborhood.

  4. $(iv)$

_Neighbor samples:_ For each vertex $v$, store each neighbor of $v$ in
$I_{\textnormal{sample}}(v)$ with probability $\beta^{2}/\Delta$.

Algorithm 2 The find-decomposition algorithm.

Let us start by bounding the space used by find-decomposition and then present
the main properties of the algorithm for our purpose.

######  Lemma 4.12.

With high probability, find-decomposition uses $O(n\log^{4}{n})$ bits of
space.

######  Proof 4.13.

The set SAMPLE has size $\gamma\cdot n\log n/\Delta$ in expectation, and since
each vertex $v$ is in SAMPLE independently, the size is at most (say)
$5\gamma\cdot n\log n/\Delta$ with high probability by Chernoff bound
(Proposition 3.1). For each $v\in\textnormal{{SAMPLE}}$, we use upto
$\Delta\cdot{\left\lceil{\log n}\right\rceil}$ bits of space to store all of
its edges, and hence in total we use $O(n\log^{2}n)$ bits to store SAMPLE and
the neighborhood of vertices in it.

The sets $N_{\textnormal{sample}}(v)$ have fixed sizes
$(\gamma\cdot\varepsilon^{-2}\cdot\log n)$ each. Storing a neighbor takes
${\left\lceil{\log n}\right\rceil}$ bits, and hence storing all the sets
$N_{\textnormal{sample}}(v)$ takes $O(n\log^{4}n)$ bits of space.

The set $I_{\textnormal{sample}}(v)$ is of size at most $2\beta^{2}$ with high
probability (again, the proof is the same as in Lemma 4.8). Hence storing
$I_{\textnormal{sample}}(v)$ for all $v$ uses $O(n\log^{3}n)$ bits of space.

We now establish the main properties we need from find-decomposition.

######  Lemma 4.14.

We can compute a sparse-dense decomposition (Proposition 3.4) of the input
graph $G=(V,E)$ with high probability using the samples collected by find-
decomposition.

######  Proof 4.15.

The proof is immediate—we collect SAMPLE and $N_{\textnormal{sample}}(v)$ as
needed by Proposition 3.4, so we can use the algorithm in the proposition to
compute the decomposition.

We will also show that the independent random edge samples
$I_{\textnormal{sample}}(v)$ are enough for a tester that can distinguish
friends from strangers for any almost-clique.

######  Lemma 4.16.

There exists an algorithm that given an almost-clique $K$, a vertex $v\notin
K$, and the random neighbor samples $I_{\textnormal{sample}}(v)$, with high
probability can distinguish:

  * •

$v$ has at most $\Delta/\beta$ neighbors in $K$, that is, $v$ is a stranger to
$K$;

  * •

$v$ has at least $2\Delta/\beta$ neighbors in $K$, that is, $v$ is a friend of
$K$.

The randomness in this lemma is only over the sample
$I_{\textnormal{sample}}(v)$.

######  Proof 4.17.

Fix a vertex $v\notin K$. Let $u$ be any neighbor of $v$ in $K$. Then $u\in
I_{\textnormal{sample}}(v)$ with probability $\beta^{2}/\Delta$. Let
$X_{u}\in\left\\{0,1\right\\}$ be the indicator random variable which is $1$
iff $u\in I_{\textnormal{sample}}(v)$. Thus, $X:=\sum_{u\in N(v)\cap K}X_{u}$
counts the size of intersection of $I_{\textnormal{sample}}(v)$ with $K$.
Firstly, we have

$\operatorname*{{\mathbb{E}}}\left[X\right]=\sum_{u\in N(v)\cap
K}\frac{\beta^{2}}{\Delta}=\left|{N(v)\cap
K}\right|\cdot\frac{\beta^{2}}{\Delta}.$

Thus, by Definition 4.4, $\operatorname*{{\mathbb{E}}}\left[X\right]$ is at
least $2\beta$ if $v$ is a friend of $K$ and at most $\beta$ if $v$ is a
stranger. Our tester can simply compute the value of $X$ and output friend if
$X$ is more than $\frac{3}{2}\beta$, and stranger otherwise. To prove the
correctness, suppose that $\left|{N(v)\cap K}\right|<\Delta/\beta$, i.e. $v$
is a stranger. Then, by an application of Chernoff bound (Proposition 3.1 with
$\delta=1/2$) we have:

by the choice of $\beta$ in Eq. 1. The other case can be proven symmetrically.
Hence if $v$ is a stranger (resp. friend), our tester also outputs stranger
(resp. friend) with high probability.

An immediate consequence of Lemma 4.16 is that we have a tester that can
distinguish friendly almost-cliques from lonely almost-cliques (Definition
4.5).

######  Lemma 4.18.

There exists an algorithm that given an almost-clique $K$, and to the random
neighbor samples $I_{\textnormal{sample}}(v)$ for every $v\in V$, with high
probability can distinguish:

  * •

$K$ is a friendly almost-clique;

  * •

$K$ is a lonely almost-clique.

The randomness in this lemma is only over the samples
$\left\\{I_{\textnormal{sample}}(v)\mid v\in V\right\\}$.

######  Proof 4.19.

For each vertex $v\in V\setminus K$, run the tester from Lemma 4.16. If $K$
has even one friend, then that friend is distinguished by the tester in Lemma
4.16 as a friend, and we can return that $K$ is friendly. Otherwise, if $K$ is
lonely, it means that every vertex $v$ we tested for $K$ will be considered
stranger also with high probability and thus we can correctly mark $K$ as
lonely.

####  4.4 Sparse Recovery for Almost-Cliques

Finally, we come to the most novel part of this section. Recall that as
discussed earlier, palette sparsification (and thus our own palette-sampling)
is doomed to fail for $\Delta$-coloring. To bypass this, we rely on the
_helper structures_ defined in Definitions 4.7 and 4.6, which, combined with
the palette sparsification-type approach of palette-sampling, allow us to
color the graph.

The first challenge here is that we obviously cannot afford to find the
neighborhood of every vertex, and we do not know _during_ the stream which
vertices will satisfy the properties we need for these structures. We step
around this by (crucially) using randomization to sample the “right” vertices.
The second and main challenge is that for some almost-cliques (say, a critical
almost-clique with only one non-edge), we may actually have to recover
neighborhood of _all_ vertices in the almost-clique before finding the
required helper structure; but doing this naively requires too much space.
Instead, we use the sparse recovery matrices of Section 3.2, in conjunction
with the decomposition found by find-decomposition, to recover these parts
much more efficiently.

Input: Graph $G=(V,E)$ with known vertices $V$ and streaming edges $E$.

For every $r\in R=\\{2^{i}\mid 0\leqslant
i\leqslant{\left\lceil{\log\Delta}\right\rceil}\\}$:111111Think of $r$ as a
fixed sampling rate from a set of rates $R$.

  1. $(i)$

Sample each vertex $v\in V$ in a set $V_{r}$ independently with probability
$\min\\{1,\frac{\beta}{\varepsilon\cdot r}\\}$.

  2. $(ii)$

Construct the $(2r\times n)$ _Vandermonde matrix_ $\Phi^{\textnormal{V}}_{r}$
(see Proposition 3.5) and sample an $(\alpha\times n)$ _random matrix_
$\Phi^{\textnormal{R}}_{r}$ (see Proposition 3.6) over the field
$\mathbb{F}_{p}$ where $p$ is a fixed prime larger than $n$ and smaller than,
say, $n^{2}$, and $\alpha$ is the parameter in Eq. 1.

  3. $(iii)$

For each vertex $v\in V_{r}$, define a vector $y(v)\in\mathbb{F}_{p}^{\,2r}$
and $z(v)\in\mathbb{F}_{p}^{\,\alpha}$ initially set to $0$. For any incoming
edge $\\{u,v\\}$ in the stream, update

$y(v)\leftarrow
y(v)+\Phi^{\textnormal{V}}_{r}\cdot\mathbf{e}_{u}\qquad\text{and}\qquad
z(v)\leftarrow z(v)+\Phi^{\textnormal{R}}_{r}\cdot\mathbf{e}_{u},$

where $\mathbf{e}_{u}$ is the $n$-dimensional vector which is $1$ on
coordinate $u$ and $0$ everywhere else.

Algorithm 3 The sparse-recovery algorithm.

Let us start by bounding the space of this algorithm.

######  Lemma 4.20.

sparse-recovery uses $O(n\log^{4}{n})$ bits of space.

######  Proof 4.21.

For each $r\in R$, each $v\in V$ is sampled into $V_{r}$ with probability (at
most) $\frac{\beta}{\varepsilon r}$, which means the expected size of $V_{r}$
is (at most) $\frac{\beta n}{\varepsilon r}$. Since each sample is
independent, we have by Chernoff bound (Proposition 3.1) that,

$\displaystyle\leqslant\exp\left(-\frac{\beta n}{4\varepsilon
r}\right)\leqslant\exp\left(-\frac{100n\log n}{4\varepsilon\cdot
2\Delta}\right)\leqslant n^{25/2\cdot\varepsilon}\ll 1/\mbox{\rm poly}{(n)},$

by the choice of $\varepsilon=\Theta(\log^{-1}(n))$ in Eq. 1.

Combining with the union bound over $O(\log{\Delta})$ choices of $r\in R$, we
have that each $V_{r}$ is of size at most $\frac{2\beta n}{\varepsilon r}$
with high probability. For each $v\in V_{r}$, Algorithm 3 stores two vectors
$y(v)$ and $z(v)$ that require $O(r\cdot\log{p})$ and $O(\alpha\cdot\log{p})$
bits, respectively, where $p$ is the order of the field $\mathbb{F}_{p}$.
This, together with the bound on $V_{r}$ and since $\alpha=\Theta(1)$ by Eq. 1
means that the total number of bits needed to store these vectors is
$O(\varepsilon^{-1}\cdot\beta n\log{p}\cdot\log{\Delta})=O(n\log^{4}{n})$ bits
(where we used the fact that both $\varepsilon^{-1}$ and $\log{p}$ are bounded
by $O(\log{n})$).

Finally, the algorithm does not need to explicitly store the Vandermonde
matrix for $\Phi^{\textnormal{V}}_{r}$ (as each of its entries can be easily
generated in $O(\log{p})$ space at any point) and can store each random matrix
$\Phi^{\textnormal{V}}_{r}$ in $O(\alpha\cdot n\log{p})=O(n\log{n})$ bits as
$\alpha=\Theta(1)$ and $\log{p}=O(\log{n})$. Thus, for all $r\in R$, we also
need to store $O(n\log^{2}{n})$ bits to store the random matrices. Overall,
the total space of the algorithm is still $O(n\log^{4}{(n)})$, concluding the
proof.

We now switch to proving the main properties of sparse-recovery for our
purpose. Before getting into details however, we state a standard observation
about linear transformations (namely, $\Phi^{\textnormal{V}}_{r}$ and
$\Phi^{\textnormal{R}}_{r}$ in sparse-recovery) over a stream of updates.

Fix any $r\in R$ and $v\in V_{r}$ in sparse-recovery. At the end of the
stream,

$y(v)=\Phi^{\textnormal{V}}_{r}\cdot\chi(N(v))\qquad\text{and}\qquad
z(v)=\Phi^{\textnormal{R}}_{r}\cdot\chi(N(v)),$

where $\chi(N(v))\in\left\\{0,1\right\\}^{V}$ is the characteristic vector of
$N(v)$.

######  Proof 4.22.

We only prove the equation for $y(v)$; the one for $z(v)$ follows similarly.
Initially, we set $y(v)=0$. Then, during the stream, whenever we see the edge
$\\{u,v\\}$ for each $u\in N(v)$, we update $y(v)$ by adding
$\Phi^{\textnormal{V}}_{r}\cdot\mathbf{e}_{u}$ to it. As
$\Phi^{\textnormal{V}}_{r}$ is a linear transformation, we have,

$y(v)=\sum_{u\in
N(v)}\Phi^{\textnormal{V}}_{r}\cdot\mathbf{e}_{u}=\Phi^{\textnormal{V}}_{r}\cdot\left(\sum_{u\in
N(v)}\mathbf{e}_{u}\right)=\Phi^{\textnormal{V}}_{r}\cdot\chi(N(v)),$

concluding the proof.

Recall from Proposition 3.5 that given $\Phi^{\textnormal{V}}_{r}\cdot x$ for
an $r$-sparse vector $x\in\mathbb{F}_{p}^{n}$, we can recover $x$ in
polynomial time, and by Proposition 3.6, we can test our recovered vector to
make sure with high probability that it is indeed equal to $x$. We use this
idea combined with the fact that at the end of the stream we know a sparse-
dense decomposition of the graph to recover one helper structure for each
almost-clique (that needs one). We start with the key part that handles the
critical-helper structures (Definition 4.6). There will also be a simpler part
that handles friendly-helper structures almost-cliques (Definition 4.7).

###### Finding Critical-Helper Structures.

We start by recovering a critical-helper structure for any critical almost-
clique as defined in Definition 4.6. Let $K$ be a critical almost-clique and
$v$ be a vertex in $K$. Define the vector $x(v):=\chi(N(v))-\chi(K)$. For any
coordinate $u\in[n]$ in $x(v)$,

$\displaystyle x(v)_{u}=\begin{cases}\phantom{-}0&\textnormal{if }u\notin
N(v)\cup K\textnormal{ or }u\in N(v)\cap K\\\ \phantom{-}1&\textnormal{if
}u\in N(v)\setminus K\\\ p-1&\textnormal{if }u\in K\setminus N(v)\end{cases},$
(2)

as we do the computation over $\mathbb{F}_{p}$. Notice that since $v$ belongs
to the almost-clique $K$, by Definition 3.3, size of both $N(v)\setminus K$
and $K\setminus N(v)$ is at most $10\varepsilon\Delta$. Thus, $x(v)$ is
already considerably sparser than $\chi(N(v))$. In the following, we are going
to take this idea to the next level to recover a critical-helper structure for
$K$ using the vectors computed by sparse-recovery.

######  Lemma 4.23.

There exists an algorithm that given a critical almost-clique $K$ (Definition
4.1), with high probability, finds a critical-helper structure $(v,u,N(v))$ of
$K$ (Definition 4.6) using the information gathered by sparse-recovery.

######  Proof 4.24.

(4.24 gives an illustration that might be helpful to refer to during the
proof.) For any vertex $w\in K$, define:

  * •

$\overline{N}_{K}({w}):=K\setminus N(w)$: as the non-edge neighborhood of $w$
in $K$ and $\overline{\deg}_{K}({w})=\left|{\overline{N}_{K}({w})}\right|$ as
the non-edge degree of $w$.

Define $w^{*}$ as the vertex that maximizes this non-edge degree, i.e.,
$w^{*}=\operatorname*{arg\,max}_{w\in K}\,\,\overline{\deg}_{K}({w})$. By
Section 4.1, we have $\overline{\deg}_{K}({w^{*}})\geqslant 1$. We first have
the following simple claim that will be crucial in finding the neighborhood of
at least one vertex in $\overline{N}_{K}({w^{*}})$ using sparse recovery.

$w^{*}$$\vdots$$v$$K$$\left|{N(v)\setminus
K}\right|\leqslant\overline{\deg}_{K}({w^{*}})\approx r$$\left|{K\setminus
N(v)}\right|\leqslant\overline{\deg}_{K}({w^{*}})\approx r$

Finding a critical-helper: With high probability, there is a vertex
$v\in\overline{N}_{K}({w^{*}})$ which is sampled in $V_{r}$.

######  Claim 10.

Let $r\in R$ be the smallest integer such that $r\geqslant
2\cdot\overline{\deg}_{K}({w^{*}})$. Then, for every
$w\in\overline{N}_{K}({w^{*}})$, the vector $x(w):=\chi(N(w))-\chi(K)$ is
$r$-sparse.

Fix any $w\in\overline{N}_{K}({w^{*}})$. By the definition of $w^{*}$, we have
$\overline{\deg}_{K}({w})\leqslant\overline{\deg}_{K}({w^{*}})\leqslant r/2$.
At the same time, since $K$ is a critical almost-clique and thus has size
$\Delta+1$, this means that the number of neighbors of $w$ outside $K$ is also
at most $\overline{\deg}_{K}({w^{*}})\leqslant r/2$. By Eq. 2, this means that
$x(w)$ has at most $r$ non-zero entries.

Consider the parameter $r$ of Claim 10. We have that
$\overline{\deg}_{K}({w^{*}})\geqslant r/4$ as elements of $R$ are within a
factor two of each other and by the value of $r$. Given that each vertex is
chosen in $r$ with probability $\min\left\\{1,\beta/(\varepsilon\cdot
r)\right\\}$, we have,

$\operatorname*{\textnormal{Pr}}\left(V_{r}\cap\overline{N}_{K}({w^{*}})=\emptyset\right)\leqslant\left(1-\frac{\beta}{\varepsilon\cdot
r}\right)^{r/4}\leqslant\exp\left(-\frac{\beta}{4\varepsilon}\right)\ll
1/\mbox{\rm poly}{(n)},$

by the choice of $\beta=\Theta(\log{n})$ and
$\varepsilon=\Theta(\log^{-1}(n))$ in Eq. 1. In the following, we condition on
the high probability event that a vertex $v\in\overline{N}_{K}({w^{*}})$ is
sampled in $V_{r}$. For now, let us _assume_ that we know the identity of this
vertex $v$ in $V_{r}$.

Firstly, by Claim 10, we have that the vector $x(v)$ is $r$-sparse. Secondly,
since $v\in V_{r}$, sparse-recovery has computed
$y(v)=\Phi^{\textnormal{V}}_{r}\cdot\chi(N(v))$ by Section 4.4 and since we
are given $K$, we can also compute $\Phi^{\textnormal{V}}_{r}\cdot\chi(K)$.
Thus, by linearity, we can compute $\Phi^{\textnormal{V}}_{r}\cdot x(v)$ this
way. Finally, since $x(v)$ is $r$-sparse, by Proposition 3.5, we can actually
recover $x(v)$ from $\Phi^{\textnormal{V}}_{r}\cdot x(v)$. But again, since we
know $\chi(K)$, this gives us $\chi(N(v))$ and in turn $N(v)$ as well. Thus,
the algorithm can return the critical-helper structure $(v,u,N(v))$ for
$u=w^{*}$ which satisfies all the properties (as $(v,w^{*})$ is a non-edge).

It only remains the remove the assumption on the knowledge of identity of $v$
in $V_{r}$ (and possibly the value of $r$ itself). For this, we simply iterate
over all vertices $w\in K$ and for each one run
$\Phi^{\textnormal{V}}_{r}\cdot x(w)$ and $\Phi^{\textnormal{R}}_{r}\cdot
x(w)$ as described above for all values of $r\in R$ (by using $z(v)$ in place
of $y(v)$ when computing the latter). As outlined in Section 3.2, we can now
apply Proposition 3.6 to the outcome of each sparse recovery to get that with
high probability, any vector $\chi(N(w))$ that we recover is correct. Since we
know that the vertex $v$ will _not_ output ’fail’, we are guaranteed that with
high probability we will return a valid critical-helper structure, concluding
the proof.

###### Finding Friendly-Helper Structures.

We now switch to finding a friendly-helper structure of Definition 4.7 for
each almost-clique $K$ that is unholey and _not_ lonely.

######  Lemma 4.25.

There exists an algorithm that given an unholey and not lonely almost-clique
$K$ (Definition 4.1) and a vertex $u\notin K$ which is not a stranger to $K$,
with high probability, finds a friendly-helper structure $(u,v,w,N(v),N(w))$
of $K$ (Definition 4.7) using the information gathered by sparse-recovery.

######  Proof 4.26.

Define $r_{\max}=\max_{r\in R}r$. We have the following straightforward
claim.121212A careful reader may notice that in this claim, we actually do not
really need sparse recovery; we could have simply stored all edges of vertices
sampled in $V_{r_{\max}}$ explicitly during the stream. However, given that we
indeed need sparse recovery for all other ranges of $V_{r}$ for $r\in R$ in
the previous part, we use a unified approach for $V_{r_{\max}}$ as well.

######  Claim 11.

For any vertex $v\in V$, with probability at least
$\frac{\beta}{2\varepsilon\cdot\Delta}$, we can recover the set $N(v)$.

Note that $r_{\max}=2^{{\left\lceil{\log\Delta}\right\rceil}}$ which is
between $\Delta$ and $2\Delta$. Recall that each $v$ is sampled into the set
$V_{r_{\max}}$ with probability $\frac{\log n}{\varepsilon\cdot r_{\max}}$,
which is at least $\frac{\log n}{2\varepsilon\cdot\Delta}$. And then note that
for each vertex $v$ in $V_{r_{\max}}$, sparse-recovery stores
$\Phi^{\textnormal{V}}_{r_{\max}}\cdot\chi(N(v))$ by Section 4.4. By
Proposition 3.5, we can recover $N(v)$ from
$\Phi^{\textnormal{V}}_{r_{\max}}\cdot\chi(N(v))$ for every $v\in
V_{r_{\max}}$, concluding the proof of the claim.

We prove Lemma 4.25 using this claim. Firstly, by property $iv)$. of
Definition 3.3, there are also at least $10\varepsilon\Delta$ vertices $w$ in
$K$ that are not neighbors of $u$. By Claim 11, we recover $N(w)$ for any such
choice of $w$ with probability at least ${\beta}/({2\varepsilon\cdot\Delta})$.
As such, we have,

$\operatorname*{\textnormal{Pr}}\left(\textnormal{$N(w)$ is not recovered for
any $w\in K\setminus
N(u)$}\right)\leqslant\left(1-\frac{\beta}{2\varepsilon\cdot\Delta}\right)^{\varepsilon\cdot\Delta}\leqslant\exp\left(-\frac{\beta}{2}\right)\leqslant
n^{-50},$

by the choice of $\beta=100\log{n}$ in Eq. 1. In the following, we further
condition on the high probability event that for some $w\in K\setminus N(u)$,
we have recovered $N(w)$. Similar to the proof of Lemma 4.23, let us _assume_
that we know the identity of $w$.

Now consider $N(w)\cap N(u)\cap K$; since $\left|{N(u)\cap
K}\right|\geqslant\Delta/\beta$ as $u$ is not a stranger to $K$ (Definition
4.4), and $\left|{K\setminus N(w)}\right|\leqslant 10\varepsilon\Delta$ by
property $ii)$. of Definition 3.3, we have that

$\left|{N(w)\cap N(u)\cap
K}\right|\geqslant\Delta/\beta-10\varepsilon\Delta>\Delta/2\beta$

by the choice of parameters $\varepsilon<10^{-6}\cdot 1/\beta$ in Eq. 1. By
the same argument as above, we have,

$\operatorname*{\textnormal{Pr}}\left(\textnormal{$N(v)$ not recovered for any
$v\in N(w)\cap N(u)\cap
K$}\right)\leqslant\left(1-\frac{\beta}{2\varepsilon\cdot\Delta}\right)^{\Delta/2\beta}\leqslant\exp\left(-\frac{1}{2\varepsilon}\right)\leqslant
n^{-100},$

by the choice of $\varepsilon$ in Eq. 1. We now have: $u$ is a vertex which is
not a stranger to $K$, $w$ is a non-neighbor of $u$ in $K$ and we have $N(w)$,
and $v$ is a neighbor of both $u$ and $w$ and we have $N(v)$. Thus, we can
return $(u,v,w,N(v),N(w))$ as a friendly-helper structure of $K$.

Finally, removing the assumption on the knowledge of $v$ and $w$ is exactly as
in the proof of Lemma 4.23: we simply go over all choices of vertices in $K$
that we have sampled in $V_{r_{\max}}$ and check whether any pairs of them
satisfy the requirements of the structure or not—by the above argument, with
high probability, we will find a pair.

####  4.5 Listing the Information Collected by the Algorithm

For the ease of reference in the analysis, we now take stock of what all our
algorithms collected about the graph from the stream. In particular, with high
probability, we have the following information at the end of the stream:

  1. $\emph{1}.$

A list of sampled colors $L(v)$ for every vertex $v\in V$ as specified in
Algorithm 1.

_Proof:_ Follows from the definition of palette-sampling in Algorithm 1.

  2. $\emph{2}.$

The conflict graph $H$ consisting of every edge $(u,v)$ in the graph where
$L(u)\cap L(v)\neq\emptyset$.

_Proof_ : Follows from the definition of palette-sampling in Algorithm 1.

  3. $\emph{3}.$

A decomposition of $G$ into sparse vertices and almost-cliques as specified in
Proposition 3.4.

_Proof:_ Follows from Lemma 4.14 for find-decomposition in Algorithm 2.

  4. $\emph{4}.$

A collection $\mathcal{K}_{\textnormal{friendly}}$ of almost-cliques that
contains _all_ friendly almost-cliques and _no_ lonely almost-clique, and for
each $K\in\mathcal{K}_{\textnormal{friendly}}$, one vertex $u\notin K$ which
is not a stranger to $K$.

_Proof:_ Follows from Part ($\emph{3}.$) and Lemma 4.18 for find-decomposition
in Algorithm 2.

  5. $\emph{5}.$

A collection $\mathcal{K}_{\textnormal{lonely}}$ of almost-cliques that
contains _all_ lonely almost-cliques and _no_ friendly almost-clique.
Moreover,
$\mathcal{K}_{\textnormal{friendly}}\sqcup\mathcal{K}_{\textnormal{lonely}}$
partition _all_ almost-cliques, which also implies that every social almost-
clique belongs to exactly one of these two collections.

_Proof:_ Follows from Parts ($\emph{3}.$), ($\emph{4}.$), and Lemma 4.18 for
find-decomposition in Algorithm 2.

  6. $\emph{6}.$

A collection of $\mathcal{K}_{\textnormal{critical}}$ of critical almost-
cliques and for each $K\in\mathcal{K}_{\textnormal{critical}}$, a critical-
helper structure $(u,v,N(v))$ of Definition 4.6.

_Proof:_ Follows from Part ($\emph{3}.$) and Lemma 4.23 for sparse-recovery in
Algorithm 3.

  7. $\emph{7}.$

A collection of friendly-helper structures
$\left\\{(u,v,w,N(v),N(w))\right\\}$ of Definition 4.7, one for each
$K\in\mathcal{K}_{\textnormal{friendly}}$ such that $u$ is the vertex
specified for $K\in\mathcal{K}_{\textnormal{friendly}}$ in Part ($\emph{4}.$).

_Proof:_ Follows from Part ($\emph{4}.$) and Lemma 4.25 for sparse-recovery in
Algorithm 3.

  8. $\emph{8}.$

The recovery graph $H^{+}$ consisting of all edges in the critical-helper
structures of Part ($\emph{6}.$) and in the friendly-helper structures of Part
($\emph{7}.$).

_Proof:_ Follows from Parts ($\emph{6}.$) and ($\emph{7}.$).

We shall note that at this point, we covered all the process that is done by
our algorithm _during_ the stream and what remains is to prove this
information is useful, i.e., we can indeed color the graph in the _post-
processing step_ using this information. This is the content of the next
section.

Before moving on, we should note that, with high probability, the space
complexity of $(i)$ palette-sampling is $O(n\log^{7}{n})$ bits by Lemma 4.10,
$(ii)$ find-decomposition is $O(n\log^{4}{n})$ bits by Lemma 4.12, and $(iii)$
sparse-recovery is $O(n\log^{4}{n})$ by Lemma 4.20. Thus, our entire streaming
algorithm takes $O(n\log^{7}{n})$ space. This adhere to the space complexity
promised in Theorem 1.1.

######  Remark 4.27.

As stated, the space complexity of our algorithm is bounded with high
probability but not in the worst-case. This is standard to fix; simply run the
algorithm as it is and whenever it attempted to use more than, say, $100$
times, the space guaranteed by its expectation, terminate it and “charge” the
failure probability to the error.

######  Remark 4.28 (Removing Prior Knowledge of $\Delta$).

We observe that this semi-streaming algorithm does not really need to know
$\Delta$ before the stream begins. In particular, we can run $O(\log n)$
independent copies of the algorithm, each with a difference “guess” of
$\Delta\in\left\\{2^{k}\mid 2^{k}\leqslant 2n\right\\}$. At the same time, we
can compute $\Delta$ at the end of the stream by simply counting for each
vertex the number of edges incident to it in $O(n\log n)$ space.

An overestimate of $\Delta$ does not hurt us in terms of space usage, but an
underestimate can (for example, if we guess $\Delta=1$, and the input includes
a clique on $n-1$ vertices, the algorithm stores the entire graph). Hence, if
at any point (for any guess $\Delta$), if a vertex has degree larger than
$2\Delta$, we stop that run of the algorithm. Now, at the end of the stream we
will have:

  * •

The actual maximum degree $\Delta$.

  * •

The output of the algorithm for $\Delta^{\prime}$ and $2\Delta^{\prime}$ such
that $\Delta^{\prime}\leqslant\Delta\leqslant 2\Delta^{\prime}$.

But now we can get the desired samples by “resampling” the outputs from
Algorithms 1, 2 and 3. In particular, for each vertex $v\in V$, and each color
$c\in L(v)$ from the run of Algorithm 1 with guess $\Delta^{\prime}$, we keep
$c$ with probability $\Delta^{\prime}/\Delta$. Since we are only dropping
colors from the palettes, this process only removes some edges from the
conflict graph. The samples of Algorithm 2 are adapted in a similar manner.
Finally, the set of sampling rates $R$ in Algorithm 3 for $2\Delta^{\prime}$
is a superset of that for a (hypothetical) run with the correct guess of
$\Delta$, so we can just ignore the vectors corresponding to unused sample
rates.131313Technically, there is no need to even run Algorithm 3 separately
for different guesses of $\Delta$.

Hence at the end of the stream we know $\Delta$ and can adapt the samples as
required, so the coloring procedure in the next section can proceed as normal.

###  5 The Coloring Procedure

We now describe the coloring procedure that we use to find a $\Delta$-coloring
of the graph. This procedure is agnostic to the input graph, in the sense that
we run it after processing the stream, and it only uses the information we
gathered in the previous section, listed in Section 4.5 (throughout, we
condition on the high probability event that the correct information is
collected from the stream).

The general framework in our coloring procedure is the following: We will
maintain a proper partial $\Delta$-coloring $C\colon
V\to\left[\Delta\right]\cup\\{\perp\\}$ (as defined in Section 3). We then go
through different phases in the coloring algorithm and each phase updates $C$
by coloring certain subsets of vertices, say, (a subset of) sparse vertices,
or certain almost-cliques. These new colorings are typically going to be
extensions of $C$ but in certain cases, we crucially have to go back and
“edit” this partial coloring, i.e., come up with a new proper partial coloring
which is no longer an extension the current one. Eventually, we will color all
the vertices of the graph and end up with a proper $\Delta$-coloring.

In the following, we present the order of the phases of our coloring procedure
and the task we expect from each one. Each phase shall use a different list of
colors $L_{1}(\cdot),\cdots,L_{6}(\cdot)$ computed by palette-sampling
(Algorithm 1) when updating the partial coloring. We also note that the order
of running these phases is crucial as some of them present further guarantees
for subsequent phases, and some of them need to assume certain properties of
the current partial coloring which will no longer remain true if we change the
order of phases.

On the high level, the coloring procedure is as follows (Table 1 give a
summary of which combination of almost-cliques are handled in which phase).

  * •

Phase 1 – One-Shot Coloring (Section 5.1): We use the single color sampled in
$L_{1}(v)$ for every vertex $v\in V$ to color a large fraction of vertices.
The effect of this coloring is that it “sparsifies” the graph for sparse
vertices. We note that this part is standard and appears in many other
coloring results starting from, to our knowledge, [51]; see [7] for more
details.

  * •

Phase 2 – Lonely (or Social) Small Almost-Cliques (Section 5.2): Recall that
from Part ($\emph{5}.$) of Section 4.5, we have a list of
$\mathcal{K}_{\textnormal{lonely}}$ of almost-cliques that contains all lonely
almost-cliques and potentially some social ones. We can easily also identify
which of these almost-cliques are small (Definition 4.1) based on their size.

We will color all these small almost-cliques in
$\mathcal{K}_{\textnormal{lonely}}$ by colors in $L_{2}(\cdot)$. This requires
a novel argument that uses the facts that: $(i)$ these almost- cliques are
“loosely connected” to outside (no “high degree” neighbor, formally friend
vertices, in their neighborhood), and $(ii)$ the coloring outside only used a
limited set of colors, namely, is sampled from $L_{1}(\cdot)$ and
$L_{2}(\cdot)$ so far and is thus not “too adversarial” (recall the discussion
we had in Section 2.1 regarding necessity of such arguments). Moreover, the
coloring in this phase is an extension of the last one.

  * •

Phase 3 – Sparse Vertices (Section 5.3): We then conclude the coloring of all
sparse vertices using the sampled lists $L_{3}(v)$ for every sparse vertex
$v\in V$ (by Part ($\emph{3}.$) of Section 4.5, we know these vertices). This
part is also a standard argument as a continuation of Phase 1. But to apply
this standard argument, we use the fact that even though we interleaved the
standard approach with Phase 2 in the middle, since that coloring was only an
extension of Phase 1 (meaning it did not _recolor_ any vertex colored in Phase
1), the argument still easily goes through.

The coloring in this phase is also an extension of the last one. However, now
that all sparse vertices are colored, we go ahead and remove the color of any
vertex which is not sparse and nor is colored by Phase 2 (these are remnants
of one-shot coloring in Phase 1 and we no longer need them now that all sparse
vertices are colored). This is just to simplify the analysis for later parts.

It is worth mentioning that this interleaving of Phase 2 in the middle of
Phase 1 and 3 is crucial for our arguments (this is the chicken-and-egg
problem mentioned in Section 2.2): the lists $L_{3}(\cdot)$ used in Phase 3
are much larger than the rest and thus the “not-too-adversarial” property of
coloring of outside vertices in Phase 2 will no longer be guaranteed had we
changed the order of Phase 2 and 3; at the same time, changing the order of
Phase 1 and 2 will also destroy the “sparsification” guarantee provided by
Phase 1 for sparse vertices.

Type | _Holey_ | _Unholey_
---|---|---
_Friendly_ | _Social_ | _Lonely_ | _Friendly_ | _Social_ | _Lonely_
_Small_ | Phase 4 | Phases 2 or 4 | Phase 2 | Phase 6 | Phases 2 or 6 | Phase 2
_Critical_ | Phase 4 | Phase 4 | Phase 4 | Phase 5 | Phase 5 | Phase 5
_Large_ | Phase 4 | Phase 4 | Phase 4 | – | – | –
Table 1: A list of all combination of different almost-cliques together with
the phase of our coloring procedure that is responsible for handling them.
Note that by Section 4.1, there are no unholey large almost-cliques. The
sparse vertices are handled in Phase 1 and Phase 3. Moreover, Phase 1 may
color some vertices of lonely (or social) small almost-cliques that we are
_not_ allowed to recolor (we can recolor all the other remnants of Phase 1
after Phase 3).

  * •

Phase 4 – Holey Almost-Cliques (Section 5.4): The next step is to color holey
almost-cliques (Definition 4.3), i.e., the ones with
$\Omega(\varepsilon\Delta)$ non-edges inside them, using colors sampled in
$L_{4}(\cdot)$. We note that we actually do _not_ know which almost-cliques
are holey and which ones are not.141414Technically, we could have designed a
semi-streaming algorithm that also recovers this information about the
decomposition (at least approximately). However, as we explain next, this is
not needed. Instead, we simply run this phase over all remaining almost-
cliques and argue that all the holey ones (and possibly some other ones) will
get fully colored as desired.

The proof of this phase is a simple generalization of a similar proof used in
the palette sparsification theorem of [7], which even though quite technical,
does not involve much novelty from us in this work. The coloring in this phase
is an extension of the last one.

  * •

Phase 5 – Unholey Critical Almost-Cliques (Section 5.5): By Section 4.1, all
large almost-cliques are holey. Thus, the largest remaining almost-cliques at
this point are unholey critical almost-cliques. We know these almost-cliques
in $\mathcal{K}_{\textnormal{critical}}$ by Part ($\emph{6}.$) of Section 4.5
(the holey ones are already colored and it is possible, yet unlikely, that
even some of unholey ones are also colored in Phase 4). We color the remainder
of $\mathcal{K}_{\textnormal{critical}}$ now.

In the previous phases, we solely colored vertices from lists $L(\cdot)$
sampled in palette-sampling. But we already know that such an approach is just
not going to work for unholey critical almost-cliques (recall the example in
Figure 1(b) discussed in Section 2.1). This is the first time we deviate from
this approach (and thus deviate from palette sparsification-type arguments).

We now will use the critical-helper structures (Definition 4.6)—which our
streaming algorithm collected in Part ($\emph{6}.$) of Section 4.5—and a new
“out of palette” coloring argument, wherein we color one of the vertices of
the almost-clique using a color not sampled for it, so that _two_ vertices of
the almost-clique are colored the _same_. We then show that this already buys
us enough flexibility to color the remaining vertices using lists
$L_{5}(\cdot)$ of vertices similar to Phase 4. The coloring in this phase is
also an extension of the last one.

  * •

Phase 6 – Unholey Friendly (or Social) Small Almost-Cliques (Section 5.6): It
can be verified, after a moment of thought or better yet by consulting Table
1, that the only almost-cliques remained to color are the ones that are
unholey, small, and also not lonely. They are perhaps the “most problematic”
ones and are handled last.151515It is quite natural to ask if these almost-
cliques are the “hardest” to color, why do we wait to color them after
everything else, at which time, our hands might be too tied? There are two
closely related answers: $(i)$ they may just be connected to each other (or
rather the graph can only consists of these types of almost-cliques) and thus
we anyway have to deal with at least one of them after having colored the rest
of the graph; and $(ii)$ even though they are “hard” to color, they are
somewhat “more robust” also, compared to say Phase 2 almost-cliques, in that
we can color them even when their outside neighbors are colored adversarially
by using a key recoloring step. These almost-cliques also require the “out of
palette” coloring argument used in Phase 5, but even this is not enough for
them (we already discussed this regarding Figure 4(b) in Section 2.2). In
particular, unlike Phase 4 and 5 that allowed for coloring of the almost-
cliques even in the presence of adversarial coloring of outside vertices, this
simply cannot be true for this phase (as shown in Figure 4(b)); at the same
time, unlike Phase 2 almost-cliques, we cannot hope for a “random” coloring of
outside vertices.

To handle these almost-cliques, we rely on our friendly-helper structures
(Definition 4.7) combined with a recoloring step: in particular, we recolor
one vertex outside of the almost-clique using the sampled lists $L_{6}(\cdot)$
and show that this recoloring, plus another out of palette coloring argument,
again buys us enough flexibility to color these almost-cliques also from lists
$L_{6}(\cdot)$ (we note that this out of palette coloring argument is in fact
different from the one used in Phase 5). Finally, due to the recoloring step,
the coloring in this phase is no longer an extension of the last one.

After all these phases, we have finished coloring all the vertices. In other
words, we now have $\Delta$-coloring of the entire graph as desired. This will
then conclude the proof of Theorem 1.1.

In the rest of this section, we go over each of these phases in details and
present the algorithm and analysis for each one (postponing the less novel
ones to Appendix B). We again emphasize that to find the final
$\Delta$-coloring, this phases must be executed _in this particular order_.

####  5.1 Phase 1: One-Shot Coloring

We start with the standard _one-shot coloring_ algorithm used extensively in
the coloring literature (to the best of our knowledge, this idea has appeared
first in [51]). The purpose of this algorithm is to color many _pairs_ of
vertices in the neighborhood of sparse vertices using the _same_ color (recall
that neighborhood of sparse vertices contains many non-edges which can
potentially be colored the same). This then effectively turn the sparse
vertices into “low degree” ones and reduces the problem from $\Delta$-coloring
to $O(\Delta)$-coloring which is much simpler.

Input: The vertex set $V$, the conflict-graph $H$, and the list $L_{1}(v)$ for
every vertex $v\in V$.

  1. $(i)$

For every vertex $v\in V$:

     * •

_Activate_ $v$ independently with probability $1/\alpha$ for parameter
$\alpha=\Theta(1)$ in Eq. 1.

     * •

If $v$ is activated, set $x(v)$ to be the only color in $L_{1}(v)$, otherwise
set $x(v)=\perp$.

  2. $(ii)$

For every vertex $v\in V$, set $C_{1}(v)=x(v)$ if for all $u\in N_{H}(v)$,
$x(v)\neq x(u)$; otherwise, set $C_{1}(v)=\perp$. In words, any activated
vertex $v$ keeps its color $x(v)$ iff it is not used anywhere in its
neighborhood.

Algorithm 4 The one-shot-coloring algorithm.

We have the following basic observation about the correctness of one-shot-
coloring.

The partial coloring $C_{1}$ computed by one-shot-coloring is a proper partial
$\Delta$-coloring in $G$.

######  Proof 5.1.

It is immediate to verify that $C_{1}$ is a proper partial coloring in $H$
simply because we remove both colors of any monochromatic edge. To see this
also holds in $G$, note that for any edge $(u,v)\in G$, if
$C_{1}(u)=C_{1}(v)\neq\perp$, then it means that $x(u)=x(v)$ which in
particular also means $L_{1}(u)\cap L_{1}(v)\neq\emptyset$. Thus, the conflict
graph $H$ contains the edge $(u,v)$ also, a contradiction with $C_{1}$ being a
proper partial coloring of $H$.

We now get to the main property of one-shot-coloring. The effect of this
partial coloring is that the neighborhood of every _sparse_ vertex $v\in V$
becomes abundant with available colors (compared to the remaining degree of
$v$). In particular, recall the definition of $\mathsf{coldeg}_{C_{1}}(v)$ as
the colored degree of a vertex $v$ and $\mathsf{avail}_{C_{1}}(v)$ as the
number of colors available to $v$ with respect to a partial coloring $C_{1}$
(defined in Section 3). Then we have the following guarantee for the one-shot-
coloring algorithm:

######  Lemma 5.2.

For every sparse vertex $v\in V_{\textnormal{sparse}}$, in the partial
coloring $C_{1}$ of one-shot-coloring,

$\mathsf{avail}_{C_{1}}(v)>(\deg{(v)}-\mathsf{coldeg}_{C_{1}}(v))+\frac{\varepsilon^{2}\cdot\Delta}{2\alpha}$

with high probability, where the randomness is only over the choice of the
lists $L_{1}(v)$.

The proof is postponed to Section B.1.

####  5.2 Phase 2: Lonely (or Social) Small Almost-Cliques

In this section, we will describe an algorithm that extends the partial
coloring $C_{1}$ of Phase 1 to all small almost-cliques that are in
$\mathcal{K}_{\textnormal{lonely}}$ of Part ($\emph{5}.$) of Section 4.5
(which in particular, contains all lonely almost-cliques and no friendly
almost-clique). We are going to work with palette graphs introduced in Section
3.3 in this phase. The algorithm is simply as follows.

Input: A proper partial $\Delta$-coloring $C$, a small almost-clique
$K\in\mathcal{K}_{\textnormal{lonely}}$, the conflict-graph $H$, and the list
$L_{2}(v)$ for every vertex $v\in K$.

  1. $(i)$

Construct the sampled palette graph
$\mathcal{G}_{\textnormal{{Sample}}}=(\mathcal{L},\mathcal{R},\mathcal{E}_{\textnormal{{Sample}}})$
of the almost-clique $K$, $C$, and $\SS:=\left\\{L_{2}(v)\mid v\in K\right\\}$
(according to Definition 3.9).

  2. $(ii)$

Find an $\mathcal{L}$-perfect matching $\mathcal{M}$ in
$\mathcal{G}_{\textnormal{{Sample}}}$ and output ‘fail’ if it does not exists.
Otherwise, update $C(v)=\mathcal{M}(v)$ where $\mathcal{M}(v)$ denotes the
color corresponding to the color-node matched to the vertex-node $v$ by the
matching $\mathcal{M}$.

Algorithm 5 The algorithm of Phase 2 for coloring each small almost-clique in
$\mathcal{K}_{\textnormal{lonely}}$.

In Phase 2, we start by setting $C$ to be equal to $C_{1}$ of Phase 1 and then
successively run Algorithm 5 on each small almost-clique
$K\in\mathcal{K}_{\textnormal{lonely}}$ while updating $C$ as described by the
algorithm. At the end, we let $C_{2}$ denote the final partial
$\Delta$-coloring.

######  Lemma 5.3.

With high probability, $C_{2}$ computed by Phase 2 is a proper partial
$\Delta$-coloring in $G$ that is an extension of $C_{1}$ and colors all small
almost-cliques in $\mathcal{K}_{\textnormal{lonely}}$.

The randomness in this lemma is only over the randomness of one-shot-coloring
(activation probabilities) and choice of the lists $L_{1}(v)$ and $L_{2}(v)$
for all $v\in V$.

We prove Lemma 5.3 in the rest of this subsection. The fact that $C_{2}$ is an
extension of $C_{1}$ follows immediately from the definition of the algorithm
as for every $K\in\mathcal{K}_{\textnormal{lonely}}$, the corresponding
$\mathcal{G}_{\textnormal{{Sample}}}$ only contains vertices uncolored by
$C_{1}$ and we never change the color of any colored vertex. Moreover, the
fact that $C_{2}$ is a proper $\Delta$-coloring follows from the definition of
$\mathcal{G}_{\textnormal{{Sample}}}$ as described in Section 3.3 (note that
we only need edges in $H$ and not all of $G$ to construct
$\mathcal{G}_{\textnormal{{Sample}}}$).

The main part of the proof in this phase is to show that we actually succeed
in coloring all small almost-cliques in $\mathcal{K}_{\textnormal{lonely}}$ in
this phase, i.e., w.h.p., Algorithm 5 does not ever return ‘fail’.

Fix a small almost-clique $K\in\mathcal{K}_{\textnormal{lonely}}$. Consider
the base palette graph
$\mathcal{G}_{\textnormal{{Base}}}=(\mathcal{L},\mathcal{R},\mathcal{E}_{\textnormal{{Base}}})$
of $K$ and $C$ (Definition 3.8) where $C$ denotes the partial coloring passed
to Algorithm 5 when coloring $K$. First, note that
$\left|{\mathcal{L}}\right|\leqslant\left|{\mathcal{R}}\right|$ since
$\left|{K}\right|\leqslant\Delta$ as $K$ is small (Definition 4.1), and we
remove at most one color-node in $\mathcal{R}$ per each vertex-node in
$\mathcal{L}$ removed from $K$. Thus, having an $\mathcal{L}$-perfect matching
in $\mathcal{G}_{\textnormal{{Base}}}$ and
$\mathcal{G}_{\textnormal{{Sample}}}$ is not _entirely_ out of the question.
We now establish two other properties of $\mathcal{G}_{\textnormal{{Base}}}$
that will allow us to argue that $\mathcal{G}_{\textnormal{{Base}}}$ has an
$\mathcal{L}$-perfect matching. We will then build on these properties to
prove the same for $\mathcal{G}_{\textnormal{{Sample}}}$ as well.

######  Claim 12.

Every vertex in $\mathcal{L}$ in $\mathcal{G}_{\textnormal{{Base}}}$ has
degree at least $3\Delta/4$, with high probability.

Fix a vertex-node $v\in\mathcal{L}$ (and $v\in K$). By property $iii)$. of
Definition 3.3, $v$ has at most $10\varepsilon\Delta$ neighbors outside $K$,
each of which can rule out at most one color for $v$. As for neighbors inside
$K$, recall that each vertex $u\in K$ activates in Algorithm 4 with
probability $1/\alpha$. This implies that in expectation, at most
$\Delta/\alpha$ of them can receive a color in $C_{1}$ (and hence $C$). By an
application of Chernoff bound (Proposition 3.1), at most
$2\Delta/\alpha<\Delta/100$ vertices of $K$ are colored by $C_{1}$ with high
probability (for the choice of $\alpha$ in Eq. 1).

Hence, in total, only $10\varepsilon\Delta+\Delta/100$ colors are ruled out
for $v$ by $C$ with high probability. Given the value of $\varepsilon$ in Eq.
1, this means $\deg_{\mathcal{G}_{\textnormal{{Base}}}}(v)>3\Delta/4$ with
high probability.

The following claim—albeit simple to prove after having setup the process
carefully—is the heart of the argument in this phase. Roughly speaking, this
claim allows us to treat the coloring outside the almost-clique as “not too
adversarial”.

######  Claim 13.

Every vertex in $\mathcal{R}$ in $\mathcal{G}_{\textnormal{{Base}}}$ has
degree at least $3\Delta/4$, with high probability.

######  Proof 5.4.

To lower bound the degree of a color-node $c\in\mathcal{R}$, we have to work a
little harder. The main idea is this: for a color-node $c$ to lose its edges
to $\Omega(\Delta)$ vertex-nodes in $\mathcal{L}$, the color $c$ itself must
have been used to color $\Omega(\beta)$ vertices outside $K$ by $C$; this is
because of the crucial condition that $K$ is _not_ friendly and hence each
vertex receiving the color $c$ outside of $K$ only rules $c$ out for less than
$2\Delta/\beta$ vertex-nodes of $\mathcal{L}$. It is generally very hard to
keep track of which colors are assigned by $C$ so far in the neighborhood of
$K$, but fortunately we have a loose but simple proxy for that: as $C$ is
using only the colors in $L_{1}(\cdot)$ and $L_{2}(\cdot)$ at this point, we
can simply consider which colors are sampled in these lists in the
neighborhood of $K$ instead. We formalize this in the following.

Fix a color-node $c\in\mathcal{R}$. For every vertex $v\notin K$, we define
$m(v,K)$ as the number of edges from $v$ to $K$ in $G$. We define the random
variable $X_{c,v}$ which is equal to $m(v,K)$ iff $c\in L_{1}(v)\cup L_{2}(v)$
and otherwise $X_{c,v}=0$. Notice that $X_{c,v}$ is a (potentially loose)
upper bound on the _reduction_ in the degree of color-node $c\in\mathcal{R}$
because of any assignment of a color the vertices outside of $K$. In other
words, we have that,

$\displaystyle\deg_{\mathcal{G}_{\textnormal{{Base}}}}{(c)}\geqslant\left|{\mathcal{L}}\right|-\sum_{v\notin
K}X_{c,v}\,.$ (3)

We use the variable $X_{c,v}$, instead of the actual color assignment of $v$
by $C$, for two reasons: One, it is easy to compute its probability, and
second (and more importantly) these variables for different $v$’s are
_independent_ (while the actual color of vertices will be correlated). We
would like to show that random variable $X_{c}:=\sum_{u\notin K}X_{c,u}$ is
sufficiently small.

Recall that $c\in L_{1}(v)$ with probability $1/\Delta$, and it is in
$L_{2}(v)$ with probability $\beta/\Delta$ by the choice of lists in palette-
sampling (Algorithm 1). Thus, it is in the union of the two lists with
probability at most $2\beta/\Delta$. Hence,

$\displaystyle\operatorname*{{\mathbb{E}}}\left[X_{c}\right]$
$\displaystyle\leqslant\sum_{v\notin
K}m(v,K)\cdot\frac{2\beta}{\Delta}=\sum_{u\in K}\left|{N(u)\setminus
K}\right|\cdot\frac{2\beta}{\Delta}$ (by a simple double counting argument for
edges between $K$ and its neighbors)
$\displaystyle\leqslant\left|{K}\right|\cdot
10\varepsilon\Delta\cdot\frac{2\beta}{\Delta}$ (by property $iii)$. of almost-
cliques in Definition 3.3) $\displaystyle\leqslant\Delta\cdot
20\varepsilon\cdot\beta$ (as $\left|{K}\right|\leqslant\Delta$ since $K$ is
small by Definition 4.1) $\displaystyle\leqslant\Delta/100.$ (by the choice of
$\varepsilon,\beta$ in Eq. 1)

To prove a concentration bound for $X_{c}$, note that it is a sum of
independent random variables in the range $[0,2\Delta/\beta]$, as each vertex
$v\notin K$ has less than $2\Delta/\beta$ neighbors in $K$ (as $K$ is not a
friendly almost-clique and thus has no friend neighbors—see Definition 4.4).
Thus, by Chernoff bound (Proposition 3.1 for $b=2\Delta/\beta$), we have,

$\displaystyle\leqslant\exp\left(-\frac{20^{2}\cdot\Delta/100}{(3+20)\cdot
2\Delta/\beta}\right)=\exp\left(-\frac{400\log{n}}{46}\right)<n^{-8},$

by the choice of $\beta$ in Eq. 1. A union bound over all choices of $v\notin
K$ and $c\in[\Delta]$, combined with Eq. 3, implies that with high
probability,
$\deg_{\mathcal{G}_{\textnormal{{Base}}}}{(c)}\geqslant\left|{\mathcal{L}}\right|-21\Delta/100$.

Finally, as already proven in Claim 12,
$\left|{\mathcal{L}}\right|\geqslant\left|{K}\right|-\Delta/100$ with high
probability as at most $\Delta/100$ vertices of $K$ are colored by $C_{1}$.
Given that size of $K$ is also at least $(1-5\varepsilon)\Delta$ by property
$i)$. of almost-cliques in Definition 3.3, and by the choice of $\varepsilon$
in Eq. 1, we get that with high probability
$\left|{\mathcal{L}}\right|\geqslant\Delta-2\Delta/100$. Combined with the
above bound, we have

$\deg_{\mathcal{G}_{\textnormal{{Base}}}}{(c)}\geqslant\Delta-2\Delta/100-21\Delta/100>3\Delta/4$

as desired, concluding the proof.

Given that size of $\mathcal{L}$ in $\mathcal{G}_{\textnormal{{Base}}}$ is at
most $\Delta$, it is now easy to use Claims 12 and 13, combined with Hall’s
theorem (Fact 1) to prove that $\mathcal{G}_{\textnormal{{Base}}}$ has an
$\mathcal{L}$-perfect matching. But, our goal is to prove that
$\mathcal{G}_{\textnormal{{Sample}}}$, not only
$\mathcal{G}_{\textnormal{{Base}}}$, has such a matching; this is the content
of the next claim.

######  Claim 15.

The subgraph $\mathcal{G}_{\textnormal{{Sample}}}$ has an
$\mathcal{L}$-perfect matching with high probability.

######  Proof 5.5.

We condition on the high probability events that
$\mathcal{G}_{\textnormal{{Base}}}$ has the properties in Claims 12 and 13. An
important observation is in order: the properties of
$\mathcal{G}_{\textnormal{{Base}}}$ depend on the choice of $L_{1}(v)$ for
$v\in V$ but only $L_{2}(v)$ for $v\notin K$ (as we only need to visit the
coloring of $C$ with $L_{2}(\cdot)$ _outside_ of $K$). As a result, even
conditioned on these properties, the choice of $L_{2}(v)$ for $v\in K$ is
independent and from its original distribution in palette-sampling.

At this point, $\mathcal{G}_{\textnormal{{Sample}}}$ is a subgraph of
$\mathcal{G}_{\textnormal{{Base}}}$ obtained by sampling each edge
independently and with probability $\beta/\Delta$ by the choice of
$L_{2}(\cdot)$ in palette-sampling (Algorithm 1). We use this to prove that
$\mathcal{G}_{\textnormal{{Sample}}}$ should also have an
$\mathcal{L}$-perfect matching with high probability. The argument follows
standard ideas in random graph theory (even though
$\mathcal{G}_{\textnormal{{Sample}}}$ is not exactly a random graph).

By Hall’s theorem (Fact 1), for $\mathcal{G}_{\textnormal{{Sample}}}$ to _not_
have an $\mathcal{L}$-perfect matching, there should exist a set
$A\subseteq\mathcal{L}$ such that
$\left|{N_{\mathcal{G}_{\textnormal{{Sample}}}}(A)}\right|<\left|{A}\right|$.
But for this to happen, there should exist a pair $(S,T)$ of subsets of
$\mathcal{L}$ and $\mathcal{R}$, respectively, such that
$\left|{T}\right|=\left|{S}\right|-1$ and no edge between $S$ and
$\mathcal{R}\setminus T$ is sampled in $\mathcal{G}_{\textnormal{{Sample}}}$
(simply take $A=S$ and notice that $N(A)\subseteq T$ which has size less than
$A$). We refer to any such pair $(S,T)$ as a witness pair. We bound the
probability that any witness pair exists in
$\mathcal{G}_{\textnormal{{Sample}}}$.

###### Case 1: when $\left|{S}\right|\leqslant 2\Delta/3$.

Consider any choice of the set $T$ with $\left|{T}\right|=\left|{S}\right|-1$
from $\mathcal{R}$. By Claim 12, degree of every vertex-node in $S$ is at
least $3\Delta/4$ in $\mathcal{G}_{\textnormal{{Base}}}$. This means the
number of edges from $S$ to $\mathcal{R}\setminus T$ is at least
$\left|{S}\right|\cdot(3\Delta/4-2\Delta/3)=\left|{S}\right|\cdot\Delta/12$.
As such,

$\operatorname*{\textnormal{Pr}}\left(\text{$(S,T)$ is a witness
pair}\right)\leqslant\left(1-\frac{\beta}{\Delta}\right)^{\left|{S}\right|\cdot\Delta/12}\leqslant\exp\left(-\frac{100}{12}\cdot\left|{S}\right|\cdot\log{n}\right)<n^{-8\left|{S}\right|},$

by the choice of $\beta$ in Eq. 1. A union bound over all
${{\left|{\mathcal{R}}\right|}\choose{\left|{S}\right|-1}}<n^{\left|{S}\right|-1}$
choices for $T$ then implies that for any such $S$,

$\operatorname*{\textnormal{Pr}}\left(\text{there is a set $T$ so that $(S,T)$
is a witness pair}\right)\leqslant n^{\left|{S}\right|-1}\cdot
n^{-8\left|{S}\right|}<n^{-7\left|{S}\right|}.$

Finally, a union bound all choices for the set $S$, partitioned based on their
size, implies that,