text:
\section{Introduction}\label{sec:intro}
A hypergraph is a pair $(V,E)$ where $V$ is a set whose elements are called \textit{vertices}, and $E$ is a family of subsets of $V$ called \textit{edges}.
A hypergraph has \textit{rank $k$} if every edge contains between $2$ and $k$ vertices, and is \textit{$k$-uniform} if every edge contains exactly $k$ vertices.
A \textit{proper coloring} of $\mathcal{H}$ is an assignment of colors to the vertices so that no edge is monochromatic.
The smallest number of colors that are required for a proper coloring of $\mathcal{H}$, is called the \textit{chromatic number} of $\mathcal{H}$ and denoted by $\chi(\mathcal{H})$.
Given a set $L(v)$ of colors for every vertex $v\in V(\mathcal{H})$, a \textit{proper list coloring} of $\mathcal{H}$ is a proper coloring, where every vertex $v$ receives a color from $L(v)$.
The \textit{list chromatic number} of $\mathcal{H}$, denoted by $\chi_{\ell}(\mathcal{H})$, is the minimum number $c$ so that if $|L(v)| \geq c$ for all $v$, then $\mathcal{H}$ has a proper list coloring.
It is not hard to see that $\chi(\mathcal{H}) \leq \chi_{\ell}(\mathcal{H})$.

The study of the chromatic number of graphs (i.e., 2-uniform hypergraphs) has a rich history.
A straightforward greedy coloring algorithm shows that any graph $G$ with maximum degree $\Delta$ has chromatic number $\chi(G) \leq \Delta +1$, while the celebrated Brooks' theorem~\cite{brooks1941colouring} states that for connected graphs equality holds only for cliques and odd cycles.
Moving beyond Brooks' theorem, a natural question to consider is: what structural constraints one can be put on a graph to decrease its chromatic number?
In particular, Vizing~\cite{vizing1968some} proposed a question in 1968 which asked for the best possible upper bound for the chromatic number of a triangle-free graph.
Improving on results of Catlin~\cite{catlin1978bound}, Lawrence~\cite{lawrence1978covering}, Borodin and Kostochka ~\cite{borodin1977upper}, Kostochka~\cite{kostochkaletter}, and Kim~\cite{kim1995brooks}, in 1996 Johansson~\cite{johansson1996asymptotic} showed that
\begin{equation}\label{johansson}
\chi(G)=\mathcal{O}(\Delta/\log\Delta)
\end{equation}
for any triangle-free graph $G$ with maximum degree $\Delta$, and this bound is known to be tight up to a constant factor by constructions of Kostochka and Masurova~\cite{kostochka1977inequality}, and Bollob{\'a}s~\cite{bollobas1978chromatic}.
Indeed, Johansson~\cite{johansson1996asymptotic} proved a stronger result by showing that the list chromatic number $\chi_{\ell}(G)\leq (9+o(1))\Delta/\log\Delta.$
Pettie and Su~\cite{pettie2015distributed} subsequently improved the above constant from $9$ to $4$.
Later, Molloy~\cite{molloy2019list} further reduced the constant to $1$ while Bernshteyn~\cite{bernshteyn2019johansson} then provided a shorter proof of Molloy's result.

Analogous problems have also been investigated for hypergraphs by many researchers over the years.
For a rank $k$ hypergraph $\mathcal{H}$ and an positive integer $i \leq k$, the \textit{$i$-degree} of a
vertex $v$ is the number of size $i$ edges containing $v$.
Using the Lov{\'a}sz Local Lemma, one can easily show that $\chi(\mathcal{H})=\mathcal{O}\left(\Delta^{1/(k-1)}\right)$ for any $k$-uniform hypergraph $\mathcal{H}$ with maximum $k$-degree $\Delta$.
Similarly as for the graph case, one may ask what local constraints can be imposed on a hypergraph in order to significantly improve its chromatic number beyond this easy bound. We say a hypergraph is \textit{linear} if any two of its edges intersect in at most one vertex, and a \textit{loose triangle} in a linear hypergraph is a set of three pairwise intersecting edges containing no common point.
Frieze and Mubayi~\cite{frieze2008chromatic} first generalized Johansson's theorem (that is,~\eqref{johansson}) to all $3$-uniform linear hypergraphs as follows.
\begin{thm}[Frieze and Mubayi~\cite{frieze2008chromatic}]\label{thm:FM1}
If $\mathcal{H}$ is a  linear $3$-uniform hypergraph which does not contain any loose triangles, then
\[
\chi(\mathcal{H})=\mathcal{O}\left((\Delta/\log\Delta)^{1/2}\right),
\]
where $\Delta$ is the maximum $3$-degree of $\mathcal{H}$.
\end{thm}
It was subsequently realized by the same group in~\cite{frieze2013coloring} that for linear hypergraphs, the triangle-free condition in Theorem~\ref{thm:FM1} can be removed while the same conclusion still holds.
Meanwhile, they also showed that such a linear hypergraph result can be generalized to any uniformity, by proving that if $\mathcal{H}$ is a $k$-uniform linear hypergraph with maximum $k$-degree $\Delta$, then
\begin{equation}\label{linearthm}
\chi(\mathcal{H})=\mathcal{O}\left((\Delta/\log\Delta)^{1/(k-1)}\right).
\end{equation}
On the other hand, Cooper and Mubayi~\cite{cooper2015list} removed the restriction to linear systems from~Theorem~\ref{thm:FM1}, and then generalized Johansson's theorem from graphs to all rank $3$ hypergraphs.
In order to formally state their result, we first introduce a definition of `triangle' for general hypergraphs, which was used in~\cite{cooper2015list}.
\begin{defi}[Triangle]\label{def:tri}
A \textit{triangle} in a hypergraph $\mathcal{H}$ is a set of three distinct edges $e, f, g\in\mathcal{H}$ and three distinct vertices $u, v, w\in V(H)$ such that $\{u, v\}\subseteq e$, $\{v, w\}\subseteq f$, $\{w, u\}\subseteq g$ and $\{u, v, w\}\cap e\cap f\cap g=\emptyset$.
\end{defi}
Note that similarly to a more classical definition of the hypergraph triangle, the \textit{Berge triangle}, the notion of triangle in Definition~\ref{def:tri} refers to a family of hypergraphs.
However, Definition~\ref{def:tri} is weaker than the definition of Berge triangles, in the sense that the triangle family it refers to is a subfamily of Berge triangles.
For example, there are three triangles in a $3$-uniform hypergraph: the loose triangle $C_3=\{abc, cde, efa\}$, $F_5=\{abc, bcd, aed\}$, and $K^-_4=\{abc, bcd, abd\}$. On the other hand, for example, $\{abc,bcd,ace\}$ is a Berge triangle that is not a triangle.

We say a hypergraph is \textit{triangle-free} if it does not contains any triangle as a subgraph.
As in Johansson's theorem~\cite{johansson1996asymptotic}, the main result of Cooper and Mubayi can be stated in terms of list chromatic number.
\begin{thm}[Cooper and Mubayi~\cite{cooper2015list}]\label{CooperMubayi}
Let $\mathcal{H}$ be a rank $3$, triangle-free hypergraph with maximum $3$-degree $\Delta_3$ and maximum $2$-degree $\Delta_2$. Then
\[
\chi_{\ell}(\mathcal{H}) \leq c\cdot \max\left\{
\left(\frac{\Delta_3}{\log\Delta_3}\right)^{1/2},\ \frac{\Delta_2}{\log\Delta_2}
\right\},
\]
where $c$ is a fixed constant, not depending on $\mathcal{H}$.
\end{thm}

\subsection{Our main result}
Given a rank $k$ hypergraph $\mathcal{H}$, an integer $2\leq \ell \leq k$, and a set $S$ of vertices (where $1 \leq |S| <\ell$), we define $\deg_{\ell}(S, \mathcal{H})$ to be the number of size $\ell$ edges containing $S$.
In particular, when $S$ consists of a single vertex $v$, then $\deg_{\ell}(S, \mathcal{H})$ is exactly the $i$-degree of $v$.
The \textit{maximum $\ell$-degree} of $\mathcal{H}$, denoted by $\Delta_{\ell}(\mathcal{H})$, is the maximum of $\mathrm{deg}_{\ell}(v, \mathcal{H})$ over all vertices $v$ in $\mathcal{H}$; the \textit{maximum $(s,\ell)$-codegree of $\mathcal{H}$}, denoted by $\delta_{s, \ell}(\mathcal{H})$, is the maximum of $\deg_{\ell}(S, \mathcal{H})$ over all $s$-vertex sets $S$ in $\mathcal{H}$.
When the underlying graph is clear from the context, we simply write $\Delta_{\ell}$ and $\delta_{s, \ell}$ instead.

We extend Cooper and Mubayi's theorem to all hypergraphs as follows.
\begin{thm}\label{mainthm1}
Let $k\geq 3$ be an integer,
and $\mathcal{H}$ be a rank $k$, triangle-free hypergraph. Then
\[
\chi_{\ell}(\mathcal{H})\leq c\cdot \max_{2\leq \ell \leq k} \left\{\left(  \frac{\Delta_{\ell}}{\log \Delta_{\ell}} \right)^{\frac{1}{\ell-1}} \right\},
\]
where $c$ depends only on $k$, not on $\mathcal{H}$.
\end{thm}
It is shown in~\cite[Theorem~5]{frieze2008chromatic} that there exists $k$-uniform triangle-free hypergraph with maximum degree $\Delta$ and chromatic number at least $c'\left(\Delta/\log \Delta\right)^{1/(k-1)}$ for some absolute constant $c'$, which only depends on $k$.
Therefore, Theorem~\ref{mainthm1} is sharp apart from the constant $c$.

In fact, we will derive Theorem~\ref{mainthm1} as a corollary of the following weaker theorem.
\begin{thm}\label{mainthm2}
Let $k\geq 3$ be an integer,
and $\mathcal{H}$ be a rank $k$, triangle-free hypergraph. If there exists $\Delta$ such that
\begin{itemize}
\item[(i)] $\Delta_{\ell} \leq \Delta^{1 - \frac{k - \ell}{k-1}} (\log \Delta)^{\frac{k - \ell}{ k-1}}$ for $2\leq \ell \leq k$;
\item[(ii)] $\delta_{s, \ell} \leq (\Delta/\log\Delta)^{\frac{\ell - s}{k-1}}$ for $2\leq s<\ell \leq k$,
\end{itemize}
then
\[
\begin{split}
\chi_{\ell}(\mathcal{H}) &\leq c \cdot\left( \frac{\Delta}{\log \Delta}\right)^{\frac{1}{k-1}},
\end{split}
\]
where $c$ depends only on $k$, not on $\mathcal{H}$.
\end{thm}

The proof technique known as the \emph{semi-random} or \emph{nibble} method, was first introduced by R{\"o}dl~\cite{rodl1985packing} in 1985, to settle the Erd\H{o}s-Hanani conjecture about the existence of asymptotically optimal designs.
It was later found by many researchers (such as~\cite{cooper2015list, frieze2008chromatic, frieze2013coloring, jamall2011brooks, johansson1996asymptotic, kim1995brooks}) that the R{\"o}dl nibble method is also a very powerful tool in dealing with graph/hypergraph coloring problems.
The core idea of this R{\"o}dl nibble approach is to iteratively color a small portion of the currently uncolored vertices of the graph/hypegraph, record the fact that a color already used at $u$ will have `limited usage' in future on the uncolored neighbors of $u$, and continue this process until the graph/hypegraph induced by the uncolored vertices has small maximum degree, whereas each vertex will still have a large enough number of `usable' colors.
Once this has been achieved, then the remaining uncolored vertices can be properly colored without violating the `limitations', usually using the greedy algorithm or the Lov{\'a}sz Local Lemma.

In order to better illustrate the difficulties and the novelty of our work, let us first go back to the graph setting.
In the iterative colouring procedure, each vertex $u$ maintains a \textit{palette}, which consists of the `usable' colors.
Once a vertex $u$ is colored by some color $c$,  this color will no longer be `usable' for all neighbors of $u$, and then will be removed from their palettes.
We define the \textit{$c$-degree} of $u$ to be the number of its neighbors whose palettes contain $c$.
In Kim's algorithm~\cite{kim1995brooks} for girth-5 graphs, $c$-degrees can be bounded after each iteration using standard concentration inequalities, due to a nice independence property of girth-5 graphs, that is, whether a color $c$ remains in the palette of one neighbor of a vertex $u$ has little influence on a different neighbor of $u$.
However, for triangle-free graphs, there is no guarantee of such independence, and therefore $c$-degree is no longer well-concentrated.

To address the problem of coloring triangle-free graphs, there are essentially three different approaches in the literature.
The first approach, which was proposed by Johansson~\cite{johansson1996asymptotic}, is to control the entropy of the remaining palettes so that every color in the palette is picked nearly uniformly at each iteration; such uniformity turned out to be useful and crucial in bounding $c$-degrees.
The second approach is that of Pettie and Su~\cite{pettie2015distributed} who show that although each $c$-degree does not concentrate, the average $c$-degree (over all colors in the palette) can be well-concentrated; they used this approach to improve the constant of 9 by Johansson to 4.
Despite the difference on concentration details, both two approaches rely on applications of the Lov{\'a}sz Local Lemma, in which there is a lot of ``slackness".
Molloy~\cite{molloy2019list} and Bernshteyn~\cite{bernshteyn2019johansson}, rather than being concerned with concentration details, provide dramatically simpler proofs by the use of the entropy compression method/the ``lopsided" Lov\'{a}sz Local Lemma and thereby improve the constant to 1.

Going back to hypergraphs, all prior work (\cite{cooper2015list, frieze2008chromatic, frieze2013coloring}) essentially employed the entropy approach of Johansson.
In particular, Cooper and Mubayi~\cite{cooper2015list} extended the entropy approach to all rank $3$ hypergraphs.
However, their proof does not readily generalize to higher ranks as far as we can see, due to the increasing complexity of concentration analysis brought on by codegrees of high rank hypergraphs.
Meanwhile, it does not seem that the Molloy/Bernshteyn approach will generalize to hypergraphs.

In contrast to the aforementioned studies on hypergraphs, our work uses the second approach of focusing on concentrating the average of $c$-degrees.
Not surprisingly, when it comes to hypergraphs, several new challenges arise.
This first challenge is that the coloring algorithm necessarily becomes much more complicated.
For example, when a vertex $u$ is colored by some color $c$,  it is no longer tractable to immediately remove this color from the palettes of its neighbours since too many colors may be lost this way. So instead, for each hyperedge $e$ containing $u$ who might receive the same color $c$, we replace this edge with a new edge $e'=e-u$, who now has lower uniformity, and then update the coloring restriction so that vertices in $e'$ cannot all receive color $c$.
To facilitate this, we introduce a collection of different hypergraphs $\mathcal{H}_{c, \ell}$ at each stage of the algorithm that tracks the coloring restrictions of each size $\ell$ for each color $c$. Keeping track of these hypergraphs requires controlling more parameters during the iteration, which makes problem much more difficult for hypergraphs than graphs. We note that essentially this means we start and maintain a hypergraph whose edges have colors (while there may be multiple of the same edge in different colors) and hence we in fact have proved the \emph{color-degree} version of Theorem~\ref{mainthm1} though we omit its statement and even the more general form as mentioned where edges only have certain colors forbidden from being monochromatic.

Another fundamental challenge is that given the existence of edges of different uniformity, how do we generalize the notion of `$c$-degree' to hypergraphs?
Perhaps the most obvious and straightforward approach would be to define $c$-degree for each uniformity individually, for example, define the \textit{$(c, \ell)$-degree} of $u$ to be its $\ell$-degree in $\mathcal{H}_{c, \ell}$.
However, unlike the graph case, now it is not even clear if such $(c, \ell)$-degrees are always decreasing during an iteration, since in addition to removing old edges, the algorithm also generates new edges of lower uniformity.
One of the novelties of our approach is that we introduce a special \textit{weighted sum of $(c, \ell)$-degrees} (see Section~\ref{sec:algo} for details), to play the role of `$c$-degree' in hypergraphs, in which the weights are carefully chosen to balance the contribution from each uniformity and therefore ensure that the average of such `$c$-degrees' over colors is monotone decreasing in expectation, and can be well-concentrated.
The introduction of this new definition is one of the main contributions of our paper, and this lays the foundation for all follow-up analysis. We also note this weighted sum is a \emph{linear} combination of the $(c, \ell)$-degrees (as opposed to the perhaps more natural sum of the polynomial roots in the statement of Theorem~\ref{mainthm1}); this linearity is quite useful not only in determining the expectation but also in proving the concentration of the new weighted sum in the next iteration of the algorithm.

The structural intricacy of hypergraphs also brings new dependencies among the trials and variables that are much more involved than the graph case.
We shall see later in the algorithm that the $c$-degree of a vertex is determined by colorings on its neighbors and second neighbors; therefore, whether average $c$-degrees are concentrated is profoundly affected by the dependency brought by high codegrees.
Unlike Cooper and Mubayi~\cite{cooper2015list} who chose to keep track of all codegrees, another novelty of our work is that we develop a \textit{codegree reduction algorithm}, which directly reduces all codegrees by contracting multiple hyperedges into one hyperedge of smaller uniformity.
This reduction process obviates the need for tracking codegrees (which becomes even more sophisticated when the rank gets higher), while keeping all \textit{crucial} coloring information and properties (see Section~\ref{sec:coredu} for details).

In addition to overcoming the intrinsic obstacles mentioned above, overcoming technical difficulties in concentration analysis is also one of the core components of our work.
For this purpose, rather than classical concentration tools, we make use of a new version of Talagrand's concentration inequality (with exceptional events) from a recent paper of Delcourt and Postle~\cite{DP} (see Section~[\ref{sec:prob}, Theorem~\ref{talagrand}]) which crucially provides a linear (as opposed to quadratic) dependence on the so-called Lipschitz constant under some additional assumption. Moreover, the way we use it is also not direct but rather highly involved and novel, including breaking target random variables into several variables for which Theorem~\ref{talagrand} are applicable, and building up the set of exceptional events by iterative applications of Theorem~\ref{talagrand}.

Besides that and similar to what happened in the graph case, the triangle-free condition is not enough to guarantee the independence of the colorings on each vertex, which is important for bounding $c$-degrees. However, using Janson's Inequality (see Section~\ref{sec:prob}), we show that triangle-freeness is sufficient to guarantee some kind of `almost independence', which will be enough for our usage. Altogether then, it is the combination of the right definitions (e.g. colored edges, weighted color-degree etc.) and new ideas/tools (e.g. codegree reduction, the new version of Talagrand's, etc.) which leads to our proof of Theorem~\ref{mainthm1}.

Lastly, before moving to applications of our result, we want to point out that although the triangle-freeness is crucial for reducing the chromatic number of hypergraphs, the vast majority of our proof indeed does not rely on it.
The only place we use the triangle-freeness is in Section~\ref{sec:dep}, where the above mentioned `almost independence' needs to be guaranteed during the algorithm. In other words, the triangle-free assumption of Theorem~\ref{mainthm1} could be replaced by any condition which establishes the conclusion of Lemma~\ref{lem:dep}.

\subsection{Applications to sparse hypergraphs coloring}
Alon, Krivelevich and Sudakov~\cite{alon1999coloring} extended~\eqref{johansson} by showing that for a graph $G$ with maximum degree $\Delta$, if every vertex
$u$ is in at most $\Delta^2/f$ triangles, then
\begin{equation}\label{ref:AKS}
\chi(G) = \mathcal{O}(\Delta/\log f),
\end{equation}
where $\Delta\rightarrow\infty$.
This was later generalized to rank $3$ hypeprgraphs due to the work of Cooper and Mubayi~\cite{cooper2016coloring}. To state their result, we first recall some terminology from~\cite{cooper2016coloring}.

Given two hypergraphs $\mathcal{F}_1$ and $\mathcal{F}_2$, a map $\phi : V(\mathcal{F}_1) \rightarrow V(\mathcal{F}_2)$ is an \textit{isomorphism} if
for all $E\subset V(\mathcal{F}_1)$, $\phi(E)\in \mathcal{F}_2$ if and only if $E\in \mathcal{F}_1$. If there exists an isomorphism $\phi : V (\mathcal{F}_1) \rightarrow V (\mathcal{F}_2)$, we say $\mathcal{F}_1$ is \textit{isomorphic} to $\mathcal{F}_2$ and denoted it by $\mathcal{F}_1\cong_{\phi}\mathcal{F}_2$.
For two hypergraphs $\mathcal{F}, \mathcal{H}$ and a vertex $v\in V(\mathcal{F})$, let
\[
\Delta_{\mathcal{F}, v}(\mathcal{H})=\max_{u\in V(\mathcal{H})}|\{\mathcal{F}'\subseteq \mathcal{H}: \mathcal{F}'\cong_{\phi} \mathcal{F} \text{ and } \phi(u)=v\}|
\]
and
\[
\Delta_{\mathcal{F}}(\mathcal{H}) = \min_{v\in V(\mathcal{F})}\Delta_{\mathcal{F}, v}(\mathcal{H}).
\]

Cooper and Mubayi~\cite{cooper2016coloring} proved the following theorem.
\begin{thm}[Cooper and Mubayi~\cite{cooper2016coloring}]\label{CMspar}
Let $\mathcal{H}$ be a rank $3$ hypergraph with maximum $3$-degree $\Delta_3$ and maximum 2-degree $\Delta_2$.
Let $\mathcal{T}$ denote the family of rank $3$ triangles.
If
\[
\Delta_{T}(\mathcal{H})\leq \left(\max\left\{\Delta_3^{1/2}, \Delta_2\right\}\right)^{v(T)-1}/f
\]
for all $T\in \mathcal{T}$, then
\[
\chi(\mathcal{H})\leq \mathcal{O}\left(\max \left\{\left(\frac{\Delta_3}{\log f} \right)^{1/2},\ \frac{\Delta_{2}}{\log f} \right\}\right).
\]
\end{thm}
The main idea behind both~\eqref{ref:AKS} and Theorem~\ref{CMspar} is the following: if a graph/hypergraph $\mathcal{H}$ is \textit{sufficiently sparse} (i.e., has bounded degrees and codegrees), and every vertex lies in \textit{not many} triangles, then we can partition $\mathcal{H}$ into \textit{a few} graphs/hypergraphs such that each of them is \textit{triangle-free}; after that, we just apply the known results for triangle-free graphs on each part individually.
As the main contribution of their paper, Cooper and Mubayi~\cite{cooper2016coloring} established such partition lemma (see Section~\ref{sec:spars} for details) in a even more general set-up: the hypergraph can be of any rank, and triangles can be replaced by other families of some fixed hypegraphs.
Therefore, the only missing ingredient for extending~\eqref{ref:AKS} to any rank is in proving the corresponding result for the chromatic number of triangle-free hypergraphs.

By using our main theorem then, we generalize the results of~Alon, Krivelevich and Sudakov~\cite{alon1999coloring} and Cooper and Mubayi~\cite{cooper2016coloring} to all hypergraphs as follows.

\begin{thm}\label{sparsethm}
Fix $k\geq 3$. Let $\mathcal{H}$ be a rank $k$ hypergraph with maximum $\ell$-degree at most $\Delta_{\ell}$ for each $2\leq \ell\leq k$.
Denote by $\mathcal{T}$ the family of rank $k$ triangles.
If
\[
\Delta_{T}(\mathcal{H})\leq \left(\max_{2\leq\ell\leq k}\Delta_{\ell}^{1/(\ell-1)}\right)^{v(T)-1}/f
\]
for all $T\in \mathcal{T}$, then
\[
\chi(\mathcal{H})\leq \mathcal{O}\left(\max_{2\leq \ell \leq k} \left\{\left(  \frac{\Delta_{\ell}}{\log f} \right)^{\frac{1}{\ell-1}} \right\}\right).
\]
\end{thm}
Notice that the hypotheses of Theorem~\ref{sparsethm} are satisfied when $\mathcal{H}$ is linear, $k$-uniform and $f =\Delta_k^{1 - 1/(k-1)}$, so Theorem~\ref{sparsethm} implies \eqref{linearthm}.

Using Theorem~\ref{sparsethm}, we also extend a result of Cooper-Mubayi~\cite{cooper2016coloring} from $k$-uniform hypergraphs to all hypergraphs with the following theorem.
\begin{thm}\label{CMspar2}
Fix $k\geq 3$. Let $\mathcal{H}$ be a rank $k$ hypergraph with maximum $\ell$-degree at most $\Delta_{\ell}$ for each $2\leq \ell\leq k$.
Suppose that for all $2\leq s<\ell \leq k$, the maximum $(s, \ell)$-codegree
\[
\delta_{s, \ell}(\mathcal{H})\leq \left(\max_{2\leq\ell\leq k}\Delta_{\ell}^{1/(\ell-1)}\right)^{\ell-s}/f,
\]
and additionally for the graph triangle $T_0$,
\[
\Delta_{T_0}(\mathcal{H})\leq \left(\max_{2\leq\ell\leq k}\Delta_{\ell}^{1/(\ell-1)}\right)^{2}/f.
\]
Then we have
\[
\chi(\mathcal{H})\leq \mathcal{O}\left(\max_{2\leq \ell \leq k} \left\{\left(  \frac{\Delta_{\ell}}{\log f} \right)^{\frac{1}{\ell-1}} \right\}\right).
\]
\end{thm}
Observe that given such an $\mathcal{H}$, for any rank $k$ triangle $T$ (except for $T_0$), one can easily use the codegree conditions to show that
\[
\Delta_{T}(\mathcal{H})\leq \mathcal{O}\left(\left(\max_{2\leq\ell\leq k}\Delta_{\ell}^{1/(\ell-1)}\right)^{v(T)-1}/f \right).
\]
Theorem~\ref{sparsethm} then immediately yields Theorem~\ref{CMspar2}.

\subsection{Applications to independence number of hypergraphs}
Closely related to coloring problems are questions about the independence number of hypergraphs.
The \textit{independence number $\alpha(\mathcal{H})$} of a hypergraph $\mathcal{H}$ is the size of a largest set of vertices containing no edge of $\mathcal{H}$.
Using Turan's theorem, one can easily show that a $n$-vertex $k$-uniform hypergraphs with maximum degree $\Delta_k$ has $\alpha(\mathcal{H})=\Omega\left(n/\Delta_k^{1/(k-1)}\right)$.
A seminal result of Ajtai, Koml{\'o}s, Pintz, Spencer, and Szemer{\'e}di~\cite{ajtai1982extremal} showed that this trivial lower bound could be improved by forbidding certain small subgraphs.

For $\ell\geq 2$, a \textit{(Berge) cycle} of length $\ell$ in $\mathcal{H}$ is a collection of $\ell$ edges $E_1,\cdots, E_{\ell}\in\mathcal{H}$ such that there exists $\ell$ distinct vertices $v_1,\cdots, v_{\ell}$ with $v_i\in E_i\cap E_{i+1}$ for $i\in[\ell-1]$ and $v_{\ell} \in E_{\ell}\cap E_1$.
\begin{thm}[Ajtai, Koml{\'o}s, Pintz, Spencer and Szemer{\'e}di~\cite{ajtai1982extremal}]\label{AKPSS}
Let $\mathcal{H}$ be a $k$-uniform hypergraph with maximum degree $\Delta_k$ that contains no cycles of length 2, 3, and 4. Then
\[
\alpha(\mathcal{H})\geq c\cdot n\left(\frac{\log\Delta_k}{\Delta_k}\right)^{1/(k-1)}
\]
where $c$ depends only on $k$, not on $\mathcal{H}$.
\end{thm}
Ajtai, Erd\H{o}s, Koml{\'o}s and Szemer{\'e}di~\cite{ajtai1981turan} proposed the problem on determining whether Theorem~\ref{AKPSS} could also be extended to other families of hypergraphs.
In particular, Spencer~\cite{nesetril2012mathematics} conjectured that the same conclusion holds for linear hypergraphs, and this was later proved by Duke, Lefmann and R{\"o}dl~\cite{duke1995uncrowded}.

Our main result (Theorem~\ref{mainthm1}) immediately yields the following strengthed version of Theorem~\ref{AKPSS}, showing that the same lower bound holds even if $\mathcal{H}$ just contains no triangles.
\begin{thm}\label{mainthmind}
Let $\mathcal{H}$ be a $k$-uniform triangle-free hypergraph with maximum degree $\Delta_k$.
Then
\[
\alpha(\mathcal{H})\geq c\cdot n\left(\frac{\log\Delta_k}{\Delta_k}\right)^{1/(k-1)}
\]
where $c$ depends only on $k$, not on $\mathcal{H}$.
\end{thm}

Rather than considering $F$-free hypergraphs, Kostochka, Mubayi and Verstra{\"e}te~\cite{kostochka2014independent} proved the following general result on the independence number for $k$-uniform hypergraphs given the maximum $(k-1, k)$-codegree.
\begin{thm}[Kostochka, Mubayi and Verstra{\"e}te~\cite{kostochka2014independent}]\label{KMVCo}
Fix $k\geq 3$. There exists $c_k>0$ such that if $\mathcal{H}$ is an $k$-uniform hypergraph on $n$ vertices with the maximum $(k-1, k)$-codegree $\delta_{k-1, k}(\mathcal{H}):=d< n/(\log n)^{3(r-1)^2}$, then
\[
\alpha(\mathcal{H}) \geq c_k\left(\frac{n}{d}\log\frac{n}{d}\right)^{\frac{1}{k-1}},
\]
where $c_k>0$ and $c_k \sim k/e$ as $k\rightarrow\infty$.
\end{thm}
Our next theorem improves and extends Kostochka, Mubayi and Verstra{\"e}te's result on the independence
number to non-uniform hypergraphs and chromatic number. We also weaken the hypothesis
by not requiring any upper bound condition on codegrees.
Note that an important aspect of Theorem~\ref{KMVCo} is
that the value of the constant $c_k$ is the best possible, while we do not optimize the constant in our result below.
\begin{thm}
Fix $k\geq 3$, and let $\mathcal{H}$ be a rank $k$ hypergraph on $n$ vertices with the maximum $(\ell-1, \ell)$-codegree $\delta_{\ell-1, \ell}(\mathcal{H})\leq d_{\ell}$. Set
\[
f:=\min_{2\leq \ell \leq k}\left\{\left(n/d_\ell\right)^{\frac{1}{\ell-1}}\right\},
\]
and assume additionally that for the graph triangle $T_0$,
\[
\Delta_{T_0}(\mathcal{H})\leq n^2/f^3.
\]
Then we have
\[
\chi(\mathcal{H})\leq \mathcal{O}\left(\max_{2\leq \ell \leq k} \left\{\left(\frac{n^{\ell-2}d_{\ell}}{\log f} \right)^{\frac{1}{\ell-1}} \right\}\right).
\]
In particular,
\[
\alpha(\mathcal{H}) \geq \Omega\left(\min_{2\leq\ell\leq k}\left\{\left(\frac{n}{d_{\ell}}\log f\right)^{\frac{1}{\ell-1}}\right\}\right).
\]
\end{thm}
\begin{proof}
Observe that for every $2\leq s<\ell \leq k$, we have $\Delta_{\ell}(\mathcal{H})\leq n^{\ell-2}d_{\ell}$, and
\[
\delta_{s, \ell}(\mathcal{H})\leq n^{\ell-s-1}d_{\ell} = (n^{\ell-2}d_{\ell})^{\frac{\ell-s}{\ell-1}}/\left(n/d_{\ell}\right)^{1- \frac{\ell-s}{\ell-1}}\leq (n^{\ell-2}d_{\ell})^{\frac{\ell-s}{\ell-1}}/f.
\]
Moreover, for the graph triangle $T_0$, we have
\[
\Delta_{T_0}(\mathcal{H})\leq n^2/f^3 = \left(\max_{2\leq \ell\leq k}\left\{(n^{\ell-2}d_{\ell})^{\frac{1}{\ell-1}}\right\}\right)^{2}/f
\]
Then by Theorem~\ref{CMspar2}, we obtain that
\[
\chi(\mathcal{H})\leq \mathcal{O}\left(\max_{2\leq \ell \leq k} \left\{\left(\frac{n^{\ell-2}d_{\ell}}{\log f} \right)^{\frac{1}{\ell-1}} \right\}\right).
\]

\end{proof}

\subsection{Organization of paper}
In the next section, we present some related probabilistic tools.
In Section~\ref{sec:algo}, we describe our codegree reduction algorithm and main coloring algorithm.
Section~\ref{sec:mainthm2} contains an analysis of our coloring algorithm.
In particular, in this section we state our Key Lemma (Lemma~\ref{lem:key}), the concentration result for average $c$-degrees, and show how to use it to prove Theorem~\ref{mainthm2}.
Sections~\ref{sec:concede} and~\ref{sec:keylemma} are devoted to the proof of Lemma~\ref{lem:key}.
We then show how Theorem~\ref{mainthm1} is derived from Theorem~\ref{mainthm2} in Section~\ref{sec:mainthm1}, and prove Theorem~\ref{sparsethm} in Section~\ref{sec:spars}.
Finally, we close the paper with some open problems in Section~\ref{sec:conclu}.

\section{Proof of Lemma~\ref{lem:key}}\label{sec:keylemma}
In this section, we prove our Key Lemma (Lemma~\ref{lem:key}) which we restate for convenience.
\begin{lemma}[Key Lemma]
Let $0\leq i\leq T$.
Assume that $\mathcal{D}_{i-1}(u) \leq t'_{i-1}$ for all $u\in U_{i-1}$. Then for every $u\in U_{i}$,
\[
\mathbf{Pr}\left(\sum_{c\in\hat{P}_{i}(u)}\hat{d}_{i}(u, c) \leq \alpha'_{i}\beta^{k}|P_{i-1}(u)|\left(\Lambda_{i-1}(u) + \frac{\varepsilon}{4}t_{i-1}\right) \right)\geq 1- \exp\left(-\Omega(\log^2\Delta)\right),
\]
where $\varepsilon=4\Delta^{-\theta}\log^{2k}\Delta$.
\end{lemma}

\subsection{A lemma on dependency}\label{sec:dep}
In this section, we discuss some dependency issue which arises from the analysis of the algorithm. Indeed, this is the only place throughout the entire proof that we need the triangle-freeness.
Before doing that, we first show that the algorithm always maintains the triangle-freeness of hypergraphs.

\begin{prop}\label{trianglefree}
For every $0\leq i \leq T$ and color $c$, the hypergraph $\bigcup_{\ell=2}^{k}\mathcal{H}^{i}_{\ell, c}$ is triangle-free.
\end{prop}
\begin{proof}
We prove it by induction on $i$. The case $i=0$ is trivial as our input hypergraph $\mathcal{H}$ is triangle-free.
Suppose that $\bigcup_{\ell=2}^{k}\mathcal{H}^{i-1}_{\ell, c}$ is triangle-free for all color $c$.

We assume by contradiction that $\bigcup_{\ell=2}^{k}\mathcal{H}^{i}_{\ell, c}$ is not triangle-free for some $c$. By the mechanics of the algorithm and Proposition~\ref{prop:redu}, such a triangle can not be created during the filtering process (step 7), or the codegree reduction process (step 8) of the algorithm.
Therefore, there exists a triangle $\{e, f, g\}\in\bigcup_{\ell=2}^{k}\hat{\mathcal{H}}^{i}_{\ell, c}$ such that $\{u, v\}\subseteq e$, $\{v, w\}\subseteq f$, $\{w, u\}\subseteq g$ and $\{u, v, w\}\cap e\cap f\cap g=\emptyset$. In particular, we have $w\notin e$.
Clearly, a least one of these three edges is not in $\bigcup_{\ell=2}^{k}\mathcal{H}^{i-1}_{\ell, c}$. To simplify the discussion, we further assume that $e$ is the only edge who is in $\bigcup_{\ell=2}^{k}\hat{\mathcal{H}}^{i}_{\ell, c}$  but not in $\bigcup_{\ell=2}^{k}\mathcal{H}^{i-1}_{\ell, c}$; other cases will follow from a similar argument. Let $s:=|e|$.

By the definition of $\hat{\mathcal{H}}^{i}_{\ell, c}$ , this new edge $e$ was created in the following situation:
going back to the step 6 of $i$-th iteration round, there exists some edge $e'\in \bigcup_{\ell=2}^{k}\mathcal{H}^{i-1}_{\ell, c}$ such that all vertices in $e'-e$ are colored by $c$. Note that $w\notin e'-e$, and therefore not in $e'$, since $w$ remains uncolored at the end of round $i$. Then $\{e', f, g\}$ forms triangle in $\bigcup_{\ell=2}^{k}\mathcal{H}^{i-1}_{\ell, c}$, which contradicts our induction assumption.
\end{proof}

In order to bound the expectation of $\hat{d}_{i}(u, c)$, we will need an upper bound on the probability $\mathbf{Pr}(c\in \hat{P}_{i}(v) \text{ for all } v\in e)$ where $e$ is some hyperedge. Note that if the events $\{c\in  \hat{P}_{i}(v)\}$ are mutually independent, then we can easily do it.
However, we do not have such independence; worse still, these events are indeed positively correlated, as in the hypergraph set-up, two vertices $v, u\in e$ can share some common neighbors from $e$, even with the triangle-freeness.
Fortunately, the next lemma shows that although these events are not independent, they are `almost independent'.

\begin{lemma}\label{lem:dep}
Let $1\leq i\leq T$, and $c$ be an arbitrary color.
For any $e_0\in \cup_{\ell=2}^k\mathcal{H}^{i-1}_{\ell, c}$ and $S\subseteq e_0$,
\begin{equation}
\mathbf{Pr}(c\in \hat{P}_{i}(v) \text{ for all } v\in S) \leq (1 + \varepsilon_0)\prod_{v\in S}\mathbf{Pr}(c\in \hat{P}_{i}(v)) = (1 + \varepsilon_0)\beta^{|S|},
\end{equation}
where $\varepsilon_0=\beta\pi_{i}p_{i-1}/60$.
\end{lemma}
\begin{proof}
By~\eqref{eq:ncolor} and the fact that $\eta^{i}_{v, c}$'s are independent variables, it is sufficient to prove that
\begin{equation}
\mathbf{Pr}(c\notin L_{i}(v) \text{ for all } v\in S) \leq (1 + \varepsilon_0)\prod_{v\in S}\mathbf{Pr}(c\notin L_{i}(v)).
\end{equation}

For a vertex $v\in S$, and an edge $e\in\bigcup_{\ell=2}^{k}\mathcal{H}^{i-1}_{\ell, c}$, denote by $\mathcal{A}_{e, v}$ the event that $\gamma^{i}_{u,c}=1$ for all $u\in e-v$.
For each $v\in S$, let $\mathcal{I}_v=\left\{(e, v):\ v\in e\in\bigcup_{\ell=2}^{k}\mathcal{H}^{i-1}_{\ell, c}\right\}$ be an finite index set.
Note that by~\eqref{reduce:de},
\begin{equation}\label{dep:assum}
\text{there is no two distinct pairs $(e, v), (e', v')$ in the index sets such that $e\subsetneq e'$}.
\end{equation}
Then by the definition of $L_i(v)$ and $\mathcal{I}_v$, we have
\[
\mathbf{Pr}(c\notin L_{i}(v)) = \mathbf{Pr}\left(\bigwedge_{(e,v)\in\mathcal{I}_v}\overline{\mathcal{A}_{e,v}}\right)
\]
for each $v\in S$, and
\[
\mathbf{Pr}(c\notin L_{i}(v) \text{ for all } v\in S) = \mathbf{Pr}\left(\bigwedge_{v\in S}\bigwedge_{(e,v)\in\mathcal{I}_v}\overline{\mathcal{A}_{e,v}}\right).
\]

Write $(e,v)\sim (e', v')$, if $(e, v)\neq (e', v')$ and $(e-v)\cap (e' -v')\neq \emptyset$. We will need the following claim.
\begin{claim}\label{claim:dep}
If $(e,v)\sim (e', v')$, then $|e'|>(e-v)\cap (e' -v')|+1$.
\end{claim}
\begin{proof}
Assume by contradiction that $|e'|=|(e-v)\cap (e' -v')|+1$, i.e., $e'=(e-v)\cap (e' -v')+v'$.
Then we must have $v\neq v'$ and $e\neq e_0$, as otherwise, we either have $(e, v)=(e', v')$, or $e'\subsetneq e$, which contradicts~\eqref{dep:assum}.
Moreover, $e'$ cannot be equal to either $e_0$ or $e$, because $v\notin e'$ but $v\in e, e_0$.

Now we have $v\neq v'$ and $e, e', e_0$ are three distinct edges.
Note that again by~\eqref{reduce:de}, $e'$ cannot be fully contained in $e_0$, and so for $(e-v)\cap (e' -v')$.
Therefore, there exists an vertex $w\in (e-v)\cap (e' -v')$ such that $w\notin e_0$.
Then $\{e_0, e, e'\}$ forms a triangle as $\{v, v'\}\subseteq e_0$, $\{v, w\}\subseteq e$, $\{v', w\}\subseteq e'$, and $\{v, v', w\}\cap e_0\cap e\cap e'=\emptyset$.
This contradicts Proposition~\ref{trianglefree}.

\end{proof}

Now we are ready to apply Theorem~\ref{Janson} (Janson's Inequality) on $\mathbf{Pr}\left(\bigwedge_{v\in S}\bigwedge_{(e,v)\in\mathcal{I}_v}\overline{\mathcal{A}_{e,v}}\right)$.
We first set
\[
M:= \prod_{v\in S}\prod_{(e,v)\in\mathcal{I}_v}\mathbf{Pr}\left(\overline{\mathcal{A}_{e,v}}\right),
\]
and note that
\begin{equation}\label{dep:M}
M=\prod_{v\in S}\left(\prod_{(e,v)\in\mathcal{I}_v}\mathbf{Pr}\left(\overline{\mathcal{A}_{e,v}}\right)\right)
\leq \prod_{v\in S}\mathbf{Pr}\left(\bigwedge_{(e,v)\in\mathcal{I}_v}\overline{\mathcal{A}_{e,v}}\right)
=\prod_{v\in S}\mathbf{Pr}(c\notin L_{i}(v)).
\end{equation}
Next, we define
\[
\begin{aligned}
\mu:&=\sum_{v\in S}\sum_{(e, v)\in \mathcal{I}_v}\mathbf{Pr}(\mathcal{A}_{e,v})=\sum_{v\in S}\sum_{(e, v)\in \mathcal{I}_v}\pi_{i}^{|e|-1} & \quad \text{defn. of $\mathcal{A}_{e,v}$}\\
&\leq \sum_{v\in S}\sum_{\ell=2}^{k}d^{i-1}_{\ell}(v, c)\pi_{i}^{\ell-1}
\leq \frac{2t_{i-1}}{(\cdep_{i-1})^{k-1}}\sum_{v\in S}\sum_{\ell=2}^{k}(\cdep_{i-1}\pi_{i})^{\ell-1}           & \text{by~\eqref{ite:asump2}}\\
&=\frac{2t_{i-1}}{(\cdep_{i-1})^{k-1}}\cdot k^2(\cdep_{i-1}\pi_{i})& \text{by~\eqref{indas4}} \\
&=k^2\varphi_2/2.  & \pi_{i}=\varphi_2\frac{(\cdep_{i-1})^{k-2}}{4t_{i-1}}
\end{aligned}
\]

Then we have
\[
\begin{aligned}
\Delta^*:&=\sum_{(e, v)}\sum_{(e', v')\sim (e, v)}\mathbf{Pr}(\mathcal{A}_{e, v}\wedge\mathcal{A}_{e',v'})=\sum_{(e, v)}\mathbf{Pr}(\mathcal{A}_{e, v})\sum_{(e', v')\sim (e, v)}\mathbf{Pr}(\mathcal{A}_{e',v'}\mid \mathcal{A}_{e, v}) &\\
&= \sum_{(e, v)}\mathbf{Pr}(\mathcal{A}_{e, v})\sum_{(e', v')\sim (e, v)}\pi_{i}^{|e'-v'-e|} & \text{defn. of $\mathcal{A}_{e,v}$}\\
&\leq \sum_{(e, v)}\mathbf{Pr}(\mathcal{A}_{e, v})\sum_{q=1}^{|e-v|}\sum_{Q\in\binom{e-v}{q}}\sum_{\substack{(e', v') s.t.\\ v'\notin Q,\ Q+v'\subseteq e' \\ |e'|>q+1}}\pi_{i}^{|e'|-q-1} & \text{Claim~\ref{claim:dep}}\\
&\leq \sum_{(e, v)}\mathbf{Pr}(\mathcal{A}_{e, v})\sum_{q=1}^{|e-v|}\sum_{Q\in\binom{e-v}{q}}|S|\sum_{s=q+2}^{k}(\cdep_{i-1})^{s-q-1}\cdot \pi_{i}^{s-q-1} & \text{by~\eqref{reduce:code}}\\
&\leq\mu\cdot 2^{k-1}k^2(\cdep_{i-1}\pi_{i})& \text{by~\eqref{indas4}}\\
&\leq 2^{k-2}k^4(\varphi_2\cdep_{i-1}\pi_{i})\leq \beta\pi_{i}p_{i-1}/120. & \text{$\varphi_1, \varphi_2\ll 1$}
\end{aligned}
\]
Observe that for each $(e, v)$, we have $\mathbf{Pr}(\mathcal{A}_{e, v})\leq \pi_{i} \ll 1/2.$
Then by Theorem~\ref{Janson} and~\eqref{dep:M}, we obtain that
\[
\mathbf{Pr}\left(\bigwedge_{v\in S}\bigwedge_{(e,v)\in\mathcal{I}_v}\overline{\mathcal{A}_{e,v}}\right) \leq M\exp(\Delta^*) \leq M(1 + \beta\pi_{i}p_{i-1}/60)=(1 + \varepsilon_0)\prod_{v\in S}\mathbf{Pr}(c\notin L_{i}(v)),
\]
which completes the proof.
\end{proof}

\subsection{Expectation of degrees}
we consider the expectation of $\mathbf{X}_{\ell}$. For each $2\leq \ell \leq k$, recall from~\eqref{def:keedge} that
\[
\mathbf{X}_{\ell}=\sum_{c\inP_{i-1}(u)}\sum_{\substack{e\in\mathcal{H}^{i-1}_{\ell, c}\\ u\in e}} \mathbf{I}[x\in U_{i} \text{ for all $x\in e\setminus\{u\}$} \ \&\  c\in\hat{P}_{i}(y) \text{ for all } y\in e],
\]
Fix a color $c\inP_{i-1}(u)$, and an edge $e\in\mathcal{H}^{i-1}_{\ell, c}$ containing $u$. We first prove the following claim.
\begin{claim}\label{claim:mono1}
For every vertex $x\in e-\{u\}$,
\[
\mathbf{Pr}(x\in U_{i} \mid  c\in\hat{P}_{i}(y) \text{ for all } y\in e)\leq \alpha_{i},
\]
where $\alpha_{i}=1 - \beta\pi_{i}p_{i-1}/5$.
\end{claim}
\begin{proof}
Recall from the main algorithm that a vertex $x$ remains uncolored in step $i$, if and only if none of colors from $P_{i-1}(x)$ survives in $\hat{P}_{i}(x)\cap A_{i}(x)$. Then we have
\[
\begin{split}
\mathbf{Pr}\left(x\in U_{i} \mid c\in\hat{P}_{i}(y) \text{ for all } y\in e\right)
&=\mathbf{Pr}\left(\hat{P}_{i}(x)\capA_{i}(x)=\emptyset \mid c\in\hat{P}_{i}(y) \text{ for all } y\in e\right)\\
&\leq\mathbf{Pr}\left(\hat{P}_{i}(x)\capA_{i}(x)-\{c\}=\emptyset \mid c\in\hat{P}_{i}(y) \text{ for all } y\in e\right)\\
&=\mathbf{Pr}\left(\hat{P}_{i}(x)\capA_{i}(x)-\{c\}=\emptyset\right),
\end{split}
\]
where the last equality follows from the independence of random variables among different colors.
Recall from Lemma~\ref{lem:exceout1} that $\Omega\setminus\Omega_1^*$ represents all the possible outcomes in the probability space, such that the following event holds:
\[
|\hat{P}_{i}(v)|\geq (1 - \varepsilon/8)\beta|P_{i-1}(v)| \quad \text{for all vertices $v\in N^2_{i-1}(u)$}.
\]
Then by Lemma~\ref{lem:prb}, we have
\[
\begin{split}
\mathbf{Pr}\left(\hat{P}_{i}(x)\capA_{i}(x)-\{c\}=\emptyset\right) &\leq \mathbf{Pr}\left(\hat{P}_{i}(x)\capA_{i}(x)-\{c\}=\emptyset \mid \Omega\setminus\Omega_1^*\right) + \mathbf{Pr}\left(\Omega\setminus\Omega_1^*\right)\\
&\leq (1 - \pi_{i})^{(1 - \varepsilon/8)\beta|P_{i-1}(v)|-1} +  k^4\Delta^2\exp\left(-\Omega(\varepsilon^2p_{i})\right) \\
&\leq (1 - \pi_{i})^{(1 -  (1 + \varepsilon)^{i-1}/2)(1 - \varepsilon/8)^{i}\betap_{i-1}-1} +  k^4\Delta^2\exp\left(-\Omega(\varepsilon^2p_{i-1})\right) \\
&\leq(1 - \beta\pi_{i}p_{i-1}/4)+  k^4\Delta^2\exp\left(-\Omega(\varepsilon^2p_{i-1})\right)\leq \alpha_{i},
\end{split}
\]
where the third inequality uses Proposition~\ref{prop:pbou}. This, together with the previous inequality, completes the proof.
\end{proof}

Applying Claim~\ref{claim:mono1} and Lemma~\ref{lem:dep}, we have
\begin{multline*}
\mathbf{Pr}\left(x\in U_{i} \text{ for all $x\in e\setminus\{u\}$} \ \&\  c\in\hat{P}_{i}(y) \text{ for all } y\in e\right)\\
\leq \alpha_{i}\cdot\mathbf{Pr}(c\in\hat{P}_{i}(y) \text{ for all } y\in e)\le (1 + \varepsilon_0)\alpha_{i}\beta^{\ell}.
\end{multline*}
Finally, using the linearity of the expectation, we obtain that
\begin{equation}\label{exp:de}
\mathbf{E}[\mathbf{X}_{\ell}] \leq  (1 + \varepsilon_0)\alpha_{i}\beta^{\ell}\sum_{c\in P_{i-1}(u)}d^{i-1}_{\ell}(u, c).
\end{equation}

Next, we consider the expectation of $\mathbf{X}_{\ell, s}$.
For every $2\leq \ell <s\leq k-1$, recall from~\eqref{def:inedge} that
\[
\mathbf{X}_{\ell, s}:=\sum_{c\inP_{i-1}(u)}\sum_{\substack{e\in \mathcal{H}^{i-1}_{s, c}\\ u\in e}}\sum_{Q\in\binom{e-u}{s-\ell}}
\mathbf{I}[c\inA_{i}(x) \text{ for all }x\in Q \ \&\ c\in \hat{P}_{i}(y) \text{ for all } y\in e].
\]
Again, fix a color $c\inP_{i-1}(u)$, an edge $e\in \mathcal{H}^{i-1}_{s, c}$ containing $u$, and a set $Q\in\binom{e-u}{s-\ell}$. We prove the following claim.
\begin{claim}
\begin{multline*}
\mathbf{Pr}(c\inA_{i}(x) \text{ for all }x\in Q \ \&\ c\in \hat{P}_{i}(y) \text{ for all } y\in e)\\
\leq \mathbf{Pr}(c\inA_{i}(x)\text{ for all $x\in Q$})\cdot \mathbf{Pr}(c\in \hat{P}_{i}(y) \text{ for all } y\in e).
\end{multline*}
\end{claim}
\begin{proof}

Recall from the algorithm that a color $c$ is in $\hat{P}_{i}(y)$, if $\eta^{i}_{y, c}=1$, and for every edge $e^*\in \mathcal{H}^{i-1}_{2, c}\cup\ldots\cup\mathcal{H}^{i-1}_{k, c}$ with $y\in e^*$, there exists a vertex $z\in e^*\setminus \{y\}$ such that $\gamma^{i}_{z, c}=0$.
Let \[N:=\left\{\mathbf{I}[\gamma^{i}_{v, c}=1]\right\}_{v\in N^2_{i-1}(u)}\cup\left\{\mathbf{I}[\eta^{i}_{v, c}=0]\right\}_{v\in N_{i-1}(u)}.\]
Then the event $\left\{c\in\hat{P}_{i}(y) \text{ for all } y\in e\right\}$ is a decreasing family of subsets of $N$, as a color $c$ is more likely to survive in the palette if less vertices are being $c$ activated, or less vertices have $c$ not kept.
On the other hand, the event $\left\{c\inA_{i}(x)\text{ for all $x\in Q$}\right\}$ is an increasing family of subsets of $N$.
These two facts, together Theorem~\ref{FKG}, give the desired result.
\end{proof}

This claim, together with the definition of $A_{i}(x)$ and Lemma~\ref{lem:dep}, gives that
\[
\begin{split}
& \mathbf{Pr}(c\inA_{i}(x) \text{ for all }x\in Q \ \&\ c\in \hat{P}_{i}(y) \text{ for all } y\in e)  \\
\leq\ & \mathbf{Pr}(c\inA_{i}(x)\text{ for all $x\in Q$})\cdot \mathbf{Pr}(c\in \hat{P}_{i}(y) \text{ for all } y\in e)
\leq (1 + \varepsilon_0)\pi_{i}^{s- \ell}\beta^{s}.
\end{split}
\]
Applying the linearity of the expectation, we obtain that
\begin{equation}\label{exp:code}
\mathbf{E}[\mathbf{X}_{\ell, s}] \leq (1 + \varepsilon_0)\binom{s-1}{s-\ell}\pi_{i}^{s- \ell}\beta^{s}\sum_{c\inP_{i-1}(u)}d^{i-1}_{s}(u, c).
\end{equation}

\subsection{Proof of the Key Lemma~}

\begin{proof}[Proof of the Key Lemma (Lemma~\ref{lem:key})]
Recall from~\eqref{def:sumde} that
\[
\sum_{c\in\hat{P}_{i}(u)}\hat{d}_{i}(u, c)
=\sum_{\ell=2}^k(\cdep_{i})^{k-\ell}\left(
\mathbf{X}_{\ell} + \sum_{s=\ell+1}^{k}\mathbf{X}_{\ell, s}\right).
\]
This, together with~\eqref{exp:de}, and~\eqref{exp:code}, shows that the expectation of the above sum is
\[
\begin{split}
\mathbf{E}\left[\sum_{c\in\hat{P}_{i}(u)}\hat{d}_{i}(u, c)\right]
&=\sum_{\ell=2}^k(\cdep_{i})^{k-\ell}
\left(\mathbf{E}[\mathbf{X}_{\ell}]
 + \sum_{s=\ell+1}^{k}\mathbf{E}[\mathbf{X}_{\ell, s}]\right)\\
&\leq \sum_{\ell=2}^k(\cdep_{i})^{k-\ell}
\left((1 + \varepsilon_0)\alpha_{i}\beta^{\ell}\sum_{c\in P_{i-1}(u)}d^{i-1}_{\ell}(u, c)\right.\\
& \quad \quad \quad \left. + \sum_{s=\ell+1}^{k}(1 + \varepsilon_0)\binom{s-1}{s-\ell}\pi_{i}^{s- \ell}\beta^{s}\sum_{c\inP_{i-1}(u)}d^{i-1}_{s}(u, c)\right) \\
&= (1 + \varepsilon_0)\beta^{k}\sum_{c\in P_{i-1}(u)}\sum_{\ell=2}^k(\cdep_{i-1})^{k-\ell}
\Bigg(\alpha_{i}d^{i-1}_{\ell}(u, c)\\
& \quad \quad \quad  + \sum_{s=\ell+1}^{k}\binom{s-1}{s-\ell}(\pi_{i}\beta)^{s- \ell}d^{i-1}_{s}(u, c)\Bigg)\\
&= (1 + \varepsilon_0)\beta^{k}\sum_{c\in P_{i-1}(u)}\Bigg[d^{i-1}_{2}(u, c)(\cdep_{i-1})^{k-2}\cdot \alpha_{i}\\
& \quad \quad \quad  + \sum_{\ell=3}^kd^{i-1}_{\ell}(u, c)\Bigg(
\alpha_{i}(\cdep_{i-1})^{k-\ell}
 + \sum_{q=2}^{\ell-1}\binom{\ell-1}{\ell-q}(\pi_{i}\beta)^{\ell - q}(\cdep_{i-1})^{k-q}\Bigg)\Bigg]\\
&= (1 + \varepsilon_0)\beta^{k}\sum_{c\in P_{i-1}(u)}\Bigg[d^{i-1}_{2}(u, c)(\cdep_{i-1})^{k-2}\cdot \alpha_{i}\\
& \quad \quad \quad  + \sum_{\ell=3}^kd^{i-1}_{\ell}(u, c)(\cdep_{i-1})^{k-\ell}\Bigg(
\alpha_{i}
 + \sum_{q=2}^{\ell-1}\binom{\ell-1}{\ell-q}(\varphi_1\beta\pi_{i}p_{i-1})^{\ell - q}\Bigg)\Bigg],
\end{split}
\]
where $\varepsilon_0=\beta\pi_{i}p_{i-1}/60$, and $\alpha_{i}=1 - \beta\pi_{i}p_{i-1}/5$.
Recall from~\eqref{indas4} that $\pi_{i}p_{i-1} \ll 1$. Then we have
\[
\sum_{q=2}^{\ell-1}\binom{\ell-1}{\ell-q}(\varphi_1\beta\pi_{i}p_{i-1})^{\ell - q}
\leq 2^{\ell-1}\varphi_1\beta\pi_{i}p_{i-1} \leq \beta\pi_{i}p_{i-1}/60,
\]
as $\varphi_1 \ll 1$.
Therefore, we obtain that
\[
\begin{split}
\mathbf{E}\left[\sum_{c\in\hat{P}_{i}(u)}\hat{d}_{i}(u, c)\right]
&\leq (1 + \varepsilon_0)(\alpha_{i} + \beta\pi_{i}p_{i-1}/60)\beta^{k}\sum_{c\in P_{i-1}(u)}\sum_{\ell=2}^kd^{i-1}_{\ell}(u, c)(\cdep_{i-1})^{k-\ell}\\
&\leq \alpha'_{i}\beta^{k}\sum_{c\in P_{i-1}(u)}d_{i-1}(u, c)
=\alpha'_{i}\beta^{k}|P_{i-1}(u)|\Lambda_{i-1}(u),
\end{split}
\]
where $\alpha'_{i}=1 -\beta\pi_{i}p_{i-1}/6.$
This, together with our concentration result, i.e., Lemma~\ref{lem:concen}, completes the proof.
\end{proof}

\section{Coloring algorithm}\label{sec:algo}

The input to our algorithm is a rank $k$, triangle-free  hypergraph $\mathcal{H}$, who satisfies all the degree and codegree assumptions in Theorem~\ref{mainthm2}.
Let $\mathcal{P}=\{P(u)\}_{u\in V(\mathcal{H})}$ be a list assignment of $\mathcal{H}$, where each $P(u)$ represents the color \textit{palette}, i.e., the set of usable colors of $u$.
Let
\[
\mathrm{C}:=\varphi_1^{-1}(\Delta/\log\Delta)^{1/(k-1)}
\]
be the number of colors in the palettes, where $\varphi_1:=1/(60\cdot2^k)$ is a small constant (chosen to fulfil the need of analysis).
The plan is to show that for any list assignment $\mathcal{P}$ with $|P(u)|= \mathrm{C}$ for all vertices $u$, our coloring algorithm always generate a proper partial coloring of $\mathcal{H}$, which can be easily extended to a proper coloring of $\mathcal{H}$.

\begin{table}[H]
\centering
\begin{tabular}{lll}
\hline
\hline
Notation & Value & Description \\
\hline
$\mathcal{H}$ &  & rank $k$, triangle-free hypergraph \\
$\Delta_{\ell}(\mathcal{H})$ &  $\leq \Delta^{1 - \frac{k - \ell}{k-1}} (\log \Delta)^{\frac{k - \ell}{ k-1}}$ & maximum $\ell$-degree\\
$\delta_{s, \ell}(\mathcal{H})$ &  $\leq(\Delta/\log\Delta)^{\frac{\ell - s}{k-1}}$ & maximum codegree\\
$P(u)$ &  & Color palette of the vertex $u$\\
$\mathrm{C}$ & $\varphi_1^{-1}(\Delta/\log\Delta)^{1/(k-1)}$ & number of colors in the palette\\
$\varphi_1$  & $1/(60\cdot2^k)$  & constant\\
\hline
\hline
\end{tabular}
\caption{Basic hypergraph parameters}
\end{table}

As already mentioned in Section~\ref{sec:intro}, in principle, our coloring algorithm is the same as the work of Pettie-Su~\cite{pettie2015distributed} for triangle-free graphs, but there are several important modifications we made in order to generalize the method to hypergraphs.
Before moving to the description of our main algorithm, we first introduce a \textit{codegree reduction algorithm}, which will be applied as a subroutine to control codegrees at each step of our coloring algorithm.

\subsection{Codegree reduction algorithm}\label{sec:coredu}
Given a rank $k$ hypergraph $\mathcal{F}$, and a function $f: \mathbb{Z}\times\mathbb{Z}\rightarrow \mathbb{Z}$, we will generate a new hypergraph with bounded codegrees through the following algorithm.
\newline

\noindent\textbf{Codegree reduction algorithm.}
Let $V:=V(\mathcal{F})$.
We start the algorithm with $\mathcal{F}^0:=\mathcal{F}$.
In the $i$-th iteration round, for every vertex $u$ and $2\leq k-i < \ell \leq k$, let
\[
F_{k-i, \ell}(u):=\left\{ S\subseteq V:\ |S|=k-i,\ u\in S,\  \text{and}\  \deg_{\ell}(S, \mathcal{F}^{i-1}) \geq f(k-i, \ell)\right\}.
\]
We then define $\mathcal{F}^i$ as the following:
\[
E(\mathcal{F}^i) := E(\mathcal{F}^{i-1}) - \bigcup_{u}\bigcup_{\ell>k-i}\bigcup_{S\in F_{k-i, \ell}(u)}\{e\in \mathcal{F}^{i-1}:\  e \supseteq S,\ |e|=\ell \} + \bigcup_{u}\bigcup_{\ell>k-i}F_{k-i, \ell}(u),
\]
and move to the next round.
We stop the algorithm after $k-2$ steps.
\newline

Intuitively speaking, in each round, we only adjust codegrees $\delta_{s, \ell}$ with given $s$, and the ordering we picked to run the algorithm ensures that, the codegrees we have already adjusted will not increase in the future steps.

\begin{defi}[$f$-reduction]
For two hypergraphs $\mathcal{F},\ \mathcal{F}'$, and a function $f: \mathbb{Z}\times\mathbb{Z}\rightarrow \mathbb{Z}$, we say $\mathcal{F}'$ is an \textit{$f$-reduction} of $\mathcal{F}$, if $\mathcal{F}'$ is generated from the \textit{codegree reduction algorithm} with the input $\mathcal{F}$.
\end{defi}
\begin{prop}\label{prop:redu}
Let $f: \mathbb{Z}\times\mathbb{Z}\rightarrow \mathbb{Z}$ be a function with $f(\ell, \ell)=1$ for every $\ell$, such that
\[f(s_1, \ell) < f(s_2, \ell) \quad \text{if $s_1> s_2$}.\]
For a rank $k$ hypergraph $\mathcal{F}$, the $f$-reduction $\mathcal{F}'$ of $\mathcal{F}$ satisfies the following properties:
\begin{itemize}
\item[(1)] for every $2\leq s < \ell \leq k$,
$\delta_{s, \ell}(\mathcal{F}')\leq f(s, \ell);$
\item[(2)] any proper coloring of $\mathcal{F}'$ is also proper for $\mathcal{F}$.
\end{itemize}
Moreover, if $\mathcal{F}$ is triangle-free, then $\mathcal{F}'$ is also triangle-free.
\end{prop}
\begin{proof}
The first two properties follow directly from the construction of the $f$-reduction hypergraph.
Now, assume that $\mathcal{F}$ is triangle-free, and let $\mathcal{F}^0, \ldots, \mathcal{F}^{k-2}$ be the hypergraphs generated from our reduction algorithm. Note that $\mathcal{F}'=\mathcal{F}^{k-2}$. To show that $\mathcal{F}'$ is triangle-free, we will prove by induction on $i$ that every $\mathcal{F}^i$ is triangle-free.

The base case $i=0$ is trivially true as $\mathcal{F}^0=\mathcal{F}$.
Suppose that $\mathcal{F}^{i-1}$ is triangle-free, and assume by contradiction that there exists a triangle $\{e, f, g\}$ in $\mathcal{F}^{i}$ with vertices $u, v, w$ such that $\{u, v\}\subseteq e$, $\{v, w\}\subseteq f$, $\{w, u\}\subseteq g$ and $\{u, v, w\}\cap e\cap f\cap g=\emptyset$. In particular, we have $w\notin e$.
Clearly, a least one of these three edges is not in $\mathcal{H}^{i-1}$. To simplify the discussion, we further assume that $e$ is the only edge who is in $\mathcal{F}^{i}$  but not in $\mathcal{F}^{i-1}$; other cases follow by similar arguments which we omit.

By the definition of $e$ and $\mathcal{F}^{i}$, we have $|e|=k-i$, and moreover, there exists an integer $\ell > k-i$ such that there are at least $f(k-i, \ell)$ edges in $\mathcal{F}^{i-1}$ which contain $e$.
Note that the construction of $\mathcal{F}^{i-1}$ gives that $\delta_{k-i+1, \ell}(\mathcal{F}^{i-1}) \leq f(k-i+1, \ell)$, which is strictly less than $f(k-i, \ell)$ by the definition of $f$.
Therefore, there must be at least one edge in $\mathcal{F}^{i-1}$, say $e'$, such that $e'\supseteq e$ and $w\notin e'$. Then $\{e', f, g\}$ forms a triangle in $\mathcal{F}^{i-1}$, which contradicts our induction assumption.
\end{proof}

\subsection{Coloring algorithm}
We now describe the coloring algorithm as follows.
\newline

\noindent\textbf{Initial set-ups of the algorithm.}
For every vertex $u\in V(\mathcal{H})$, let $P_{0}(u):=P(u)$.
Denote by $U_0:=V(\mathcal{H})$ the set of uncolored vertices.
For any color $c$ and $2\leq \ell \leq k-1$, let
\[
\mathcal{H}^0_{\ell, c}:=\{e\in\mathcal{H} :\ |e|=\ell, \text{ and } c\in P_{0}(u) \text{ for all } u\in e\}
\]
be the $\ell$-uniform hypergraph who records all the coloring restrictions of size $\ell$ related to the color $c$.
Intuitively speaking, in a proper coloring of $\mathcal{H}$, none of the edges in $\mathcal{H}^0_{\ell, c}$ will be allowed to have all its vertices colored by $c$.
For every vertex $u$, let $d^0_{\ell}(u, c)$ be the number of edges in $\mathcal{H}^0_{\ell, c}$ incident to $u$.
Set
\[
p_0:=\mathrm{C} \quad \text{and} \quad t_0:=(k-1)\Delta.
\]
We then define the \textit{$c$-degree of $u$} to be
\[
d_0(u, c):=\sum_{\ell=2}^k(\varphi_1 p_{0})^{k-\ell} d^{0}_{\ell}(u, c).
\]
Note that by definition we have that for all $u$ and $c\in P_0(u)$,
\[
d_0(u, c)\leq \sum_{\ell=2}^k(\varphi_1 \mathrm{C})^{k-\ell}\Delta^{1 - \frac{k - \ell}{k-1}} (\log \Delta)^{\frac{k - \ell}{ k-1}}=\sum_{\ell=2}^k \Delta =(k-1)\Delta \leq  2t_0,
\]
and
\[
\delta_{s, \ell}(\mathcal{H}^{0}_{\ell, c})\leq \left(\frac{\Delta}{\log\Delta}\right)^{\frac{\ell-s}{k-1}}=(\cdep_0)^{\ell-s}.
\]
\newline

\noindent\textbf{Iteration of the algorithm.}
At the beginning of the $i$-th iteration round, we are given
\begin{itemize}
\item an \textit{ideal $c$-degree} $t_{i-1}$,
\item an \textit{ideal palette size} $p_{i-1}$,
\item a set of uncolored vertices $U_{i-1}$,
\item a family of hypergraphs $\{\mathcal{H}^{i-1}_{\ell, c}\}_{\ell, c}$,
\item a sequence of $c$-degrees $\{d_{i-1}(u, c)\}_{u, c}$,
\item and a collection of color palettes $\{P_{i-1}(u)\}_{u}$,
\end{itemize}
who satisfy the following induction assumptions:
\begin{equation}\label{ite:asump1}
d_{i-1}(u, c) \leq 2t_{i-1}, \quad \text{for all }u\in U_{i-1} \text{ and } c\in P_{i-1}(u),
\end{equation}
and
\begin{equation}\label{ite:asumpcode}
\delta_{s, \ell}(\mathcal{H}^{i-1}_{\ell, c})\leq (\cdep_{i-1})^{\ell-s} \quad \text{for all } c.
\end{equation}
It is important to note that
\[d_{i-1}(u, c)=\sum_{\ell=2}^k(\varphi_1 p_{i-1})^{k-\ell} d^{i-1}_{\ell}(u, c),\]
where $d^{i-1}_{\ell}(u, c)$ is the number of edges incident to $u$ in $\mathcal{H}^{i-1}_{\ell, c}$.
Hence, \eqref{ite:asump1} further implies
\begin{equation}\label{ite:asump2}
d^{i-1}_{\ell}(u, c)\leq 2t_{i-1}/(\varphi_1 p_{i-1})^{k-\ell} \quad \text{for each } \ell.
\end{equation}

The iterative algorithm runs as follows.
\begin{enumerate}
\item For every vertex $u\in U_{i-1}$, independently activate each of the color $c\in P_{i-1}(u)$ with probability \[\pi_{i}:=\varphi_2\frac{(\cdep_{i-1})^{k-2}}{4t_{i-1}}, \]
where $\varphi_2:=1/k^4$ is a small constant.
Let
\[
\gamma^{i}_{u, c}:=\begin{cases}
1, & \text{ if } c \text{ is activated on } u \\
0, & \text{ otherwise, }
\end{cases}
\]
be the indicator random variable for such activation operation, and then define the \textit{set of activated colors} of $u$ as $A_{i}(u):=\{c\inP_{i-1}(u): \gamma^{i}_{u, c}=1\}$.

\item We say a color $c$ is \textit{lost} at a vertex $u$, if there exists an edge $e\in\cup_{\ell\geq 2}\mathcal{H}^{i-1}_{\ell, c}$ s.t.
$u\in e$ and $\gamma^{i}_{u, c}=1$ for all $v\in e\setminus\{u\}$.
Denote by $L_{i}(u)$ the \textit{set of lost colors} of $u$, and by $q^{i}_{u, c}$ the probability that a color $c$ is \textit{not} lost at $u$. Note that
\[
\begin{split}
q^{i}_{u, c}&= \mathbf{Pr}(c\notinL_{i}(u))
\geq 1 - \sum_{\ell=2}^{k}d^{i -1}_{\ell}(u, c)\pi_{i}^{\ell-1}
\geq 1 - \sum_{\ell=2}^{k}\frac{2t_{i-1}}{(\cdep_{i-1})^{k-\ell}}\pi_{i}^{\ell-1}\\
&\geq 1- \frac{2t_{i-1}}{(\cdep_{i-1})^{k-1}}\sum_{\ell=2}^{k}(\cdep_{i-1}\pi_{i})^{\ell-1}
\geq 1- \frac{2t_{i-1}}{(\cdep_{i-1})^{k-1}}2\cdep_{i-1}\pi_{i} = 1- \varphi_2,
\end{split}
\]
where the second inequality follows from~\eqref{ite:asump2}, and the last inequality uses a fact that $\cdep_{i-1}\pi_{i} \ll 1$, due to the termination condition of the algorithm (see later in~\eqref{fact} for details).
\item
For ease of notation, let
\[
\beta:=1 - \varphi_2.
\]
Now, for every vertex $u\in U_{i-1}$, independently select each color $c\in P_{i-1}(u)$ with probability $\beta/q^{i}_{u, c}$.
Define the indicator variable
\[
\eta^{i}_{u, c}=\begin{cases}
1, & \text{ if } c \text{ is selected on } u \\
0, & \text{ otherwise, }
\end{cases}
\]
and let the \textit{set of selected colors} of $u$ be $K_{i}(u):=\{c\inP_{i-1}(u): \eta^{i}_{u, c}=1\}$.

\item
For every $u\in U_{i-1}$, set the \textit{temporary palette} of the vertex $u$ to be
\[\hat{P}_{i}(u):=K_{i}(u)\setminus L_{i}(u).\] Note that
\begin{equation}\label{eq:ncolor}
\mathbf{Pr}(c\in\hat{P}_{i}(u))
=\mathbf{Pr}(c\notinL_{i}(u))\mathbf{Pr}(\eta^{i}_{u, c}=1)
=\beta\quad\text{ for every } c\inP_{i-1}(u),
\end{equation}
and therefore we have $\mathbf{E}[\hat{P}_{i}(u)] = \beta|P_{i-1}(u)|$.

\item Now we start to assign colors to some vertices.
We \textit{permanently color} a vertex $u$ by any of the colors in $A_{i}(u)\cap \hat{P}_{i}(u)$, if $A_{i}(u)\cap \hat{P}_{i}(u) \neq \emptyset$.
Once a vertex receives a permanent color, we immediately remove it from $U_{i-1}$.
In the end of this process, let $U_{i}$ be the set of remaining vertices in $U_{i-1}$.

\item
Set
\begin{equation}
p_{i}:=\betap_{i-1}, \quad t_{i}:=\alpha'_{i}\beta^{k-1}t_{i-1},
\end{equation}
who represents the ideal palette size and the ideal $c$-degree after this round.
For every color $c$ and $\ell$, define
\[
\begin{split}
\hat{\mathcal{H}}^{i}_{\ell, c}=&\left\{e\in\mathcal{H}^{i-1}_{\ell, c}:\ e\subseteq U_{i},\ c\in \hat{P}_{i}(u) \text{ for all } u\in e\right\} \\
 &+ \left\{S\subseteq \binom{U_{i}}{\ell}: S\subsetneq e\in \bigcup_{s> \ell}\mathcal{H}^{i-1}_{s, c},\ c\in \bigcap_{u\in S}\hat{P}_{i}(u)\ \& \text{ all } v\in e\setminus S \text{ are colored by } c\right\}.
 \end{split}
\]
Note that $\hat{\mathcal{H}}^{i}_{\ell, c}$'s record all the coloring restrictions, that is, none of the edges in $\hat{\mathcal{H}}^{i}_{\ell, c}$ could have all its vertices colored by $c$.
In other words, any extension of the current partial coloring will be a proper coloring of $\mathcal{H}$, if it does not violate the above mentioned restriction.

\item
While it seems natural to proceed to the next round now, as discovered by Pettie-Su~\cite{pettie2015distributed}, we need to \textit{filter out} colors with large $c$-degree, in order to better control the algorithm.
We first let the \textit{temporary $c$-degree} of $u$ be
\begin{equation}
\hat{d}_{i}(u, c):=\sum_{\ell=2}^k(\varphi_1 p_{i})^{k-\ell}\hat{d}^{i}_{\ell}(u, c),
\end{equation}
where $\hat{d}^{i}_{\ell}(u, c)$ is the number of edges incident to $u$ in $\hat{\mathcal{H}}^{i}_{\ell, c}$.
Then we define the \textit{new palette} of $u$ as
\begin{equation}
P_{i}(u) := \{c\in \hat{P}_{i}(u):\ \hat{d}_{i}(u, c)\leq 2t_{i}\}.
\end{equation}
We further assume, without loss of generality, that
\begin{equation}\label{def:palet}
|P_{i}(u)|:=\min\{|\{c\in \hat{P}_{i}(u):\ \hat{d}_{i}(u, c)\leq 2t_{i}\}|,\ p_{i}\},
\end{equation}
by deleting some extra colors with large $c$-degree from $P_{i}(u)$.
The purpose of this step is to give an upper bound on the size of palettes, which will be used in the analysis of degree concentration.
Indeed, we shall see later in Section~\ref{sec:mainthm2} that in each round, with high probability one always have $|P_{i}(u)|=(1 - o(1)) p_{i}$ for all $u\in U_{i}$.

\item Next we reach to another crucial step of the algorithm, \textit{reducing codegrees} of our hypergraphs.
For every color $c$ and $\ell$, let
\[
\mathcal{F}_{\ell, c}:=\{e\in\hat{\mathcal{H}}^{i}_{\ell, c}:\ c\in P_{i}(v) \text{ for all } v\in e\}.
\]
For integers $s, \ell\geq 0$, let $f(s, \ell):=(\cdep_{i})^{\ell-s}.$
Observe that such a function $f$ satisfies the assumption of Proposition~\ref{prop:redu}.
For each $c$, denote by $\mathcal{F}_c$ the $f$-reduction of $\bigcup_{\ell=2}^{k}\mathcal{F}_{\ell, c}$.

\item Finally, for every color $c$ and $\ell$, we define
\[
\mathcal{H}^{i}_{\ell, c}:=\{e\in\mathcal{F}_c: |e|=\ell\}.
\]
Observe that for every $e\in\mathcal{H}^{i}_{\ell, c}$, we have $c\in P_{i}(v)$ for all $v\in e$.
By Proposition~\ref{prop:redu}, we have that for every $c$ and $2\leq s<\ell\leq k$,
\begin{equation}\label{reduce:code}
\delta_{s, \ell}(\mathcal{H}^{i}_{\ell, c})\leq (\cdep_{i})^{\ell-s}.
\end{equation}
Let $d^{i}_{\ell}(u, c)$ be the number of edges in $\mathcal{H}^{i}_{\ell, c}$ which are incident to $u$, and define
\begin{equation}
d_{i}(u, c):=\sum_{\ell=2}^k(\varphi_1 p_{i})^{k-\ell}d^{i}_{\ell}(u, c).
\end{equation}
It is important to note that, $f$-reduction will not increase the value of our weighted sum of degrees, as $(\cdep_{i})^{k-s}\cdot 1 - (\cdep_{i})^{k-\ell}\cdot (\cdep_{i})^{\ell-s}=0$. Therefore, we have that for all $c\in P_{i}(u)$,
\begin{equation}
d_{i}(u, c)\leq \hat{d}_{i}(u, c)\leq 2t_i.
\end{equation}
Without loss of generality, we further assume that
\begin{equation}\label{reduce:de}
\text{
for each $c$, there is no pair of edges $e_1, e_2\in \sum_{\ell=2}^{k}\mathcal{H}^{i}_{\ell, c}$ such that $e_1\subsetneq e_2$,
}
\end{equation}
as otherwise we would always delete the larger edge $e_2$ (and this neither increases $d_{i}(u, c)$, nor loses information on coloring restrictions.)
After this, we move to the next round until the termination condition occurs.
\end{enumerate}
\vspace{3mm}

\noindent\textbf{The termination condition.}
For each $i\geq 0$, let \[\zeta_{i}:=\frac{t_{i}}{(\cdep_{i})^{k-1}},\] which measures the ratio between the ideal $c$-degree and the ideal palette size.
We terminate this semi-random coloring algorithm after $T$ rounds, where $T$ is the first integer such that
\begin{equation}\label{ratioT}
\zeta_{T}\leq 1/8k.
\end{equation}
Observe that $\zeta_{0}=(k-1)\log\Delta$, and
\[
\zeta_{i}=\frac{\alpha'_{i}\beta^{k-1}t_{i-1}}{(\varphi_1\betap_{i-1})^{k-1}}=\alpha'_{i}\frac{t_{i-1}}{(\cdep_{i-1})^{k-1}}
=\left(1 - \frac{\beta}{6}\left(\varphi_2\frac{(\cdep_{i-1})^{k-2}}{4t_{i-1}}\right)p_{i-1}\right)\frac{t_{i-1}}{(\cdep_{i-1})^{k-1}}
=\zeta_{i -1} - \frac{\beta\varphi_2}{24\varphi_1},
\]
which is a strictly decreasing function.
Therefore, we have
\[T\leq \frac{24(k-1)\varphi_1}{(1 - \varphi_2)\varphi_2}\log\Delta.\]

When the algorithm terminates, we obtain a proper partial coloring of $\mathcal{H}$, and there might still be some uncolored vertices $U^T$.
However, since now $\zeta_{T}$ is small enough, it is not hard to color the rest of vertices $U^T$ properly using the standard Local Lemma, see later in Section~\ref{sec:mainthm2} for details.
\newline

\subsection{Notation and parameters}
As shown above, the algorithm is parameterized by the ideal $c$-degrees $\{t_{i}\}$ and the ideal palette sizes $\{p_{i}\}$.
Of course, the \textit{actual} palette sizes and $c$-degrees after $i$ rounds will drift from their ideal values.
To account for deviations from the ideal, we let $p'_{i}$ and $t'_{i}$ be the \textit{approximate} versions of $p_{i}$ and $t_{i}$, defined in terms of a small error control parameter $\varepsilon$.
Besides, for ease of notation, we also introduce another parameter $\alpha_{i}$, who will be used to measure the decreasing rate of $c$-degrees. The precise definition of $p'_{i}$, $t'_{i}$ $\varepsilon$ and $\alpha_{i}$ will be presented in Table~\ref{table2}.

We summarize all notation and parameters in the below table for the convenience of readers.
\begin{table}[H]
\centering
\begin{tabular}{lll}
\hline
\hline
Notation & Value & Description \\
\hline
$U_{i}$ & & the set of uncolored vertices. \\
$P_{i}(u)$ &  & Color palette of the vertex $u$\\
$\mathcal{H}^{i}_{\ell, c}$ & & $\ell$-uniform hypergraph s.t. for any edge $e$, $c\in P_{i}(v)$ for all $v\in e$\\
$d^{i}_{\ell}(u, c)$ & & number of edges of $\mathcal{H}^{i}_{\ell, c}$ that are incident to $u$\\
$d_{i}(u, c)$ & $\sum_{\ell=2}^k(\varphi_1 p_{i})^{k-\ell}d^{i}_{\ell}(u, c)$& $c$-degree of $u$\\
$\hat{P}_{i}(u)$ &  & temporary palette of the vertex $u$\\
$\hat{\mathcal{H}}^{i}_{\ell, c}$ & & $\ell$-uniform hypergraph s.t. for any edge $e$, $c\in \hat{P}_{i}(v)$ for all $v\in e$\\
$\hat{d}^{i}_{\ell}(u, c)$ & & number of edges of $\hat{\mathcal{H}}^{i}_{\ell, c}$ that are incident to $u$\\
$\hat{d}_{i}(u, c)$ & $\sum_{\ell=2}^k(\varphi_1 p_{i})^{k-\ell}\hat{d}^{i}_{\ell}(u, c)$& temporary $c$-degree of $u$\\
\hline
$\gamma^{i}_{u, c}$ & & indicater variable for the event that $c$ is activated on $u$\\
$\eta^{i}_{u, c}$ & & indicater variable for the event that $c$ is kept on $u$\\
$A_{i}(u)$ & & the set of activated color of the vertex $u$\\
$L_{i}(u)$ & & the set of lost color of the vertex $u$\\
$K_{i}(u)$ & & the set of selected color of the vertex $u$\\
$\pi_{i}$ & $\varphi_2\frac{(\cdep_{i-1})^{k-2}}{4t_{i-1}}$  & color-activation probability\\
$\beta$ & $1 - \frac{4t_{i -1}\pi_{i}}{(\varphi_1 p_{i-1})^{k-2}}=1 - \varphi_2$   & ideal probability of retaining a color\\
$\alpha_{i}$ &  $1 - \beta\pi_{i}p_{i-1}/5$  & decreasing rate\\
$\alpha'_{i}$ & $1 - \beta\pi_{i}p_{i-1}/6$  & adjusted decreasing rate\\
\hline
$p_{0}$ & $\varphi_1^{-1}(\Delta/\log\Delta)^{1/(k-1)}$ & ideal palette size \\
$p_{i}$ & $\betap_{i-1}$ & ideal palette size \\
$p'_{i}$ & $(1 - \varepsilon/8)^{i}p_{i}$  & approximate palette size \\
$t_{0}$ & $(k-1)\Delta$  & ideal $c$-degree\\
$t_{i}$ & $\alpha'_{i}\beta^{k-1}t_{i-1}$  & ideal $c$-degree\\
$t'_{i}$ & $(1 + \varepsilon)^{i}t_{i}$   & approximate $c$-degree\\
$\zeta_{i}$ & $\frac{t_{i}}{(\cdep_{i})^{k-1}}$ & a ratio\\
$T$  &  $\leq\frac{24(k-1)\varphi_1}{(1 - \varphi_2)\varphi_2}\log\Delta$  & number of iteration rounds\\
\hline
$\varphi_1$  & $1/(60\cdot2^k)$  & constant\\
$\varphi_2$  & $1/k^4$  & constant\\
$\theta$  & $1/4k$  & constant\\
$\varepsilon$ &  $4\Delta^{-\theta}\log^{2k}\Delta$  & error term \\
\hline
\hline
\end{tabular}
\caption{Notation and parameters}
\label{table2}
\end{table}

To end this section, we present three useful facts which follow directly from the definition of parameters:
\begin{equation}\label{ratio}
 1/8k \leq \zeta_{i} \leq (k-1)\log\Delta \quad \text{for all }0\leq i<T,
\end{equation}
\begin{equation}\label{fact}
\pi_{i}p_{i-1} \ll \varphi_1\pi_{i}p_{i-1} = \varphi_2/(4\zeta_{i-1})\ll 1 \quad \text{for all }0\leq i\leq T,
\end{equation}
and
\begin{equation}\label{pbound}
p_{i}\geq \beta^{T}p_0 \geq (1 - \varphi_2)^{\frac{24(k-1)\varphi_1}{(1 - \varphi_2)\varphi_2}\log\Delta}\varphi_1^{-1}(\Delta/\log\Delta)^{1/(k-1)}\geq\Delta^{\frac{1}{2(k-1)}} \quad \text{for all $0\leq i\leq T$}.
\end{equation}

\section{Concentration on $c$-degree}

\begin{center}
\begin{tabular}{lll}
\hline
\hline
Notation & Value  \\
\hline
$\overline{d}_{i}(u)$ & $\sum_{c\in P_{i}(u)}\frac{d_{i}(u, c)}{|P_{i}(u)|}$ \\
$\lambda_{i}(u)$ & $\min\left\{1, \frac{|P_{i}(u)|}{p'_{i}}\right\}$\\
$\mathcal{D}_{i}(u)$ & $\lambda_{i}(u)\overline{d}_{i}(u) + (1 - \lambda_{i}(u))2t_{i}$\\
$\hat{d}_{i}(u)$ & $\sum_{c\in \hat{P}_{i}(u)}\frac{d_{i}(u, c)}{|\hat{P}_{i}(u)|}$ \\
$\hat{\lambda}_{i}(u)$ & $\min\left\{1, \frac{|\hat{P}_{i}(u)|}{p'_{i}}\right\}$\\
\hline
\hline
\end{tabular}
\end{center}

We want to prove:
\begin{thm}\label{thm:de}
For every $1\leq i \leq T$ and every vertex $u\in U_{i}$,
\[
\mathbf{Pr}(\mathcal{D}_{i}(u)\leq t'_{i} \mid \mathcal{D}_{i-1}(u) \leq t'_{i-1} \text{ for all } u\in U_{i-1})\geq 1  - error?
\]
\end{thm}
\begin{prop}\label{prop:pbou}
For every $1\leq i \leq T$, if $\mathcal{D}_{i}(u)\leq t'_{i}$, then
\[
|P_{i}(u)|\geq (1 -  (1 + \varepsilon)^{i}/2)p'_{i}.
\]
\end{prop}
\begin{proof}
If $\mathcal{D}_{i}(u)\leq t'_{i}$, then by the definition $\mathcal{D}_{i}(u)$ we have
\[
(1 - \lambda_{i}(u))2t_{i}\leq \mathcal{D}_{i}(u)\leq t'_{i}.
\]
This gives that
\[
\frac{|P_{i}(u)|}{p'_{i}}\geq\lambda_{i}(u)\geq 1 - \frac{t'_{i}}{2t_{i}}=1 -  \frac{(1 + \varepsilon)^i}{2},
\]
which completes the proof.
\end{proof}

From now on, throughout this section, we assume the following induction assumption holds:
\begin{equation}\label{eq:indas}
\mathcal{D}_{i-1}(u) \leq t'_{i-1} \text{ for all } u\in U_{i-1}.
\end{equation}

To prove Theorem~\ref{thm:de}, the main work is to study the concentration of $d_{i}(u, c)$.

Fix an uncolored vertex $u\in U_{i}$.
\subsection{Step 1}
Define
\[
\hat{E}^{i}_{\ell}(u, c):=\{e\in \mathcal{H}^{i-1}_{\ell, c}:\ u\in e, \text{ and } c\in\hat{P}_{i}(x) \text{ for all } x\in e\},
\]
and let $\hat{h}^{i}_{\ell}(u, c):=|\hat{E}^{i}_{\ell}(u, c)|$.
Set
\[
\mathbf{X}:=\sum_{c\in\hat{P}_{i}(u)}\sum_{\ell=2}^{k}\hat{h}^{i}_{\ell}(u, c)(\cdep_{i})^{k-\ell}.
\]
In this section, we will concentrate $\mathbf{X}$.

For $c\in P_{i-1}(u)$, define
\[
\mathbf{Y}_c=\begin{cases}
\sum_{\ell=2}^{k}\hat{h}^{i}_{\ell}(u, c)(\cdep_{i})^{k-\ell}, & \text{ if } c\in \hat{P}_{i}(u) \\
0, & \text{ otherwise, }
\end{cases}
\]
Note that $\mathbf{Y}_c$ are pairwise independent and $0\leq \mathbf{Y}_c\leq \sum_{\ell=2}^{k}d^{i-1}_{\ell}(u, c)(\cdep_{i-1})^{k-\ell} =d_{i-1}(u, c)\leq 2t_{i-1}$ for each $c$ .

Then we have
\[
\begin{array}{lll}
\mathbf{E}[\mathbf{Y}_c]&=\mathbf{Pr}(c\in \hat{P}_{i}(u))\mathbf{E}[\mathbf{Y}_c\mid c\in \hat{P}_{i}(u)] & \\
&=\mathbf{Pr}(c\in \hat{P}_{i}(u))\sum_{\ell=2}^{k}(\cdep_i)^{k-\ell}
\sum_{\substack{e\in \mathcal{H}^{i-1}_{\ell,c}\\ u\in e}}\mathbf{Pr}(c\in\hat{P}_{i}(x) \text{ for all } x\in e \mid c\in \hat{P}_{i}(u)) &  \\
&=\sum_{\ell=2}^{k}(\cdep_i)^{k-\ell}
\sum_{\substack{e\in \mathcal{H}^{i-1}_{\ell,c}\\ u\in e}}\mathbf{Pr}(c\in\hat{P}_{i}(x) \text{ for all } x\in e) & \\
&\leq \sum_{\ell=2}^{k}(\cdep_i)^{k-\ell}
\sum_{\substack{e\in \mathcal{H}^{i-1}_{\ell,c}\\ u\in e}}(1 + \varepsilon_0)\prod_{x\in e}\mathbf{Pr}(c\in\hat{P}_{i}(x)) & \text{ by Lemma~\ref{lem:dep}} \\
&= (1 + \varepsilon_0)\sum_{\ell=2}^{k}(\cdep_i)^{k-\ell}
d^{i-1}_{\ell}(u, c)\beta_{i}^{\ell} & \\
&= (1 + \varepsilon_0)\beta_{i}^{k}\sum_{\ell=2}^{k}(\cdep_{i-1})^{k-\ell}
d^{i-1}_{\ell}(u, c)& \text{ by } p_{i}=\beta_{i}p_{i-1} \\
&= (1 + \varepsilon_0)\beta_{i}^{k}
d_{i-1}(u, c)&
\end{array}
\]
Therefore, we have
\[
\begin{array}{lll}
\mathbf{E}[\mathbf{X}]&=\sum_{c\in P_{i-1}(u)}\mathbf{E}[\mathbf{Y}_c]
\leq (1 + \varepsilon_0)\beta_{i}^{k}\sum_{c\in P_{i-1}(u)}
d_{i-1}(u, c)  & \\
&=  (1 + \varepsilon_0)\beta_{i}^{k}\overline{d}_{i-1}(u)|P_{i-1}(u)| & \text{ by }\overline{d}_{i-1}(u)=\sum_{c\in P_{i-1}(u)}\frac{d_{i-1}(u, c)}{|P_{i-1}(u)|}
\end{array}
\]
\ad{Here we assume $\varepsilon_0 \ll \varepsilon$.}

Hence, we obtain
\[
\begin{array}{lll}
&\mathbf{Pr}\left(\mathbf{X} \geq \beta_{i}^{k}|P_{i-1}(u)|\left(\overline{d}_{i-1}(u) + \frac{\varepsilon}{4}t_{i-1}\right)\right)\\
\leq &\mathbf{Pr}\left(\mathbf{X} \geq \beta_{i}^{k}|P_{i-1}(u)|\left((1 + \varepsilon_0)\overline{d}_{i-1}(u) + \frac{\varepsilon}{8}t_{i-1}\right)\right) & \text{ by }\varepsilon_0 \ll \varepsilon\ \&\  \overline{d}_{i-1}(u)\leq 2t_{i-1}\\
\leq & \mathbf{Pr}\left(\mathbf{X} \geq \mathbf{E}[\mathbf{X}] + \frac{\varepsilon}{8}\beta_{i}^{k}|P_{i-1}(u)|t_{i-1}\right) \\
\leq & \exp\left(-\frac{2(\varepsilon\beta_{i}^{k}|P_{i-1}(u)|t_{i-1})^2}{64\sum_{c\inP_{i-1}(u)}(2t_{i-1})^2}\right) & \text{ by Lemma~\ref{hoeffding}}\\
= & \exp\left(-\frac{\varepsilon^2\beta_{i}^{2k}|P_{i-1}(u)|}{128}\right) &  \\
\leq & \exp\left(-\frac{\varepsilon^2\beta_{i}^{2k}(1 -  (1 + \varepsilon)^{i-1}/2)p'_{i-1}}{128}\right) & \text{ by \eqref{eq:indas} \& Proposition~\ref{prop:pbou}} \\
\leq & \exp\left(-\Omega(\varepsilon^2p'_{i})\right) \ll  1 &
\end{array}
\]
Therefore, we show that w.h.p.
\[
\sum_{c\in\hat{P}_{i}(u)}\sum_{\ell=2}^{k}\hat{h}^{i}_{\ell}(u, c)(\cdep_{i})^{k-\ell} \leq  \beta_{i}^{k}|P_{i-1}(u)|\left(\overline{d}_{i-1}(u) + \frac{\varepsilon}{4}t_{i-1}\right).
\]

\subsection{Step 2}
For every $2\leq \ell \leq k$ and $c\in \hat{P}_{i}(u)$, define
\[
\tilde{h}^{i}_{\ell}(u, c):=\{e\in \hat{E}^{i}_{\ell}(u, c):\ x\in U_{i} \text{ for all } x\in e\}.
\]
Fix an integer $\ell$ and a color $c$, let us concentrate $\tilde{h}^{i}_{\ell}(u, c)$.
\newline

\noindent\textbf{Expectation.}
Fix an edge $e=uv_1\ldots v_{\ell-1}\in \hat{E}^{i}_{\ell}(u, c)$.
Let $\mathcal{A}$ be the event that $|\hat{P}_{i}(x)| \geq (1 - \varepsilon/8)\beta_{i}|P_{i-1}(x)|$ for all $x\sim v_1$.
By Chernoff bound (see Lemma~\ref{chernoff}) and~\eqref{eq:ncolor}, we have
\[
\begin{array}{lll}
|\mathbf{Pr}(\overline{\mathcal{A}})| &\leq k^2\Delta\exp\left(-\frac{(\varepsilon/8)^2\beta_{i}|P_{i-1}(x)|}{2 + \varepsilon/8}\right) &\\
&\leq k^2\Delta\exp\left(-\frac{(\varepsilon/8)^2\beta_{i}(1 -  (1 + \varepsilon)^{i}/2)p'_{i-1}}{2 + \varepsilon/8}\right)  & \text{ by Proposition~\ref{prop:pbou}}\\
&\leq  k^2\Delta\exp\left(-\Omega(\varepsilon^2p'_{i})\right)  & \text{ by } \beta_{i}=\Theta(1) \text{ and } p'_{i}=(1 - \varepsilon/8)\beta_{i}p'_{i-1},
\end{array}
\]
which is tiny.

If $\mathcal{A}$ holds, then by~Proposition~\ref{prop:pbou}, we have
\[
|\hat{P}_{i}(x)| \geq (1 - \varepsilon/8)\beta_{i}|P_{i-1}(x)| \geq (1 - \varepsilon/8)\beta_{i}(1 -  (1 + \varepsilon)^{i-1}/2)p'_{i-1}=(1 -  (1 + \varepsilon)^{i-1}/2)p'_{i}.
\]
Therefore,
\[
\begin{split}
\mathbf{Pr}(x\in U_{i} \text{ for all } x\in e)
&\leq \mathbf{Pr}(v_1\in U_{i} \mid \mathcal{A}) + \mathbf{Pr}(\overline{\mathcal{A}}) \\
&\leq (1 - \pi_{i})^{(1 -  (1 + \varepsilon)^{i-1}/2)p'_{i}} +  k^2\Delta\exp\left(-\Omega(\varepsilon^2p'_{i})\right)=\alpha_{i} + k^2\Delta\exp\left(-\Omega(\varepsilon^2p'_{i})\right).
\end{split}
\]
Finally, we have
\[
\mathbf{E}[\tilde{h}^{i}_{\ell}(u, c)]\leq \alpha_{i}\hat{d}^{i}_{\ell}(u, c) + k^2\Delta^2\exp\left(-\Omega(\varepsilon^2p'_{i})\right).
\]

\noindent\textbf{Concentration.}
Define
\[
\begin{split}
\mathbf{a}_{i_1, j_1, \ldots,i_{\ell-1}j_{\ell-1}}:=\ & \text{number of tuples } (v_1,\ldots,v_{\ell-1}) \text{ with } uv_1\ldots v_{\ell-1}\in \hat{E}^{i}_{\ell}(u, c) \text{ s.t. } \\
&\text{for each $v_r$, $|A_{i}(v_r)|=i_r$ and $|A_{i}(v_r)\cap(P_{i-1}(v_r) - \hat{P}_{i}(v_r))|=j_r$}.
\end{split}
\]
It is not hard to observe that
\[
\tilde{h}^{i}_{\ell}(u, c) = \sum_{\substack{0\leq i_r=j_r\leq \mathrm{C}\\  \forall r\in[\ell-1]}}\mathbf{a}_{i_1, j_1,i_2, j_2,\ldots,i_{\ell-1}j_{\ell-1}}.
\]
Therefore, it is sufficient to properly concentrate each $\mathbf{a}_{i_1, j_1, \ldots,i_{\ell-1}j_{\ell-1}}$.

First, similarly as before, when $j_r=i_r$, we have
\[
\begin{split}
\mathbf{E}[\mathbf{a}_{i_1, i_1 \ldots,i_{\ell-1}, i_{\ell-1}}]
&\leq \sum_{uv_1\ldots v_{\ell-1}\in \hat{E}^{i}_{\ell}(u, c)} \mathbf{Pr}(|A_{i}(v_1)|=i_1 \ \&\  |A_{i}(v_1)\cap(P_{i-1}(v_1) - \hat{P}_{i}(v_1))|=i_1 \mid \mathcal{A}) + \mathbf{Pr}(\overline{\mathcal{A}})\\
&\leq \sum_{uv_1\ldots v_{\ell-1}\in \hat{E}^{i}_{\ell}(u, c)}\binom{(1- (1 - \varepsilon/8)\beta_{i})|P_{i-1}(v_i)|}{i_1}\pi_{i}^{i_1}(1 - \pi_{i})^{|P_{i-1}(v_i)|- i_1} + \mathbf{Pr}(\overline{\mathcal{A}})\\
&\leq \binom{(1- (1 - \varepsilon/8)\beta_{i})|P_{i-1}(v_i)|}{i_1}\pi_{i}^{i_1}(1 - \pi_{i})^{|P_{i-1}(v_i)|- i_1} \hat{d}^{i}_{\ell}(u, c)   + k^2\Delta\exp\left(-\Omega(\varepsilon^2p'_{i})\right).
\end{split}
\]

Define
\[
\begin{split}
\mathbf{b}_{i_1, j_1, \ldots,i_{\ell-1}j_{\ell-1}}:=\ & \text{number of tuples } (v_1,\ldots,v_{\ell-1}) \text{ with } uv_1\ldots v_{\ell-1}\in \hat{E}^{i}_{\ell}(u, c) \text{ s.t. } \\
&\text{for each $v_r$, $|A_{i}(v_r)|\geq i_r$ and $|A_{i}(v_r)\cap(P_{i-1}(v_r) - \hat{P}_{i}(v_r))|\geq j_r$}.
\end{split}
\]
\begin{prop}
\[
\mathbf{a}_{i_1, j_1,\ldots,i_{\ell-1}}=\sum_{\substack{\sigma_r, \tau_r\in\{0,1\}\\  \forall r\in[\ell-1]}} (-1)^{f(\sigma_1, \tau_1, \ldots, \sigma_{\ell-1}, \tau_{\ell-1})}\mathbf{b}_{i_1+\sigma_1, j_1 +\tau_1, \ldots, i_{\ell-1} + \sigma_{\ell-1}, j_{\ell-1} + \tau_{\ell-1}},
\]
where
\[
f(\sigma_1, \tau_1, \ldots, \sigma_{\ell-1}, \tau_{\ell-1}):= \text{number of labels $r$ s.t. $\sigma_r\neq \tau_r$}.
\]
\end{prop}

We will use Lemma~\ref{talagrand} to concentrate $\mathbf{b}_{i_1, j_1,\ldots,i_{\ell-1}}$.
We first write it as a sum of indicator variables:
\[
\mathbf{b}_{i_1, j_1,\ldots,i_{\ell-1}} = \sum_{\substack{(v_1, \ldots, v_{\ell-1}) \text{ s.t. }\\ e=uv_1\ldots v_{\ell-1} \in \hat{E}^{i}_{\ell}(u, c)}} \mathbf{I}_{e},
\]
where $\mathbf{I}_e$ is the indicate variable for the event that for each $v_r$, $|A_{i}(v_r)|\geq i_r$ and $|A_{i}(v_r)\cap(P_{i-1}(v_r) - \hat{P}_{i}(v_r))|\geq j_r$.
Note that $\mathbf{b}_{i_1, j_1,\ldots,i_{\ell-1}}$ is determined by random varibles $\{\gamma^{i}_{v, c^*}\}_{v, c^*}\cup \{\eta^{i}_{v, c^*}\}_{v, c^*}$.

Consider a random sampling $\omega\in\Omega$ s.t. $\mathbf{I}_e(\omega)=1$. Then by definition, for each $v_r$, we have $|A_{i}(v_r)|\geq i_r$ and $|A_{i}(v_r)\cap(P_{i-1}(v_r) - \hat{P}_{i}(v_r))|\geq j_r$.

Let $C^a_{v_r}$ be a subset of colors $A_{i}(v_r)$ of size exactly $i_r$, and $C^l_{v_r}$ be a subset of colors $A_{i}(v_r)\cap(P_{i-1}(v_r) - \hat{P}_{i}(v_r))$ of size exactly $j_r$.

Recall that a color $c^*$ is lost on a vertex $v_r$, either because of $\eta^{i}_{v_r, c^*}=0$ or because there exists an edge $e_{r, c^*}\in\cup_{\ell\geq 2}\mathcal{H}^{i-1}_{\ell, c^*}$ s.t.
$v_r\in e_{r, c^*}$ and $\gamma^{i}_{v_r, c^*}=1$ for all $v\in e\setminus\{v_r\}$.
Let
\[
\hat{C}^l_{v_r}:=\{c^*\in C^l_{v_r} \mid \eta^{i}_{v_r, c^*}=0\} ,
\] and
\[
\tilde{C}^l_{v_r}:=\{c^*\in C^l_{v_r} \mid  e_{r, c^*} \text{ exsits}\}.
\]
Then we define the verifier of $\mathbf{I}_e$ to be
\[
R_{e}(\omega)=\bigcup_{r=1}^{\ell-1}\left[\left( \bigcup_{c^*\in C^a_{v_r}}\gamma^{i}_{v_r, c^*}\right)
\cup \left(\bigcup_{c^*\in \tilde{C}^l_{v_r}}\bigcup_{v\in e_{r, c^*}\setminus\{v_r\}}\gamma^{i}_{v, c^*}\right) \cup \left(\bigcup_{c^*\in \hat{C}^l_{v_r}}\eta^{i}_{v_r, c^*}\right)\right].
\]
Observe that $|R_{e}(\omega)|\leq \sum_{r=1}^{\ell-1}(i_r + j_r(k-1) + j_r)=\sum_{r=1}^{\ell-1}i_r + k\sum_{r=1}^{\ell-1}j_r$.
\ad{so this value could be in the order of $\mathrm{C}=\varphi_1(\Delta/\log\Delta)^{1/(k-1)}$.}

Next, for every $\omega\in\Omega$ and $i$,  define
\[
J_{\omega, i}:=\{e:\ \mathbf{I}_e(w)=1\ \&\ i\in R_{e}(w)\}.
\]
If $i=\eta_{v, c^*}$ for some $v, c^*$, then
\begin{equation}
|J_{\omega, i}| \leq \max_{v}\hat{h}^{i}_{\ell}(v, c^*)
\end{equation}
\ad{This is already too large...... For $i=\gamma_{v, c^*}$, the value will be even larger as the second neighborhood is involved. Another issue is that I believe we want to compare $rd$ with $\mathbf{E}[\mathbf{a}_{i_1, j_1,\ldots,i_{\ell-1}}]$, not $\mathbf{E}[\hat{h}^{i}_{\ell}(u, c)]$, as the later term is a sum of $\mathrm{C}^{\ell-1}$ many previous terms. If so, this require our $d$ should be even much smaller.}

\subsection{Step 3}
For every $2\leq \ell \leq k-1$ and $c\in \hat{P}_{i}(u)$, define
\[
\tilde{d}^{i}_{\ell}(u, c):=\sum_{s=\ell+1}^{k}\sum_{\substack{e\in \mathcal{H}^{i-1}_{s, c}\\ u\in e}}\sum_{S\in\binom{e}{\ell}}
\mathbf{I}[c\in \hat{P}_{i}(x) \text{ for all } x\in e\setminus\{u\}\ \&\ \text{all vertices in $e-S$ are colored by $c$}].
\]
Fix an integer $\ell$ and a color $c$, let us concentrate $\tilde{d}^{i}_{\ell}(u, c)$.

For an fixed edge $e\in \mathcal{H}^{i-1}_{s, c}$ with $u\in e$, and a set $S\in\binom{e}{\ell}$, observe that
\[
\begin{split}
& \mathbf{Pr}(c\in \hat{P}_{i}(x) \text{ for all } x\in e\setminus\{u\}\ \&\ \text{all vertices in $e-S$ are colored by $c$}) \\
\leq & \mathbf{Pr}(c\in \hat{P}_{i}(x) \text{ for all } x\in e\setminus\{u\}\ \mid c\inA_{i}(x)\text{ for all $x\in e-S$})\cdot \mathbf{Pr}(c\inA_{i}(x)\text{ for all $x\in e-S$}) \\
= & \pi_{i}^{s- \ell}\mathbf{Pr}(c\in \hat{P}_{i}(x) \text{ for all } x\in e\setminus\{u\}\ \mid c\inA_{i}(x)\text{ for all $x\in e-S$}) \\
\leq & \pi_{i}^{s- \ell}\mathbf{Pr}(c\in \hat{P}_{i}(x) \text{ for all } x\in e\setminus\{u\})
\leq (1 + \varepsilon_0)\pi_{i}^{s- \ell}\prod_{x\in e\setminus\{u\}}\mathbf{Pr}(c\in \hat{P}_{i}(x))\\
= & (1 + \varepsilon_0)\pi_{i}^{s- \ell}\beta_{i}^{s-1}.
\end{split}
\]
Therefore, we have
\[
\mathbf{E}[\tilde{d}^{i}_{\ell}(u, c)] \leq (1 + \varepsilon_0)\sum_{s=\ell+1}^{k}\binom{s}{\ell}\pi_{i}^{s- \ell}\beta_{i}^{s-1}d^{i-1}_{s}(u, c).
\]

\section{Proof of Theorem~\ref{mainthm2}}\label{sec:mainthm2}
As we mentioned at the beginning, rather than bound $c$-degrees, we will show that after each round the \textit{average $c$-degree}, defined as
\[
\Lambda_{i}(u):=\sum_{c\in P_{i}(u)}\frac{d_{i}(u, c)}{|P_{i}(u)|},\]
can be bounded with a certain probability.
Moreover, following an idea of Pettie-Su~\cite{pettie2015distributed}, we introduce the following notation in order to balance the tradeoff between the palette size and the average $c$-degree:
\[
\mathcal{D}_{i}(u):=\lambda_{i}(u)\Lambda_{i}(u) + (1 - \lambda_{i}(u))2t_{i},
\]
where $\lambda_{i}(u):=\min\left\{1, |P_{i}(u)|/p'_{i}\right\}$.
\begin{thm}\label{thm:de}
For every $0\leq i \leq T$ and every vertex $u\in U_{i}$,
\[
\mathbf{Pr}(\mathcal{D}_{i}(u)\leq t'_{i})\geq 1- \exp\left(-\Omega(\log^2\Delta)\right).
\]
\end{thm}
Before moving to the proof of Theorem~\ref{thm:de}, we first explain how our main theorem, Theorem~\ref{mainthm2}, follows from Theorem~\ref{thm:de}.
We start with the following simple proposition.
\begin{prop}\label{prop:pbou}
Let $0\leq i \leq T$.
If $\mathcal{D}_{i}(u)\leq t'_{i}$, then
\begin{equation*}
|P_{i}(u)|
\geq (1 -  (1 + \varepsilon)^{i}/2)p'_{i}
= (1 -  (1 + \varepsilon)^{i}/2)(1 - \varepsilon/8)^{i}p_{i}.
\end{equation*}
\end{prop}
\begin{proof}
By the definition of $\mathcal{D}_{i}(u)$, if $\mathcal{D}_{i}(u)\leq t'_{i}$, then we have $(1 - \lambda_{i}(u))2t_{i}\leq \mathcal{D}_{i}(u)\leq t'_{i}.$
This, together with the definition of $\lambda_{i}$, gives that
\[
\frac{|P_{i}(u)|}{p'_{i}}\geq\lambda_{i}(u)\geq 1 - \frac{t'_{i}}{2t_{i}}=1 -  \frac{(1 + \varepsilon)^{i}}{2},
\]
which completes the proof.
\end{proof}

The mechanics of the algorithm, that is, filtering out colors with larger $c$-degree, ensures that the $c$-degrees of hypergraphs is decreasing in a fairly fast speed, while Theorem~\ref{thm:de} and Proposition~\ref{prop:pbou} together imply that if for each uncolored vertex, there is still a sufficiently amount of usable colors when the algorithm terminates. After that, we can color the remaining vertices using the standard approach, the Local Lemma.

\begin{proof}[Proof of Theorem~\ref{mainthm2}]
After the iterative portion of the algorithm, we obtain a proper partial coloring of $\mathcal{H}$, and there are still some uncolored vertices $U^T$.
Moreover, by Theorem~\ref{thm:de}, Proposition~\ref{prop:pbou}, and the union bound, with probability at least $1- \exp\left(-\Omega(\log^2\Delta)\right)$, there is an assignment of colors to the vertices so
that $|P_{T}(u)|\geq p_{T}/4$ for all $u\in U_T$.

For every vertex $u\in U^T$, we color it with colors in $P_{T}(u)$ uniformly at random.
The goal is to show that with high probability there is a proper coloring on hypergraph $\cup_{c}\cup_{i=2}^{k}\mathcal{H}^T_{i, c}$. By the mechanics of the algorithm, this coloring, combined with the partial coloring from the algorithm, is a proper list coloring of $\mathcal{H}$.

For a color $c$, $2\leq \ell\leq k$, and an edge $e_{\ell}\in \mathcal{H}^T_{\ell, c}$, let $\mathcal{A}_{e_{\ell}, c}$ be the event that all the vertices in $e_{\ell}$ receive the color $c$. In other words, we want to prove that with positive probability, none of the events $\mathcal{A}_{e_{\ell}, c}$ occur.
Fix an arbitrary event $\mathcal{A}_{e_{\ell}, c}$, where $e_\ell\in \mathcal{H}^T_{\ell, c}$.
First, we observe that
\[\mathbf{Pr}\left[\mathcal{A}_{e_{\ell}, c}\right]=\prod_{u\in e_{\ell}}\frac{1}{|P_{T}(u)|}
\leq \left(\frac{1}{p_{T}/4}\right)^{\ell} \ll \frac14.\]

Next, Let $\mathcal{D}$ be the collection of events $\mathcal{A}_{e, c'}$ that are dependent on $\mathcal{A}_{e_{\ell}, c}$. Note that two events $\mathcal{A}_{e_{\ell}, c}$, $\mathcal{A}_{e, c'}$ are dependent if and only if $e_{\ell} \cap e \neq \emptyset$.
Therefore, we have
\[
\begin{split}
\sum_{\mathcal{A}\in\mathcal{D}}\mathbf{Pr}\left[\mathcal{A}\right]
&\leq \sum_{u\in e_{\ell}}\sum_{c\in P_{T}(u)}\sum_{\ell=2}^k\sum_{\substack{e\in \mathcal{H}^T_{\ell,c}\\ u\in e}}\mathbf{Pr}\left[\mathcal{A}_{e, c}\right]
=\sum_{u\in e_{\ell}}\sum_{c\in P_{T}(u)}\sum_{\ell=2}^k\sum_{\substack{e\in \mathcal{H}^T_{\ell,c}\\ u\in e}}\frac{1}{|P_{T}(u)|}\prod_{v\in e\setminus\{u\}}\frac{1}{|P_{T}(v)|}\\
&\leq \sum_{u\in e_{\ell}}\sum_{c\in P_{T}(u)}
\frac{1}{|P_{T}(u)|}\sum_{\ell=2}^kd^{T}_{\ell}(u, c)\left(\frac{4}{p_{T}}\right)^{\ell -1}
\leq \sum_{u\in e_{\ell}}\sum_{c\in P_{T}(u)}
\frac{1}{|P_{T}(u)|}\sum_{\ell=2}^kd^{T}_{\ell}(u, c)\left(\frac{1}{\cdep_{T}}\right)^{\ell -1}\\
&=\sum_{u\in e_{\ell}}\sum_{c\in P_{T}(u)}
\frac{1}{|P_{T}(u)|}\left(\frac{1}{\cdep_{T}}\right)^{k -1} d^{T}(u, c)
\leq k\frac{2t_{T}}{(\cdep_{T})^{k -1}} =2k\zeta_{T} \leq 1/4.
\end{split}
\]
The Asymmetric Local Lemma implies that there exists a coloring where none of the events
$\mathcal{A}_{e, c}$ occur, which completes the proof.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:de}}\label{sec:mainproof}
The proof of Theorem~\ref{thm:de} is established on the following two lemmas. The first lemma states that the size of temporary palette $\hat{P}_{i}(u)$ is well-concentrated.
\begin{lemma}\label{lem:exceout1}
Let $0\leq i\leq T$.
Denote by $\Omega^*_1$ the set of events where there exists an vertex $v\in N^2_{i-1}(u)$ such that $|\hat{P}_{i}(v)|\leq (1 - \varepsilon/8)\beta|P_{i-1}(v)|$. Then
\[
\mathbf{Pr}(\Omega^*_1) \leq \exp\left(-\Omega(\log^2\Delta)\right).
\]
\end{lemma}

\begin{proof}
For every vertex $v\in N^2_{i-1}(u)$, recall that $\mathbf{E}|\hat{P}_{i}(v)|=\beta|P_{i-1}(v)|$. Then by the Chernoff bounds (Lemma~\ref{chernoff}), we have
\[
\begin{array}{lll}
\mathbf{Pr}\left(|\hat{P}_{i}(v)|\leq (1 - \varepsilon/8)\beta|P_{i-1}(v)|\right)&
\leq \exp\left(-(\varepsilon/8)^2\beta|P_{i-1}(v)|/(2 + \varepsilon/8)\right) &   \\
&=\exp\left(- \Omega\left( \varepsilon^2
\betap_{i-1}\right)\right) & \text{Proposition~\ref{prop:pbou}} \\
&=\exp\left(- \Omega\left( \varepsilon^2
p_{i-1}\right)\right) &  \beta=\Theta(1).\\
\end{array}
\]
Finally, by the union bound, we have
\[
\mathbf{Pr}(\Omega^*_1) \leq |N^2_{i-1}(u)|\exp\left(- \Omega\left( \varepsilon^2
p_{i-1}\right)\right) \leq k^4\Delta^2\exp\left(- \Omega\left( \varepsilon^2
p_{i-1}\right)\right) \leq \exp\left(-\Omega(\log^2\Delta)\right),
\]
where the last inequality uses~\eqref{pbound}.
\end{proof}

The second lemma, which is also the key lemma toward the proof, shows that the sum of temporary $c$-degrees $\hat{d}_{i}(u, c)$ over all colors in $\hat{P}_{i}(u)$ is well-concentrated.
\begin{lemma}[Key Lemma]\label{lem:key}
Let $0\leq i\leq T$.
Assume that $\mathcal{D}_{i-1}(u) \leq t'_{i-1}$ for all $u\in U_{i-1}$. Then for every $u\in U_{i}$,
\[
\mathbf{Pr}\left(\sum_{c\in\hat{P}_{i}(u)}\hat{d}_{i}(u, c) \leq \alpha'_{i}\beta^{k}|P_{i-1}(u)|\left(\Lambda_{i-1}(u) + \frac{\varepsilon}{4} t_{i-1}\right)\right)\geq 1- \exp\left(-\Omega(\log^2\Delta)\right),
\]
where $\varepsilon=4\Delta^{-\theta}\log^{2k}\Delta$.
\end{lemma}
The proof of the Key Lemma, which served as the most crucial and technical component of our work, will be deferred to Section~\ref{sec:keylemma}.
We end this section by using Lemmas~\ref{lem:exceout1} and~\ref{lem:key} to establish Theorem~\ref{thm:de}.
\vspace{3mm}

\begin{proof}[Proof of Theorem~\ref{thm:de}]
First observe that for every vertex $u$, $\mathcal{D}_{0}(u)=\Lambda_{i}(u)\leq \Delta = t'_0.$ Then by the union bound, it is sufficient to show that
\[
\mathbf{Pr}(\mathcal{D}_{i}(u)\leq t'_{i} \mid \mathcal{D}_{i-1}(u) \leq t'_{i-1} \text{ for all } u\in U_{i-1})\geq 1- \exp\left(-\Omega(\log^2\Delta)\right).
\]

Assume that $\mathcal{D}_{i-1}(u) \leq t'_{i-1}$ for all $u\in U_{i-1}$.
By Lemmas~\ref{lem:exceout1} and~\ref{lem:key}, and the union bound, with probability at least $1- \exp\left(-\Omega(\log^2\Delta)\right)$, the following holds:
\begin{gather}
\sum_{c\in\hat{P}_{i}(u)}\hat{d}_{i}(u, c) \leq \alpha'_{i}\beta^{k}|P_{i-1}(u)|\left(\Lambda_{i-1}(u) + \frac{\varepsilon}{4}t_{i-1}\right)\label{eq:re2}\\
|\hat{P}_{i}(u)|\geq (1 - \varepsilon/8)\beta|P_{i-1}(u)|;\label{eq:re1},
\end{gather}
where $\varepsilon=4\Delta^{-\theta}\log^{2\ell}\Delta$.
Let $\hat{\Lambda}_{i}(u):=\sum_{c\in \hat{P}_{i}(u)}\frac{\hat{d}_{i}(u, c)}{|\hat{P}_{i}(u)|}$. Then we have
\begin{equation}
\label{eq:Lamh1}
\begin{aligned}
\hat{\Lambda}_{i}(u) &\leq\frac{|P_{i-1}(u)|}{|\hat{P}_{i}(u)|}\alpha'_{i}\beta^{k}\left(\Lambda_{i-1}(u) + \frac{\varepsilon}{4}t_{i-1}\right) & \text{by}~\eqref{eq:re2}\\

 & \leq (1 + \varepsilon/2)\alpha'_{i}\beta^{k-1}\left(\Lambda_{i-1}(u) + \frac{\varepsilon}{4}t_{i-1}\right) & \text{by}~\eqref{eq:re1}\\
 & \leq \alpha'_{i}\beta^{k-1}\Lambda_{i-1}(u) + (\varepsilon/2+\varepsilon/4+\varepsilon^2/8)\alpha'_{i}\beta^{k-1}t'_{i-1} & \Lambda_{i-1}(u)\leq \mathcal{D}_{i-1}(u) \leq t'_{i-1}\\
 & \leq \alpha'_{i}\beta^{k-1}\Lambda_{i-1}(u) + \varepsilon(1+ \varepsilon)^{i-1}t_{i}  & \alpha'_{i}\beta^{k-1}t'_{i-1}=(1+ \varepsilon)^{i-1}t_{i}.
\end{aligned}
\end{equation}
In particular, we have
\begin{equation}\label{eq:Lamh2}
\hat{\Lambda}_{i}(u) \leq \alpha'_{i}\beta^{k-1}t'_{i-1} + \varepsilon(1+ \varepsilon)^{i-1}t_{i}
=(1+ \varepsilon)^{i-1}t_{i} + \varepsilon(1+ \varepsilon)^{i-1}t_{i} = (1+ \varepsilon)^{i}t_{i} \leq 2t_{i}.
\end{equation}
Instead of bounding $\mathcal{D}_{i}(u)$ directly, we consider
\[\hat{\mathcal{D}}_{i}(u):=\hat{\lambda}_{i}(u)\hat{\Lambda}_{i}(u) + (1 - \hat{\lambda}_{i}(u))2t_{i},\]
where $\hat{\lambda}_{i}(u):=\min\left\{1, |\hat{P}_{i}(u)|/p'_{i}\right\}$.
Compared to $\mathcal{D}_{i}(u)$, $\hat{\mathcal{D}}_{i}(u)$ can be viewed as the average $c$-degree of the palette obtained by changing those colors in $\hat{P}_{i}(u)$ who has larger $c$-degrees to dummy colors with $c$-degrees
exactly $2t_{i}$. Since the average only goes down in this process, we immediately have
\[
\mathcal{D}_{i}(u)\leq \hat{\mathcal{D}}_{i}(u).
\]
Observe by~\eqref{eq:re1} that
\[
\frac{\hat{P}_{i}(u)}{p'_{i}} \geq \frac{(1 - \varepsilon/8)\beta|P_{i-1}(u)|}{(1 - \varepsilon/8)\betap'_{i-1}}=
\frac{|P_{i-1}(u)|}{p'_{i-1}}.
\]
and therefore
\begin{equation}\label{eq:lamh}
\hat{\lambda}_{i}(u)\geq \lambda_{i}(u),\ \lambda_{i-1}(u).
\end{equation}
Finally, we obtain that
\begin{align*}
\mathcal{D}_{i}(u) &\leq \hat{\mathcal{D}}_{i}(u)=\hat{\lambda}_{i}(u)\hat{\Lambda}_{i}(u) + (1 - \hat{\lambda}_{i}(u))2t_{i} & \\
& \leq \lambda_{i-1}(u)\hat{\Lambda}_{i}(u) + (1 - \lambda_{i-1}(u))2t_{i} & \text{by}~\eqref{eq:Lamh2}~\&~\eqref{eq:lamh}\\
& \leq \lambda_{i-1}(u)\left(\alpha'_{i}\beta^{k-1}\Lambda_{i-1}(u) + \varepsilon(1+ \varepsilon)^{i-1}t_{i}\right) + (1 - \lambda_{i-1}(u))2t_{i} & \text{by}~\eqref{eq:Lamh1}\\
& \leq \alpha'_{i}\beta^{k-1}\left(\lambda_{i-1}(u)\Lambda_{i-1}(u) + (1 - \lambda_{i-1}(u))2t_{i-1}\right)+\varepsilon(1+ \varepsilon)^{i-1}t_{i} & t_{i}=\alpha'_{i}\beta^{k-1}t_{i-1}\\
&=\alpha'_{i}\beta^{k-1}\mathcal{D}_{i-1}(u)+\varepsilon(1+ \varepsilon)^{i-1}t_{i}\leq \alpha'_{i}\beta^{k-1}t'_{i-1} +\varepsilon(1+ \varepsilon)^{i-1}t_{i} & \text{defn. of }\mathcal{D}_{i-1}(u)\\
&\leq (1 + \varepsilon)^{i-1}t_{i}+\varepsilon(1+ \varepsilon)^{i-1}t_{i}=t'_{i} & t'_{i}=(1 + \varepsilon)^{i}t_{i},
\end{align*}
which completes the proof.
\end{proof}

\section{Proof of Theorem~\ref{mainthm1}}\label{sec:mainthm1}
\begin{proof}[Proof of Theorem~\ref{mainthm1}]
We will use our codegree reduction algorithm (see Section~\ref{sec:coredu}) to reduce codegrees of the original hypergraph, until the conditions of Theorem~\ref{mainthm2} are reached for some $\Delta$.

Let $V:=V(\mathcal{H})$.
We start the algorithm with $\mathcal{H}^0:=\mathcal{H}$ and $\Lambda_{k} := (k2^k)^k\Delta_k$. In the $i$-th iteration round, for every vertex $u$ and $2\leq k-i < \ell \leq k$, let
\[
F_{k-i, \ell}(u):=\left\{ S\subseteq V:\ |S|=k-i,\ u\in S,\  \text{and}\  \deg_{\ell}(S, \mathcal{H}^{i-1}) \geq (\Lambda_{\ell}/\log\Lambda_{\ell})^{\frac{\ell - (k -i)}{k-1}}\right\}.
\]
Define $\mathcal{H}^i$ as the following:
\[
E(\mathcal{H}^i) := E(\mathcal{H}^{i-1}) - \bigcup_{u}\bigcup_{\ell>k-i}\bigcup_{S\in F_{k-i, \ell}(u)}\{e\in \mathcal{H}^{i-1}:\  e \supseteq S,\ |e|=\ell \} + \bigcup_{u}\bigcup_{\ell>k-i}F_{k-i, \ell}(u).
\]
We then take $\Lambda_{k-i}$ such that
\begin{equation}\label{sec:reduce:def:Lambda}
\Delta_{k-i}(\mathcal{H}^{i})=\frac{1}{(k2^k)^{k-i}}\cdot \Lambda_{k-i}^{1 - \frac{i}{k-1}} (\log \Lambda_{k-i})^{\frac{i}{ k-1}}.
\end{equation}
The algorithm terminates after $k-2$ rounds.

Observe that this reducing process satisfies the following properties:
\begin{itemize}
\item[(1)] for every $0\leq i<j \leq k-2$, any proper coloring of $\mathcal{H}^{j}$ is also proper for $\mathcal{H}^{i}$;
\item[(2)] for every $0\leq i \leq k-2$,
\begin{multline*}
\Delta_{k-i}(\mathcal{H}^0)=\ldots=\Delta_{k-i}(\mathcal{H}^{i-1}) \leq \Delta_{k-i}(\mathcal{H}^{i})=\frac{1}{(k2^k)^{k-i}}\cdot \Lambda_{k-i}^{1 - \frac{i}{k-1}} (\log \Lambda_{k-i})^{\frac{i}{ k-1}}\\
\geq \Delta_{k-i}(\mathcal{H}^{i+1})\geq \ldots \geq \Delta_{k-i}(\mathcal{H}^{k-2});
\end{multline*}
\item[(3)] for every $2\leq k-i < \ell \leq k$,
\[
\delta_{k-i, \ell}(\mathcal{H}^{k-2})  \leq \ldots \leq \delta_{k-i, \ell}(\mathcal{H}^{i+1}) \leq \delta_{k-i, \ell}(\mathcal{H}^{i})
\leq (\Lambda_{\ell}/\log\Lambda_{\ell})^{\frac{\ell - (k-i)}{k-1}}.
\]
\end{itemize}
Most importantly, note that $\mathcal{H}^{k-2}$ is indeed a $f$-reduction of $\mathcal{H}$ with the function $f(s,  \ell)=(\Lambda_{\ell}/\log\Lambda_{\ell})^{\frac{\ell - s}{k-1}}$, which satisfies the assumption of Proposition~\ref{prop:redu}. Therefore, by Proposition~\ref{prop:redu}, the hypergraph $\mathcal{H}^{k-2}$ is also triangle-free.

Define
\[
\Delta := \max_{0\leq i \leq k-2} \Lambda_{k-i}.
\]
Applying Theorem~\ref{mainthm2} on $\mathcal{H}^{k-2}$ with $\Delta$, we have
\begin{equation}\label{sec:reduce:chibd}
\chi_{\ell}(\mathcal{H})
\leq \chi_{\ell}(\mathcal{H}^{k-2})
\leq c' \left( \frac{\Delta}{\log \Delta}\right)^{\frac{1}{k-1}},
\end{equation}
for some constant $c'$.

Fix $i$ such that $\Delta = \Lambda_{k-i}$. First, by the definition, we have that for every vertex $u$ and $\ell> k- i$,
\begin{multline*}
\frac{1}{(k2^k)^{\ell}}\cdot\Lambda_{\ell}^{1 - \frac{k-\ell}{k-1}} (\log \Lambda_{\ell})^{\frac{k-\ell}{ k-1}}
=\Delta_\ell(\mathcal{H}^{k-\ell})\geq \Delta_\ell(\mathcal{H}^{i-1})\geq d_{\ell}(u, \mathcal{H}^{i-1})\\
\geq \frac{1}{\binom{\ell-1}{k-i-1}} |F_{k-i, \ell}(u)|(\Lambda_{\ell}/\log\Lambda_{\ell})^{\frac{\ell - (k -i)}{k-1}}.
\end{multline*}
This together with (\ref{sec:reduce:def:Lambda}) indicates that
\[
|F_{k-i, \ell}(u)|
\leq \frac{\binom{\ell-1}{k-i-1}}{(k2^k)^{\ell}}\Lambda_{\ell}^{1 - \frac{i}{k-1}}(\log \Lambda_{\ell})^{\frac{i}{ k-1}}
\leq \frac{1}{2k(k2^k)^{\ell-1}}\Lambda_{k-i}^{1 - \frac{i}{k-1}}(\log \Lambda_{k-i})^{\frac{i}{ k-1}}
\leq \frac{1}{2k}\Delta_{k-i}(\mathcal{H}^i).
\]
Then by the definition of $E(\mathcal{H}^i)$, we have
\[
\Delta_{k-i}(\mathcal{H}^i) \leq \Delta_{k-i} + \max_{u}\sum_{\ell>k-i}|F_{k-i, \ell}(u)| \leq
\Delta_{k-i} +  \Delta_{k-i}(\mathcal{H}^i)/2,
\]
and therefore $\Delta_{k-i}(\mathcal{H}^i) \leq 2\Delta_{k-i}$.
This, together with (\ref{sec:reduce:def:Lambda}) and (\ref{sec:reduce:chibd}), gives that
\[
\chi_{\ell}(\mathcal{H})
\leq c' \left( \frac{\Lambda_{k-i}}{\log \Lambda_{k-i}}\right)^{\frac{1}{k-1}}
\leq \frac{c}{2}\left( \frac{\Delta_{k-i}(\mathcal{H}^i)}{\log \Delta_{k-i}(\mathcal{H}^i)}\right)^{\frac{1}{k-i-1}}
\leq c\left( \frac{\Delta_{k-i}}{\log \Delta_{k-i}}\right)^{\frac{1}{k-i-1}},
\]
for some sufficiently large constant $c$, which completes the proof.
\end{proof}

\section{Proof of Theorem~\ref{sparsethm}}\label{sec:spars}
We say a rank $k$ hypergraph $\mathcal{H}$ is \textit{$(\Delta, \omega_2,\ldots, \omega_{k})$-sparse}, if $\mathcal{H}$ has
maximum $k$-degree at most $\Delta$, and for all $1 \leq s < \ell \leq k$, $\mathcal{H}$ has maximum $(s, \ell)$-codegree $\delta_{s, \ell} \leq \Delta^{\frac{\ell-s}{k-1}}\omega_{\ell}$.

To prove Theorem~\ref{sparsethm}, we use the following partition lemma from~\cite{cooper2016coloring}.

\begin{lemma}\label{lem:parti}
Fix $k\geq 2$. Let $\mathcal{H}$ be a rank $k$ hypergraph, and $\mathcal{F}$ be a finite family of fixed, connected hypergraphs. Let $f=\Delta^{O(1)}$, where $f$ is sufficiently large. Suppose that
\begin{itemize}
\item $\mathcal{H}$ is $(\Delta, \omega_2,\ldots, \omega_{k})$-sparse, where $\omega_{\ell}=\omega_{\ell}(\Delta)=f^{o(1)}$ for all $2\leq j \leq k$;
\item for all $F\in\mathcal{F}$, $\Delta_{F}(\mathcal{H})\leq \Delta^{\frac{v(F)-1}{k-1}}/f^{v(F)}$.
\end{itemize}
Then $V(\mathcal{H})$ can be partitioned into $\mathcal{O}\left(\Delta^{\frac{1}{k-1}}/f\right)$ parts such that the hypergraph induced by each part is $\mathcal{F}$-free and has maximum $\ell$-degree at most $2^{2k}f^{\ell-1}\omega_{\ell}$ for each $2 \leq \ell\leq k$.
\end{lemma}

\begin{proof}[Proof of Theorem~\ref{sparsethm}]
Without loss of generality, we assume that $1\ll f =\Delta^{\mathcal{O}(1)}$, as otherwise, the conclusion easily follows from Theorem~\ref{mainthm1} or a direction application of the Local Lemma.
Take $\Delta$ such that
\[
\left(\frac{\Delta}{\log f}\right)^{\frac{1}{k-1}}=\max_{2\leq \ell \leq k} \left\{\left(\frac{\Delta_{\ell}}{\log f}\right)^{\frac{1}{\ell-1}}\right\},
\]
and set
\[
f_1:=f/(\log f)^{(k-2)(3k - 4)/(k-1)}.
\]
By the maximality, we have that for all $2\leq \ell\leq k$,
\begin{equation}\label{debound}
\Delta_{\ell} \leq \Delta^{\frac{\ell-1}{k-1}}(\log f)^{1 - \frac{\ell-1}{k-1}},
\end{equation}
and therefore for all $T\in \mathcal{T}$,
\begin{equation}\label{tribound}
\begin{split}
\Delta_{T}(\mathcal{H})& \leq \left(\max_{2\leq\ell\leq k}\Delta_{\ell}^{1/(\ell-1)}\right)^{v(T)-1}/f
\leq \left(\max_{2\leq\ell\leq k}\Delta^{1/(k-1)}(\log f)^{\frac{k-\ell}{(k-1)(\ell-1)}}\right)^{v(T)-1}/f\\
& \leq \left(\Delta^{1/(k-1)}(\log f)^{\frac{k-2}{k-1}}\right)^{v(T)-1}/f
\leq \left(\Delta^{1/(k-1)}\right)^{v(T)-1}/f_1,
\end{split}
\end{equation}
where the last inequality follows from the fact that $v(T)\leq 3k-3$.

Let $\mathcal{H}'$ be a $g$-reduction of $\mathcal{H}$, where $g(x, y):=\Delta^{\frac{y-x}{k-1}}$. Indeed, by Proposition~\ref{prop:redu} and the mechanics of the algorithm, this codegree reduction process produces a sequence of hypergraphs $\{\mathcal{H}=\mathcal{H}^0, \ldots, \mathcal{H}^{i}, \ldots, \mathcal{H}^{k-2}=\mathcal{H}'\}$, which satisfies the following properties:
\begin{itemize}
\item[(1)] any proper coloring of $\mathcal{H}'$ is also proper for $\mathcal{H}$;
\item[(2)] for every $0\leq i \leq k-2$,
\begin{multline}\label{itm:de}
\Delta_{k-i}=\Delta_{k-i}(\mathcal{H}^0)=\ldots=\Delta_{k-i}(\mathcal{H}^{i-1}) \leq \Delta_{k-i}(\mathcal{H}^{i})\\
\geq \Delta_{k-i}(\mathcal{H}^{i+1})\geq \ldots \geq \Delta_{k-i}(\mathcal{H}^{k-2});
\end{multline}
\item[(3)] for every $2\leq k-i < \ell \leq k$,
\begin{equation}\label{itm:code}
\delta_{k-i, \ell}(\mathcal{H}')  \leq  g(k-i, \ell)\leq \Delta^{\frac{\ell - (k-i)}{k-1}}.
\end{equation}
\end{itemize}
Moreover, we have the following claim.
\begin{claim}\label{claim:De}
For every $0\leq i \leq k-2$,
\[
\Delta_{k-i}(\mathcal{H}^{i}) \leq 2\Delta^{\frac{k-i-1}{k-1}}(\log f)^{1 - \frac{k-i-1}{k-1}}.
\]
\end{claim}
\begin{proof}[Proof of Claim~\ref{claim:De}]
We prove it by induction on $i$. The base case $i=0$ is trivially true by~\eqref{debound}.
Assume that the claim holds for all $j<i$. This, together with~\eqref{itm:de}, indicates that
\begin{equation}\label{claim:assump}
\Delta_{\ell}(\mathcal{H}^{i-1})\leq \Delta_{\ell}(\mathcal{H}^{k-\ell}) \leq 2\Delta^{\frac{\ell-1}{k-1}}(\log f)^{1- \frac{\ell-1}{k-1}}.
\end{equation}
for all $\ell>k-i$.

Now let us focus on the $i$-th round of the algorithm. By the definition of $F_{k-i, \ell}(u)$, we have that for every vertex $u$ and $\ell> k- i$,
\begin{equation*}
\frac{1}{\binom{\ell-1}{k-i-1}} |F_{k-i, \ell}(u)|\Delta^{\frac{\ell - (k -i)}{k-1}}
\leq d_{\ell}(u, \mathcal{H}^{i-1}) \leq \Delta_\ell(\mathcal{H}^{i-1}).
\end{equation*}
This, together with~\eqref{claim:assump}, shows that
\[
|F_{k-i, \ell}(u)|
\leq \binom{\ell-1}{k-i-1}\Delta_\ell(\mathcal{H}^{i-1})\Delta^{-\frac{\ell - (k -i)}{k-1}}
\leq 2\binom{\ell-1}{k-i-1}\Delta^{\frac{k-i-1}{k-1}}(\log f)^{1 -\frac{\ell-1}{k-1}}.
\]
Then by the definition of $E(\mathcal{H}^i)$, we obtain
\[
\Delta_{k-i}(\mathcal{H}^i) \leq \Delta_{k-i} + \max_{u}\sum_{\ell>k-i}|F_{k-i, \ell}(u)| \leq
2\Delta^{\frac{k-i-1}{k-1}}(\log f)^{1 - \frac{k-i-1}{k-1}},
\]
where the last inequality follows from~\eqref{debound} and $\ell>k-i$.
\end{proof}

Claim~\ref{claim:De} together with~\eqref{itm:code} shows that
\begin{equation}
\text{$\mathcal{H}'$ is $(2^{k-1}\Delta, \omega_2, \ldots, \omega_k)$-sparse, where $\omega_{\ell}=(\log f)^{1 -\frac{\ell-1}{k-1}}$ for each $2\leq \ell\leq k$.}
\end{equation}
After establishing the sparseness, next we estimate the number of triangles in $\mathcal{H}'$.
\begin{claim}\label{claim:tri}
For every $0\leq i \leq k-2$ and $T\in\mathcal{T}$,
\[
\Delta_{T}(\mathcal{H}^{i}) \leq k^{3i}\left(\Delta^{1/(k-1)}\right)^{v(T)-1}/f_1.
\]
\end{claim}
\begin{proof}[Proof of Claim~\ref{claim:tri}]
We prove it by induction on $i$. The base case $i=0$ holds trivially true by~\eqref{tribound}.
Assume that the claim holds for $i-1$, i.e.,
\[
\Delta_{T}(\mathcal{H}^{i-1}) \leq k^{3(i-1)}\left(\Delta^{1/(k-1)}\right)^{v(T)-1}/f_1.
\]
for all $T\in\mathcal{T}$.
As all edges in $\mathcal{H}^{i} - \mathcal{H}^{i-1}$ are of size $k-1$, it is sufficiently to consider all triangles $T$ who contains at least one edge of size $k-1$.
To simplify the discussion, we further assume that $T$ contains exactly one edge of size $k-1$; other cases will follow by applying the same argument on each size $k-1$ edge.

Let $\mathcal{F}$ be the family of copies of $T$ which are in $\mathcal{H}^{i}$ but not in $\mathcal{H}^{i-1}$. For every $F\in \mathcal{F}$, denote by $e_F$ the edge which is not in $\mathcal{H}^{i-1}$. Then by the definition of $H^{i}$, there exists an integer $\ell_F > k-i$, such that there are at least $\Delta^{\frac{\ell_F -(k-i)}{k-1}}$ edges $e'$ of size $\ell_F$ in $\mathcal{H}^{i-1}$ with $e'\supseteq e_F$. Moreover, every such $\{e', f, g\}$ forms a copy of triangle $T_{\ell_F}$ in $\mathcal{H}^{i-1}$, where $T_{\ell_F}$ is the triangle obtained by replacing the
size $k-i$ edge $e$ in $T$ with a size $\ell_F$ edge containing $e$ and some vertex outside of $T$.

For every $\ell>k-i$, define
\[
\mathcal{F}_{\ell}=\{F\in \mathcal{F}:\ \ell_F=\ell\}.
\]
Then from the above discussion, we have
\[
|\mathcal{F}_{\ell}| \cdot \Delta^{\frac{v(T_{\ell}) - v(T)}{k-1}}=|\mathcal{F}_{\ell}| \cdot \Delta^{\frac{\ell -(k-i)}{k-1}}\leq k^{3(i-1)}\left(\Delta^{1/(k-1)}\right)^{v(T_{\ell})-1}/f_1,
\]
and therefore,
\[
|\mathcal{F}_{\ell}| \leq \Delta_{T}(\mathcal{H}^{i-1}) \leq k^{3(i-1)}\left(\Delta^{1/(k-1)}\right)^{v(T)-1}/f_1.
\]
Finally, we obtain that
\[
\Delta_{T}(\mathcal{H}^{i}) \leq \Delta_{T}(\mathcal{H}^{i-1}) + \sum_{\ell>k-i}|\mathcal{F}_{\ell}| \leq k^{3i}\left(\Delta^{1/(k-1)}\right)^{v(T)-1}/f_1,
\]
which completes the proof.
\end{proof}

Set $f':=\left(f_1/k^{3k}\right)^{1/(3k-3)}$, and note that $\log f' = \Theta(\log f)$. Claim~\ref{claim:tri} therefore implies that
\[
\Delta_{T}(\mathcal{H}') \leq \left(\Delta^{1/(k-1)}\right)^{v(T)-1}/(f')^{v(T)}.
\]
for all $T\in\mathcal{T}$.
Applying Lemma~\ref{lem:parti} on $\mathcal{H}'$ with $f'$, we obtain a partition of $V(\mathcal{H})$ into $\mathcal{O}\left(\Delta^{1/(k-1)}/f'\right)$ parts such that the hypergraph induced by each part is triangle-free and has maximum $\ell$-degree at most
at most $2^{2k}(f')^{\ell-1}\omega_{\ell}$ for every $2 \leq \ell\leq k$, where $\omega_{\ell}=(\log f)^{1 -\frac{\ell-1}{k-1}}.$
By Theorem~\ref{mainthm1}, we can properly color each part with lists of
\[
\mathcal{O}\left(
\max_{2\leq \ell \leq k} \left\{\left(  \frac{(f')^{\ell-1}\omega_{\ell}}{\log (f')^{\ell-1}\omega_{\ell}}\right)^{\frac{1}{\ell-1}} \right\}
\right) \leq
\mathcal{O}\left( f'\max_{2\leq \ell \leq k}\left\{
\left(\frac{\omega_{\ell}}{\log f}\right)^{\frac{1}{\ell-1}}
\right\}\right)
= \mathcal{O}\left(f'
\left(\log f\right)^{-\frac{1}{k-1}}
\right)
\]
colors.
Finally, we conclude that
\[
\chi(\mathcal{H})\leq \chi(\mathcal{H}') \leq \mathcal{O}\left(\Delta^{1/(k-1)}/f'\right)\cdot \mathcal{O}\left(f'
\left(\log f\right)^{-\frac{1}{k-1}}
\right)
= \mathcal{O}\left(
\max_{2\leq \ell \leq k} \left\{\left(\frac{\Delta_{\ell}}{\log f}\right)^{\frac{1}{\ell-1}}\right\}
\right),
\]
where the last equality follows from the definition of $\Delta$.
\end{proof}

\subsection{Concentration of $\mathbf{X}_{\ell, s}$}
For every $2\leq \ell <s\leq k-1$, recall from~\eqref{def:inedge} that
\[
\mathbf{X}_{\ell, s}:=\sum_{c\inP_{i-1}(u)}\sum_{\substack{e\in \mathcal{H}^{i-1}_{s, c}\\ u\in e}}\sum_{Q\in\binom{e-u}{s-\ell}}
\mathbf{I}[c\inA_{i}(x) \text{ for all }x\in Q \ \&\ c\in \hat{P}_{i}(y) \text{ for all } y\in e].
\]
Similarly as in before, we will express $\mathbf{X}_{\ell, s}$ as a linear combination of several random variables, which are $(r, d)$-observable with respect to some exceptional outcomes space.

Set the following index set:
\[
\mathcal{I}_{\ell, s}=\{(c, e, Q)\mid c\in P_{i-1}(u),\ u\in e\in \mathcal{H}^{i-1}_{s, c},\ Q\subseteq e \text{ and } |Q|=s-\ell\}.
\]
we define
\[
\mathbf{X}^1_{\ell, s}:=\sum_{(c, e, Q)\in\mathcal{I}_{\ell, s}}\mathbf{I}[c\inA_{i}(x) \text{ for all }x\in Q],
\]
and
\[
\mathbf{X}^2_{\ell, s}:=\sum_{(c, e, Q)\in\mathcal{I}_{\ell, s}}\mathbf{I}[c\inA_{i}(x) \text{ for all }x\in Q \ \&\ c\notin \hat{P}_{i}(y) \text{ for some } y\in e],
\]
and note that $\mathbf{X}_{\ell, s}=\mathbf{X}^1_{\ell, s}-\mathbf{X}^2_{\ell, s}$.
We claim that
\begin{equation}\label{inedge:con:obser}
\text{both $\mathbf{X}^1_{\ell, s}$, $\mathbf{X}^2_{\ell, s}$ are $\{r, d\}$-observable with respect to $\Omega^*_{s-\ell-1, 1}\cup \Omega^*_{s-\ell}$,}
\end{equation}
where $r=2k$ and $d=\binom{s-1}{s-\ell}|P_{i-1}(u)|(\varphi_1 p_{i-1})^{\ell-1}\log^{2(s-\ell)}\Delta$.
We will only present the proof of \eqref{inedge:con:obser} for $\mathbf{X}^2_{\ell, s}$, and a similar (and even simpler) argument will show that \eqref{inedge:con:obser} is also true for $\mathbf{X}^1_{\ell, s}$.

For ease of notation, for each $(c, e, Q)\in \mathcal{I}_{\ell, s}$, write
\[
\mathbf{I}[c\inA_{i}(x) \text{ for all }x\in Q \ \&\ c\notin \hat{P}_{i}(y) \text{ for some } y\in e]:=\mathbf{I}_{c, e,Q},
\]
and then $\mathbf{X}^2_{\ell, s}=\sum_{(c, e, Q)\in\mathcal{I}_{\ell, s}}\mathbf{I}_{c, e,Q}$.
For an arbitrary random variable $\mathbf{I}_{c, e, Q}$, let $\omega\in \Omega\setminus(\Omega^*_{s-\ell-1, 1}\cup \Omega^*_{s-\ell})$ be a random sampling such that $\mathbf{I}_{c, e, Q}(\omega)=1$. By the definition of $\mathbf{I}_{c, e, Q}$, we have $\gamma^{i}_{x, c}=1$ for all $x\in Q$, and there exists a vertex $y\in e$ such that $c\notin\hat{P}_{i}(y)$.
Note that $c\notin \hat{P}_{i}(y)$, either because of $\eta^{i}_{y, c}=0$, or because that there exists an edge $e^*\in \mathcal{H}^{i-1}_{2, c}\cup\ldots\cup\mathcal{H}^{i-1}_{k, c}$ s.t. $y\in e^*$ and $ \gamma^{i}_{z, c}=1$ for all $z\in e^*\setminus \{y\}$.
Therefore, we set
\[
R_{c, e, Q}(\omega):=
\begin{cases}
\{\gamma^{i}_{x, c},\ x\in Q\}\cup\{\eta^{i}_{y, c}\},  & \text{if } \eta^{i}_{y, c}=0; \\
\{\gamma^{i}_{x, c},\ x\in Q\}\cup\{\gamma^{i}_{z, c},\ z\in e^*\setminus \{y\}\},  & \text{otherwise}.
\end{cases}
\]
It is not hard to see that $\mathbf{I}_{c, e, Q}$ is $2k$-verifiable with verifier $R_{c, e, Q}$.

Moreover, note that a necessary condition for a triple $(c, e, Q)$ with $\mathbf{I}_{c, e, Q}=1$ to include $\eta^{i}_{y,c}$ in its verifier, is that there are at least $s-\ell$ vertices in $e-u$ who have color $c$ being activated.
Therefore, for every $\omega\in \Omega \setminus(\Omega^*_{s-\ell-1, 1}\cup \Omega^*_{s-\ell})$ and random varible $\eta^{i}_{y,c}$,
we have
\[
\begin{split}
&|\{
(c, e, Q)\in \mathcal{I}_{\ell, s}\mid \mathbf{I}_{c,e,Q}(\omega)=1,\ \eta^{i}_{y,c}\in R_{c, e, Q}(\omega)
\}|\\
\leq\ &\{e\in \mathcal{H}^{i-1}_{s, c} \mid u\in e,\ \sum_{v\in e-u}\gamma^{i}_{v,c}\geq s-\ell\}|\cdot\binom{s-1}{s-\ell}\\
\leq\ &\binom{s-1}{s-\ell}(\varphi_1 p_{i-1})^{\ell-1}\log^{2(s-\ell)}\Delta,
\end{split}
\]
where the last inequality follows from the choice of $\omega$ and the definition of $\Omega^*_{s-\ell}$.
For the same reason, for every $\omega\in \Omega \setminus(\Omega^*_{s-\ell-1, 1}\cup \Omega^*_{s-\ell})$ and random variable $\gamma^{i}_{x, c}$, we also obtain that
\[
|\{
(c, e, Q)\in \mathcal{I}_{\ell, s}\mid \mathbf{I}_{c,e,Q}(\omega)=1,\ \gamma^{i}_{x,c}\in R_{c, e, Q}(\omega)
\}|
\leq \binom{s-1}{s-\ell}(\varphi_1 p_{i-1})^{\ell-1}\log^{2(s-\ell)}\Delta,
\]
This proves~\eqref{inedge:con:obser} for $\mathbf{X}^2_{\ell, s}$.

Now observe that
\[
\begin{split}
\mathbf{E}[\mathbf{X}^2_{\ell, s}] \leq \mathbf{E}[\mathbf{X}^1_{\ell, s}]
&= |\mathcal{I}_{\ell, s}|\pi_{i}^{s-\ell}
\leq \sum_{c\in P_{i-1}(u)}d^{i-1}_{s}(u, c)\binom{s-1}{s-\ell}\pi_{i}^{s-\ell} \\
&\leq \binom{s-1}{s-\ell} |P_{i-1}(u)|\frac{2t_{i-1}}{(\cdep_{i-1})^{k-s}}\pi_{i}^{s-\ell}\\
&=\binom{s-1}{s-\ell} |P_{i-1}(u)|\frac{2t_{i-1}}{(\cdep_{i-1})^{k-\ell}}(\cdep_{i-1}\pi_{i})^{s-\ell}\\
&\leq \binom{s-1}{s-\ell} |P_{i-1}(u)|\frac{2t_{i-1}}{(\cdep_{i-1})^{k-\ell}},
\end{split}
\]
where the first inequality follows from~\eqref{indas3}, and the last inequality follows from~\eqref{indas4}.
Recall from~\eqref{def:tau1} that
\[
\tau_{\ell}= \alpha'_{i}\beta^{k}|P_{i-1}(u)|\left(\frac{t_{i-1}}{(\cdep_{i-1})^{k-\ell}}\right)\Delta^{-\theta},
\]
which is much smaller than $\mathbf{E}[\mathbf{X}^2_{\ell, s}]$.
Applying Theorem~\ref{talagrand} on $\mathbf{X}^1_{\ell, s}$, $\mathbf{X}^2_{\ell, s}$ with $\tau_{\ell}$ and $\Omega^*_{s-\ell-1, 1}\cup\Omega^*_{s-\ell}$, we obtain that
\[
\begin{split}
&\mathbf{Pr}(|\mathbf{X}^1_{\ell, s} - \mathbf{E}[\mathbf{X}^1_{\ell, s}]|>\tau_{\ell}),\ \mathbf{Pr}(|\mathbf{X}^2_{\ell, s} - \mathbf{E}[\mathbf{X}^2_{\ell, s}]|>\tau_{\ell})\\
\leq\ &4\exp\left(-\frac{\tau_{\ell}^2}{8\cdot 2k\cdot \binom{s-1}{s-\ell}(\varphi_1 p_{i-1})^{\ell-1}\log^{2(s-\ell)}\Delta(4\mathbf{E}[\mathbf{X}^1_{\ell, s}] + \tau_{\ell})}\right) + 4\mathbf{Pr}(\Omega^*_{s-\ell-1, 1}) + 4\mathbf{Pr}(\Omega^*_{s-\ell}) \\
\leq\ & \exp\left(-\Theta\left(\frac{|P_{i-1}(u)|t_{i-1}\Delta^{-2\theta}}{(\cdep_{i-1})^{k-1}\log^{2(s-\ell)}\Delta}\right)\right)
+ \exp\left(-\Omega(\log^2\Delta)\right)\\
\leq\ & \exp\left(-\Theta\left(\frac{t_{i-1}\Delta^{-2\theta}}{(\cdep_{i-1})^{k-2}\log^{2(s-\ell)}\Delta}\right)\right)
+ \exp\left(-\Omega(\log^2\Delta)\right)\\
\leq &\exp\left(-\Omega\left(\frac{\Delta^{1/2(k-1)-1/2k}}{\log^{2(s-\ell)}\Delta}\right)\right)
+ \exp\left(-\Omega(\log^2\Delta)\right)=\exp\left(-\Omega(\log^2\Delta)\right),
\end{split}
\]
where the last inequality follows from~\eqref{indas5} and $\theta=1/4k$.
Finally, by linearity, we have
\begin{equation}\label{con:code}

 \mathbf{Pr}\left(|\mathbf{X}_{\ell, s} - \mathbf{E}[\mathbf{X}_{\ell, s}]|\leq 2\tau_{\ell}\right) \geq 1- \exp\left(-\Omega(\log^2\Delta)\right).
\end{equation}
\vspace{3mm}

We end this section by using the above results to establish Lemma~\ref{lem:concen}.
\begin{proof}[Proof of Lemma~\ref{lem:concen}]
The proof follows immediately from~\eqref{def:sumde}, \eqref{def:tau1}, \eqref{con:de}, and \eqref{con:code}.

\end{proof}

\subsection{Concentration of $\mathbf{X}_{\ell}$}
For each $2\leq \ell \leq k$, recall from~\eqref{def:keedge} that
\[
\mathbf{X}_{\ell}=\sum_{c\inP_{i-1}(u)}\sum_{\substack{e\in\mathcal{H}^{i-1}_{\ell, c}\\ u\in e}} \mathbf{I}[x\in U_{i} \text{ for all $x\in e\setminus\{u\}$} \ \&\  c\in\hat{P}_{i}(y) \text{ for all } y\in e].
\]
Although we can not show that $\mathbf{X}_{\ell}$ is $(r, d)$-certifiable with respect to any appropriate set of exceptional outcomes, we can express $\mathbf{X}_{\ell}$ as linear combination of several random variables that are, and then apply Theorem~\ref{talagrand} to each of these new random variables.

Recall from previous that
$
M_{u, \ell}=\{(e, c):\ c\in P_{i-1}(u),\ u\in e\in \mathcal{H}^{i-1}_{\ell, c}\}.
$
Define
\[
\mathbf{X}^{1}_{\ell}:=\text{number of tuples } (e, c)\in M_{u, \ell} \text{ s.t. } x\in U_{i} \text{ for all $x\in e\setminus\{u\}$},
\]
and
\[
\mathbf{X}^{2}_{\ell}:=\text{number of tuples } (e, c)\in M_{u, \ell} \text{ s.t. } x\in U_{i} \text{ for all $x\in e\setminus\{u\}$} \ \&\  c\notin\hat{P}_{i}(y) \text{ for some } y\in e.
\]
Clearly, $\mathbf{X}_{\ell}=\mathbf{X}_{\ell}^1 - \mathbf{X}_{\ell}^2$.
\newline

Let us first consider $\mathbf{X}_{\ell}^1$, a slightly less complicated case. For integers $i_1, i_2, \ldots, i_{\ell-1}$, let
\[
\begin{split}
\mathbf{a}_{i_1,\ldots,i_{\ell-1}}:=\ & \text{number of tuples } (e, c)\in M_{u, \ell} \text{ with } e=uv_1\ldots v_{\ell-1}\text{ s.t. for each $v_r$,} \\
&\text{$|A_{i}(v_r)|=i_r$ and $|A_{i}(v_r)\cap(P_{i-1}(v_r) - \hat{P}_{i}(v_r))|=i_r$}.
\end{split}
\]
Recall from the main algorithm that a vertex $v\in U_i$ if and only if $\hat{P}_{i}(v) \cap A_{i}(v)=\emptyset$. Then we have
\[
\mathbf{X}_{\ell}^1 = \sum_{\substack{0\leq i_r\leq \mathrm{C}\\  \forall r\in[\ell-1]}}\mathbf{a}_{i_1 ,\ldots,i_{\ell-1}}.
\]
However, $\mathbf{X}_{\ell}^1$ consists of too many items, whose error might blow up after taking the sum.
Fortunately, by Lemma~\ref{lem:exceout3}, excluding a small set $\Omega^*_1$ of exceptional outcomes, every vertex in $N^2_{i-1}(u)$ indeed has no more than $\log^2\Delta$ activated colors.
Therefore, we can let
\begin{equation}\label{eq:Ydef}
\mathbf{Y}_{\ell}^1 := \sum_{\substack{0\leq i_r\leq \log^2\Delta \\  \forall r\in[\ell-1]}}\mathbf{a}_{i_1 ,\ldots,i_{\ell-1}},
\end{equation}
and Lemma~\ref{lem:exceout3} indicates that
\begin{equation}\label{eq:appronum}
\mathbf{Pr}(\mathbf{X}_{\ell}^1 = \mathbf{Y}_{\ell}^1) \geq 1- \mathbf{Pr}(\Omega^*_1)\geq 1 -  k^4\Delta^2\exp\left(-\Omega\left(\varepsilon^2p_{i-1}\right)\right).
\end{equation}
Hence, it suffices to only concentrate on $\mathbf{Y}_{\ell}^1$.

On the other hand, since $\mathbf{a}_{i_1 ,\ldots,i_{\ell-1}}$ requires the corresponding sets are of some exact sizes,
such variables are still not easy to handle. To overcome this obstacle, we further introduce the following new variables:
\[
\begin{split}
\mathbf{b}_{i_1, j_1, \ldots,i_{\ell-1},j_{\ell-1}}:=\ & \text{number of tuples $(e, c)\in M_{u, \ell}$ } \text{ with } e=uv_1\ldots v_{\ell-1} \text{ s.t. for each $v_r$,} \\
&\text{$|A_{i}(v_r)|\geq i_r$ and $|A_{i}(v_r)\cap(P_{i-1}(v_r) - \hat{P}_{i}(v_r))|\geq j_r$}.
\end{split}
\]
\begin{prop}\label{prop:lincomb} For any integers $i_1, \ldots,i_{\ell-1} \geq 0$,
\[
\mathbf{a}_{i_1, \ldots,i_{\ell-1}}=\sum_{\substack{\sigma_r, \tau_r\in\{0,1\}\\  \forall r\in[\ell-1]}} (-1)^{f(\sigma_1, \tau_1, \ldots, \sigma_{\ell-1}, \tau_{\ell-1})}\mathbf{b}_{i_1+\sigma_1, i_1 +\tau_1, \ldots, i_{\ell-1} + \sigma_{\ell-1}, i_{\ell-1} + \tau_{\ell-1}},
\]
where
\[
f(\sigma_1, \tau_1, \ldots, \sigma_{\ell-1}, \tau_{\ell-1}):= \text{number of labels $r$ s.t. $\sigma_r\neq \tau_r$}.
\]
\end{prop}
Putting~\eqref{eq:Ydef} and Proposition~\ref{prop:lincomb} together, we obtain that
\begin{equation}\label{eq:Ydefnew}
\mathbf{Y}_{\ell}^1=\sum_{\substack{0\leq i_r\leq \log^2\Delta\\  \forall r\in[\ell-1]}}\sum_{\substack{\sigma_r, \tau_r\in\{0,1\}\\  \forall r\in[\ell-1]}} (-1)^{f(\sigma_1, \tau_1, \ldots, \sigma_{\ell-1}, \tau_{\ell-1})}\mathbf{b}_{i_1+\sigma_1, i_1 +\tau_1, \ldots, i_{\ell-1} + \sigma_{\ell-1}, i_{\ell-1} + \tau_{\ell-1}}.
\end{equation}
The proof of Proposition~\ref{prop:lincomb} is elementary: for $\ell=2$, observe from the definition that $a_{i_1}=(b_{i_1, i_1} - b_{i_1, i_1+1}) - (b_{i_1+1, i_1} - b_{i_1+1, i_1+1})$; the cases for larger $\ell$ follow from applying the same argument on each coordinate, and we omit the details.

We will apply Theorem~\ref{talagrand} to all $\mathbf{b}_{i_1, j_1,\ldots,i_{\ell-1}, j_{\ell-1}}$'s with
\begin{equation}\label{eq:rrange}
0\leq i_r, j_r\leq \log^2\Delta + 1 \quad \text{for all } r\in[\ell-1].
\end{equation}
We first rewrite it as a sum of indicator variables:
\[
\mathbf{b}_{i_1, j_1,\ldots,i_{\ell-1}, j_{\ell-1}} = \sum_{(e, c)\in M_{u, \ell}} \mathbf{I}_{e,c},
\]
where $\mathbf{I}_{e,c}$ is the indicate variable for the event that in $e=uv_1\ldots v_{\ell}$ (the vertices in $e$ are ordered by some predefined ordering), the following holds:
\begin{itemize}
\item $|A_{i}(v_r)|\geq i_r$ for all $r\in[\ell-1]$;
\item $|A_{i}(v_r)\cap(P_{i-1}(v_r) - \hat{P}_{i}(v_r))|\geq j_r$ for all $r\in[\ell-1]$.
\end{itemize}
We claim that
\begin{equation}\label{claim:rdver1}
\text{$\mathbf{b}_{i_1, j_1,\ldots,i_{\ell-1}, j_{\ell-1}}$ is $\left(\ell k\log^2\Delta,\ 2|P_{i-1}(u)|(\cdep_{i-1})^{\ell-2}\log^2\Delta\right)$-observable with respect to $\Omega^*_3$.}
\end{equation}

To this end, let $\omega\in\Omega\setminus \Omega^*_3$ be a random sampling  s.t. $\mathbf{I}_{e,c}(\omega)=1$. By the definition of $\mathbf{I}_{e,c}$, we have $|A_{i}(v_r)|\geq i_r$ and $|A_{i}(v_r)\cap(P_{i-1}(v_r) - \hat{P}_{i}(v_r))|\geq j_r$ for all $r$.
For every $v_r$, let $C^1_{v_r}$ be a subset of colors $A_{i}(v_r)$ of size exactly $i_r$, and $C^2_{v_r}$ be a subset of colors $A_{i}(v_r)\cap(P_{i-1}(v_r) - \hat{P}_{i}(v_r))$ of size exactly $j_r$.
Recall that a color $c^*$ is removed from $\hat{P}_{i}(v_r))$, either because of $\eta^{i}_{v_r, c^*}=0$ or because there exists an edge $e_{r, c^*}\in\cup_{\ell\geq 2}\mathcal{H}^{i-1}_{\ell, c^*}$ s.t.
$v_r\in e_{r, c^*}$ and $\gamma^{i}_{v, c^*}=1$ for all $v\in e_{r, c^*}\setminus\{v_r\}$.
Then $C^2_{v_r}$ can be partitioned into two sets $\hat{C}^2_{v_r}$ and $\tilde{C}^2_{v_r}$, where
\[
\hat{C}^2_{v_r}:=\{c^*\in C^2_{v_r} \mid \eta^{i}_{v_r, c^*}=0\},
\]
and
\[
\tilde{C}^2_{v_r}:=\{c^*\in C^2_{v_r} \mid  \exists e_{r, c^*} \text{ s.t. $\gamma^{i}_{v, c^*}=1$ for all $v\in e_{r, c^*}\setminus\{v_r\}$}\}.
\]
Now we define the verifier of $\mathbf{I}_{e, c}$ to be
\[
\begin{split}
R_{e, c}(\omega)
&:=\left( \bigcup_{r=1}^{\ell-1}\bigcup_{c^*\in C^1_{v_r}}\gamma^{i}_{v_r, c^*}\right)
\cup \left(\bigcup_{r=1}^{\ell-1}\bigcup_{c^*\in \tilde{C}^2_{v_r}}\bigcup_{v\in e_{r, c^*}\setminus\{v_r\}}\gamma^{i}_{v, c^*}\right) \cup \left(\bigcup_{r=1}^{\ell-1}\bigcup_{c^*\in \hat{C}^2_{v_r}}\eta^{i}_{v_r, c^*}\right)\\
&:=R^1_{e, c}(\omega)\cup R^2_{e, c}(\omega)\cup R^3_{e, c}(\omega).
\end{split}
\]
Observe that
\[
\begin{split}
|R_{e, c}(\omega)|&\leq \sum_{r=1}^{\ell-1}(i_r + j_r(k-1) + j_r)=\sum_{r=1}^{\ell-1}i_r + k\sum_{r=1}^{\ell-1}j_r\\
&\leq \ell k\log^2\Delta,
\end{split}
\]
where the last inequality follows from the range of $i_r, j_r$, i.e.,~\eqref{eq:rrange}.
It is not hard to see that $\mathbf{Y}_{\ell}^1$ is $\ell k\log^2\Delta$-verifiable with such verifier $R$ with respect to $\Omega^*_3$.

Next, we will examine how many verifiers $R_{e, c}(\omega)$ will be influenced by a single random variable $\eta^{i}_{v, c^*}$ or $\gamma^{i}_{v, c^*}$.
Firstly, for every sampling $\omega\in\Omega\setminus\Omega^*_3$ and random variable $\eta^{i}_{v, c^*}$, we easily have
\begin{equation}\label{eq:ober1}
|\{(e, c):\ \mathbf{I}_{e, c}(w)=1\ \&\ \eta^{i}_{v, c^*}\in R_{e, c}(w)\}| \leq \sum_{c\in P_{i-1}(u)}\delta_{2,\ell}(\mathcal{H}^{i-1}_{\ell, c}) \leq |P_{i-1}(u)|(\cdep_{i-1})^{\ell-2},
\end{equation}
as for all such tuples $(e, c)$, $e$ much contain both $u, v$ vertices.
On the other hand, observe that for a random variable $\gamma_{v, c^*}$, if $\gamma^{i}_{v, c^*}\in R^2_{e, c}(w)$ for some $(e, c)$,
\begin{equation}\label{state:verif1}
\text{then there must be a vertex $v'\in e\setminus\{u\}$ s.t. $c^*\in A_{i}(v')$.}
\end{equation}
Therefore, for every sampling $\omega\in\Omega\setminus\Omega^*_3$ and random variable $\gamma_{v, c^*}$, we obtain that
\begin{equation}
\begin{array}{ll}
& |\{(e, c):\ \mathbf{I}_{e, c}(w)=1\ \&\ \gamma^{i}_{v, c^*}\in R_{e, c}(w)\}| \\
\leq &  |\{(e, c):\ \mathbf{I}_{e, c}(w)=1\ \&\ \gamma^{i}_{v, c^*}\in R^1_{e, c}(w)\}|
+
|\{(e, c):\ \mathbf{I}_{e, c}(w)=1\ \&\ \gamma^{i}_{v, c^*}\in R^2_{e, c}(w)\}|\\
\leq & \sum_{c\in P_{i-1}(u)}\delta_{2,\ell}(\mathcal{H}^{i-1}_{\ell, c}) + |\{(e, c):\ \mathbf{I}_{e, c}(w)=1\ \&\ \gamma^{i}_{v, c^*}\in R^2_{e, c}(w)\}|\\
\leq & |P_{i-1}(u)|(\cdep_{i-1})^{\ell-2} +  |P_{i-1}(u)|(\cdep_{i-1})^{\ell-2}\log^2\Delta \leq 2|P_{i-1}(u)|(\cdep_{i-1})^{\ell-2}\log^2\Delta,
\end{array}
\end{equation}
where the second inequality follows similarly as in~\eqref{eq:ober1}, and the second last inequality follows from~\eqref{state:verif1} and the definition of $\Omega^*_3$.
This verifies~\eqref{claim:rdver1}.

Now we set
\begin{equation}\label{def:tau1}
\tau_{\ell}: =\alpha'_{i}\beta^{k}|P_{i-1}(u)|\left(\frac{t_{i-1}}{(\cdep_{i-1})^{k-\ell}}\right)\Delta^{-\theta},
\end{equation}
Note that
\[
\mathbf{E}[\mathbf{b}_{i_1, j_1,\ldots,i_{\ell-1}, j_{\ell-1}}] \leq \sum_{c\in P_{i-1}(u)} d^{i-1}_{\ell}(u, c)
\leq |P_{i-1}(u)|\cdot\frac{2t_{i-1}}{(\cdep_{i-1})^{k -\ell}},
\]
which is much larger than $\tau_{\ell}$.
Applying Theorem~\ref{talagrand} to $\mathbf{b}_{i_1, j_1,\ldots,i_{\ell-1}, j_{\ell-1}}$, we obtain that
\[
\begin{array}{rl}
& \mathbf{Pr}(|\mathbf{b}_{i_1, j_1,\ldots,i_{\ell-1}, j_{\ell-1}}  - \mathbf{E}[\mathbf{b}_{i_1, j_1,\ldots,i_{\ell-1}, j_{\ell-1}}]|> \tau_{\ell})  \\
\leq &  4\exp\left(-\frac{\tau_{\ell}^2}{8\ell k\log^2\Delta\cdot 2|P_{i-1}(u)|(\cdep_{i-1})^{\ell-2}\log^2\Delta \cdot (4\mathbf{E}[\mathbf{b}_{i_1, j_1,\ldots,i_{\ell-1}, j_{\ell-1}} ] + \tau_{\ell})}\right) + 4\mathbf{Pr}(\Omega^*_3) \\
\leq & 4\exp\left(-\Omega\left(
\frac{t_{i-1}\Delta^{-2\theta}}{(\cdep_{i-1})^{k-2}\log^4\Delta}
\right)\right) + 4\exp\left(-\Omega\left(\log^2\Delta\right)\right) \\
\leq & 4\exp\left(-\Omega\left(
\frac{\Delta^{1/2(k-1) - 1/2k}}{\log^4\Delta}
\right)\right) + 4\exp\left(-\Omega\left(\log^2\Delta\right)\right)
= \exp\left(-\Omega\left(\log^2\Delta\right)\right).
\end{array}
\]
where the last inequality follows from~\eqref{indas5} and $\theta=1/4k$.
Then by linearity and~\eqref{eq:Ydefnew}, we have
\[
\mathbf{Pr}\left(|\mathbf{Y}_{\ell}^1 - \mathbf{E}[\mathbf{Y}_{\ell}^1]| > (2\log\Delta)^{2(\ell-1)}\tau_{\ell}\right) \\
\leq (2\log\Delta)^{2(\ell-1)}\exp\left(-\Omega\left(\log^2\Delta\right)\right) = \exp\left(-\Omega\left(\log^2\Delta\right)\right).
\]
which, together with~\eqref{eq:appronum}, implies that
\[
\begin{split}
\mathbf{Pr}\left(|\mathbf{X}_{\ell}^1 - \mathbf{E}[\mathbf{X}_{\ell}^1] | \leq (2\log\Delta)^{2(\ell-1)}\tau_{\ell}\right)
&\geq 1 - \exp\left(-\Omega\left(\log^2\Delta\right)\right) - k^4\Delta^2\exp\left(-\Omega\left(\varepsilon^2p_{i-1}\right)\right)\\
&=1 - \exp\left(-\Omega\left(\log^2\Delta\right)\right).
\end{split}
\]

The argument for the concentration of $\mathbf{X}_{\ell}^2$ is very similar to that of $\mathbf{X}_{\ell}^1$, except that this time we will apply Theorem~\ref{talagrand} on
\[
\mathbf{b}'_{i_1, j_1, \ldots,i_{\ell-1},j_{\ell-1}}:=
\sum_{(e, c)\in M_{u, \ell}} \mathbf{I}'_{e,c},
\]
where
$\mathbf{I}'_{e,c}$ are defined to be the indicate variable for the event that in $e=uv_1\ldots v_{\ell}$, the following holds:
\begin{itemize}
\item $|A_{i}(v_r)|\geq i_r$ for all $r\in[\ell-1]$;
\item $|A_{i}(v_r)\cap(P_{i-1}(v_r) - \hat{P}_{i}(v_r))|\geq j_r$ for all $r\in[\ell-1]$;
\item $c\notin\hat{P}_{i}(v_r)$ for some $r\in[\ell-1]$.
\end{itemize}

Similarly as in before, consider a random sampling $\omega\in\Omega\setminus \Omega^*_3$ s.t. $\mathbf{I}'_{e,c}(\omega)=1$.
Then by the definition of $\mathbf{I}'_{e,c}$, there exists an vertex $x\in e$ such that $c\notin \hat{P}_{i}(x)$. Note that $c\notin \hat{P}_{i}(x)$, either because of $\eta^{i}_{x, c}=0$, or because that there exists an edge $e_{x, c}\in \bigcup_{\ell\geq 2}\mathcal{H}^{i-1}_{\ell, c}$ s.t. $v\in e_{x, c}$ and $ \gamma^{i}_{v, c}=1$ for all $v\in e_{x, c}\setminus \{x\}$.
We then define the verifier of $\mathbf{I}'_{e,c}$ to be
\[
R'_{e,c}(\omega):=
\left\{\begin{array}{lr}
        R_{e,c}(\omega) \cup \{\eta^{i}_{x, c}\} & \text{if } \eta^{i}_{x, c}=0;\\
        R_{e,c}(\omega) \cup \left(\bigcup_{v\in e_{x, c}\setminus \{x\}}\gamma^{i}_{x, c}\right) & \text{if } \eta^{i}_{x, c}\neq 0.
        \end{array}\right.
\]
Now for each random variable $\eta^{i}_{v, c}$, there will be at most
\[
\begin{split}
\max\left\{\delta_{2,\ell}(\mathcal{H}^{i-1}_{\ell, c}), d^{i-1}_{\ell}(u, c)\right\}
 &\leq 2t_{i-1}/(\varphi_1 p_{i-1})^{k-\ell} \leq \mathcal{O}((\cdep_{i-1})^{\ell-1}\log\Delta) \\
 &\ll |P_{i-1}(u)|(\cdep_{i-1})^{\ell-2}\log^2\Delta
 \end{split}
\]
 additional tuples which might have $\eta^{i}_{v, c}$ in its verifier, while for each random variable $\gamma^{i}_{v, c}$, there will be at most
\[
d^{i-1}(u, c) \ll |P_{i-1}(u)|(\cdep_{i-1})^{\ell-2}\log^2\Delta
\] additional tuples which might have $\gamma^{i}_{v, c}$ in its verifier.
This indicates that $\mathbf{b}'_{i_1, j_1,\ldots,i_{\ell-1}, j_{\ell-1}}$ is $\left(\ell k\log^2\Delta,\ 3|P_{i-1}(u)|(\cdep_{i-1})^{\ell-2}\log^2\Delta\right)$-observable with respect to $\Omega^*_3$.
Following the same argument as in before, we can show that
\[
\mathbf{Pr}\left(|\mathbf{X}_{\ell}^2 - \mathbf{E}[\mathbf{X}_{\ell}^2] |\leq (2\log\Delta)^{2(\ell-1)}\tau_{\ell}\right)
\geq 1 - \exp\left(-\Omega\left(\log^2\Delta\right)\right).
\]
Finally, recall that $\mathbf{X}_{\ell}=\mathbf{X}_{\ell}^1- \mathbf{X}_{\ell}^2$, and then we immediately obtain
 \begin{equation}\label{con:de}
 \mathbf{Pr}\left(|\mathbf{X}_{\ell} - \mathbf{E}[\mathbf{X}_{\ell}] |\leq 2(2\log\Delta)^{2(\ell-1)}\tau_{\ell}\right) \geq 1 - \exp\left(-\Omega\left(\log^2\Delta\right)\right).
 \end{equation}

\section{Concentration of average $c$-degrees}\label{sec:concede}
Throughout Sections~\ref{sec:concede} and~\ref{sec:keylemma}, we fix an integer $0\leq i\leq T$, restrict our analysis to the $i$-th iteration round of the algorithm, and assume that
\begin{equation}\label{indas1}
\mathcal{D}_{i-1}(u) \leq t'_{i-1} \quad \text{for all } u\in U_{i-1},
\end{equation}
Recall from~\eqref{ite:asump1},~\eqref{ite:asumpcode}, and~\eqref{ite:asump2} that the following induction assumption holds:
\begin{equation}\label{indas2}
d_{i-1}(u, c)=\sum_{\ell=2}^kd^{i-1}_{\ell}(u, c)(\cdep_{i-1})^{k-\ell}\leq 2t_{i-1}, \quad \text{for all } u\in U_{i-1} \text{ and } c\inP_{i-1}(u),
\end{equation}
and
\begin{equation}\label{indas3}
\delta_{s, \ell}(\mathcal{H}^{i-1}_{\ell, c})\leq (\cdep_{i-1})^{\ell-s} \quad \text{for all } c.
\end{equation}
We also restate some useful quantitative inequalities from the end of Section~\ref{sec:algo}:
\begin{equation}\label{indas6}
 1/8k \leq \zeta_{i} \leq (k-1)\log\Delta \quad \text{for all }i<T.
\end{equation}

\begin{equation}\label{indas4}
\pi_{i}p_{i-1} \ll \varphi_1\pi_{i}p_{i-1}\ll 1,
\end{equation}
and
\begin{equation}\label{indas7}
p_{i}\geq \Delta^{\frac{1}{2(k-1)}} \quad \text{for all $0\leq i\leq T$}.
\end{equation}
Note that \eqref{indas6} and \eqref{indas7} further imply
\begin{equation}\label{indas5}
\frac{t_{i-1}}{(\cdep_{i-1})^{k-2}} = \cdep_{i-1}\zeta_{i-1}= \Omega\left(\Delta^{1/2(k-1)}\right),
\end{equation}
which will be useful in the calculation.
\newline

The main goal of this section is to prove the following concentration result on the average $c$-degrees.
\begin{lemma}\label{lem:concen}
For every $0\leq i\leq T$ and $u\in U^{i}$,
\[
\mathbf{Pr}\left(\sum_{c\in\hat{P}_{i}(u)}\hat{d}_{i}(u, c) - \mathbf{E}\left[\sum_{c\in\hat{P}_{i}(u)}\hat{d}_{i}(u, c)\right]\leq (\varepsilon/4)\alpha'_{i}\beta^{k}|P_{i-1}(u)|t_{i-1}\right)
\geq 1- \exp\left(-\Omega(\log^2\Delta)\right),
\]
where $\varepsilon=4\Delta^{-\theta}\log^{2k}\Delta$.
\end{lemma}

Recall from the algorithm that for each $\ell$ and $c$, the edges of $\hat{\mathcal{H}}^{i}_{\ell, c}$ come from two sources: the edges who were in $\mathcal{H}^{i-1}_{\ell, c}$, and the $\ell$-sets who were contained in some edge of larger uniformity, i.e., some $e\in \bigcap_{s>\ell}\mathcal{H}^{i-1}_{s, c}$. For the first type, we keep an edge in $\hat{\mathcal{H}}^{i}_{\ell, c}$, if and only if it remains uncolored, and still has $c$ in all their palettes. For the second type, we add an $\ell$-set $L$ to $\hat{\mathcal{H}}^{i}_{\ell, c}$, if and only if there exists some edge $e$ containing it, such that all but vertices in $L$ are colored by $c$, and all vertices in $L$ still have $c$ in their palettes.
Therefore, for each $u\in U^{i}$, we obtain that
\[
\begin{split}
\hat{d}^{i}_{\ell}(u, c)
&\leq
\sum_{\substack{e\in\mathcal{H}^{i-1}_{\ell, c}\\ u\in e}} \mathbf{I}[x\in U_{i} \text{ for all $x\in e\setminus\{u\}$} \ \&\  c\in\hat{P}_{i}(y) \text{ for all } y\in e]\\
&\quad +\sum_{s=\ell+1}^{k}\sum_{\substack{e\in \mathcal{H}^{i-1}_{s, c}\\ u\in e}}\sum_{Q\in\binom{e-u}{s-\ell}}
\mathbf{I}[\text{all $x\in Q$ are colored by $c$}\ \&\ c\in \hat{P}_{i}(y) \text{ for all } y\in e-Q].
\end{split}
\]
Recall that a vertex $x$ is colored by $c$, only if $c$ is in both $\hat{P}_{i}(x)$ and $A_{i}(x)$.
Then we further have
\[
\begin{split}
\hat{d}^{i}_{\ell}(u, c)
&\leq \sum_{\substack{e\in\mathcal{H}^{i-1}_{\ell, c}\\ u\in e}} \mathbf{I}[x\in U_{i} \text{ for all $x\in e\setminus\{u\}$} \ \&\  c\in\hat{P}_{i}(y) \text{ for all } y\in e]\\
&\quad +\sum_{s=\ell+1}^{k}\sum_{\substack{e\in \mathcal{H}^{i-1}_{s, c}\\ u\in e}}\sum_{Q\in\binom{e-u}{s-\ell}}
\mathbf{I}[c\inA_{i}(x) \text{ for all }x\in Q \ \&\ c\in \hat{P}_{i}(y) \text{ for all } y\in e]
\end{split}
\]
To simplify the notation, we introduce the following random variables:
\begin{equation}\label{def:keedge}
\mathbf{X}_{\ell}:=\sum_{c\inP_{i-1}(u)}\sum_{\substack{e\in\mathcal{H}^{i-1}_{\ell, c}\\ u\in e}} \mathbf{I}[x\in U_{i} \text{ for all $x\in e\setminus\{u\}$} \ \&\  c\in\hat{P}_{i}(y) \text{ for all } y\in e],
\end{equation}
and
\begin{equation}\label{def:inedge}
\mathbf{X}_{\ell, s}:=\sum_{c\inP_{i-1}(u)}\sum_{\substack{e\in \mathcal{H}^{i-1}_{s, c}\\ u\in e}}\sum_{Q\in\binom{e-u}{s-\ell}}
\mathbf{I}[c\inA_{i}(x) \text{ for all }x\in Q \ \&\ c\in \hat{P}_{i}(y) \text{ for all } y\in e].
\end{equation}
Observe that
\begin{equation}\label{def:sumde}
\begin{split}
\sum_{c\in\hat{P}_{i}(u)}\hat{d}_{i}(u, c)
&=\sum_{c\in\hat{P}_{i}(u)}\sum_{\ell=2}^k\hat{d}^{i}_{\ell}(u, c)(\cdep_{i})^{k-\ell}
=\sum_{\ell=2}^k(\cdep_{i})^{k-\ell}\sum_{c\in\hat{P}_{i}(u)}\hat{d}^{i}_{\ell}(u, c)\\
&\leq \sum_{\ell=2}^k(\cdep_{i})^{k-\ell}\left(
\mathbf{X}_{\ell} + \sum_{s=\ell+1}^{k}\mathbf{X}_{\ell, s}\right).
\end{split}
\end{equation}
To prove Lemma~\ref{lem:concen}, we will show that each $\mathbf{X}_{\ell}$ and $\mathbf{X}_{\ell, s}$ is well-concentrated around its expectation using our new version of Talagrand's inequality (Theorem~\ref{talagrand}).

\subsection{Exceptional outcomes}
In this section, we collect some technical results which will be used later.
Define
\[
N_{i-1}(u):=\left\{v\in U_{i-1} \mid \{u, v\}\subseteq e \text{ for some } e\in \sum_{c\inP_{i-1}(u)}\sum_{\ell=2}^{k}\mathcal{H}^{i-1}_{\ell, c}\right\},
\]
and similarly for the second neighborhood $N^2_{i-1}(u):=\bigcup_{v\in N_{i-1}(u)}N_{i-1}(v)$.
Note that
\[
\text{$|N_{i-1}(u)|\leq k^2\Delta$, and then $|N^2_{i-1}(u)|\leq k^4\Delta^2$.}
\]
Recall that the value of $\sum_{c\in\hat{P}_{i}(u)}\hat{d}_{i}(u, c)$ is determined by the $\{0,1\}$-random variables $\{\gamma^{i}_{v, c}:\ v\in N^2_{i-1}(u), c\in P_{i-1}(v)\}$ and $\{\eta^{i}_{v, c}:\ v\in N_{i-1}(u), c\in P_{i-1}(v)\}$.
Let $(\Omega, \Sigma, \mathbb{P})$ be the product space of those random variables.

The first two lemmas will be used for the concentration of $\mathbf{X}_{\ell}$.

\begin{lemma}\label{lem:exceout2}
Let $\Omega^*_2$ be the set of events where there exists an vertex $v\in N^2_{i-1}(u)$ such that $|A_{i}(v)|\geq \log^2\Delta$. Then
\[
\mathbf{Pr}(\Omega^*_2) \leq \exp\left(- \Omega\left(\log^2\Delta\right)\right).
\]
\end{lemma}
\begin{proof}
By \eqref{def:palet} and \eqref{indas4}, for every vertex $v\in N^2_{i-1}(u)$, we have
\[
\mathbf{E}[|A_{i}(v)|] = \sum_{c\in P_{i-1}(v)}\mathbf{E}[\gamma^{i}_{v, c}]=
\pi_{i}|P_{i-1}(v)|\leq \pi_{i}p_{i-1} \ll 1.
\]
Let $\delta=\frac{\log^2\Delta}{\mathbf{E}[A_{i}(v)] } - 1$. Then by the Chernoff bounds~(Lemma~\ref{chernoff}), we obtain that
\[
\begin{split}
\mathbf{Pr}\left[|A_{i}(v)|\geq \log^2\Delta \right]
&=\mathbf{Pr}\left[|A_{i}(v)|\geq \left(1 + \delta\right)\mathbf{E}[A_{i}(v)]\right]
\leq \exp\left(- \Omega\left( -\delta^2\mathbf{E}[|A_{i}(v)|]/(2 + \delta)\right)\right)\\
&= \exp\left(- \Omega\left( \delta \mathbf{E}[A_{i}(v)] \right)\right)
=\exp\left(- \Omega\left(\log^2\Delta\right)\right).
\end{split}
\]
Finally, by the union bound, we have
\[
\mathbf{Pr}(\Omega^*_2) \leq |N^2_{i-1}(u)|\exp\left(- \Omega\left(\log^2\Delta\right)\right)
\leq k^4\Delta^2\exp\left(- \Omega\left(\log^2\Delta\right)\right)=\exp\left(- \Omega\left(\log^2\Delta\right)\right).
\]
\end{proof}

Define
\begin{equation}\label{def:indexset}
M_{u, \ell}=\{(e, c):\ c\in P_{i-1}(u),\ u\in e\in \mathcal{H}^{i-1}_{\ell, c}\}.
\end{equation}
\begin{lemma}\label{lem:exceout3}
Let $\Omega^*_3$ be the set of events where there exists a color $c'\in \bigcup_{v\in N^2_{i-1}(u)}P_{i-1}(v)$ such that the number of tuples $(e, c)\in M_{u, \ell}$ satisfying $c'\in \bigcup_{x\in e\setminus\{u\}}A_{i}(x)$ is at least $|P_{i-1}(u)|(\cdep_{i-1})^{\ell-2}\log^2\Delta$.
Then
\[
\mathbf{Pr}(\Omega^*_3) \leq \exp\left(-\Omega\left(\log^2\Delta\right)\right).
\]
\end{lemma}
\begin{proof}
Fix an arbitrary color $c'\in \bigcup_{v\in N^2_{i-1}(u)}P_{i-1}(v)$.
Define the random variable
\[
\mathbf{X}:=\sum_{c\inP_{i-1}(u)}\sum_{u\in e\in\mathcal{H}^{i-1}_{\ell, c}}\mathbf{I}_{e,c},
\]
where $\mathbf{I}_{e,c}$ is the indicator random variable for the event where $c'\in \bigcup_{w\in e\setminus\{u\}}A_{i}(w)$.
Note that $\mathbf{E}[\mathbf{I}_{e, c}]=\sum_{x\in e\setminus\{u\}}\mathbf{Pr}(c'\in A_{i}(x))\leq (\ell-1)\pi_{i}$, and therefore
\[
\begin{array}{lll}
\mathbf{E}[\mathbf{X}]&=\sum_{c\inP_{i-1}(u)}\sum_{u\in e\in\mathcal{H}^{i-1}_{\ell, c}}\mathbf{E}[\mathbf{I}_{e,c}]\leq \sum_{c\inP_{i-1}(u)}d^{i-1}_{\ell}(u, c) (\ell-1)\pi_{i} & \\
&\leq|P_{i-1}(u)|\frac{2t_{i-1}}{(\cdep_{i-1})^{k-\ell}}(\ell-1)\pi_{i} & \text{by~\eqref{indas2}} \\
&=\Theta\left(|P_{i-1}(u)|(\cdep_{i-1})^{\ell-2}\right).
& \pi_{i}=\Theta\left(\frac{(\cdep_{i-1})^{k-2}}{t_{i-1}}\right)
\end{array}
\]
We claim that $X$ is $(1, |P_{i-1}(u)|(\cdep_{i-1})^{\ell-2})$-observable in $\Omega$.
To this end, for each $\mathbf{I}_{e, c}$, consider $\omega\in \Omega$ such that $\mathbf{I}_{e, c}(\omega)=1$.
Since $\mathbf{I}_{e, c}(\omega)=1$, then by the definition, there exists an vertex $x\in e\setminus\{u\}$ such that $c'\in A_{i}(x)$.
Let the verifier of $\mathbf{I}_{e, c}$ be $R_{e, c}(w):=\{\gamma^{i}_{x, c'}\}$, and it is easy to observe that $\mathbf{I}_{e,c}$ is $1$-verifiable with such verifier.

For every $\omega\in\Omega$ and random variable $\gamma^{i}_{x, c'}$,
\[
|\{(e, c):\ \mathbf{I}_{e,c}(\omega)=1\ \&\  \gamma^{i}_{x, c'}\in R_{e,c}(\omega)\}|\leq \sum_{c\inP_{i-1}(u)}\delta_{2, \ell}(\mathcal{H}^{i}_{\ell,c})
\leq |P_{i-1}(u)|(\cdep_{i-1})^{\ell-2}.
\]
Set $\tau:=|P_{i-1}(u)|(\cdep_{i-1})^{\ell-2}\log^2\Delta - \mathbf{E}[\mathbf{X}]$.
Then by Lemma~\ref{talagrand}, we have
\[
\begin{split}
\mathbf{Pr}(\mathbf{X} \geq |P_{i-1}(u)|(\cdep_{i-1})^{\ell-2}\log^2\Delta)
&\leq \mathbf{Pr}(|\mathbf{X} - \mathbf{E}[\mathbf{X}]| \geq \tau)\\
& \leq 4\exp\left( -\frac{\tau^2}{8|P_{i-1}(u)|(\cdep_{i-1})^{\ell-2})(4\mathbf{E}[\mathbf{X}] + \tau)}\right) \\
& \leq 4\exp\left( -\frac{\tau}{16|P_{i-1}(u)|(\cdep_{i-1})^{\ell-2})}\right)
= \exp\left( -\Omega(\log^2\Delta)\right).
\end{split}
\]
Finally, by the union bound, we have
\[
\mathbf{Pr}(\Omega^*_3) \leq |N^2_{i-1}(u)|\mathrm{C}\cdot \exp\left( -\Omega(\log^2\Delta)\right)\leq  k^4\Delta^{2+1/(k-1)}\exp\left(-\Omega\left(\log^2\Delta\right)\right)=\exp\left(-\Omega\left(\log^2\Delta\right)\right).
\]

\end{proof}

The next lemma establishes an exceptional outcomes space for the application of Theorem~\ref{talagrand}, and will play an important role in the concentration of $\mathbf{X}_{\ell, s}$.
\begin{lemma}\label{lem:outcome5}
Let $\Omega^*_{s-\ell}$ be the set of events where there exists a color $c\in P_{i-1}(u)$ such that
\[
|\{e\in \mathcal{H}^{i-1}_{s, c} \mid u\in e,\ \sum_{v\in e-u}\gamma^{i}_{v,c}\geq s-\ell\}| > (\varphi_1 p_{i-1})^{\ell-1}\log^{2(s-\ell)}\Delta.
\]
Then
\[
\mathbf{Pr}(\Omega^*_{s-\ell}) \leq \exp\left(-\Omega(\log^2\Delta)\right).
\]
\end{lemma}

The proof of this lemma relies on iteratively building exceptional outcome spaces through repetitive applications of Theorem~\ref{talagrand}.
As a warm-up, let us first prove the following result.
\begin{lemma}\label{lem:outcome4}
For each $0\leq m\leq s-\ell-1$ and $1\leq a\leq s-m-1$, let $\Omega^*_{m, a}$ be the set of events where there exists a set $A\in N^2_{i-1}(u)$ of size $a$ and a color $c\in P_{i-1}(u)$ such that
\[
|\{e\in \mathcal{H}^{i-1}_{s, c} \mid A\cup\{u\}\subseteq e,\ \sum_{v\in e-A\cup\{u\}}\gamma^{i}_{v,c}\geq m\}| > (\varphi_1 p_{i-1})^{s-(a+1)-m}\log^{2m}\Delta.
\]
Then
\[
\mathbf{Pr}(\Omega^*_{m,a}) \leq \exp\left(-\Omega(\log^2\Delta)\right).
\]
\end{lemma}
\begin{proof}
For $m=0$, this is trivially true with $\mathbf{Pr}(\Omega^*_{0,a})=0$, as $\delta^{i-1}_{a+1, s}(\mathcal{H}^{i-1}_{s, c}) \leq  (\varphi_1 p_{i-1})^{s-(a+1)}$.
We will prove the rest of the lemma by induction on $m\geq 1$.

For a set $A\subseteq N^2_{i-1}(u)$ of size at most $s-2$ and a color $c\in P_{i-1}(u)$, let
 $\mathcal{I}(A, c):=\{e\in \mathcal{H}^{i-1}_{s, c} \mid A\cup\{u\}\subseteq e\}$ be an index set, and define the random variable
\[
\mathbf{X}_{m, A,c}:=\sum_{e\in \mathcal{I}(A, c)}\mathbf{I}_{e, m, A, c},
\]
where $\mathbf{I}_{e, m, A, c}$ is the indicator random variable for the event that $\sum_{v\in e-A\cup\{u\}}\gamma^{i}_{v,c}\geq m$.
Clearly, $\mathbf{X}_{m, A, c}=|\{e\in \mathcal{H}^{i-1}_{s, c} \mid A\cup\{u\}\subseteq e,\ \sum_{v\in e-A\cup\{u\}}\gamma^{i}_{v,c}\geq m\}|$.
Note that for $|A|=a$,
\[
\begin{split}
\mathbf{E}[\mathbf{X}_{m, A, c}]
&\leq |\mathcal{I}(A, c)|\binom{s}{m}\pi_{i}^m
\leq \delta^{i-1}_{a+1, s}(\mathcal{H}^{i-1}_{s, c})\binom{s}{m}\pi_{i}^m
\leq \binom{s}{m}(\cdep_{i-1})^{s-(a+1)}\pi_{i}^m\\
&= \binom{s}{m}(\cdep_{i-1})^{s-(a+1)-m}(\cdep_{i-1}\pi_{i})^m
\leq \binom{s}{m}(\cdep_{i-1})^{s-(a+1)-m},
\end{split}
\]
where the third inequality follows from~~\eqref{indas3}, and the last inequality follows from~\eqref{indas4}.
Set
\[
\tau_{m,a}:=\frac12(\varphi_1 p_{i-1})^{s-(a+1)-m}\log^{2m}\Delta,
\]
and observe that $\tau_{m,a}\gg \mathbf{E}[\mathbf{X}_{m, A, c}]$.
\newline

Let us start with the base case, i.e., $m=1$.
Let $1\leq a \leq s-2$.
We claim that, for each set $A\in N^2_{i-1}(u)$ of size $a$ and color $c\in P_{i-1}(u)$,
\begin{equation}\label{outcome4:rdobe1}
\text{$X_{1, A, c}$ is $(1, (\varphi_1 p_{i-1})^{s-(a+2)})$-observable in $\Omega$.}
\end{equation}
To this end, for a random variable $\mathbf{I}_{e, 1, A, c}$ with $e\in \mathcal{I}(A, c)$, let $\omega\in \Omega$ be a random sampling such that $\mathbf{I}_{e, 1, A, c}(\omega)=1$. By the definition of $\mathbf{I}_{e, 1, A, c}$, there must exist a vertex $x\subseteq e-A\cup\{u\}$ such that $\gamma^{i}_{x,c}=1$.
Set $R_{e, 1, A, c}(\omega):=\{\gamma^{i}_{x,c}\}$, and it is not hard to see that $\mathbf{I}_{e, 1, A, c}$ is $1$-verifiable with verifier $R_{e, 1, A, c}$.
Moreover, for every $\omega\in \Omega$ and $\gamma^{i}_{x,c}$, we have
\[
\begin{split}
|\{
e\in \mathcal{I}(A,c) \mid \mathbf{I}_{e, 1, A, c}(\omega)=1,\ \gamma^{i}_{x,c}\in R_{e, 1, A, c}(\omega)
\}|
&\leq|\{e\in \mathcal{H}^{i-1}_{s, c} \mid A\cup\{u, x\}\subseteq e\}|\\
&\leq \delta^{i-1}_{a+2, s}(\mathcal{H}^{i-1}_{s, c}) \leq (\varphi_1 p_{i-1})^{s-(a+2)},
\end{split}
\]
which shows~\eqref{outcome4:rdobe1}, as claimed.

Applying Theorem~\ref{talagrand} on $\mathbf{X}_{1, A, c}$ with $\tau_{1, a}$, we obtain that
\[
\begin{split}
\mathbf{Pr}\left(\mathbf{X}_{1, A, c}> (\varphi_1 p_{i-1})^{s-(a+2)}\log^{2}\Delta\right)
&\leq \mathbf{Pr}(|\mathbf{X}_{1, A, c} - \mathbf{E}[\mathbf{X}_{1, A, c}]|>\tau_{1, a})\\
&\leq 4\exp\left(-\frac{\tau_{1, a}^2}{8\cdot 1\cdot (\varphi_1 p_{i-1})^{s-(a+2)}(4\mathbf{E}[\mathbf{X}_{1, A, c} ] + \tau_{1, a})}\right)\\
&\leq \exp\left(-\Theta(\log^2\Delta)\right).
\end{split}
\]
Then, by the union bound, we have
\[
\mathbf{Pr}(\Omega^*_{1,a}) \leq \sum_{A\in\binom{N^2_{i-1}(u)}{a}}\sum_{c\inP_{i-1}(u)}\mathbf{Pr}\left(\mathbf{X}_{1, A, c}> (\varphi_1 p_{i-1})^{s-(a+2)}\log^{2}\Delta\right) \leq \exp\left(-\Omega(\log^2\Delta)\right).
\]
\newline

Now we assume by induction that the lemma is true for $m-1$, and aim to prove it for $m$.
In particular, we have
\[
\mathbf{Pr}(\Omega^*_{m-1, a+1})\leq \exp\left(-\Omega(\log^2\Delta)\right).
\]
Let $1\leq a \leq s-m-1$.
Similarly as in the base case, we will show that, for each set $A\in N^2_{i-1}(u)$ of size $a$ and color $c\in P_{i-1}(u)$,
\begin{equation}\label{outcome4:rdobe}
\text{$X_{m, A, c}$ is $(m, (\varphi_1 p_{i-1})^{s-(a+1)-m}\log^{2(m-1)}p_{i-1})$-observable with respect to $\Omega^*_{m-1, a+1}$}.
\end{equation}

To this end, for a random variable $\mathbf{I}_{e, m, A, c}$ with $e\in \mathcal{I}(A, c)$, let $\omega\in \Omega\setminus\Omega^*_{m-1, a+1}$ be a random sampling such that $\mathbf{I}_{e, m, A, c}(\omega)=1$. By the definition of $\mathbf{I}_{e, m, A, c}$, there must exist a set $X\subseteq e-A\cup\{u\}$ of size $m$ such that $\gamma^{i}_{x,c}=1$ for all $x\in X$.
Set $R_{e, m, A, c}(\omega):=\{\gamma^{i}_{x,c},\ x\in X\}$, and it is not hard to see that $\mathbf{I}_{e, m, A, c}$ is $m$-verifiable with verifier $R_{e, m, A, c}$.
Moreover, set $A'=A\cup\{x\}$, and for every $\omega\in \Omega \setminus\Omega^*_{m-1, a+1}$ and $\gamma^{i}_{x,c}$,  we have
\[
\begin{split}
&|\{
e\in \mathcal{I}(A,c) \mid \mathbf{I}_{e, m, A, c}(\omega)=1,\ \gamma^{i}_{x,c}\in R_{e,m, A, c}(\omega)
\}|\\
\leq\ &|\{e\in \mathcal{H}^{i-1}_{s, c} \mid A'\cup\{u\}\subseteq e,\ \sum_{v\in e-A'\cup\{u\}}\gamma^{i}_{v,c}\geq m-1\}|\\
\leq\ &(\varphi_1 p_{i-1})^{s-(a+2)-(m-1)}\log^{2(m-1)}p_{i-1}
= (\varphi_1 p_{i-1})^{s-(a+1)-m}\log^{2(m-1)}p_{i-1},
\end{split}
\]
where the second inequality follows from the choice of $\omega$ and the definition of $\Omega^*_{m-1, a+1}$, and which proves~\eqref{outcome4:rdobe}.

Applying Theorem~\ref{talagrand} on $\mathbf{X}_{m, A, c}$ with $\tau_{m, a}$ and $\Omega^*_{m-1, a+1}$, we obtain that
\[
\begin{split}
&\mathbf{Pr}\left(\mathbf{X}_{m, A, c}> (\varphi_1 p_{i-1})^{s-(a+1)-m}\log^{2m}\Delta\right)
\leq \mathbf{Pr}(|\mathbf{X}_{m, A, c} - \mathbf{E}[\mathbf{X}_{m, A, c}]|>\tau_{m, a})\\
\leq\ &4\exp\left(-\frac{\tau_{m, a}^2}{8\cdot m\cdot (\varphi_1 p_{i-1})^{s-(a+1)-m}\log^{2(m-1)}p_{i-1}(4\mathbf{E}[\mathbf{X}_{m, A, c} ] + \tau_{m, a})}\right) + 4\mathbf{Pr}(\Omega^*_{m-1, a+1})\\
\leq\ &\exp\left(-\Omega(\log^2\Delta)\right).
\end{split}
\]
Again by the union bound, we have
\[
\mathbf{Pr}(\Omega^*_{m,a}) \leq \sum_{A\in\binom{N^2_{i-1}(u)}{a}}\sum_{c\inP_{i-1}(u)}\mathbf{Pr}\left(\mathbf{X}_{m, A, c}>(\varphi_1 p_{i-1})^{s-(a+1)-m}\log^{2m}\Delta\right) \leq \exp\left(-\Omega(\log^2\Delta)\right),
\]
which completes the proof.
\end{proof}

Using $\Omega^*_{s-\ell-1, 1}$ from Lemma~\ref{lem:outcome4} as the exceptional outcome space, we now apply Theorem~\ref{talagrand} one more time to prove Lemma~\ref{lem:outcome5}.

\begin{proof}[Proof of Lemma~\ref{lem:outcome5}]
The proof is very similar to that of Lemma~\ref{lem:outcome4}.
For a color $c\in P_{i-1}(u)$, let
 $\mathcal{I}(c):=\{e\in \mathcal{H}^{i-1}_{s, c} \mid u\in e\}$ be an index set, and define the random variable
\[
\mathbf{X}_{c}:=\sum_{e\in \mathcal{I}(c)}\mathbf{I}_{e, c},
\]
where $\mathbf{I}_{e, c}$ is the indicator random variable for the event that $\sum_{v\in e-u}\gamma^{i}_{v,c}\geq s-\ell$.
Clearly, $\mathbf{X}_{c}=|\{e\in \mathcal{H}^{i-1}_{s, c} \mid u\in e,\ \sum_{v\in e-u}\gamma^{i}_{v,c}\geq s-\ell\}|$.
Note that
\[
\begin{split}
\mathbf{E}[\mathbf{X}_{c}]
&\leq |\mathcal{I}(c)|\binom{s-1}{s-\ell}\pi_{i}^{s-\ell}
\leq d^{i-1}_{s}(u, c)\binom{s-1}{s-\ell}\pi_{i}^{s-\ell}
\leq \binom{s-1}{s-\ell}\frac{2t_{i-1}}{(\cdep_{i-1})^{k-s}}\pi_{i}^{s-\ell}\\
&=\binom{s-1}{s-\ell}\frac{2t_{i-1}\pi_{i}}{(\cdep_{i-1})^{k-\ell-1}}(\cdep_{i-1}\pi_{i})^{s-\ell-1}
\leq \binom{s-1}{s-\ell}\frac{2t_{i-1}\pi_{i}}{(\cdep_{i-1})^{k-\ell-1}}
=\binom{s-1}{s-\ell}\frac{\varphi_2}{2}(\cdep_{i-1})^{\ell-1},
\end{split}
\]
where the third inequality follows from~~\eqref{indas3}, and the last inequality follows from~\eqref{indas4}.
Set
\[
\tau:=\frac12(\varphi_1 p_{i-1})^{\ell-1}\log^{2(s-\ell)}\Delta,
\]
and observe that $\tau \gg \mathbf{E}[\mathbf{X}_{c}]$.

We claim that
for each color $c\in P_{i-1}(u)$,
\begin{equation}\label{outcome5:rdobe}
\text{$\mathbf{X}_{c}$ is $(s-\ell, (\varphi_1 p_{i-1})^{\ell-1}\log^{2(s-\ell-1)})$-observable with respect to $\Omega^*_{s-\ell-1, 1}$}.
\end{equation}
To this end, for a random variable $\mathbf{I}_{e, c}$ with $e\in \mathcal{I}(c)$, let $\omega\in \Omega\setminus\Omega^*_{s-\ell-1, 1}$ be a random sampling such that $\mathbf{I}_{e, c}(\omega)=1$. By the definition of $\mathbf{I}_{e, c}$, there must exist a set $X\subseteq e-\{u\}$ of size $s-\ell$ such that $\gamma^{i}_{x,c}=1$ for all $x\in X$.
Set $R_{e, m, A, c}(\omega):=\{\gamma^{i}_{x,c},\ x\in X\}$, and it is not hard to see that $\mathbf{I}_{e, m, A, c}$ is $s-\ell$-verifiable with verifier $R_{e, m, A, c}$.
Moreover, for every $\omega\in \Omega \setminus\Omega^*_{s-\ell-1, 1}$ and $\gamma^{i}_{x,c}$,  we have
\[
\begin{split}
&|\{
e\in \mathcal{I}(c) \mid \mathbf{I}_{e, c}(\omega)=1,\ \gamma^{i}_{x,c}\in R_{e, c}(\omega)
\}|\\
\leq\ &|\{e\in \mathcal{H}^{i-1}_{s, c} \mid \{u, x\}\subseteq e,\ \sum_{v\in e-\{u, x\}}\gamma^{i}_{v,c}\geq s-\ell-1\}|\\
\leq\ &(\varphi_1 p_{i-1})^{s-2-(s-\ell-1)}\log^{2(s-\ell-1)}p_{i-1}
= (\varphi_1 p_{i-1})^{\ell-1}\log^{2(s-\ell-1)}p_{i-1},
\end{split}
\]
where the second inequality follows from the choice of $\omega$ and the definition of $\Omega^*_{s-\ell-1, 1}$, and which proves~\eqref{outcome5:rdobe}.

Applying Theorem~\ref{talagrand} on $\mathbf{X}_{c}$ with $\tau$ and $\Omega^*_{s-\ell-1, 1}$, we obtain that
\[
\begin{split}
&\mathbf{Pr}\left(\mathbf{X}_{c}> (\varphi_1 p_{i-1})^{\ell-1}\log^{2(s-\ell)}\Delta\right)
\leq \mathbf{Pr}(|\mathbf{X}_{c} - \mathbf{E}[\mathbf{X}_{c}]|>\tau)\\
\leq\ &4\exp\left(-\frac{\tau^2}{8\cdot (s-\ell)\cdot (\varphi_1 p_{i-1})^{\ell-1}\log^{2(s-\ell-1)}p_{i-1}(4\mathbf{E}[\mathbf{X}_{c} ] + \tau)}\right) + 4\mathbf{Pr}(\Omega^*_{s-\ell-1, 1})\\
\leq\ &\exp\left(-\Omega(\log^2\Delta)\right).
\end{split}
\]
Finally, by the union bound, we have
\[
\mathbf{Pr}(\Omega^*_{s-\ell}) \leq \sum_{c\inP_{i-1}(u)}\mathbf{Pr}\left(\mathbf{X}_{c}> (\varphi_1 p_{i-1})^{\ell-1}\log^{2(s-\ell)}\Delta\right) \leq \exp\left(-\Omega(\log^2\Delta)\right),
\]
which completes the proof.
\end{proof}

\section{Probabilistic tools}\label{sec:prob}
\subsection{The Lov{\'a}sz Local Lemma}
\begin{thm}[The Asymmetric Local Lemma~\cite{molloy2002graph}]
Consider a set $\mathcal{E}=\{\mathcal{A}_1, \ldots, \mathcal{A}_n\}$ of (typically bad) events such that each $\mathcal{A}_i$ is mutually independent of $\mathcal{E} -(\mathcal{D}_i  \cup \mathcal{A}_i)$, for some $\mathcal{D}_i \subset \mathcal{E}$.
If for each $1 \leq i \leq n$
\begin{itemize}
\item $\mathbf{Pr}(\mathcal{A}_i) \leq 1/4$, and
\item $\sum_{\mathcal{A}_j\in \mathcal{D}_i}\mathbf{Pr}(\mathcal{A}_j) \leq 1/4$,
\end{itemize}
then with positive probability, none of the events in $\mathcal{E}$ occur.
\end{thm}

\subsection{Concentration inequalities}
\label{sec:coneq}
One of the key ingredients of our proof, is the following new version of Talagrand's concentration inequality (Theorem~\ref{talagrand}) from recent work of Delcourt and Postle~\cite{DP}.
To state their result, we first need some definitions.

\begin{defi}[$r$-verifiable]
Let $\{(\Omega_i, \Sigma_i, \mathbb{P}_i)\}^{n}_{i=1}$ be probability spaces, $(\Omega, \Sigma, \mathbb{P})$ be their product space, $\Omega^*\subseteq \Omega$ be a set of \textit{exceptional outcomes}, and $\mathbf{Y}:\Omega \rightarrow \{0, 1\}$ be a $\{0, 1\}$-random variable.
Let $r\geq 0$.
We say $\mathbf{Y}$ is \textit{$r$-verifiable} with verifier $R:\{\omega\in\Omega\setminus\Omega^*: \mathbf{Y}(\omega)=1\}\rightarrow 2^{[n]}$ with respect to $\Omega^*$ if
\begin{itemize}
\item $|R(\omega)|\leq r$ for every $\omega\in\Omega\setminus\Omega^*$ with $\mathbf{Y}(\omega)=1$, and
\item $\mathbf{Y}(\omega')=1$ for all $\omega'=(\omega'_1, \ldots, \omega'_n)\in \Omega\setminus\Omega^*$ such that $\omega_i=\omega'_i$ for each $i\in R(\omega)$.
\end{itemize}
\end{defi}

\begin{defi}[$(r, d)$-observable]
Let $\{(\Omega_i, \Sigma_i, \mathbb{P}_i)\}^{n}_{i=1}$ be probability spaces, $(\Omega, \Sigma, \mathbb{P})$ be their product space, and $\Omega^*\subseteq \Omega$ be a set of \textit{exceptional outcomes}.
Let $r, d\geq 0$.
We say a random variable $\mathbf{X}$ in $\Omega$ is \textit{$(r, d)$-observable} with respect to $\Omega^*$ if
\begin{itemize}
\item  \[
\mathbf{X}=\sum_{j=1}^{m}\mathbf{Y}_j,
\]
where for every $j\in[m]$, $\mathbf{Y}_j$ is a $\{0, 1\}$-random variable in $\Omega$ that is $r$-verifiable with verifiers $R_j$, and
\item  for  every $\omega \in \Omega\setminus\Omega^*$ and $i\in [n]$,
\[
|\{j:\ i\in R_j(\omega) \ \text{and} \ \mathbf{Y}_j(\omega)=1\}|\leq d.
\]
\end{itemize}
\end{defi}

Now we state their concentration inequality, as follows.
\begin{thm}[Delcourt-Postle~\cite{DP}]
\label{talagrand}
Let $\{(\Omega_i, \Sigma_i, \mathbb{P}_i)\}^{n}_{i=1}$ be probability spaces, $(\Omega, \Sigma, \mathbb{P})$ be their product space, and $\Omega^*\subseteq \Omega$ be a set of exceptional outcomes.
Let $r, d\geq 0$, and $\mathbf{X}: \Omega \rightarrow \mathbb{R}_{\geq 0}$ be a non-negative random variable.
If $\mathbf{X}$ is $(r, d)$-observable with respect to $\Omega^*$, then for any $\tau>96\sqrt{rd\mathbf{E}[\mathbf{X}]} + 128rd + 8\mathbf{Pr}[\Omega^*](\sup \mathbf{X})$,
\[
\mathbf{Pr}(|\mathbf{X} - \mathbf{E}[\mathbf{X}]|>\tau) \leq 4\exp\left(-\frac{\tau^2}{8rd(4\mathbf{E}[\mathbf{X}] + \tau)}\right) + 4\mathbf{Pr}(\Omega^*).
\]
\end{thm}
We also need the following classical Chernoff bound (see~\cite{alon2016probabilistic}).
\begin{lemma}[Chernoff bound]\label{chernoff}
Let $\mathbf{X}_1, \ldots, \mathbf{X}_n$ be independent $\{0, 1\}$-random variables such that $\mathbf{Pr}(\mathbf{X}_i=1)=p$.
Let $\mathbf{X}=\sum_i\mathbf{X}_i$.
Then
\begin{itemize}
\item Upper tail:
$\mathbf{Pr}(\mathbf{X} \geq (1  +\delta)\mathbf{E}[\mathbf{X}]) \leq \exp\left(-\delta^2\mathbf{E}[\mathbf{X}]/(2 + \delta)\right)$ for all $\delta >0$;
\item Lower tail:
$\mathbf{Pr}(\mathbf{X} \leq (1  -\delta)\mathbf{E}[\mathbf{X}]) \leq \exp\left(-\delta^2\mathbf{E}[\mathbf{X}]/2\right)$ for all $0<\delta <1$;
\end{itemize}
\end{lemma}
Lastly, we present a simple but useful proposition about conditional probability.
\begin{prop}\label{lem:prb}
For any two events $\mathcal{A}$ and $\mathcal{B}$,
\[
\mathbf{Pr}(\mathcal{A})\leq \mathbf{Pr}(\mathcal{A}\mid \mathcal{B}) + \mathbf{Pr}(\overline{\mathcal{B}}).
\]
\end{prop}
\begin{proof}
\[
\mathbf{Pr}(\mathcal{A})= \mathbf{Pr}(\mathcal{A}\mid \mathcal{B})\cdot\mathbf{Pr}(\mathcal{B})+ \mathbf{Pr}(\mathcal{A}\mid \overline{\mathcal{B}})\cdot\mathbf{Pr}(\overline{\mathcal{B}})
\leq \mathbf{Pr}(\mathcal{A}\mid \mathcal{B}) + \mathbf{Pr}(\overline{\mathcal{B}}).
\]
\end{proof}

\subsection{Janson's Inequality}
Let $\Omega$ be a finite universal set and let $\mathbf{R}$ be a random subset of $\Omega$ defined in such a way that the elements are chosen independently with
\[
\mathbf{Pr} (v\in \mathbf{R}) = p_v
\]
for each $v\in\Omega$.
Let $\{A_i\}_{i\in I}$ be subsets of $\Omega$, $I$ a finite index set.
Let $\mathcal{A}_{i}$ be the event $A_i\subseteq \mathbf{R}$.
(That is, each point $v\in\Omega$ ``flip a coin" to determine if it is in $\mathbf{R}$, and $\mathcal{A}_i$ is the event that the coins for all $v\in A_i$ came up ``heads".)

For $i, j\in I$ we write $i \sim j$ if $i\neq j$ and $A_i\cap A_j\neq \emptyset$.
Note that when $i\neq j$ and not $i\sim j$, then $\mathcal{A}_i$, $\mathcal{A}_j$ are independent events. We define
\begin{equation}\label{Janson:delta}
\Delta^*:=\sum_{i \sim j}\mathbf{Pr}(\mathcal{A}_i\wedge\mathcal{A}_j),
\end{equation}
where the sum is over ordered pairs $(i, j)$.
We set
\begin{equation}\label{Janson:M}
M:=\prod_{i\in I}\mathbf{Pr}(\overline{\mathcal{A}_i}).
\end{equation}
The following result was given by Janson, {\L}uczak and Ruci{\'n}ski~\cite{janson1988exponential}.
\begin{thm}[Janson's Inequality]\label{Janson}
Let $\{\mathcal{A}_i\}_{i\in I}$, $\Delta^*$, $M$ be as above and assume that there is an $\varepsilon>0$ so that $\mathbf{Pr}(\mathcal{A}_i)\leq \varepsilon$ for all $i\in I$. Then
\[
M\leq \mathbf{Pr}\left(\bigwedge_{i\in I}\overline{\mathcal{A}_i}\right) \leq M\exp\left(\frac{1}{1-\varepsilon}\frac{\Delta^*}{2}\right).
\]

\end{thm}

\subsection{A correlation inequality}
We also use the following correlation inequality from~\cite{alon2016probabilistic}.
Let $p=(p_1, \ldots, p_n)$ be a real vector, where $0\leq p_i \leq 1$. Consider the probability space whose element are all members of the power set $\mathcal{P}(N)$, where, for each $A\subseteq N$, $\mathbf{Pr}(A)=\prod_{i\in A}p_i\prod _{j\notin A}(1-p_j)$.
Clearly this probability distribution is obtained if we choose a random $A\subseteq$ by choosing each element $i\in N$, independently, with probability $p_i$.
For each $\mathcal{A} \subseteq \mathcal{P}(N)$, Let us denote by $\mathbf{Pr}_p[\mathcal{A}]$ its probability in this space, i.e., $\sum_{A\in\mathcal{A}}\mathbf{Pr}(A)$.

A family $\mathcal{A}$ of subsets of $N$ is \textit{monotone decreasing} if $A \in \mathcal{A}$ and $A'\subseteq\mathcal{A}$ indicates $A'\in\mathcal{A}$. Similarly, it is \textit{monotone increasing} if $A\in\mathcal{A}$ and $A\subseteq A'$ indicates $A'\in\mathcal{A}$.
\begin{thm}\cite[Theorem 6.3.2]{alon2016probabilistic}\label{FKG}
Let $\mathcal{A}$ and $\mathcal{B}$ be two monotone increasing families of subsets of $N$ and let $\mathcal{C}$ and $\mathcal{D}$ be two monotone decreasing families of subsets of $N$. Then, for any real vector $p=(p_1, \ldots, p_n)$, $0\leq p_i \leq 1$,
\begin{align*}
\mathbf{Pr}_p(\mathcal{A}\cap\mathcal{B}) \geq \mathbf{Pr}_p(\mathcal{A})\cdot\mathbf{Pr}_p(\mathcal{B}), \\
\mathbf{Pr}_p(\mathcal{C}\cap\mathcal{D}) \geq \mathbf{Pr}_p(\mathcal{C})\cdot\mathbf{Pr}_p(\mathcal{D}), \\
\mathbf{Pr}_p(\mathcal{A}\cap\mathcal{C}) \leq \mathbf{Pr}_p(\mathcal{A})\cdot\mathbf{Pr}_p(\mathcal{C}).
\end{align*}
\end{thm}

\section{Proof of Main Lemma}
\begin{lemma}\label{mainlemma}
For every $t\leq T-1$, if \ref{p1}--\ref{p6} holds for $t$ and $|B^t(u)|\leq \varepsilon/\hat{p}$ for all $u\in U^t$, then there exists an assignment of colors to the vertices in $U^t$ so that the following properties hold:
\begin{itemize}
\item[\namedlabel{q1}{\textrm{(Q1)}}]
\item[\namedlabel{q2}{\textrm{(Q2)}}]  for every edge $uv_1\ldots v_{\ell-1}\in \mathcal{H}^t_{k, c}$,
\[
f^{t+1}_{uv_1\ldots v_{\ell-1}}\leq f^{t}_{uv_1\ldots v_{\ell-1}} + 1/(\Delta \omega^{2});
\]
 \item[\namedlabel{q3}{\textrm{(Q3)}}]  for every $2\leq \ell \leq k-1$,
 \[
 f^{t+1}_{\ell, u}\leq  f^{t}_{\ell, u}(1 - \theta/2) + 2\theta\sum_{s=\ell+1}^{k}\binom{s-1}{\ell-1}f_{s, u}^t + 1/\omega^2;\]
  \item[\namedlabel{q4}{\textrm{(Q4)}}]

    \item[\namedlabel{q5}{\textrm{(Q5)}}] $d_{\mathcal{H}^{t+1}_{k, c}}(u)\leq (1 - \theta/2)d_{\mathcal{H}_k^t}(u) + \Delta^{1 - \frac{1}{6(k-1)}}$;

   \item[\namedlabel{q6}{\textrm{(Q6)}}]

\end{itemize}
\end{lemma}

For simplicity, we use ' for step $t+1$, and ignore the superscript for $t$.
\subsection{Proof of \ref{q1}, \ref{q2} and \ref{q4}}
\subsection{Proof of \ref{q6}}

\subsection{Proof of \ref{q3}}
Throughout this section, we fix an arbitrary vertex $u\in U$ and an integer $2\leq\ell \leq k-1$.
\[
\begin{split}
f'_{\ell, u} &= \sum_{c\in C(u)}\sum_{\substack{uv_1\ldots v_{\ell-1}\\ \in \mathcal{H}'_{\ell, c}}}p'_u(c)\prod_{i=1}^{\ell-1}p'_{v_i}(c)\\
&\leq\sum_{c\in C(u)}\sum_{\substack{uv_1\ldots v_{\ell-1}\\ \in \mathcal{H}_{\ell, c}}} p'_u(c)\prod_{i=1}^{\ell-1}p'_{v_i}(c)\mathbf{I}[v_1,\ldots, v_{\ell-1}\in U']\\
&\quad+
\sum_{c\in C(u)}\sum_{s=\ell+1}^{k}\sum_{\substack{uv_1\ldots v_{s-1}\\ \in \mathcal{H}_{s, c}}} \sum_{I\in \binom{[s-1]}{\ell -1}}
p'_u(c)\prod_{i\in I}p'_{v_i}(c)\prod_{j\in [s-1]\setminus I}\mathbf{I}[\gamma_{v_j}(c)=1]\\
&:= D_1 + D_2.
\end{split}
\]

\subsubsection{Useful claims}
\begin{claim}
Let $v\in U$.
\begin{itemize}
\item[$\mathrm{(a)}$] $\mathbf{Pr}\left[v\notin U'\right] \geq 3\theta/4$.

\item[$\mathrm{(b)}$] For every color $c$, edge $uv_1\ldots v_{\ell-1}\in \mathcal{H}_{\ell, c}$, and $S\subseteq \{u, v_1, \ldots, v_{\ell-1}\}$,
\[
\mathbf{Pr}\left[\overline{v_1, \ldots, v_{\ell-1}\in U'} \mid c\notin \bigcup_{v\in S}L(v)\right] \geq 5\theta/8.
\]
\end{itemize}
\end{claim}

\begin{claim}\label{claim:Q3:2}
Define
\[
N^*(u)=\left\{
S=\{v_1, \ldots, v_{\ell-1}\} : uv_1\ldots v_{\ell-1}\in \mathcal{H}_{\ell}
\right\}.
\]
For each integer $0\leq j\leq m-2$, let
\begin{equation}\label{sec:L3:Q3:defN1}
N^*(u, j)=\left\{
S=\{v_1, \ldots, v_{\ell-1}\}\in \binom{N_{\mathcal{H}}(u)}{\ell-1}\setminus N^*(u) :\ \Delta^{\frac{j}{(k-1)m}}\leq d_{\mathcal{H}_{\geq \ell +1}}(u\cup S) < \Delta^{\frac{j+1}{(k-1)m}}
\right\},
\end{equation}
and for $j=m-1$, let
\[
N^*(u, j)=N^*(u) \cup \left\{
S=\{v_1, \ldots, v_{\ell-1}\}\in \binom{N_{\mathcal{H}}(u)}{\ell-1}\setminus N^*(u) :\ d_{\mathcal{H}_{\geq \ell +1}} (u\cup S) \geq \Delta^{\frac{j}{(k-1)m}}
\right\}.
\]
For each color $c$ and $0\leq j \leq m-1$, we define
\begin{equation}\label{sec:L3:Q3:defA}
\mathcal{A}_{c, j}:= \text{the event that  }\sum_{v\in S}\gamma_{v} (c)\geq 1 \text{ for less than } \Delta^{1 - \frac{j}{(k-1)m}}\hat{p} \text{ sets } S\in N^*(u, j).
\end{equation}
Then $\mathbf{Pr}\left[\overline{\bigcap_{c, j}\mathcal{A}_{c, j}}\right]\leq \exp(-10\log\Delta)$.

\end{claim}

\subsubsection{Bound on $D_1$}
\noindent\textbf{Expectation.}
First, we will show that for every color $c$ and $\ell$-edge $uv_1\ldots v_{\ell-1}\in \mathcal{H}_{\ell, c}$,
\begin{equation}\label{sec:L3:Q3:d1:eq1}
\mathbf{E}\left[
p'_u(c)\prod_{i=1}^{\ell-1}p'_{v_i}(c)\mathbf{I}[v_1,\ldots, v_{\ell-1}\in U']
\right]
\leq p_u(c)\prod_{i=1}^{\ell-1}p_{v_i}(c)(1 - 9\theta/16).
\end{equation}
Then by (\ref{sec:L3:Q3:d1:eq1}) we have
\[
\begin{split}
\mathbf{E}[D_1]&=\sum_{c\in C(u)}\sum_{\substack{uv_1\ldots v_{\ell-1}\\ \in \mathcal{H}_{\ell, c}}}\mathbf{E}\left[
p'_u(c)\prod_{i=1}^{\ell-1}p'_{v_i}(c)\mathbf{I}[v_1,\ldots, v_{\ell-1}\in U']
\right] \\
&\leq \sum_{c\in C(u)}\sum_{\substack{uv_1\ldots v_{\ell-1}\\ \in \mathcal{H}_{\ell, c}}} p_u(c)\prod_{i=1}^{\ell-1}p_{v_i}(c)(1 - 9\theta/16)
= f_{\ell, u}(1 - 9\theta/16).
\end{split}
\]

\noindent\textbf{Concentration.}
For $c\in C(u)$, let
\[
\mathbf{X}_c=\{\gamma_v(c):\ v\in N(N(u))\} \cup \{\eta_v(c): \ v\in N(N(u))\}.
\]
One should think $\mathbf{X}_c$ as an $2|N(N(u))|$-dimensional vector, where each entry is an independent random variable. Note that random vectors $\{\mathbf{X}_c: c\in C(u)\}$ are mutually independent and determine the value of $D_1$. We then apply Corollary~\ref{sec:coneq:cor:mcd} on $D_1=D_1(\{\mathbf{X}_c\}_{c\in C(u)})$ with the following:
\begin{itemize}
\item $\mathcal{B}_c=\{0, 1\}^{2|N(N(u))|}$, and note that $D_1: \prod_{c\in C(u)} \mathcal{B}_c \rightarrow \mathbb{R}$;
\item For each color $c$, let $\mathcal{A}_c=\bigcap_{0\leq j\leq m-1}\mathcal{A}_{c, j}$, where $\mathcal{A}_{c, j}$ is defined as (\ref{sec:L3:Q3:defA});
\item $\mathcal{A}=\prod_{c\in C(u)} \mathcal{A}_c$.
\end{itemize}

Fix an arbitrary color $c^*\in C(u)$. Let $x, x'\in \mathcal{A}$ such that $x$ and $x'$ differ only in coordinate $c^*$. Next, we will show that
\[
|D_1(x) - D_1(x')| \leq d_{c^*}:=.
\]
Note that
\[
\begin{split}
D_1
&= \sum_{\substack{uv_1\ldots v_{\ell-1}\\\ \in \mathcal{H}_{\ell, c^*}}}p'_u(c^*)\prod_{i=1}^{\ell-1}p'_{v_i}(c^*)\mathbf{I}[v_1,\ldots, v_{\ell-1}\in U']\\
&\quad +\sum_{j=0}^{m-1}\sum_{\substack{\{v_1, \ldots, v_{\ell-1}\} \\ \in N^*(u, j)}}\mathbf{I}[v_1,\ldots, v_{\ell-1}\in U']
\sum_{\substack{c\in C(u) - c^*:\\ \ uv_1\ldots v_{\ell-1} \in \mathcal{H}_{\ell, c}}}p'_u(c)\prod_{i=1}^{\ell-1}p'_{v_i}(c)\\
&:=D_{1,1} + \sum_{j=0}^{m-1}\sum_{\substack{\{v_1, \ldots, v_{\ell-1}\} \\ \in N^*(u, j)}} D^{v_1, \ldots, v_{\ell-1}}_{1,2}.
\end{split}
\]

Observe first that $0\leq D_{1,1} \leq d_{\mathcal{H}_{\ell, c^*}}(u)\hat{p}^{\ell},$ and therefore we always have
\begin{equation*}
|D_{1,1}(x) - D_{1,1}(x')|\leq d_{\mathcal{H}_{\ell, c^*}}(u)\hat{p}^{\ell}.
\end{equation*}
Fix an arbitrary set $S=\{v_1, \ldots, v_{\ell-1}\}\in N^*(u, j)$.
If $j\leq m-2$, by the mechanics of the algorithm and the definition~(\ref{sec:L3:Q3:defN1}), $uv_1\ldots v_{\ell-1}\in \mathcal{H}_{\ell, c}$ only if there exists an edge $e\in \mathcal{H}$ with $e\supset (S\cup\{u\})$, such that all vertices in $e\setminus (S\cup\{u\})$ are colored by $c$ in the previous rounds.
By the definition of $N^*(u, j)$, we have $D^{v_1, \ldots, v_{\ell-1}}_{1,2}\leq d_{\mathcal{H}_{\geq \ell +1}}(u\cup S)\hat{p}^{\ell} < \Delta^{\frac{j+1}{(k-1)m}}\hat{p}^{\ell}$, and therefore
\begin{equation*}
|D^{v_1, \ldots, v_{\ell-1}}_{1,2}(x) - D^{v_1, \ldots, v_{\ell-1}}_{1,2}(x')|\leq \Delta^{\frac{j+1}{(k-1)m}}\hat{p}^{\ell}
\quad \text{for} \quad j\leq m-2.
\end{equation*}
If $j=m-1$, then we simply use
\begin{equation*}
|D^{v_1, \ldots, v_{\ell-1}}_{1,2}(x) - D^{v_1, \ldots, v_{\ell-1}}_{1,2}(x')|\leq C\hat{p}^{\ell} \leq \Delta^{\frac{1}{(k-1)}}\hat{p}^{\ell}
\quad \text{for} \quad j= m-1.
\end{equation*}
Moreover, suppose that in both $x$ and $x'$, none of the vertices $v_1,\ldots, v_{\ell-1}$ has color $c^*$ being activated, i.e. $\sum_{i=1}^{\ell-1}\gamma_{v_i}(c^*)=0$.
Then $\mathbf{I}[v_1,\ldots, v_{\ell-1}\in U']|_x=\mathbf{I}[v_1,\ldots, v_{\ell-1}\in U']|_{x'}$, as $x, x'$ only differ at coordinate $c^*$ and we know that $c^*$ cannot be used for coloring these vertices.
Therefore, $D^{v_1, \ldots, v_{\ell-1}}_{1,2}(x)$, $D^{v_1, \ldots, v_{\ell-1}}_{1,2}(x')$ only differ at those sets $S=\{v_1,\ldots, v_{\ell-1}\}$, where $\sum_{v\in S}\gamma_{v}(c^*)\geq 1$ in one of $x$ and $x'$.
Since $x, x'\in \mathcal{A}$, and by the definition of (\ref{sec:L3:Q3:defA}), there are at most $2\Delta^{1 - \frac{j}{(k-1)m}}\hat{p}$ such sets in $N^*(u, j)$. Hence, we have
\begin{equation}
\begin{split}
|D_1(x) - D_1(x')|
&\leq |D_{1,1}(x) - D_{1,1}(x')| + \sum_{j=0}^{m-1}\sum_{\substack{\{v_1, \ldots, v_{\ell-1}\} \\ \in N^*(u, j)}} |D^{v_1, \ldots, v_{\ell-1}}_{1,2}(x) - D^{v_1, \ldots, v_{\ell-1}}_{1,2}(x')|\\
&\leq d_{\mathcal{H}_{\ell, c^*}}(u)\hat{p}^{\ell} + \sum_{j=0}^{m-2}2\Delta^{1 - \frac{j}{(k-1)m}}\hat{p}\cdot \Delta^{\frac{j+1}{(k-1)m}}\hat{p}^{\ell}
+ 2\Delta^{1 - \frac{m-1}{(k-1)m}}\hat{p}\cdot \Delta^{\frac{1}{(k-1)}}\hat{p}^{\ell}\\
& \leq d_{\mathcal{H}_{\ell, c^*}}(u)\hat{p}^{\ell} + 2m\Delta^{1 + \frac{1}{(k-1)m}}\hat{p}^{\ell+1}:=d_{c^*}.
\end{split}
\end{equation}
Since $\sum_{c\in C(u)}d_{\mathcal{H}_{\ell, c}}(u) \leq \Delta_{\ell} + \ldots + \Delta_k \leq 2\Delta$, and by (P6),
\[
d_{\mathcal{H}_{\ell, c}}(u) \leq c(\ell, k)T\theta\hat{p}\Delta,
\]
we have
\[
\begin{split}
\sum_{c\in C(u)} d^2_c
&=\sum_{c\in C(u)}\left[d_{\mathcal{H}_{\ell, c}}(u)^2\hat{p}^{2\ell} + 4m^2\Delta^{2 + \frac{2}{(k-1)m}}\hat{p}^{2\ell+2} + 4md_{\mathcal{H}_{\ell, c}}(u)\Delta^{1 + \frac{1}{(k-1)m}}\hat{p}^{2\ell+1}\right]\\
&\leq 2c(\ell, k)T\theta\Delta^2\hat{p}^{2\ell+1} + 4Cm^2\Delta^{2 + \frac{2}{(k-1)m}}\hat{p}^{2\ell+2} + 8m\Delta^{2 + \frac{1}{(k-1)m}}\hat{p}^{2\ell+1}\\
&\leq O(C\Delta^{2 + \frac{2}{(k-1)m}}\hat{p}^{2\ell+2})
\leq O(C\Delta^{2 + \frac{2}{(k-1)m}}\hat{p}^{6})
\end{split}
\]
\textcolor{red}{which is not smaller than $\Delta^{-\epsilon}$ as we expected if $\ell\leq k-2$.}
Together with Claim~\ref{claim:Q3:2}, Corollary~\ref{sec:coneq:cor:mcd} indicates that
\[
\begin{split}
\mathbf{Pr}\left[ D_1 > f_{\ell, u }(1 - \theta/2) + 1/2\omega^2\right]
&\leq \mathbf{Pr}\left[ D_1 > f_{\ell, u}(1 - 9\theta/16)/\mathbf{Pr}[\mathcal{A}] + 1/2\omega^2\right]\\
&\leq \mathbf{Pr}\left[ D_1 > \mathbf{E} [D_1]/\mathbf{Pr}[\mathcal{A}] + 1/2\omega^2\right]\\
&\leq \exp\left(-\frac{1}{2\omega^4\sum_{c\in C(u)} d^2_c}\right) + \exp(-10\log\Delta)
\end{split}
\]

\subsubsection{Bound on $D_2$}
\noindent\textbf{Expectation.}
\begin{claim}
For any $\ell+1\leq s \leq k$ and any edge $uv_1\ldots v_{s-1}\in \mathcal{H}_{s, c}$,
\[
\mathbf{E}\left[
p'_{u}(c)\prod_{j=1}^{\ell-1}p'_{v_j}(c) \mid \prod_{j=\ell}^{s-1}\gamma_{v_j}(c)=1
\right]
\leq p_{u}(c)\prod_{j=1}^{\ell-1}p_{v_j}(c)(1 + 1/\omega_0).
\]
\end{claim}
Then
\[
\begin{split}
\mathbf{E}[D_2]
&=
\sum_{c\in C(u)}\sum_{s=\ell+1}^{k}\sum_{\substack{uv_1\ldots v_{s-1}\\ \in \mathcal{H}_{s, c}}} \sum_{I\in \binom{[s-1]}{\ell -1}}
\mathbf{E}\left[
p'_u(c)\prod_{i\in I}p'_{v_i}(c)\prod_{j\in [s-1]\setminus I}\mathbf{I}[\gamma_{v_j}(c)=1]
\right]\\
&=
\sum_{c\in C(u)}\sum_{s=\ell+1}^{k}\sum_{\substack{uv_1\ldots v_{s-1}\\ \in \mathcal{H}_{s, c}}} \sum_{I\in \binom{[s-1]}{\ell -1}}
\mathbf{E}\left[
p'_u(c)\prod_{i\in I}p'_{v_i}(c) \mid \prod_{j\in [s-1]\setminus I}\gamma_{v_j}(c)=1
\right]
\mathbf{Pr}\left[\prod_{j\in [s-1]\setminus I}\gamma_{v_j}(c)=1\right]\\
&\leq
\sum_{c\in C(u)}\sum_{s=\ell+1}^{k}\sum_{\substack{uv_1\ldots v_{s-1}\\ \in \mathcal{H}_{s, c}}} \sum_{I\in \binom{[s-1]}{\ell -1}}
p_u(c)\prod_{i\in I}p_{v_i}(c)(1 + 1/\omega_0)
\theta^{s-\ell}\prod_{j\in [s-1]\setminus I}p_{v_j}(c)\\
&\leq (1 + 1/\omega_0)
\sum_{s=\ell+1}^{k}\theta^{s-\ell}\binom{s-1}{\ell-1}f_{s, u}
\leq (1 + 1/\omega_0)\theta
\sum_{s=\ell+1}^{k}\binom{s-1}{\ell-1}f_{s, u}
\end{split}
\]
\noindent\textbf{Concentration.}

\section{Open problems}\label{sec:conclu}
In this paper, we showed that by forbidding all triangles, one can improve the trivial bound of the chromatic number and therefore independence number of hypergraphs by some polylogarithmic factor.
We remark that answering negatively a question of Ajtai, Erd\H{o}s, Koml{\'o}s and Szemer{\'e}di~\cite{ajtai1981turan}, Cooper and Mubayi~\cite{cooper2017sparse} constructed a 3-uniform, $K^-_4$-free hypergraphs with independence number at most $2n/\sqrt{\Delta}$, and thereby showed that forbidding some single triangle is not enough to improve the trivial independence number from the Tur\'an theorem, and thereofore the trivial chromatic number from the Local Lemma.
It would be interesting to determine whether our results (Theorems~\ref{mainthm1} and~\ref{mainthmind}) can be extended to a larger class of $\mathcal{T}'$-free hypergraphs, for some smaller forbidden set $\mathcal{T}'\subsetneq \mathcal{T}$ (where $\mathcal{T}$ is the collection of rank $k$ triangles for some given rank $k$).

A related but more difficult problem than that considered in this paper is to obtain analogous results for \textit{hypergraph DP-colorings}.
The concept of \textit{DP-coloring}, or so called \textit{correspondence colorings} was developed by Dvo{\v{r}}{\'a}k and Postle~\cite{dvovrak2018correspondence} in order to generalize the notion of list coloring on graphs. This concept  was later generalized to hypegraphs due to the work of Bernshteyn and Kostochka~\cite{bernshteyn2019dp}.
For a detailed definition of hypergraph DP-colorings, we refer interested readers to \cite{bernshteyn2019dp}.
Unfortunately, our approach in this paper does not readily generalize to DP-colorings, and we believe new ideas are needed.
Intuitively speaking, when our approach moves to DP-colorings, the major new challenge is that the `hyperedge shrinking' trick we employed all the time is not applicable; indeed, applying such `shrinkage' might generate a set of forbidden correspondence on edges, which is no longer a hypergraph matching, and thus no longer forms an instantce of DP-coloring.
Moreover, unlike list colorings where the random events always keep independence among different colors, there is no guarantee of such independence in DP-colorings, which certainly creates more technical difficulties in concentration analysis.

redpajama_set_name: RedPajamaArXiv