Triangle-Free Coloring in LOCAL via Resilient Lovász Local Lemma

Triangle-Free Coloring in LOCAL via Resilient Lovász Local Lemma Peter Davies-Peck, Xusheng Zhang August 14, 2026

arXiv:2608.13357v1 [cs.DC] 13 Aug 2026

Abstract The Lovász Local Lemma (LLL) is a probabilistic tool that has been shown to be of central importance in the study of distributed algorithms. For example, the constructive LLL is known to be complete for the class of locally-checkable labeling problems with o(log n) randomized complexities in the LOCAL model. One classic application of the LLL is in coloring graphs with some sparse structure, such as triangle-free graphs. Trianglefree coloring therefore serves as a benchmark problem for techniques for sublogarithmic randomized distributed algorithms. The state-of-the-art distributed triangle-free coloring algorithm of Pettie and Su [ICALP 1 2013, Information and Computation 2015] uses ∆ k colors (where k can be up to ( 4 − ε) ln ∆) ∗ and consists of O(k + log n) applications of the distributed LLL. However, the distributed LLL is itself a difficult problem; despite significant study, the fastest algorithms known require O(log∆ n) or O( log∆∆ ) + logO(1) log n rounds, and no logo(1) n-round algorithms exist except for restrictive special cases or graph classes such as trees. These LLL applications therefore dominate the round complexity of the algorithm. In this work, we adapt the Pettie-Su’s algorithm so that the resulting LLL instances can be solved in logO(1) log n rounds, by employing the ‘resilience’ definition of Davies [SODA 2023]. This gives an O(k) + logO(1) log n complexity (since the LLL is not needed when k = logω(1) log n), essentially causing the LLL steps to no longer be the bottleneck of the algorithm. As a corollary we obtain the first logO(1) log n-round algorithms for coloring triangle-free graphs with o(∆) colors. The same framework also yields a companion girth-5 algorithm, using (1 + ε)∆/ ln ∆ colors in O(k) + logO(1) log n rounds, matching the best known existential upper bound for the number of colors. The LLL instances we use are among the most difficult for which efficient LOCAL algorithms have been shown, and we hope that this sheds further light on the solvability of the distributed LLL and may lead to further efficient applications.

Acknowledgements and AI Disclosure This work is supported by EPSRC New Investigator Award UKRI155 “Distributed Lovász Local Lemma”. Codex was used to assist with language editing and LATEX typing. The tool affected the presentation of the manuscript text and source formatting. The authors take full responsibility for the content of this work.

1

Introduction

Graph coloring in the LOCAL model is one of the benchmark symmetry-breaking problems in distributed graph algorithms. In the LOCAL model, each vertex is a processor, and in each synchronous round it can exchange arbitrarily large messages with its neighbors; consequently, an r-round algorithm can use only the information contained in the radius-r neighborhood of 1

each vertex; we refer to Section 2 for the formal setup. Linial’s foundational work [27] established this model as a clean way to study locality without conflating it with bandwidth limits or local computation costs. For general graphs of maximum degree ∆, much of the literature has focused on (∆ + 1)-coloring and related degree-plus-one list-coloring variants. This target is optimal in general: complete graphs and odd cycles require ∆ + 1 colors. There is a long line of literature on (∆ + 1)-coloring algorithms, culminating in extremely fast shattering-based algorithms [24, 2, 21, 8, 18]. Sparse graph classes raise a different question: can one exploit additional structure not merely to color quickly, but also to asymptotically beat the trivial (∆ + 1) palette size? Triangle-free graphs are among the cleanest examples of this phenomenon. On the existential side, the best current bound on the number of colors possible is (1 + o(1))∆/ ln ∆ [28, 4]. On the distributed side, however, the best near-optimal results still stem from the iterative palette-reduction framework of [30]. That framework achieves a ∆ k coloring, where k can be ∗ 1 up to ( 4 − ε) ln ∆, and consists of O(k + log n) randomized phases. If ∆ > (ln n)Θε (1) , then those phases succeed with high probability, and so the overall round complexity is O(k + log∗ n). However, for lower ∆, an application of the distributed LLL is required to fix the randomness for those phases. If one plugs in the best currently-known distributed LLL algorithms, therefore, one gets a round complexity of • O(log n) using the LLL algorithm of Chung, Pettie, and Su [10, Theorem 9]; O(1) k∆ log n) = O(∆) + logO(1) log n using the LLL algorithm of Davies [11]. • O( log ∆ + k log

Our contribution is to adapt the framework to give LLL instances that can be solved in log log n rounds, thereby obtaining an O(k) + logO(1) log n-round algorithm. For the regime ∆ = logε n with constant ε ∈ (0, 1), which is the most difficult regime for the LLL, this represents a nearly exponential improvement in round complexity. O(1)

1.1

Main results.

Theorem 1. There is a distributed algorithm in the LOCAL model that, for any ε > 0, any ∆ = Ωε (1), and any k ≤ ( 14 − ε) ln ∆, with high probability colors every triangle-free graph of maximum degree ∆ using ∆/k colors in Oε (k) + logO(1) log n rounds. By applying Theorem 1 with k = min{logO(1) log n, 15 ln ∆}, we can color triangle-free graphs with some o(∆) number of colors very quickly: Corollary 2. There is a distributed algorithm in the LOCAL model that, with high probability, colors every triangle-free graph of maximum degree ∆ using o(∆) colors in logO(1) log n rounds. This complexity is polynomially close to tight, since there is an Ω(log log n) lower bound even for the problem of coloring constant-degree trees with ∆ or fewer colors [6]. The number of colors matches the best known for any (non-trivial, i.e. o(n)-round) distributed algorithm. Molloy [28] showed that triangle-free graphs can be (1 + o(1)) ln∆∆ -colored, but it is unknown whether this can be done in a distributed fashion. For girth-5 graphs, however, this (1 + o(1))∆/ ln ∆ result is achievable with the same round complexity: Theorem 3. There is a distributed algorithm in the LOCAL model that, for any ε > 0, any ∆ = Ωε (1), and any k ≤ (1 − ε) ln ∆, with high probability, (1 + o(1))∆/k-colors every girth-5 graph of maximum degree ∆ in Oε (k) + logO(1) log n rounds. Throughout the paper, the notation ∆ = Ωε (1) means that after fixing ε, we assume ∆ ≥ ∆ε for a sufficiently large threshold ∆ε depending only on ε. and we treat ε as an arbitrarily small but fixed positive constant. We expect that our arguments could also be adapted to the setting where ε = ε(∆) tends to 0 sufficiently slowly, by tracking these dependencies more explicitly. 2

Both the triangle-free and girth-5 results extend to the corresponding list-coloring setting. Indeed, the algorithms and proofs are phrased entirely in terms of evolving palettes and their sizes. Thus the same running times hold when each vertex u is given an arbitrary initial palette P0 (u) of size at least ∆/k. Our analysis is based on the following general idea, which is not a formal or well-defined statement but provides the intuition for the approach. Informal Claim. LLL instances in which the bad events are that some quantities are too far from their expectation, where • the quantities are primarily influenced by nodes’ immediate neighborhoods, and • we can tolerate O( ∆ r ) additive error in the quantities, should be O(r)-resilient and therefore O(r) + logO(1) log n-round solvable by the algorithm of [11]. Coloring applications of the LLL often have properties along these lines, since error in concentration bounds can often be offset by allowing a corresponding number of additional colors. For the triangle-free coloring algorithm of [30], for instance, if we allow an additional additive O( poly∆log ∆ ) error in the bounds proven on degree, palette size, and color degree throughout the algorithm, then we cannot show that degrees drop below O( poly∆log ∆ ). We therefore require O( poly∆log ∆ ) additional colors to color the remaining uncolored graph, but this is negligible in the overall color bound. The potential applicability of this idea is not limited to coloring problems: problems requiring that the frequencies of certain output labels in a node’s vicinity are within certain thresholds, while easier than general LLL instances, constitute the majority of concrete applications of the LLL in distributed algorithms. As we will see, though, incorporating the bad events in the LLL instances for triangle-free coloring into the resilience framework of [11] is highly nontrivial and requires substantial changes to the analysis and some technical changes to the algorithm of [30].

1.2

Technical Overview

Our starting point is the iterative coloring process of [30]. In each round, that algorithm maintains a palette for every uncolored vertex and analyzes how palette sizes and average c-degrees evolve under a random selection process, following the average-c-degree viewpoint already used in earlier triangle-free coloring analyses such as [22], where a c-degree counts how many neighbors can still have color c in their palette. Our contribution is to speed up the distributed LLL step that resolves the local failures left by this random step. For that purpose, we analyze the resulting LLL instances using the resilient partition framework of [11]. Informally, resilience means that a bad event stays unlikely even if one adversarially chooses a subset of variables from a single part of a partition to be resampled, while the new values themselves come from fresh randomness; see Section 2.2.2 for the formal definition. In that framework, the LLL instance is equipped with a partition Φ = {Φ1 , . . . , Φr } of the bad events, and the algorithm processes one part Φj at a time. The partition is useful only when each event has few neighbors in each part, because then only few neighboring events can sample and possibly revert simultaneously in any one step, which keeps the number of possible reversion patterns under control and makes resilience provable. Our technical goal is to prove that the bad events arising from the coloring process are resilient with respect to a suitable partition. The main complication is that these bad events involve the c-degrees of one-hop neighbors, so in the resilience proof one must control how 3

resampling a single part propagates through two-hop neighborhoods. On top of this, triangle-free graphs still have dependencies that mean that individual c-degree does not decrease ‘smoothly’, so the analysis here and in [30] instead analyzes the average c-degree of a node’s neighbors. For girth-5 graphs, the same resilient interface leads to a shorter argument, because one can track palette-size, c-degree, and residual-degree events for each node directly and thereby recover the sharper constant-1 regime. The key new object for our setting is therefore a color-balanced partition for the active random choices of the coloring process; see Section 3.2 for the formal definition. It is chosen so that for each vertex u, each color c, and each part Φj , the vertices in Φj contribute only a 1/r-share of the c-degree of u, up to constant factors. This is the extra control needed for the color-by-color failure modes of the coloring process. Once the corresponding LLL instance is shown to be resilient with respect to this partition, the available distributed LLL algorithm yields an O(r) + logO(1) log n-round algorithm, where r is the number of parts.

1.3

Previous work.

For sparse coloring, classical existential work already shows that triangle-free and girth-5 graphs admit far fewer than ∆ + 1 colors. Ajtai, Komlós, and Szemerédi initiated the triangle-free line with the bound χ(G) = O(∆/ ln ∆) [1], Johansson later proved the corresponding asymptotic list-coloring bound [23], Kim established the sharper (1 + o(1))∆/ ln ∆ asymptotic for girth-5 graphs [25], and the best current target for the number of colors in triangle-free graphs is now (1 + o(1))∆/ ln ∆ [28, 4]. Classical constructions of Kostochka and Bollobás show that, even for graphs of arbitrarily large girth, the chromatic number can be as large as Ω(∆/ log ∆) [26, 5], so the ∆/ ln ∆ scale is best possible up to a constant factor. For distributed algorithms, Grable and Panconesi gave efficient randomized Brooks–Vizing colorings for triangle-free and girth-5 graphs under additional regularity and degree assumptions [17], and Barenboim, Elkin, Pettie, and Schneider studied fast distributed coloring more broadly in related sparse settings, including trees and sufficiently high-girth graphs [3]. The framework of [30] gives distributed algorithms achieving both the triangle-free bound (4 + o(1))∆/ ln ∆ and the girth-5 bound (1 + o(1))∆/ ln ∆. Our work should be viewed as improving the distributed complexity of that framework while retaining the same asymptotic color guarantees in the two settings. In our setting, the distributed Lovász Local Lemma is the subroutine that handles the local bad events caused by the random coloring step. More broadly, however, distributed LLL has become a central benchmark problem in the LOCAL model; for example, it is the canonical complete problem for a major randomized LOCAL complexity class on bounded-degree graphs [9]. The constructive resampling framework of [29] already implies a distributed algorithm via parallel resampling, and Chung, Pettie, and Su gave the first explicit distributed treatment, including O(log n)-round algorithms under standard and strengthened criteria as well as an Ω(log∗ n) lower bound [10]. Brandt et al. later proved an Ω(log log n) lower bound even under much stronger criteria [6]. Fischer and Ghaffari introduced the shattering-based sublogarithmic approach [13], which, when complemented by later distributed derandomization and modern network-decomposition tools [16, 31, 15], yielded an O(d2 +logO(1) log n)-round algorithm. Davies [11] improved this round complexity for the general LLL to O( logd d + logO(1) log n), and also developed the resilient partition framework, which underlies our use. There exists an O(log log n)-round LLL algorithm on trees [7], an algorithm with O(log log n)round average-case complexity [12], and logO(1) log n-round algorithms for certain special cases of the LLL that exhibit particularly nice structures (e.g. [20, 19]), such as that bad events can be avoided based on subsets of their variables regardless of the values taken by the other variables. However, no log1−Ω(1) n-round worst-case complexity algorithm for the general LLL has yet been found. In this work we aim to widen the types of LLL instances for which logO(1) log n algorithms are known; the instances we use are more complex than previous efficiently-solvable special cases, and are the first special cases to be directly shown to fit the r-resilience framework of [11] with 4

r = ω(1). Previously, r-resilience with r = ω(1) was only used by [11] as a stepping-stone to the general LLL result.

2

Preliminaries

2.1

Model

We work in the randomized LOCAL model on an n-vertex graph G = (V, E) of maximum degree ∆. Each vertex v ∈ V hosts a processor with a unique identifier. Communication proceeds in synchronous rounds, and in each round every vertex may perform arbitrary local computation, exchange arbitrarily large messages with its neighbors, and sample fresh private random bits. At the end of the computation, each vertex must output its own part of the global solution. Thus, after r rounds, the state of a vertex is determined entirely by its radius-r neighborhood together with the identifiers, local inputs, and random choices revealed there. The complexity measure is the number of communication rounds. In particular, when we say that an algorithm colors G in t rounds, we mean that after t rounds every vertex outputs a color and the resulting labeling is a proper coloring with the claimed guarantee. All success probabilities are taken over the internal randomness of the algorithm.

2.2

Local Lemma Instances and the Polynomially-Weakened Regime

An LLL instance consists of a family X of bad events defined on a family V of mutually independent random variables. For each event A ∈ X , let var(A) ⊆ V denote the variables on which A depends. The dependency graph GX has vertex set X , with two events adjacent whenever their variable sets intersect. Its maximum degree is the dependency parameter d of the instance. In the symmetric setting, p denotes a common upper bound on the bad-event probabilities. When convenient, we write an LLL instance as a tuple L = (X , V). 2.2.1

The polynomially-weakened criterion.

The classical symmetric LLL criterion is epd ≤ 1, where p is the maximum bad-event probability and d is the maximum dependency degree. In this paper, we work throughout in the more restrictive regime p(ed)c < 1 for a large constant c. Despite the terminology, this polynomiallyweakened criterion is stricter than the traditional LLL threshold. We will use two algorithms for this regime, depending on additional structure. 2.2.2

An algorithm for resilient instances.

We use the resilient local lemma framework of [11]. Following the notation and definitions there, we work with two independent copies V 1 , V 2 of the variable family V and an r-partition Φ = {Φ1 , . . . , Φr } of the events, that is, a partition into r parts. Since, in our applications, both events and variables will be explicitly associated with a particular node of the input graph (for example, events will be things such as “node v’s degree reduces sufficiently”, and variables will be things such as “the color picked by node v”), we will sometimes abuse notation by considering Φ to be a partition of the variables; this should be understood to mean that the variables in Φi are those associated with the nodes/events in Φi . This is to avoid having to use the variable allocation notation in [11]. For an event A ∈ X and a set of variables S ⊆ V, let AS denote the event obtained by evaluating A using the second sample on the variables in S and the first sample on all other variables. Define n h i o [ A′ = PV 2 AS ≥ d−10 , i≤r, S⊆Φi

5

where d is the dependency parameter of the instance. The instance is called Φ-resilient if for every event A, PV 1 [A′ ] ≤ d−30 . Intuitively, Φ-resilience means that even if one adversarially chooses an arbitrary subset of a single partition part to switch from the first sample to the second, no bad event becomes likely. We say that an instance is r-resilient if it admits an r-partition Φ for which it is Φ-resilient. This is an additional structural assumption on top of the polynomially-weakened condition above; in particular, resilience is stricter than the polynomially-weakened condition alone. Theorem 4 (Davies [11], Theorem 12). Any r-resilient LLL instance, provided with an rpartition Φ of its variables for which it is Φ-resilient, can be solved in O(r + logO(1) log n) rounds in randomized LOCAL, with high probability.

2.3

Coloring the Remaining Graph

After coloring the majority of the graph using the adapted framework of [30] coupled with our analysis of the resulting LLL instances, we will show that the maximum degree dstop of the remaining uncolored graph is o( log∆∆ ) and then color it using O(dstop ) fresh colors. To do so, we can use the algorithm of Chang, Li, and Pettie [8] running in O(log∗ n + Det(poly log n) rounds, where Det(n′ ) is the deterministic complexity of (deg+1)-list coloring on n′ -vertex graphs. Using the current fastest such deterministic algorithm, of [14], gives a round complexity of Õ(log5/3 log n). Theorem 5 (∆ + 1-list-coloring [8, 14]). Any graph of maximum degree ∆, equipped with lists of size at least ∆ + 1 at each vertex, can be list-colored in Õ(log5/3 log n) rounds in randomized LOCAL, succeeding with high probability.

3

Triangle-Free Graphs

This section proves the triangle-free case through a round-based coloring framework. In each round, uncolored vertices make local random choices, conflicts are removed, and palettes are updated; we formulate each round as an LLL instance whose purpose is to preserve some round-based invariants. This application of the resilient LLL algorithm, however, is not automatic. There are several layers of difficulty. In each round, the iterative algorithm must maintain three invariants, so we must define three corresponding families of bad events and avoid them simultaneously. Moreover, these events depend on not only by their one-hop neighbors but also by their twohop neighbors. In triangle-free graphs, these two-hop effects do not directly decompose into independent contributions to different one-hop neighbors, which makes the analysis more delicate. Furthermore, to apply the resilient Lovász Local Lemma algorithm, the resilience condition must hold uniformly for every subset S of variables inside any given part of the partition. The concentration bounds available to us are not strong enough to support a naive union bound over all such S, so instead for each bad event we identify a “symptom event” that can be triggered by any choice of S. What makes the application even harder is that all of these requirements must be handled by one and the same partition, and such a partition also needs to be constructed fast. The rest of the section addresses these issues. Section 3.1 defines the round-i instance, Section 3.2 gives the partition tool used by the resilient solver, Section 3.3 presents the iterative algorithm, Section 3.4 specifies the bad events and parameter schedule, and Section 3.5 assembles the lemmas to prove Theorem 1. Throughout Sections 3 and 4, all asymptotic inequalities are interpreted for sufficiently large ∆ = Ωε (1); equivalently, after fixing ε, we assume ∆ ≥ ∆ε .

6

3.1

The Round-i LLL Instance

We now make the first step of the roadmap precise by considering one generic round i and describing exactly what the local LLL solver receives. The process is monotone: once a vertex is colored, it remains colored and plays no role in later rounds. Therefore, round i only sees the vertices that are still uncolored after rounds 1, . . . , i − 1; we call them active at the start of round i. Fix an iteration i ≥ 1. Let Gi−1 be the graph induced by vertices that are still uncolored after rounds 1, . . . , i − 1. Let Pi−1 (u) be the palette of an active vertex u, and let Ni−1 (u) be its residual neighborhood. For any color c, define the color-specific neighborhood Ni−1,c (u) = {v ∈ Ni−1 (u) : c ∈ Pi−1 (v)}. We call the vertices in Ni−1,c (u) the c-neighbors of u, and call |Ni−1,c (u)| the corresponding c-degree. The local random step is given in Algorithm 1. Algorithm 1 Select(u, πi , βi ) 1: for all c ∈ Pi−1 (u) independently do 2: include c in Seli (u) with probability πi 3: rc ← βi /(1 − πi )|Ni−1,c (u)| 4: if rc ≤ 1 then 5: include c in Ki (u) with probability rc 6: return (Seli (u), Ki (u)) Here Seli (u) is the set of colors tentatively selected by u, while Ki (u) is the set of colors kept available for u before conflicts are removed. For each active vertex u, define the round-i random variable Xi (u) := (Seli (u), Ki (u)). The variable family of round i is therefore Vi = {Xi (u) : u ∈ V (Gi−1 )}. Each variable Xi (u) is sampled independently at its own vertex by Algorithm 1. Let θi = (πi , βi , αi , pi , p′i , ti , t′i , di , d′i ) denote the deterministic parameter vector used in round i. We treat these quantities as part of the round-i LLL input, even though their exact formulas are only specified later in Section 3.4. With Bi denoting the local bad events also specified later, the round-i local LLL instance is Li = (Bi , Vi , θi ).

3.2

r-Partitions with Degree Parameters

The resilient LLL theorem from Section 2.2.2 requires an r-partition of the event family. Since our events and variables are both indexed by vertices, such a partition is equivalently a partition of the vertex set, and can also be considered a partition of the variable set. In [11], the partitions that are used for the general LLL result are chosen to have an upper bound on node degree within each part of the partition. Here we need slightly more complex partitions that also have an upper bound on c-degrees. We now specify formally what we require from these partitions. We will use c-degree as defined in Section 3.1, but to avoid tying the following Definition 6 to a specific round of the algorithm we will define notation without the subscript i. Let H be a graph on a vertex set U , and suppose that each u ∈ U has a palette P (u). For a color c, write Nc (u) = {v ∈ NH (u) : c ∈ P (v)}. The useful partitions are those in which no single part captures too much of either kind of degree: for every vertex u, each part should contain only an O(1/r)-share of the neighbors of u and of the c-neighbors of u for each color c. 7

Definition 6. Let d, t > 0, and let Φ = {Φ1 , . . . , Φr } be a partition of U . We call Φ a (color-balanced) r-partition with parameters d and t if: 1. for every u ∈ U and every part Φj , one has |NH (u) ∩ Φj | ≤ 100d/r; 2. for every u ∈ U , every color c ∈ P (u), and every part Φj , one has |Nc (u) ∩ Φj | ≤ 100t/r. Here d is a max-degree upper bound and t is a c-degree upper bound. Thus the first condition controls max-degree contributions, and the second controls c-degree contributions. Theorem 7 (r-partition with degree parameters). For every fixed a > 0, there is b > 0 such that the following holds. Assume ∆ ≤ (log n)a , let H be a graph on at most n vertices with maximum degree at most ∆, and suppose that |P (u)| ≤ ∆ for every u ∈ U . Set r = (log ∆)20 , rounded to an integer if necessary, and let 0 < d ≤ ∆ and t > 0. Suppose that |NH (u)| ≤ d

and

|Nc (u)| ≤ t

for every u ∈ U and every color c ∈ P (u). Suppose also that d ≥ (log ∆)b

and

t ≥ (log ∆)b .

Then, with high probability, the vertex set U , equivalently the variables indexed by U , admits an r-partition with parameters d and t. Such a partition can be constructed in logO(1) log n rounds in the LOCAL model. We construct the partition through an auxiliary LLL instance: each vertex in U chooses a part, the bad events are the violations of the two conditions from the definition, and these bad events are 1-resilient, so the resilient LLL algorithm from Section 2.2.2 applies. Proof. For each vertex v ∈ U , introduce an independent variable Yv , uniformly distributed on [r]. The value Yv = j means that v is put into the part Φj . For an outcome Y , write Φj (Y ) = {v ∈ U : Yv = j}. We define an auxiliary LLL instance whose bad events are Au = {∃j ∈ [r] such that |NH (u) ∩ Φj (Y )| > 100d/r} for each u ∈ U , and Bu,c = {∃j ∈ [r] such that |Nc (u) ∩ Φj (Y )| > 100t/r} for each u ∈ U and color c ∈ P (u). Avoiding all these events is exactly the definition of an r-partition with parameters d and t. We first bound the bad-event probabilities. For a fixed part j, the random variable |NH (u) ∩ Φj (Y )| is binomial with mean at most d/r. By Chernoff’s bound, P [|NH (u) ∩ Φj (Y )| > 100d/r] ≤ exp(−30d/r). Taking a union bound over j ∈ [r], we get P[Au ] ≤ r exp(−30d/r) ≤ ∆−200 after choosing b large enough. Similarly, for a fixed part j, the random variable |Nc (u) ∩ Φj (Y )| has mean at most t/r, so Chernoff’s bound and a union bound over the parts give P[Bu,c ] ≤ r exp(−30t/r) ≤ ∆−200 . Next we count dependencies. Both Au and Bu,c use only variables Yv with v ∈ NH (u). If one of these events shares a variable with Ax or Bx,c′ , then x is within distance two of u in H. There are at most 1 + ∆2 such choices of x. For each x, there is one event Ax and at most |P (x)| ≤ ∆ events Bx,c′ . Thus the dependency degree of the auxiliary instance is at most (1 + ∆2 )(1 + ∆) ≤ 4∆3 . Therefore p(e · 4∆3 )32 < 1 for the probability bound p = ∆−200 . 8

It remains to check 1-resilience of this auxiliary instance. The partition used here is not the output partition Φ(Y ) that we are trying to construct. Since we only need 1-resilience, we use the trivial one-part partition of the variables {Yv : v ∈ U }. Thus, in the definition of resilience, S may be any subset of these variables: the variables in S are read from the second sample, and all other variables are read from the first sample. Fix one bad event, and write it in the common form E = {∃j ∈ [r] such that |W ∩ Φj (Y )| > T } , where either W = NH (u) and T = 100d/r, or W = Nc (u) and T = 100t/r. In both cases, |W |/r ≤ T /100. Let Y 1 , Y 2 be the two samples from the definition of resilience, and let S be any subset of variables. In the mixed event E S , the variables outside S keep their first-sample values and the variables in S use their second-sample values. If the first sample satisfies |W ∩ Φj (Y 1 )| ≤ T /2

for every j ∈ [r],

then, for every choice of S, the second sample must contribute more than T /2 vertices v ∈ W whose variable Yv belongs to S to one part in order for E S to occur. By the same Chernoff bound and a union bound over the r parts, this has probability at most ∆−200 , after increasing b if necessary. Since the dependency degree is at most 4∆3 , this is at most (4∆3 )−10 , which is the D−10 threshold from the resilience definition (Section 2.2.2) with dependency parameter D = 4∆3 . Therefore the exceptional first-sample event in the definition of resilience can occur only if |W ∩ Φj (Y 1 )| > T /2

for some j ∈ [r].

The probability of this event is at most ∆−200 , again by the same Chernoff bound and a union bound over the r parts. Since the dependency degree is at most 4∆3 , this is at most (4∆3 )−30 , which is the D−30 threshold from the resilience definition with dependency parameter D = 4∆3 . Hence every bad event in the auxiliary instance is 1-resilient. The resilient LLL algorithm from Theorem 4, applied with this one-part variable partition, finds an assignment avoiding all Au and Bu,c with high probability in logO(1) log n rounds. Let Φ = {Φ1 , . . . , Φr }, where Φj = {v : Yv = j}. Since no bad event occurs, Φ is an r-partition with parameters d and t.

3.3

The Iterative Algorithm

Recall from Section 3.1 that the active vertices at the start of round i are exactly the vertices of Gi−1 . Such a vertex u has a palette Pi−1 (u), a residual neighborhood Ni−1 (u), and the color-specific neighborhoods Ni−1,c (u). The round-i LLL instance defined there contains the local choices Seli (u) and Ki (u) used by the update below. Algorithm 3 presents this coloring framework. For i ≥ 0, we write θi = (πi , βi , αi , pi , p′i , ti , t′i , di , d′i ) for the deterministic parameter vector. The sequence {θi }i≥0 is part of the input to Algorithm 3 and is fixed before the algorithm starts. In each iteration, it constructs the round-i LLL instance Li , invokes the SolveRoundLLL subroutine in Algorithm 2, and obtains a realization Xi avoiding all events of Bi . Once Xi is fixed, the algorithm uses the resulting values of Seli (u) and Ki (u) for the deterministic update. The stopping rule is d′i−1 > dstop , where dstop = ∆/(log ∆)6 : as long as this holds, another iteration is performed; once it fails, Theorem 5 from Section 2 colors the current remaining graph Gi−1 using dstop + 1 fresh colors. 9

Algorithm 2 SolveRoundLLL(i, r, Li ) 1: Let Li = (Bi , Vi , θi ) Output: a realization of Vi in which no event of Bi occurs 2: compute an r-partition from Theorem 7 for the active variables in Vi , with max-degree parameter min{d′i−1 , ∆} and c-degree parameter 2ti−1 3: run the algorithm from Theorem 4 on Li 4: return the resulting realization of Vi Algorithm 3 IterativeColoringFramework(G, {θi }i≥0 , r) 1: Set G0 = G and initialize the palettes P0 (u) to be of p0 colors for every vertex u 2: dstop ← ∆/(log ∆)6 3: i ← 1 4: while d′i−1 > dstop do 5: construct the round-i LLL instance Li 6: Xi ← SolveRoundLLL(i, r, Li ) 7: for all vertices u ∈ V (Gi−1 ) do 8: Pei (u) ← Ki (u) \ Seli (Ni−1 (u)) 9: if Seli (u) ∩ Pei (u) ̸= ∅ then 10: color u with an arbitrary color in Seli (u) ∩ Pei (u) 11: let Ui be the vertices of Gi−1 still uncolored after the round-i coloring decisions 12: for all vertices u ∈ Ui do bi,c (u) ← {v ∈ Ui ∩ Ni−1 (u) : c ∈ Pei (v)} for every c ∈ Pei (u) 13: N b bi,c (u)| ≤ 2ti } 14: Pi (u) ← {c ∈ Pei (u) : |N ′ 15: if |Pbi (u)| > pi then 16: set Pi (u) to an arbitrary subset of Pbi (u) of size exactly p′i 17: else 18: set Pi (u) ← Pbi (u) 19: let Gi be the graph induced by Ui 20: i←i+1 21: color the remaining graph Gi−1 using Theorem 5 with dstop + 1 fresh colors Recall from Section 3.1 that Xi (u) = (Seli (u), Ki (u)) for each active vertex u, so Xi records all local round-i choices. After Xi has been fixed, the deterministic update in Algorithm 3 first forms Pei (u) = Ki (u) \ Seli (Ni−1 (u)), where Seli (Ni−1 (u)) = v∈Ni−1 (u) Seli (v). A vertex is colored if one of its selected colors remains in this tentative palette. The set Ui consists of the vertices left uncolored after this decision. bi,c (u) = {v ∈ Ui ∩ Ni−1 (u) : For u ∈ Ui , the algorithm forms the color-specific neighborhoods N e e bi,c (u)| > 2ti ; the c ∈ Pi (v)}. By filtering, we mean deleting from Pi (u) every color c with |N resulting palette is Pbi (u). The algorithm then retains at most p′i of these filtered colors. After this truncation, Pi (u) is the retained palette, while Pbi (u) denotes the filtered palette before truncation. Also, Ni,c (u) denotes the residual neighbors of u whose retained palette still contains c. We now unfold the subroutine SolveRoundLLL in Algorithm 2, which returns a realization Xi of the round-i variables avoiding all bad events in Bi . It takes the LLL instance Li as input and constructs an r-partition via Theorem 7 with max-degree parameter min{d′i−1 , ∆} and c-degree parameter 2ti−1 , and then runs the algorithm from Theorem 4. After this output Xi is fixed, the remaining update steps in Algorithm 3 are deterministic. The next subsection specifies Bi and the parameters so that avoiding all events in Bi gives S

10

the palette and degree bounds needed for the next round.

3.4

Bad Events, Parameters, and the Round Invariant

We now specify the concrete objects used in Li . For round i ≥ 1, the prescribed parameter vector is θi = (πi , βi , αi , pi , p′i , ti , t′i , di , d′i ). The parameters πi and βi control sampling and color retention, while αi is the ideal attenuation factor. For pi , ti , di and their primed versions, we use the following convention throughout the section: the unprimed quantities are the ideal round-i values, and the primed quantities are analysis thresholds with slack. Thus pi is the ideal retained palette size, whereas p′i is the slightly smaller palette-size threshold used for truncation and for the padded averages; ti is the ideal scale for the average c-degree, whereas t′i is the slightly larger upper bound for the padded average c-degree in the invariant; and di is the ideal upper bound for residual degree, whereas d′i is the slightly larger residual-degree bound promised after round i. We now fix the parameter schedule explicitly; these are the values of θi supplied to Algorithm 3 and to the round-i instance Li . Fix a small constant ε > 0, choose a parameter k with 1 ≤ k ≤ (1 − ε) ln ∆/4, set ∆ ∆ p0 = − − 1, k (log ∆)6 Since k ≤ (1 − ε) ln ∆/4, we have k/(log ∆)6 = o(1) and k/∆ = o(1). Hence p0 =

k k ∆ 1− − 6 k (log ∆) ∆ 



= (1 − o(1))

∆ . k

We also define two exponent margins ε1 = 1 −

2ε 4k − , ln ∆ 3

ε2 = 1 −

4k ε − . ln ∆ 3

Thus ε1 ≥ ε/3 and ε2 ≥ 2ε/3. The constant K sets the sampling scale, δ sets the multiplicative slack between ideal and primed quantities, and T is the lower floor in the ideal average c-degree recurrence. We set 4 1 K= , δ= , T = ∆ε1 /3 . ε log4 ∆ Initialize p′0 = p0 and t0 = t′0 = d0 = d′0 = ∆. For i ≥ 1, set πi = and

βi = (1 − πi )2ti−1 , αi = (1 − πi )(1−(1+2δ)

i−1 /2)p′ i

1 2Kti−1 + 1

pi = βi pi−1 , ,

,

p′i = (1 − δ/7)i pi ,

ti = max{αi βi ti−1 , T },

t′i = (1 + 2δ)i ti .

For the degree upper bounds, we set ∆ dstop = , (log ∆)6

dstop di = max αi di−1 , (1 + δ)i 



,

d′i = (1 + δ)i di

for i ≥ 1. Given a round-i outcome, we use the surviving vertex set Ui and the tentative palette Pei (u) produced by Algorithm 3. For each color c ∈ Pi−1 (u), define ei,c (u) = {x ∈ Ni−1,c (u) : c ∈ Pei (x)}. N

11

Write ni (u) =

X 1 |Ni,c (u)|, |Pi (u)| c∈P (u)

e i (u) = n

i

1 |Pei (u)|

X

|Ni,c (u)|.

ei (u) c∈P

If one of these denominators is zero, we interpret the corresponding average as 0. We also set |Pi (u)| λi (u) = min 1, p′i (

and

( ) |Pei (u)| e λi (u) = min 1, , ′

)

,

pi

Di (u) = λi (u)ni (u) + (1 − λi (u))2ti ,

e i (u)n e i (u))2ti . e i (u) = λ e i (u) + (1 − λ D

The round event Fi (u) is the statement that: 1. Di (u) ≤ t′i , 2. |Ni (u)| ≤ d′i . Let Fi be the event that Fi (u) holds for every vertex in Ui . We refer to Fi as the round-i invariant event. The round-i bad-event family Bi contains three types of local failures, with r = (log ∆)20 as in Theorem 7: Q+ i (u) := Ri+ (u) :=



  200  δ  e 1− |Pi (u)| < |Pi−1 (u)|βi 1 − ,

8

 

|Ni,c (u)|



r

δ

> αi 1 +  |P (u)| 3 i−1 c∈Pi−1 (u)   δ 200 X

Mi+ (u) := |Ni (u)| > αi 1 +

3

d′i−1 +

 δ δ  300 βi2 ni−1 (u) + ti−1 + ti−1 + T , 4 r 3  



r



d′i−1 +



∆ r(log ∆)8



.

+ Here Q+ i means that too few colors remain in the tentative palette, Ri (u) means that the + average residual c-degree is too large, and Mi means that the residual degree is too large. When none of these events occurs, the resulting palette and degree estimates imply Fi ; this implication is stated in Lemma 9 below and proved in Section 4. Our Algorithm 3 closely aligns with Variant A of Algorithm 2 in Pettie and Su [30]: it has the same iterative structure, and the parameter vector θi follows the same schedule up to changes in a few constants. There are two substantive differences. First, the round instances are solved by our resilience LLL subroutine in Algorithm 2, so we use modified bad events together with the corresponding entries of θi . Second, instead of switching to their later phase, we stop once the residual degree is low enough and add the events Mi+ (u) to certify that the final low-degree cleanup from Theorem 5 can be applied. We also make the minor bookkeeping change of truncating palettes to simplify the analysis.

3.5

Main Lemmas and Proof of Theorem 1

We now state the three main lemmas needed to conclude the main triangle-free theorem. The first gives a fast solver for each local LLL instance; the second says that eliminating the three bad-event families establishes Fi at the end of round i; and the third says that d′i reaches the final threshold quickly. Together with Fi , this last statement is what makes the residual graph small enough for the final coloring step. Section 4 proves these lemmas. Lemma 8. With the parameter schedule fixed in Section 3.4, for every fixed C > 0, the following holds whenever ∆ ≤ (log n)C . Suppose Fi−1 holds and d′i−1 > dstop . Then, with high probability, Algorithm 2 solves the round-i instance Li in (log log n)O(1) rounds. 12

Lemma 9. With the parameter schedule fixed in Section 3.4, assume Fi−1 holds and d′i−1 > dstop . For any realization Xi of the round-i variables in which no bad event of Bi occurs, the deterministic post-processing step in Algorithm 3 yields Fi . Lemma 10. With the parameter schedule fixed in Section 3.4, d′i reaches the final threshold: there is an integer ℓ = O(k + log log ∆) such that d′ℓ ≤ dstop = ∆/(log ∆)6 .

Proof of Theorem 1. Fix a constant ε > 0 and a parameter k with 1 ≤ k ≤ (1 − ε) ln ∆/4. Let ∆ε be large enough so that all asymptotic inequalities used in the three supporting lemmas hold for every ∆ ≥ ∆ε , and assume ∆ ≥ ∆ε . We first dispose of the genuinely large-degree case. By Pettie and Su [30, Corollary 2], there is a constant C = C(ε) such that, whenever ∆ > (log n)C , the desired ∆/k-coloring is found in O(k + log∗ n) rounds. This is already O(k + (log log n)O(1) ). It remains to consider the range ∆ ≤ (log n)C , where C is fixed. Let ℓ be the first round with d′ℓ ≤ dstop . Lemma 10 gives ℓ = O(k + log log ∆), and since ∆ ≤ (log n)C , this is O(k + (log log n)O(1) ). It is enough to prove that Fi holds for every i ≤ ℓ with high probability. Indeed, if Fℓ holds, then ∆(Gℓ ) = max |Nℓ (u)| ≤ d′ℓ ≤ dstop , u∈Uℓ

so the final residual graph is eligible for Theorem 5 from Section 2. We now prove that Fi holds throughout the process. Before the first iteration, F0 holds deterministically: G0 = G, each initial palette has size p′0 = p0 , every initial c-degree is at most ∆ = t′0 , and |N0 (u)| ≤ ∆ = d′0 for every vertex u. For the induction step, fix 1 ≤ i ≤ ℓ and assume Fi−1 holds at the start of iteration i. By the minimality of ℓ, d′i−1 > dstop . Algorithm 3 constructs Li and calls Algorithm 2. Lemma 8 shows that this call finishes in (log log n)O(1) rounds. Condition on the event that this solver call returns a realization Xi avoiding every bad event of Bi . Once Xi is fixed, Lemma 9 implies that the deterministic update step establishes Fi . Therefore Fi holds after every completed iteration up to ℓ, provided all invoked solvers have succeeded. For success probability, Lemma 8 gives that each of the ℓ calls to Algorithm 2 succeeds with high probability. Since C is fixed, ℓ = O(k + log log ∆) = O(log log n) in this range. A union bound therefore implies that all ℓ calls succeed simultaneously with probability at least 1 − n−c1 for some constant c1 > 1, after decreasing the exponent constant if necessary. Algorithm 3 uses Theorem 5 to color Gℓ in Õ(log5/3 log n) rounds, using dstop + 1 fresh colors, with probability at least 1 − n−c2 for some constant c2 > 1. Taking one final union bound with the iteration-level error probabilities yields an overall success probability of at least 1 − n−c3 for some constant c3 > 1, i.e. w.h.p.. ∆ The main phase uses p0 = ∆ k − (log ∆)6 − 1 colors, so the total number of colors is at most ∆/k. The total number of LOCAL rounds is O(k + (log log n)O(1) ): since ∆ ≤ (log n)C , we have k = O(log log n) and hence ℓ = O(k + log log ∆) = O(log log n). Moreover, Lemma 8 shows that each call to Algorithm 2 takes (log log n)O(1) rounds. Therefore the ℓ per-iteration solver calls, together with the O(1) rounds of deterministic steps in each iteration, contribute only (log log n)O(1) rounds in total.

4

Proofs of the Triangle-Free Lemmas

This section provides the deferred proofs of the three lemmas from Section 3: Section 4.1 proves Lemma 10, Section 4.2 proves Lemma 8, Section 4.3 proves the resilience propositions used in the instance proof, and Section 4.4 proves Lemma 9. 13

4.1

Numerical Parameter Bounds

We prove a more detailed numerical theorem, from which Lemma 10 follows directly. Theorem 11. Define the stopping time τend := inf{i ≥ 1 : d′i−1 ≤ dstop } ∈ N∪{∞}. Assume r = (log ∆)20 and that ∆ ≥ ∆ε . For the parameter choices fixed in Section 3.4, τend = O(k+log log ∆). Moreover, for every i with 1 ≤ i < τend , βi ≥ e−1/K ,  200  δ  1− ≥ p′i , p′i−1 βi 1 − 8 r  δ 200 ′ ∆ αi 1 + d′i−1 + ≤ d′i , di−1 + 3 r r(log ∆)8 p′i ≥ T (log ∆)6 . Proof. For every i, the inequality ln(1 − x) ≥ −x/(1 − x) for 0 < x < 1, applied with x = 1/(2Kti−1 + 1), gives 

βi = 1 −

1

2ti−1

2Kti−1 + 1

2ti−1 ≥ exp − 2Kti−1 



≥ e−1/K .

Let si = ti /pi . Let τ = min{i ≥ 0 : pi ≥ ti }. Set C := 4Ke11/K . Fix i ≤ min{τ, 2k/C}. Since k ≤ (1−ε) ln ∆/4 and C is fixed, i = O(log ∆), so p′i = (1 − o(1))pi and (1 + 2δ)i−1 = 1 + o(1). Also βi ≥ e−1/K . Therefore 

αi = 1 −

1

(1−(1+2δ)i−1 /2)p′

i

2Kti−1 + 1



≤ exp −

(1 − o(1))pi 4Kti−1





≤ exp −(1 − o(1))C

pi−1 . ti−1 

Hence, for every i < min{τ, 2k/C}, ti (1 − o(1))C si = = αi si−1 ≤ si−1 exp − pi si−1 



.

Now let u := k 2/3 . While si−1 ≥ u, set wi := (1 − o(1))C/si−1 = o(1). Then si ≤ si−1 e−wi ≤ si−1 1 − (1 − o(1))wi ≤ si−1 − (1 − o(1))C.

k−u Thus, the number of steps needed to go from s0 = (1 + o(1))k down to u is at most (1−o(1))C =

(1 + o(1)) Ck . Once si ≤ u, the recurrence is si+1 ≤ si e−(1−o(1))C/si . For m ≥ 0, whenever si ∈ [2m , 2m+1 ], we have (1 − o(1))C (1 − o(1))C ≥ , si 2m+1 hence each step decreases log si by at least (1 − o(1))C/2m+1 . Crossing one dyadic block changes log si by at most log 2, so it takes at most O(2m ) steps. Summing over all blocks with 2m ≤ u gives ⌊log2 u⌋

X

O(2m ) = O(u).

m=0

To see τ = O(log ∆), we argue by cases. If τ < 2k/C, we are done since k ≤ (1 − ε) ln ∆/4. Otherwise τ ≥ 2k/C, so the recurrence is valid for every i < min{τ, 2k/C} = 2k/C. In that case, the first phase takes at most (1 + o(1))k/C rounds and the second phase takes at most O(u) = o(k/C) rounds, so within the first 2k/C rounds we obtain si ≤ 1, giving τ ≤ (1 + o(1))

k = O(log ∆). C

14

For any fixed constant A and every j ∈ [τ, τ + A log log ∆], we have j ≤ τ + A log log ∆, hence pj =

j Y

βℓ p0 ≥ (1 − o(1))e−j/K

ℓ=1

k ∆ ∆ ≥ (1 − o(1))e−(τ +A log log ∆)/K ≥ ∆ 1−(1+o(1)) CK ln ∆ −o(1) . k k

Since C = 4Ke11/K , this is

1/K

pj ≥ ∆ 1−(1+o(1))4e

k −o(1) ln ∆

.

Using K = 4/ε and k ≤ (1 − ε) ln ∆/4,   k 4 e1/K − 1 ≤ eε/4 − 1 (1 − ε) ≤ ln ∆ 



ε ε2 5ε ε + (1 − ε) ≤ < , 4 16 16 3 !

where we used ex − 1 ≤ x + x2 for x ∈ [0, 1/4]. Hence, for ∆ ≥ ∆ε , 4k

ε

pj ≥ ∆ 1− ln ∆ − 3 −o(1) = ∆ε2 −o(1) > ∆ε1 /3 = T.

(1)

By definition of τ , we have tτ ≤ pτ . We now prove tj ≤ pj on this interval by induction on j. The base case j = τ is already noted. If τ ≤ j < τ + A log log ∆ and tj ≤ pj , then αj+1 βj+1 tj ≤ βj+1 pj = pj+1 , and, by (1) we also have tj+1 = max{αj+1 βj+1 tj , T } ≤ pj+1 . Therefore tj ≤ pj for all j ∈ [τ, τ +A log log ∆]. In particular, for every τ +1 ≤ i ≤ τ +A log log ∆, βi pi−1 pi ti−1 = ti−1 ≥ βi . Now fix such an i. Since i = O(log ∆), we obtain (1 − o(1))pi αi ≤ exp − 4Kti−1 



−1/K

and therefore αi ≤ exp − e 4K





(1 − o(1))e−1/K ≤ exp − 4K

!

. Hence, whenever τ ≤ i ≤ τ + A log log ∆ and d′i > dstop , we

also have di > dstop /(1 + δ)i , so by the recurrence for di , e−1/K di = αi di−1 ≤ exp − 4K

!

di−1 .

−1/K

Write c = e 4K > 0. Iterating, for every s ≥ 0 with τ + s < τend , dτ +s ≤ e−cs dτ . Also dτ ≤ ∆, so dτ +s ≤ e−cs ∆. Since τ + s = O(log ∆) and δ = (log ∆)−4 , d′τ +s = (1 + δ)τ +s dτ +s ≤ eδ(τ +s) e−cs ∆ ≤ 2e−cs ∆, for ∆ ≥ ∆ε . Therefore, if s = A log log ∆ and A > 7/c, then d′τ +s ≤ 2∆ e−cA log log ∆ =

∆ 2∆ ≤ = dstop . cA (log ∆) (log ∆)6

Hence τend ≤ τ + A log log ∆ + 1 ≤ (1 + o(1))k/C + A log log ∆ + 1 = O(k + log log ∆). It remains to collect the bounds that hold in every executed round. For every 1 ≤ i < τend , we have p′i ≥ T (log ∆)6 . Indeed, i = O(k + log log ∆) and pi ≥ ∆ε2 , so p′i = (1 − o(1))pi . Since ε2 − ε1 /3 > 0, for ∆ ≥ ∆ε , p′i ≥ ∆ε2 ≥ ∆ε1 /3 (log ∆)6 = T (log ∆)6 . The palette inequality holds for every i ≥ 1. Indeed, from p′i = (1 − δ/7)i pi , pi = βi pi−1 , and 200/r = o(δ), we get 

p′i−1 βi 1 −

δ  200  1− ≥ (1 − δ/7)βi p′i−1 = p′i . 8 r 15

For the degree-bound inequality, fix i with 1 ≤ i < τend , and write 

Ei := αi 1 +

200 ′ ∆ δ ′ d + d + . 3 i−1 r i−1 r(log ∆)8

Since αj ≤ 1 for every round j, the recurrence for d′j gives d′j ≤ (1 + δ)j ∆

for all j ≥ 0.

Because i − 1 < τend = O(k + log log ∆) = O(log ∆) and δ = log−4 ∆, we have (1 + δ)i−1 ≤ 2 for ∆ ≥ ∆ε . Hence d′i−1 ≤ 2∆. Therefore

200 ′ 401∆ δ ∆ ≤ ≤ di−1 + dstop 8 20 r r(log ∆) (log ∆) 10

since dstop = ∆/(log ∆)6 and r = (log ∆)20 . If αi di−1 ≥ dstop /(1 + δ)i , then di = αi di−1 , hence d′i = (1 + δ)i di = (1 + δ)αi d′i−1 . The displayed lower bound on αi d′i−1 implies 

d′i − αi 1 +

2δ 2δ δ δ ′ di−1 = αi d′i−1 ≥ dstop ≥ dstop . 3 3 3(1 + δ) 2

Combining this with the bound on the additive error terms gives Ei ≤ d′i . If αi di−1 < dstop /(1 + δ)i , then d′i = dstop , while 

αi 1 +

1 + δ/3 δ ′ di−1 < dstop . 3 1+δ

Using the same additive-error estimate, we obtain 

Ei <

1 + δ/3 δ + dstop < dstop = d′i . 1+δ 10 

Thus Ei ≤ d′i for every i < τend . This proves the theorem.

4.2

Proof of Lemma 8

Fix a round i and assume that Fi−1 holds. Since Lemma 8 is invoked only while Algorithm 3 is still iterating, we also have d′i−1 > dstop . As in Section 3, we work for sufficiently large ∆ (equivalently ∆ ≥ ∆ε after fixing ε). Fix any partition Φ = (Φ1 , . . . , Φr ) that is an r-partition with parameters min{d′i−1 , ∆} and 2ti−1 in the sense of Definition 6 from Section 3.2. The three propositions below, proved in Section 4.3, establish resilience for all bad events in Bi with respect to Φ. Once these three statements are established for the same partition Φ, Theorem 4 can be applied to the whole LLL instance Li . Proposition 12. Assume Fi−1 holds and d′i−1 > dstop . Then for every active vertex u, 

PV 1  i

[ [ n

j≤r S⊆Φj

 o S 1 −20  (Q+ ≤ d−35 . i (u)) | Vi > 2d

h

PV 2 i

i

In particular, the bad event Q+ i (u) is resilient with respect to Φ. 16

Proposition 13. Assume Fi−1 holds and d′i−1 > dstop . Then for every active vertex u, the bad event Ri+ (u) is resilient with respect to Φ. Proposition 14. Assume Fi−1 holds and d′i−1 > dstop . Then for every active vertex u, the bad event Mi+ (u) is resilient with respect to Φ. In Proposition 12, we prove a slightly stronger notion of resilience of Q+ i (u) to support the proof of Proposition 13. Given these propositions, we can prove Lemma 8 as below. Proof of Lemma 8. Fix C > 0 such that ∆ ≤ (log n)C , and let b be the constant supplied by Theorem 7 from Section 3.2 with a = C. The assumptions of that theorem hold as follows. For every active vertex u, the invariant Fi−1 gives |Ni−1 (u)| ≤ d′i−1 , and the original maximum-degree bound gives |Ni−1 (u)| ≤ ∆, so |Ni−1 (u)| ≤ min{d′i−1 , ∆}. For the c-degree condition, every c ∈ Pi−1 (u) satisfies |Ni−1,c (u)| ≤ 2ti−1 . It remains to check the lower bounds on min{d′i−1 , ∆} and 2ti−1 required by Theorem 7. Since this iteration is executed only while d′i−1 > dstop , we have min{d′i−1 , ∆} ≥ dstop = ∆/(log ∆)6 ≥ (log ∆)b , for ∆ ≥ ∆ε . Also, by definition of tj , we have 2ti−1 ≥ 2T = 2∆ε1 /3 ≥ (log ∆)b . Thus Theorem 7 applies to H = Gi−1 , U = V (Gi−1 ), and the palettes Pi−1 , with max-degree parameter min{d′i−1 , ∆} and c-degree parameter 2ti−1 . Therefore, Algorithm 2 constructs with high probability an r-partition Φ = (Φ1 , . . . , Φr ) that satisfies Definition 6 for these parameters. Condition on this event and fix that Φ. By Propositions 12, 13, and 14, every bad event in Bi is resilient with respect to Φ. Therefore Theorem 4 applies to the round instance with the partition Φ. Because r = (log ∆)20 ≤ (log log n)O(1) in the present range, the partition construction and Theorem 4 together take (log log n)O(1) rounds with high probability. This proves the claimed guarantee.

4.3

Event-by-Event Resilience

Shared Setup Throughout this subsection, fix the round i, assume Fi−1 , and let Φ = (Φ1 , . . . , Φr ) be the r-partition supplied by the proof of Lemma 8. We will use its two consequences separately. For every active vertex u, every color c ∈ Pi−1 (u), and every part Φj , |Ni−1 (u) ∩ Φj | ≤ 100 min{d′i−1 , ∆}/r ≤ 100d′i−1 /r, and

|Ni−1,c (u) ∩ Φj | ≤ 200ti−1 /r.

The first estimate is the lightness bound used in the max-degree argument, and the second is the color-balance bound used in the palette and c-degree arguments. To verify resilience, we use the mixed-sample notation from Section 2. Let Vi1 and Vi2 be independent copies of the round-i variable family Vi . For any event A determined by the round-i variables and any set S ⊆ Φj , let AS denote the mixed-sample event obtained by taking the variables in S from Vi2 and all remaining variables from Vi1 . If Zi is any round-i object determined ei,c (u), or Ni (u), then Z ℓ denotes the by the sampled variables, such as Seli (u), Ki (u), Pei (u), N i ℓ corresponding object computed from the sample Vi , and ZiS denotes the corresponding object 17

computed from the mixed sample that uses Vi2 on S and Vi1 outside S. In the proofs below, the target events are indexed either by a vertex u or by a pair (u, c), and only vertices in Ni−1 (u) ∩ Φj or Ni−1,c (u) ∩ Φj can change the indexed quantity under one-part resampling. We repeatedly invoke Theorem 11. Since d′i−1 > dstop , the round i is executed before the stopping time, so that theorem gives



αi 1 +

200  δ  1− ≥ p′i , 8 r



βi ≥ e−1/K ,

p′i−1 βi 1 −

δ ′ 200 ′ ∆ di−1 + di−1 + ≤ d′i , 3 r r(log ∆)8

p′i ≥ T (log ∆)6 ,

and i = O(k + log log ∆) = O(log ∆). In particular, t′i−1 = (1 + 2δ)i−1 ti−1 ≤ 2ti−1 for ∆ ≥ ∆ε , and every concentration estimate below is applied in a polylog-large range. We also introduce the following bad events. 

Qi (u) :=

  δ e , |Pi (u)| < |Pi−1 (u)|βi 1 −

8  δ ′ Mi (u) := |Ni (u)| > αi 1 + di−1 . 5 



+ Thus Q+ i (u) ⊆ Qi (u) and Mi (u) ⊆ Mi (u). The following simple fact will be useful in the next proofs.

Lemma 15. If Fi−1 (u) holds, then (1 + 2δ)i−1 1− 2

|Pi−1 (u)| ≥ In particular, |Pi−1 (u)| ≥



1 2 − o(1)



!

p′i−1 .

pi−1 .

Proof. From Fi−1 (u), we have (1 − λi−1 (u))2ti−1 ≤ Di−1 (u) ≤ t′i−1 = (1 + 2δ)i−1 ti−1 , so i−1

λi−1 (u) ≥ 1 − (1+2δ) , which gives the first bound. Also p′i−1 = (1 − δ/7)i−1 pi−1 . Since 2 i < τend , Theorem 11 from Section 4.1 gives i = O(k + log log ∆) = O(log ∆), and with δ = 1/ log4 ∆ we obtain (1 + 2δ)i−1 = 1 + o(1) and (1 − δ/7)i−1 = 1 − o(1). Therefore,  |Pi−1 (u)| ≥ 12 − o(1) pi−1 . e i (u) in V 1 as follows: Proof of Proposition 12. Fix a part Φj , and a subset S ⊆ Φj . Define Q i n

e i (u) := Qi (u) ∪ P 2 Q V

h

i

{u}

Qi (u)

i

o

Vi1 > d−20 .

The second term is included to handle the case in the resilience definition where the adversarial
{u} set S contains the variable Xi (u). By the notation of Section 2.2.2, Qi (u) is the event Qi (u) evaluated with Xi (u) taken from the second sample and all other round-i variables taken e i (u) rules out, in advance, the bad first samples for which merely from the first sample. Thus Q resampling Ki (u) would make the palette event likely. By Lemma 23 from Appendix A, P[Qi (u)] ≤ ∆−300 ≤ d−75 . Also, since PV 1 [·] and PV 2 [·] are the same distribution, this implies that i

i

h

h

EV 1 PV 2 i

i

{u}

Qi (u)

| Vi1

ii

= P[Qi (u)] ≤ d−75 ,

so by Markov’s inequality h

h

PV 1 PV 2 i

i

{u}

Qi (u)

i

i

| Vi1 > d−20 ≤ d−55 .

18

e i (u)] ≤ d−35 . Hence PV 1 [Q i

e i (u) does not occur for the variables in V 1 . In particular, Qi (u) does not Assume that Q i occur. If u ∈ / S, then the set Ki (u) is determined by Vi1 , and the only additional palette loss due to resampling comes from vertices of S ∩ Ni−1 (u). For each color c ∈ Pei1 (u), the event that c survives the resampling inside S depends only on the c-selection bits of the vertices in S ∩ Ni−1,c (u). These events are independent across colors. Moreover, by the partition bound |S ∩ Ni−1,c (u)| ≤ |Φj ∩ Ni−1,c (u)| ≤ 200ti−1 /r and the definition πi = 1/(2Kti−1 + 1), h

i

PV 2 c ∈ / Sel2i (S ∩ Ni−1,c (u)) | Vi1 = (1 − πi )|S∩Ni−1,c (u)| i

1



≥ 1−

200ti−1 /r

2Kti−1 + 1 200ti−1 ≥1− . r(2Kti−1 + 1)

Then |PeiS (u)| is a sum of independent indicators indexed by the colors in Pei1 (u), and the 200ti−1 calculation above shows that each indicator has conditional mean at least 1 − r(2Kt . Hence i−1 +1) µ := EV 2 i

 i  δ S 1 e e |P (u)| | V , ¬Qi (u) ≥ |Pi−1 (u)|βi 1 − 1−

h

i

8

i

200ti−1 . r(2Kti−1 + 1) 





200ti−1 ≤ 100 By Lemma 15, |Pi−1 (u)| ≥ 12 − o(1) pi−1 . Also 2Kt K ≤ 25, since K = 4/ε ≥ 4. i−1 +1 Hence      1 δ 25 −1/K µ≥ − o(1) e 1− 1− pi−1 = Ω(pi−1 ). 2 8 r S Hence µ = Ω(pi ) as well, since pi = βi pi−1 ≤ pi−1 . The bad event (Q+ i (u)) is precisely

   δ  200  100 S e |P (u)| < |Pi−1 (u)|βi 1 − 1− ≤ 1− µ.

8

i

r

r

Since |PeiS (u)| is a sum of independent Bernoulli variables with mean µ, Chernoff’s bound gives 

PV 2 i

|Pe S (u)| < i

100 e i (u) ≤ exp − 10000µ 1− µ Vi1 , ¬Q r 2r2











5000 µ = exp − . r2 



Finally, Theorem 11 gives p′i−1 ≥ T (log ∆)6 , and p′i−1 = (1 −  δ/7)i−1 pi−1 with i = O(log ∆) µ implies pi−1 = (1 + o(1))p′i−1 . Since µ = Ω(pi−1 ), we obtain exp − 5000 ≤ d−20 . r2 If u ∈ S, then Ki (u) is also resampled. This is the only additional difficulty beyond the u∈ / S case: resampling Xi (u) can change Ki (u) itself. On the complement of the second term e i (u), the palette Pe {u} (u) of u after resampling Ki (u) has size at least |Pi−1 (u)|βi (1 − δ/8) in Q i except with probability d−20 . Condition on this good event. After that conditioning, the only remaining loss again comes from the vertices in S ∩ Ni−1 (u), so the same Chernoff calculation gives the stronger bound d−20 for the extra loss. Therefore

h

i

S 1 −20 e PV 2 (Q+ . i (u)) Vi , ¬Qi (u) ≤ 2d i

For each j, define Ej :=

[ n

h

i

o

S 1 −20 PV 2 (Q+ . i (u)) Vi > 2d i

S⊆Φj

Crucially, no union bound over the exponentially many subsets S ⊆ Φj is needed. The preceding e i (u) is excluded, for every possible S, the bad event under argument was uniform in S: after Q e i (u) does not resampling has conditional probability at most 2d−20 . By the bound above, if Q e occur then Ej does not occur either, so Ej ⊆ Qi (u). The same inclusion holds hS i for every j because S e e i (u)] ≤ d−35 . the argument is uniform in j. Therefore j≤r Ej ⊆ Qi (u), so PV 1 j≤r Ej ≤ PV 1 [Q i

i

This proves the stronger statement in the proposition, and hence Q+ i (u) is resilient. 19

Proof of Proposition 13. Fix a vertex u, and a part Φj from Φ. Let Hi+ (u) :=

 

X





c∈Pi−1

  ei,c (u)| > β 2 |Pi−1 (u)| ni−1 (u) + δ ti−1 + 300 ti−1 |Pi−1 (u)| . |N i  4 r (u) 

We will prove the following two claims. 1. With probability at least 1 − 2d−40 over the choice of the first sample Vi1 , h

i

PV 2 (Hi+ (u))S | Vi1 = 0

for every S ⊆ Φj .

i

(2)

2. For each c ∈ Pi−1 (u), with probability at least 1 − 2d−34 over the choice of the first sample Vi1 , for every S ⊆ Φj we have 

S e S (u)|αi 1 + PV 2 |Ni,c (u)| > |N i,c i

δ
δ + T | Vi1 < 3d−18 , 3 3 

e S (u) and N S (u) for the mixed-sample version of N ei,c (u) and Ni,c (u) respectively. where we write N i,c i,c We will prove the two claims below. For each fixed j, except on a first-sample event of probability at most 2d−40 +2|Pi−1 (u)|d−34 , Claim 1 holds and Claim 2 holds simultaneously for all c ∈ Pi−1 (u) by a union bound. Then, for every S ⊆ Φj , a union bound over colors gives h

i

PV 2 (Ri+ (u))S | Vi1 ≤ 3|Pi−1 (u)|d−18 ≤ d−10 , i

since on the complement of the bad events from Claim 2 and Claim 1, (Ri+ (u))S does not occur. Taking a final union bound over j = 1, . . . , r, we obtain the resilience of Ri+ (u) with respect to Φ. To prove the two claims, we organize the random variables {Xi (v)} in the set S into two parts. Let 

Sa :=

[

Ki (v) ∪ 

v∈Ni−1 (u)∩S

 [

Seli (w) ,

[

v∈Ni−1 (u) w∈Ni−1 (v)∩S

Sb :=

[

Seli (v).

v∈Ni−1 (u)∩S

Note that these are the only variables that can affect the event Ri+ (u), and that Sa and Sb are disjoint since Gi−1 is triangle-free. Moreover, for the resilience of Hi+ (u), we only need to e S (u) = N e Sa (u) and thus (H + (u))S = (H + (u))Sa . consider the variables in Sa . In particular, N i,c i,c i i For the first claim, we first define an auxiliary event Hi (u) :=

 

X



c∈Pi−1

 

ei,c (u)| > β 2 |Pi−1 (u)| ni−1 (u) + δ ti−1 |N , i  4 (u) 

and note that Hi+ (u) ⊆ Hi (u). By Lemma 23 from Appendix A, PV 1 [Hi (u)] ≤ ∆−200 ≤ d−40 . i We will control how much the resampling inside Φj can increase ei,c (u)|. |N

X c∈Pi−1 (u)

e S (u) but not to N ei,c (u), then this Fix c ∈ Pi−1 (u) and a vertex x ∈ Ni−1,c (u). If x belongs to N i,c change must be caused by the resampling inside Φj . There are two possibilities. First, x itself may lie in Φj . Second, in the first sample some vertex of Φj selected the color c and thereby prevented x from being counted, whereas after resampling no vertex of Φj selects c.

20

The vertices of the first type contribute at most |Ni−1,c (u) ∩ Φj | ≤

X c∈Pi−1 (u)

200 ti−1 |Pi−1 (u)|. r

To capture the second type, define Ai,j (u, c) := x ∈ Ni−1,c (u) \ Φj : c ∈ Sel1i (y) for some y ∈ Φj ∩ Ni−1,c (x) . 

e S (u) \ N ei,c (u)) \ Φj , then x must arise from the second type above, and hence If x ∈ (N i,c x ∈ Ai,j (u, c). Therefore
e S (u) \ N ei,c (u) \ Φj ⊆ Ai,j (u, c) N i,c

for every S ⊆ Φj . For a fixed vertex x ∈ Ni−1,c (u) \ Φj , we have |Φj ∩ Ni−1,c (x)| ≤ 200ti−1 /r, so PV 1 [x ∈ Ai,j (u, c)] ≤ i

200πi ti−1 200ti−1 100 = ≤ . r r(2Kti−1 + 1) Kr

Summing over x and then over colors yields 

µ := E 



|Ai,j (u, c)| ≤

X

c∈Pi−1 (u)

100 X |Ni−1,c (u)| Kr c∈P (u) i−1

200 ≤ ti−1 |Pi−1 (u)| Kr 50 ≤ ti−1 |Pi−1 (u)|, r Let Bi,j (u) :=

 

X



c∈Pi−1

since K = 4/ε ≥ 4. 

 100 |Ai,j (u, c)| > ti−1 |Pi−1 (u)| .  r (u)

The random variables |Ai,j (u, c)| are independent across colors, and each is bounded by |Ni−1,c (u)| ≤ 2ti−1 , so Hoeffding’s inequality gives 

 2 P[Bi,j (u)] ≤ exp− 

 2 ≤ exp−





100 r ti−1 |Pi−1 (u)| − µ 4t2i−1 |Pi−1 (u)|

2   

2 

50 r ti−1 |Pi−1 (u)| 4t2i−1 |Pi−1 (u)|

  1250 |Pi−1 (u)|  .  = exp − 2

r

By Lemma 15, |Pi−1 (u)|/r2 ≫ log d, so this is at most d−40 . Then PV 1 [Bi,j (u)] ≤ d−40 , and on i the complement of Bi,j (u) we have e S (u)| ≤ |N i,c

X c∈Pi−1 (u)

ei,c (u)| + |N

X c∈Pi−1 (u)

300 ti−1 |Pi−1 (u)| r

for every S ⊆ Φj . Therefore, if we fix a realization of Vi1 for which neither Hi (u) nor Bi,j (u) occurs, then the defining inequality of Hi+ (u) cannot hold in the mixed sample. Thus, for such Vi1 , h i for every S ⊆ Φj . PV 2 (Hi+ (u))S | Vi1 = 0 i

on

Next we will work on the second claim. Note that the events {Q+ i (v)}v∈Ni−1 (u) depend only 

Vi1,a :=

[



K 1 (v) ∪

[

i

v∈Ni−1 (u)

w∈Ni−1 (v)

21

Sel1i (w) ,

S

S

  P 2

[

S

a + + so = . By Proposition 12 and a union bound over v∈Ni−1 (u) Qi (v) v∈Ni−1 (u) Qi (v) −34 v ∈ Ni−1 (u), with probability at least 1 − d over the choice of the first sample Vi1 , we have

S

Vi

Sa

Q+ i (v)



| Vi1,a  ≤ d−18

for every S ⊆ Φj .

(3)

v∈Ni−1 (u)

Fix a realization of Vi1,a such that (3) holds. For a given S ⊆ Φj , assume that the assignment
Sa S + in V2i on Sa is such that does not occur. We refer to this event as E(Sa ). v∈Ni−1 (u) Qi (v) Then under E(Sa ), for each v ∈ Ni−1 (u), we have |PeiSa (v)| ≥ |Pi−1 (v)|βi (1 − δ/8). Since S S S |Ni,c (u)| ≤ |Ni,c (u) ∩ S| + |Ni,c (u) \ S|, S (u) \ S|. Observe that a node it suffices to derive upper bounds on both |Ni−1,c (u) ∩ S| and |Ni,c e Sa (u) belongs to N S (u) if and only if SelSb (v) ∩ Pe Sa (v) = ∅. If v ∈ S, then v ∈ N S (u) v∈N i,c i,c i,c i i S (u) if and only if Sel1 (v) ∩ P e Sa (v) = ∅. if and only if Sel2i (v) ∩ PeiSa (v) = ∅; otherwise v ∈ Ni,c i i
S The random variables v∈Ni−1 (u) Sel1i (v) =: Vi1,b are independent of Vi1,a and the event E(Sa ). Under E(Sa ), by Lemma 15, the event Sel1i (v) ∩ PeiSa (v) = ∅ happens with probability at most

 |Pi−1 (v)|βi (1−δ/8)

(1 − πi )

≤ (1 − πi )

1−

(1+2δ)i−1 2



p′i−1 βi (1−δ/8)



≤ (1 − πi )

1−

(1+2δ)i−1 2



p′i

= αi . (4)

S (u) \ S| is a sum of independent Bernoulli variables with mean µ ≤ α |N e Sa (u) \ S|. Therefore |Ni,c i i,c We claim

δ
δ 1+ + T | Vi1,a , E(Sa ) ≤ d−34 . 3 6 



S e Sa (u) \ S |Ni,c (u) \ S| > αi N i,c

PV 1,b i

Indeed, if µ ≥ T , then

δ
δ δ
+ T ≥µ 1+ , 3 6 3

e Sa (u) \ S 1 + αi N i,c

so the Chernoff bound gives
S e Sa (u) \ S| 1 + δ + δ T P |Ni,c (u) \ S| > αi |N i,c 

3

6

If µ < T , then e Sa (u) \ S| 1 + αi |N i,c



δ2µ ≤ exp − 27

!



P

S e Sa (u) \ S| 1 + δ + δ T |Ni,c (u) \ S| > αi |N i,c

3

!

.

δ
δ δ + T ≥ µ + T. 3 6 6 2

t Applying Chernoff bound of the form P[X > µ + t] ≤ exp − 2(µ+t/3) and t = δT /6, and using µ < T and δ < 1, we get



δ2T ≤ exp − 27



3



S (u) \ S| with X = |Ni,c

(δT /6)2 ≤ exp − 2(µ + δT /18)

!

δ2T ≤ exp − 74 

2

!

. 

Since δ = log−4 ∆, T = ∆ε1 /3 , and d ≤ ∆4 , we have δ 2 T ≫ log d, so for ∆ ≥ ∆ε , exp − δ74T ≤ d−34 , and the claim follows.
S Moreover, the variables in v∈Ni−1 (u)∩S Sel2i (v) are also independent of Vi1,a and the event E(Sa ), and by (4), for each v ∈ Ni−1 (u) ∩ S, the event Sel2i (v) ∩ PeiSa (v) = ∅ happens with probability at most αi . Through a similar argument, we can also show that 

PV 2 i

S e Sa (u) ∩ S |Ni,c (u) ∩ S| > αi N i,c

δ
δ 1+ + T | Vi1,a , E(Sa ) ≤ d−18 . 3 6

22



Therefore, by a union bound, with probability at least 1 − 2d−34 over the choice of the first sample Vi1 = Vi1,a ∪ Vi1,b , for every S ⊆ Φj we have 

S e S (u)| 1 + PV 2 |Ni,c (u)| > αi |N i,c i

δ
δ + T | Vi1 < 3d−18 , 3 3 

which completes the proof of the second claim and hence of the proposition. Before proving Proposition 14, define a signature map Γ that assigns to each nonempty color set L a witness color Γ(L) ∈ L. In the proof below, whenever a vertex x comes with a nonempty set Lx of colors still available to it, we use Γ(Lx ) as the witness color of x. Proof of Proposition 14. Fix a vertex u, a part Φj , and a subset S ⊆ Φj . Recall that we let Niℓ (u) be the residual neighborhood of u in the sample Viℓ , and let NiS (u) be the residual neighborhood of u in the mixed sample determined by S. We consider the neighbors outside Φj that are newly
S (u) := N S (u) \ N 1 (u) ∪ Φ . added to the residual neighborhood by resampling, namely Wi,j j i i Then every vertex of NiS (u) is either already in Ni1 (u), or lies in Φj ∩ Ni−1 (u), or belongs to S (u). Therefore Wi,j S |NiS (u)| ≤ |Ni1 (u)| + |Ni−1 (u) ∩ Φj | + |Wi,j (u)|.

By Lemma 23 from Appendix A, PV 1 [Mi (u)] ≤ ∆−200 ≤ d−40 . Here Mi (u) is precisely i the event {|Ni1 (u)| > αi (1 + δ/5)d′i−1 }, so on its complement the first term above satisfies |Ni1 (u)| ≤ αi (1 + δ/5)d′i−1 . Also, the partition bound gives |Ni−1 (u) ∩ Φj | ≤ 100d′i−1 /r. S (u). For every vertex x ∈ N We next bound the size of Wi,j i−1 (u) \ Φj , define its first1 1 e sample certifying color set Cx := Seli (x) ∩ Pi (x) and, whenever Cx = ̸ ∅, let σ(x) = Γ(Cx ). If S (u), then x ∈ x ∈ Wi,j / Ni1 (u), so Cx ̸= ∅. Moreover, x is uncolored in the mixed sample, so every color in Cx is selected by some vertex of S ∩ Ni−1,σ(x) (x). For each color c′ , define S Wi,j (u, c′ ) := x ∈ Ni−1 (u) \ Φj : Cx ̸= ∅, σ(x) = c′ ,



c′ ∈ Sel2i (y) for some y ∈ S ∩ Ni−1,c′ (x) . Then

S Wi,j (u) ⊆

[

S Wi,j (u, c′ ),

hence

c′

S |Wi,j (u)| ≤

X

S |Wi,j (u, c′ )|.

c′

S (u, c′ )| depends only on the c′ -selection bits of the vertices For fixed c′ , the random variable |Wi,j in S from the second sample. Hence, once the first sample Vi1 has been fixed, the family S (u, c′ )| : c′ } is independent under P [· | V 1 ]. {|Wi,j Vi2 i S ′ To control the size of the set Wi,j (u, c ), define the following event in Vi1 ,

Oi (u, c′ ) :=

n

o

{x ∈ Ni−1,c′ (u) \ Φj : c′ ∈ Sel1i (x)} > (log ∆)8 .

Since |Ni−1,c′ (u)| ≤ 2ti−1 , the random variable inside Oi (u, c′ ) is binomial with mean at most 2ti−1 πi ≤ 1/K. Thus a standard binomial tail bound gives PV 1 [Oi (u, c′ )] ≤ exp(−Ω((log ∆)8 )). i S There are at most ∆ relevant colors, so PV 1 [ c′ Oi (u, c′ )] ≤ d−40 for ∆ ≥ ∆ε . Moreover, if i S (u, c′ ), then σ(x) = c′ ∈ C ⊆ Sel1 (x) and x ∈ N x ∈ Wi,j x i−1,c′ (u) \ Φj . Therefore i S Wi,j (u, c′ ) ⊆ {x ∈ Ni−1,c′ (u) \ Φj : c′ ∈ Sel1i (x)}, S (u, c′ ) satisfies |W S (u, c′ )| ≤ (log ∆)8 . so on the complement of these events, each set Wi,j i,j

23

Now fix a realization of the first sample Vi1 on which neither Mi (u) nor any event Oi (u, c′ ) occurs. Under the conditional law PV 2 [· | Vi1 ], for a fixed vertex x ∈ Ni−1 (u) \ Φj , if σ(x) = c′ , i then h i 1 200ti−1 100 S · ≤ . PV 2 x ∈ Wi,j (u, c′ ) | Vi1 ≤ πi |S ∩ Ni−1,c′ (x)| ≤ i 2Kti−1 + 1 r Kr S (u, c′ ) are pairwise Moreover, since σ(x) is uniquely defined whenever Cx ̸= ∅, the sets Wi,j ′ disjoint in c . Hence

X

S |Wi,j (u, c′ )| =

c′

X

X

1{x∈W S (u,c′ )} , i,j

x∈Ni−1 (u)\Φj c′ Cx ̸=∅

and for each x the inner sum has at most one nonzero term. Summing the conditional probabilities over all x ∈ Ni−1 (u) \ Φj gives "

µ := EV 2 i

# X

S |Wi,j (u, c′ )| Vi1 ≤

c′

100 100 ′ 25 |Ni−1 (u)| ≤ di−1 ≤ d′i−1 . Kr Kr r

S (u, c′ )|} ′ are independent, Under the conditional law PV 2 [· | Vi1 ], the random variables {|Wi,j c i each lies in [0, (log ∆)8 ] because Vi1 avoids every event Oi (u, c′ ), and there are at most ∆ relevant colors c′ . Applying Hoeffding’s inequality to their sum therefore gives

PV 2



∆ 100 ′  2 di−1 + Vi1 ≤ exp− 8 r r(log ∆)

"

#

X

i

S |Wi,j (u, c′ )| >

c′



75 ′ ∆ r di−1 + r(log ∆)8 ∆(log ∆)16

2   

≤ d−20 , because d′i−1 > dstop = ∆/(log ∆)6 and r = (log ∆)20 . Therefore, for this fixed Vi1 and every S ⊆ Φj , 

i

h



PV 2 (Mi+ (u))S Vi1 ≤ PV 2 |NiS (u)| > αi 1 + i

i

−20

≤d

δ ′ 200 ′ ∆ di−1 + di−1 + V1 5 r r(log ∆)8 i



< d−10 .

It follows that, for each fixed part Φj , i

h

[ n

o

PV 2 (Mi+ (u))S Vi1 > d−10 ⊆ Mi (u) ∪ i

[

Oi (u, c′ ),

c′

S⊆Φj

whose probability is at most 2d−40 . Since r = (log ∆)20 = do(1) , a union bound over j ≤ r still leaves total first-sample probability at most d−30 , proving the resilience condition for Mi+ (u).

4.4

Proof of Lemma 9

Lemma 16. With the parameter schedule fixed in Section 3.4, assume Fi−1 holds and d′i−1 > + dstop . If Q+ i (u) and Ri (u) fail to occur, then e i (u) ≤ αi βi ni−1 (u) + 2δti . n

Proof. Fix u ∈ Ui . Since Pei (u) ⊆ Pi−1 (u), e i (u) = n

1 |Pei (u)|

X

|Ni,c (u)| ≤

ei (u) c∈P

24

1

X

|Pei (u)| c∈Pi−1 (u)

|Ni,c (u)|.

+ Since Q+ i (u) and Ri (u) do not occur, we have

|Pei (u)| ≥ |Pi−1 (u)|βi 1 − and

P

c∈Pi−1 (u) |Ni,c (u)|

|Pi−1 (u)| Therefore e i (u) ≤ n

δ
200
1− 8 r

 300 δ  2 δ δ βi ni−1 (u) + ti−1 + ≤ αi 1 + ti−1 + T. 3 4 r 3 



αi 1 + 3δ



h 2

i

δ βi ni−1 (u) + 4δ ti−1 + 300 r ti−1 + 3 T

βi (1 − δ/8)(1 − 200/r)

.

Because d′i−1 > dstop , we have i < τend by definition. Theorem 11 therefore applies to round i, so i = O(k + log log ∆) = O(log ∆), and hence t′i−1 = (1 + 2δ)i−1 ti−1 ≤ 2ti−1 for ∆ ≥ ∆ε . Also, Theorem 11 gives βi ≥ e−1/K , while the recurrence gives ti ≥ T and ti ≥ αi βi ti−1 . Note that 1 + δ/3 δ ≤1+ . (1 − δ/8)(1 − 200/r) 2 Also, the contribution of the 3δ T term is δT δ δ δ ≤ e1/K (1 + o(1)) T ≤ T ≤ ti , 3βi (1 − δ/8)(1 − 200/r) 3 2 2 where we use βi ≥ e−1/K , (1 − δ/8)−1 (1 − 200/r)−1 = 1 + o(1), ti ≥ T , and e1/K ≤ e1/4 < 3/2 δ since K = 4/ε ≥ 4. Likewise, the contribution of the 300 r ti−1 term is at most 10 ti , because βi ≥ e−1/K and 1/r = o(δ). Using also ni−1 (u) ≤ 2ti−1 , since every color in Pi−1 (u) has residual c-degree at most 2ti−1 , we obtain δ δ δ δ e i (u) ≤ 1 + n αi βi ni−1 (u) + ti−1 + ti + ti 2 4 10 2 δ 3δ δ δ αi βi ti−1 + ti + ti ≤ αi βi ni−1 (u) + αi βi ni−1 (u) + 2 10 10 2 3δ δ δ ≤ αi βi ni−1 (u) + δti + ti + ti + ti 10 10 2 ≤ αi βi ni−1 (u) + 2δti , 







after enlarging ∆ if necessary. This is the required estimate. Proof of Lemma 9. Assume Fi−1 holds and d′i−1 > dstop . Also assume that the output of SolveRoundLLL(i, r, Li ) avoids every bad event in Bi . Fix u ∈Ui .   200 ′ β 1− δ Because Q+ (u) does not occur and Theorem 11 gives p 1 − ≥ p′i , we obtain i i−1 i 8 r ( ) ( ) |Pei (u)| |Pi−1 (u)| e λi (u) = min 1, ≥ min 1, = λi−1 (u). ′ ′

pi

pi−1

e i (u) ≤ αi βi ni−1 (u) + 2δti . Since Pi (u) is obtained from Pei (u) by first Next, Lemma 16 gives n deleting every color whose residual degree exceeds 2ti and then truncating to at most p′i colors,

25

every color removed in this filtering-truncation step contributes at most the dummy value 2ti . e i (u) ≥ λi−1 (u), we may write e i (u). Using also λ Therefore Di (u) ≤ D e i (u) Di (u) ≤ D e i (u)n e i (u))2ti e i (u) + (1 − λ =λ e i (u) + (1 − λi−1 (u))2ti ≤ λi−1 (u)n

≤ λi−1 (u) (αi βi ni−1 (u) + 2δti ) + (1 − λi−1 (u))2ti ti Di−1 (u) + 2δti ≤ ti−1 ≤ (1 + 2δ)i−1 ti + 2δti ≤ (1 + 2δ)i ti = t′i , where the fourth line uses ti ≥ αi βi ti−1 , the next line uses Fi−1 (u), and the last step uses (1 + 2δ)i−1 ≥ 1. Finally, since Mi+ (u) does not occur, by Theorem 11 

|Ni (u)| ≤ αi 1 +

δ ′ 200 ′ ∆ ≤ d′i . di−1 + di−1 + 3 r r(log ∆)8

Thus both parts of Fi (u) hold. Since u was arbitrary, Fi holds after the deterministic postprocessing step.

5

Girth-Five Graphs

This section proves Theorem 3 stated in the introduction. The proof follows the same resilientLLL framework as Section 3, but random coloring on girth-5 graphs gives enough local independence to maintain direct per-color c-degree upper bounds instead of the average c-degree upper bounds used in the triangle-free case. We therefore define the more suitable round-i instance, invariant, and simplified iterative algorithm together, then prove the theorem.

5.1

The Round-i Instance, Invariant, and Algorithm

Fix a round i ≥ 1. Let Gi−1 be the graph induced by the vertices still uncolored at the start of round i. Let Pi−1 (u) be the palette of an active vertex u, let Ni−1 (u) be its neighborhood in Gi−1 , and let Ni−1,c (u) = {v ∈ Ni−1 (u) : c ∈ Pi−1 (v)}. As in Section 3, the round variables are Xi (u) = (Seli (u), Ki (u)), sampled independently by Algorithm 1, and the round-i variable family is Vi = {Xi (u) : u ∈ V (Gi−1 )}. Let θi = (πi , βi , αi , pi , p′i , ti , t′i , di , d′i ) denote the deterministic parameter bundle for round i, and let Li = (Bi , Vi , θi ) be the associated local LLL instance. For a vertex u still active after round i, let Ni (u) be its neighborhood in Gi , and let Fi (u) be the event that 1. |Pi (u)| ≥ p′i , 2. |Ni,c (u)| ≤ t′i for every color c ∈ Pi (u), 3. |Ni (u)| ≤ d′i . Let Fi be the event that Fi (u) holds for every vertex still present in Gi . We now state the streamlined iterative algorithm 4. In each round, the vertices sample (Seli (u), Ki (u)), solve the associated local LLL instance, delete direct color conflicts, color every vertex that still keeps one of its selected colors, and truncate each surviving palette to the target size p′i . 26

Algorithm 4 IterativeColoringFramework(G, {θi }i≥0 , r) 1: Set G0 = G and initialize the palettes P0 (u) to be of p0 colors for every vertex u 2: dstop ← ∆/(log ∆)6 3: i ← 1 4: while d′i−1 > dstop do 5: construct the round-i LLL instance Li 6: Xi ← SolveRoundLLL(i, r, Li ) 7: for all vertices u ∈ V (Gi−1 ) do 8: Pbi (u) ← Ki (u) \ Seli (Ni−1 (u)) 9: if Seli (u) ∩ Pbi (u) ̸= ∅ then 10: color u with an arbitrary color in Seli (u) ∩ Pbi (u) 11: let Ui be the vertices of Gi−1 still uncolored after the round-i coloring decisions 12: for all vertices u ∈ Ui do 13: set Pi (u) to an arbitrary subset of Pbi (u) of size exactly p′i let Gi be the graph induced by Ui i←i+1 16: color the remaining graph Gi−1 using Theorem 5 with dstop + 1 fresh colors 14: 15:

The family Bi of bad events is the following. δ  200  1− , 8 r     300 + δT , Hi+ (u, c) := |Ni,c (u)| > t′i−1 (1 + δ)αi βi′ + r     δ 200 ′ ∆ Mi+ (u) := |Ni (u)| > αi 1 + d′i−1 + di−1 + . 3 r r(log ∆)8 





′ b Q+ i (u) := |Pi (u)| < pi−1 βi 1 −

Fix a constant ε > 0, choose a parameter k with 1 ≤ k ≤ (1 − ε) ln ∆, and define ε ε2 = , 5

ε1 = ε2



4 K= . ε

ε 1− , 3 

Set

1 , r = (log ∆)20 , 4 log ∆ and let T = ∆ε1 /3. The target palette size and its relaxed lower bound are δ=

p0 =

∆ ∆ − − 1, k (log ∆)6

p′i = (1 − δ/7)i pi .

pi = βi pi−1 ,

The sampling probability is

1

πi =

, Kt′i−1 + 1

the color-retention factor is ′

βi = (1 − πi )ti−1 ,

βi′ =

βi , 1 − πi

and the residual-degree attenuation factor is ′

αi = (1 − πi )pi . We then define t0 = ∆, and d0 = d′0 = ∆,

ti = max{αi βi′ ti−1 , T, pi },

t′i = (1 + 2δ)i ti ,

∆ di = max αi di−1 , (1 + δ)i (log ∆)6 

27



,

d′i = (1 + δ)i di .

5.2

Main Lemmas and Proof of the Girth-5 Theorem

We now state the three ingredients needed for Theorem 3. They are the girth-5 counterparts of Lemmas 8, 9, and 10 from Section 3.5. As in Section 3, the first lemma gives a fast solver for each round-i local LLL instance, the second shows that avoiding the bad events propagates the round invariant Fi , and the third shows that the degree-bound sequence d′i reaches the stopping threshold quickly. Lemma 17. With the parameter schedule fixed in Section 5.1, for every fixed C > 0, the following holds whenever ∆ ≤ (log n)C . Suppose Fi−1 holds and d′i−1 > dstop . Then, with high probability, Algorithm 2 solves the round-i instance Li in (log log n)O(1) rounds. Lemma 18. With the parameter schedule fixed in Section 5.1, assume Fi−1 holds and d′i−1 > dstop . For any realization Xi of the round-i variables in which no bad event of Bi occurs, the deterministic post-processing step in Algorithm 4 yields Fi . Lemma 19. With the parameter schedule fixed in Section 5.1, there is ℓ = O(k + log log ∆) such that ∆ . pj > T for every 1 ≤ j ≤ ℓ and d′ℓ ≤ dstop = (log ∆)6 Theorem 3 is deduced from these lemmas in exactly the same way that Theorem 1 is deduced from Lemmas 8, 9, and 10 in the proof from Section 3.5. First, Lemma 19 gives a round ℓ = O(k + log log ∆) with d′ℓ ≤ dstop . Next, Lemmas 17 and 18 show that the rounds 1, . . . , ℓ can be executed while maintaining Fi . Consequently the residual graph Gℓ has maximum degree at most dstop , so Theorem 5 completes the coloring. We therefore omit the proof of Theorem 3 here and instead prove the three lemmas. For Lemma 17, the key ingredient is that the three girth-5 bad-event families are resilient with respect to a suitable partition. Accordingly, fix an r-partition Φ with degree parameters min{d′i−1 , ∆} and t′i−1 in the sense of Definition 6 from Section 3.2. We first state the corresponding resilience propositions, whose proofs are deferred to the next subsection; once they are proved, the proof of Lemma 17 is the same as the proof of Lemma 8 from Section 4, so we omit it. Proposition 20. Assume Fi−1 holds and d′i−1 > dstop . Then for every active vertex u, the bad event Q+ i (u) is resilient with respect to Φ. Proposition 21. Assume Fi−1 holds and d′i−1 > dstop . Then for every active vertex u and every color c ∈ Pi−1 (u), the bad event Hi+ (u, c) is resilient with respect to Φ. Proposition 22. Assume Fi−1 holds and d′i−1 > dstop . Then for every active vertex u, the bad event Mi+ (u) is resilient with respect to Φ. Proof of Lemma 18. Assume Fi−1 holds, d′i−1 > dstop , and no bad event of Bi occurs. We verify the three clauses of Fi . First, Q+ i (u) does not occur, so 

|Pbi (u)| ≥ p′i−1 βi 1 −

δ  200  1− . 8 r

By the definition p′i = (1 − δ/7)i pi and pi = βi pi−1 , the right-hand side is at least p′i for ∆ ≥ ∆ε , because 200/r = o(δ). Therefore the truncation step in Algorithm 4 is well-defined, and after truncation |Pi (u)| = p′i . Second, let c ∈ Pi (u). Because Hi+ (u, c) does not occur, we obtain |Ni,c (u)| ≤ t′i−1

300 (1 + δ)αi βi′ +



r

28



+ δT.

(5)

To compare the right-hand side of (5) with t′i , note that t′i−1 = (1 + 2δ)i−1 ti−1 and t′i = (1 + 2δ)i ti . Also πi = (Kt′i−1 + 1)−1 ≤ (KT )−1 = o(δ). Hence, for ∆ ≥ ∆ε , we have πi ≤ 1/2, βi′ =

βi ≤ βi e2πi = βi (1 + o(δ)) 1 − πi

Moreover, ′

′

βi = (1 − πi )ti−1 ≥ e−2πi ti−1 ≥ e−2/K

′

′

αi = (1 − πi )pi ≥ e−2πi pi ≥ e−2/K ,

and

because t′i−1 πi ≤ 1/K and p′i ≤ t′i−1 . Hence αi βi′ ≥ αi βi ≥ e−4/K . Therefore, 

|Ni,c (u)| ≤ t′i−1 (1 + δ)αi βi′ +

300 r



+ δT,

by (5),

300ti−1 r
i−1 ′ ≤ (1 + 2δ) (1 + 2δ)αi βi ti−1 + δT , 

≤ (1 + 2δ)i−1 (1 + δ)αi βi′ ti−1 +



+ δT,

using t′i−1 = (1 + 2δ)i−1 ti−1 , since αi βi′ ≥ e−4/K and 300r−1 = o(δ),

≤ (1 + 2δ)i ti ,

because ti ≥ αi βi′ ti−1 , T,

= t′i ,

by definition of t′i .

Finally, we consider the upper bound of |Ni (u)|. Since Mi+ (u) does not occur, we have δ ′ 200 ′ ∆ di−1 + di−1 + , 3 r r(log ∆)8  δ ≤ αi 1 + d′i−1 + o(δαi d′i−1 ), 3 ≤ (1 + δ)αi d′i−1 , 

|Ni (u)| ≤ αi 1 +

≤ d′i . All three defining properties of Fi (u) hold for every active vertex u, so Fi holds. Proof of Lemma 19. Let si = ti /pi , and let τ = min{i ≥ 0 : pi ≥ ti }. Since ti ≥ pi for every i by definition of ti , this is equivalently τ = min{i ≥ 0 : ti = pi }. Exactly as in the proof of Theorem 11 from Section 4.1, the same recurrence for si yields τ = O(k + log log ∆), and, for every fixed constant A and every j ∈ [τ, τ + A log log ∆], pj ≥ ∆ε2 −o(1) > T.

(6)

We do not repeat the same analysis here. We now analyze the rounds after τ . By definition of τ , we have tτ = pτ . We claim that tj = pj for every j ∈ [τ, τ + A log log ∆]. The base case j = τ is immediate. If τ ≤ j < τ + A log log ∆ and tj = pj , then (6) gives pj+1 > T , and therefore tj+1 = max{αj+1 βj+1 tj , T, pj+1 } = max{αj+1 pj+1 , T, pj+1 } = pj+1 , since αj+1 ≤ 1. This proves the claim. Now fix i with τ + 1 ≤ i ≤ τ + A log log ∆. Since i = O(k + log log ∆) = O(log ∆), we have p′i = (1 − o(1))pi and t′i−1 = (1 + o(1))ti−1 . Using ti−1 = pi−1 , and writing πi = (Kt′i−1 + 1)−1 , we get πi = o(1) and therefore t′i−1 log(1 − πi ) = −t′i−1 πi + O(t′i−1 πi2 ) = − 29

t′i−1 1 + o(1) = − + o(1). ′ Kti−1 + 1 K

Therefore

pi



′

ti−1

= βi = (1 − πi )ti−1 = exp −

1 + o(1) . K 

Consequently, p′i

αi = (1 − πi )

(1 − o(1))pi ≤ exp − Kti−1 



!

e−1/K − o(1) ≤ exp − . K

Therefore, there is a constant c := e−1/K /(2K) > 0 such that αi ≤ e−c throughout this interval. Since also (1 + δ)e−c ≤ e−c/2 for ∆ ≥ ∆ε , we get n

o

d′i = max (1 + δ)αi d′i−1 , dstop ≤ max e−c/2 d′i−1 , dstop . 

for every τ + 1 ≤ i ≤ τ + A log log ∆. Consequently, until the sequence first reaches dstop , it shrinks geometrically by the factor e−c/2 . Since αj ≤ 1 for every j, the recurrence for d′j gives d′j ≤ (1 + δ)j ∆ for all j ≥ 0. Because τ = O(k + log log ∆) = O(log ∆) and δ = log−4 ∆, we have d′τ ≤ (1 + δ)τ ∆ = (1 + o(1))∆. Therefore d′τ +s ≤ (1 + o(1))e−cs/2 ∆ for every s ≥ 0 for which the rounds τ + 1, . . . , τ + s are still executed. Choosing A > 14/c, we obtain ∆ ∆ < = dstop . d′τ +A log log ∆ ≤ (log ∆)7 (log ∆)6 Let ℓ be the first round with d′ℓ ≤ dstop . Then ℓ ≤ τ + A log log ∆ = O(k + log log ∆), and (6) implies pj > T for every j ∈ [τ, ℓ]. Since pj = βj pj−1 and 0 < βj ≤ 1 for every j, the sequence (pj )j≥0 is nonincreasing. Therefore pj ≥ pℓ > T for every 1 ≤ j ≤ ℓ. This proves the lemma.

5.3

Proofs of the Resilience Propositions

Throughout this subsection, fix a round i, assume Fi−1 holds and d′i−1 > dstop , and let Φ = (Φ1 , . . . , Φr ) be an r-partition with parameters min{d′i−1 , ∆} and t′i−1 in the sense of Definition 6 from Section 3.2. Thus, for every active vertex u, every color c ∈ Pi−1 (u), and every part Φj , |Ni−1 (u) ∩ Φj | ≤

100 min{d′i−1 , ∆} 100d′i−1 ≤ r r

and

|Ni−1,c (u) ∩ Φj | ≤

100t′i−1 . r

Let Vi1 and Vi2 be independent copies of the round-i variables, and for S ⊆ Φj let ZiS denote the mixed-sample version of any round-i random object Zi , as in Section 2.2.2. We write d for the dependency degree of the round-i event graph, so d ≤ ∆4 . The proofs of Propositions 20 and 22 follow the proofs of Propositions 12 and 14 from Section 4, with the necessary changes in the constants involved. We therefore focus only on Proposition 21, which is the only genuinely new point in the girth-5 case. Fix once and for all a signature map σ that chooses one color from each nonempty set of colors. Proof of Proposition 21. Fix u, c ∈ Pi−1 (u), a part Φj , and S ⊆ Φj . For this proof only, let bi,c (u) := {x ∈ Ni−1,c (u) ∩ Ui : c ∈ Pbi (x)}. N

Since every vertex of Ni,c (u) lies in Ni−1,c (u) ∩ Ui and satisfies Pi (x) ⊆ Pbi (x), we have Ni,c (u) ⊆ bi,c (u). Hence it is enough to prove resilience for N 



′ b + (u, c) := |N bi,c (u)| > t′ H i−1 (1 + δ)αi βi + i

30

300 r





+ δT .

Let

n

o

b i (u, c) := |N bi,c (u)| > t′ (1 + δ)αi β ′ + δT . H i−1 i

b i (u, c)] ≤ ∆−200 for ∆ ≥ ∆ε . Define By Lemma 24 from Appendix A, we have P[H n

o

i

h

e i (u, c) := H b i (u, c) ∪ P 2 (H b i (u, c)){u} ≥ d−15 . H V i

Since the mixed sample with resampling set {u} has the same distribution as the original round-i sample, we have h h ii b i (u, c)){u} V 1 = P[H b i (u, c)] ≤ ∆−200 . EV 1 PV 2 (H i i

i

Hence Markov’s inequality gives h

h

i

i

b i (u, c)){u} V 1 ≥ d−15 ≤ d15 ∆−200 ≤ d−35 , PV 1 PV 2 (H i i

i

because d ≤ ∆4 . Therefore e i (u, c)] ≤ P[H b i (u, c)] + d−35 ≤ 2d−35 . PV 1 [ H i

For any round-i random object Zi , let Zi⋆ denote the sample obtained by first resampling u if u ∈ S, and otherwise leaving the first sample unchanged. Thus Zi⋆ is either the first sample itself or the mixed sample in which only u is resampled. If u ∈ S, fix an arbitrary realization b S (u) with N b ⋆ (u). ξu of Xi2 (u); if u ∈ / S, no additional conditioning is needed. We compare N i,c i,c b S (u) \ N b ⋆ (u) is produced by one of the following three effects. Every vertex in N i,c i,c The first effect is the direct contribution of the resampled block itself: b S (u). ∆S1 := Φj ∩ N i,c

By the definition of an r-partition, |∆S1 | ≤ |Φj ∩ Ni−1,c (u)| ≤

100t′i−1 . r

The second effect is that a vertex x ∈ Ni−1,c (u) \ Φj may satisfy c ∈ PbiS (x) \ Pbi⋆ (x). Define n

o

b S (u) \ N b ⋆ (u) : x ∈ ∆S2 := x ∈ N / Φj , c ∈ / Pbi⋆ (x) , i,c i,c

and n

o

Ai,j (u, c) := x ∈ Ni−1,c (u) \ Φj : c ∈ Sel1i (y) for some y ∈ (Φj \ {u}) ∩ Ni−1,c (x) . Then ∆S2 ⊆ Ai,j (u, c), because the ⋆-sample and the S-sample agree outside S \ {u} ⊆ Φj \ {u}, and therefore the only way for a vertex x ∈ / Φj to satisfy c ∈ PbiS (x) \ Pbi⋆ (x) is that some vertex of (Φj \ {u}) ∩ Ni−1,c (x) selected c in the ⋆-sample. For each fixed x ∈ Ni−1,c (u) \ Φj , PV 1 [x ∈ Ai,j (u, c)] ≤ πi · |(Φj \ {u}) ∩ Ni−1,c (x)| ≤ i

100 . Kr

Moreover, if x ̸= x′ are distinct vertices in Ni−1,c (u) \ Φj , then Ni−1,c (x) ∩ (Φj \ {u}) ∩ Ni−1,c (x′ ) ∩ (Φj \ {u}) = ∅,

for otherwise some vertex z ∈ Φj \ {u} adjacent to both x and x′ would create a cycle of length 4 on the vertices {u, x, z, x′ }. Hence the indicators of the events x ∈ Ai,j (u, c) are independent. Let ( ) 100t′i−1 Ji,j (u, c) := |Ai,j (u, c)| > . r 31

Since |Ni−1,c (u)| ≤ t′i−1 , the random variable |Ai,j (u, c)| is a sum of independent Bernoulli variables with mean µA := EV 1 [|Ai,j (u, c)|] ≤ 100t′i−1 /(Kr). Hence 100t′i−1 /r ≥ KµA . Applying i the Chernoff bound in the form P[X ≥ aµ] ≤ (e/a)aµ for a ≥ 1, with X = |Ai,j (u, c)|, µ = µA , and a = K, gives  100t′ /r i−1 e ≤ d−35 PV 1 [Ji,j (u, c)] ≤ i K for ∆ ≥ ∆ε , because t′i−1 ≥ T = ∆ε1 /3, r = (log ∆)20 , and d ≤ ∆4 . b ⋆ (u) but belong The third effect is that a vertex x ∈ Ni−1,c (u) \ Φj may fail to belong to N i,c b S (u) because the resampling of S \ {u} causes x to become uncolored. Define to N i,c n

o

b S (u) \ N b ⋆ (u) : x ∈ ∆S3 := x ∈ N / Φj ∪ Ai,j (u, c) . i,c i,c

For each x ∈ Ni−1,c (u) \ Φj , let 



Lx := Sel⋆i (x) ∩ Ki⋆ (x) \ Sel⋆i (Ni−1 (x) \ Φj ) ∪ {u} . Thus Lx is the set of colors selected by x that remain available after deleting the conflicts created by the neighbors of x in (Ni−1 (x) \ Φj ) ∪ {u}. Equivalently, the only vertices that can still delete a color from Lx are the vertices of (Φj \ {u}) ∩ Ni−1 (x). Write σ(x) := σ(Lx ) whenever Lx ̸= ∅. If Lx = ∅, set YxS := 0; otherwise, let YxS be the indicator of the event that some vertex of (S \ {u}) ∩ Ni−1,σ(x) (x) selects σ(x) in the second sample; that is, h

i

YxS = 1 σ(x) ∈ SelSi (y) for some y ∈ (S \ {u}) ∩ Ni−1,σ(x) (x) . b ⋆ (u), it follows that x is If x ∈ ∆S3 , then x ∈ / Ai,j (u, c), so c ∈ Pbi⋆ (x). Since also x ∈ / N i,c ⋆ ⋆ b colored in the ⋆-sample. Hence Seli (x) ∩ Pi (x) ̸= ∅, and every color in this set belongs to b S (u), so x is uncolored in the S-sample. Lx ; in particular, Lx ̸= ∅. On the other hand, x ∈ N i,c Therefore the color σ(x) ∈ Lx is deleted in the S-sample, which means that σ(x) ∈ SelSi (y) for some y ∈ (S \ {u}) ∩ Ni−1,σ(x) (x). Thus YxS = 1, and hence

∆S3 ⊆ {x : YxS = 1}. For each x with Lx ̸= ∅, we have h

i

PV 2 YxS = 1 | Vi1 , Xi2 (u) = ξu ≤ πi · |(S \ {u}) ∩ Ni−1,σ(x) (x)| ≤ πi · i

100t′i−1 100 ≤ . r Kr

Also, since G is girth-5, the indicators YxS are independent. Let Y S :=

X

YxS .

x∈Ni−1,c (u)\Φj

Then EV 2 [Y S | Vi1 , Xi2 (u) = ξu ] ≤ 100t′i−1 /(Kr). Writing µY := EV 2 [Y S | Vi1 , Xi2 (u) = ξu ], we i i therefore have 100t′i−1 /r ≥ KµY . Applying the same Chernoff bound with X = Y S , µ = µY , and a = K, we obtain "

PV 2 Y i

S

100t′i−1 > r

#

Vi1 , Xi2 (u) = ξu



≤

e K

100t′

i−1 /r

≤ d−15

again because t′i−1 ≥ T = ∆ε1 /3, r = (log ∆)20 , and d ≤ ∆4 . e i (u, c) and Ji,j (u, c) do not occur. Then |∆S | ≤ |Ai,j (u, c)| ≤ 100t′ /r. Now assume that H 2 i−1 Also, h i b i (u, c))⋆ | V 1 , ¬H e i (u, c) < d−15 . PV 2 (H i i

32

On the event

( b i (u, c))⋆ ∩ ¬(H

Y

S

100t′i−1 ≤ r

)

,

the three effects give b S (u)| ≤ |N b ⋆ (u)| + |∆S | + |∆S | + |∆S | |N i,c i,c 1 2 3

≤ t′i−1 (1 + δ)αi βi′ + δT + = t′i−1



(1 + δ)αi βi′ +

300 r

100t′i−1 100t′i−1 100t′i−1 + + r r  r + δT.

b + (u, c))S can occur only if either (H b i (u, c))⋆ occurs or Y S > 100t′ /r. Since ξu Therefore (H i−1 i was arbitrary, averaging over Xi2 (u) when u ∈ S and taking a union bound gives h

i

b + (u, c))S | V 1 , ¬H e i (u, c), ¬Ji,j (u, c) ≤ 2d−15 < d−10 . PV 2 (H i i i

Finally,

h

i

e i (u, c) ∪ Ji,j (u, c) ≤ 3d−35 < d−30 . PV 1 H i

b + (u, c), and hence H + (u, c), is resilient with respect to Φ. Thus H i i

6

Conclusions

We have shown improved distributed algorithms for coloring triangle-free graphs, by improving the distributed Lovász Local Lemma steps that were previously the bottleneck in the algorithm of Pettie and Su [30]. This was achieved by adapting the algorithm and analysis of Pettie and Su to fit the LLL calls into the resilient partition framework of [11]. The LLL instances we solved here are arguably the most complex and difficult such instances yet to be solved in logO(1) log n rounds of LOCAL, and mark another step towards efficient distributed algorithms for the general LLL. For future work there are several interesting open questions:

6.1

General LLL.

Despite recent progress, an exponential gap still remains in the complexity of the general distributed LLL. Can a logO(1) log n round algorithm that solves all LLL instances (perhaps with polynomially weakened criteria, as in [13, 11], or can the Ω(log log n)-round lower bound of [6] be improved?

6.2

Special cases of the LLL.

If no efficient general LLL algorithm can be found, can we further identify applications with efficiently-solvable LLL instances, such as in other vertex coloring or degree splitting problems? In particular, this work indicates that LLL instances in which the bad events are failure to satisfy some concentration bounds, and in which we have some slack in the amount of allowable error, are prime candidates for solving quickly using [11].

6.3

Triangle-free coloring.

Molloy [28] showed that the constant in the number of colors needed for coloring triangle-free coloring can be improved from 4 to 1, but no (nontrivial) distributed algorithm yet exists to match this bound. Can such an algorithm be devised, and if so (since it will almost certinly involve LLL calls as in [28]) can the LLL instances therein be efficiently solved, similarly to this work? 33

References [1] Miklós Ajtai, János Komlós, and Endre Szemerédi. A note on ramsey numbers. Journal of Combinatorial Theory, Series A, 29(3):354–360, 1980. doi:10.1016/0097-3165(80) 90030-8. [2] Leonid Barenboim, Michael Elkin, and Fabian Kuhn. Distributed (∆ + 1)-coloring in linear (in ∆) time. SIAM Journal on Computing, 43(1):72–95, 2014. doi:10.1137/12088848X. [3] Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 321–330, 2012. doi:10.1109/FOCS.2012.60. [4] Anton Bernshteyn. The johansson-molloy theorem for dp-coloring. Random Structures & Algorithms, 54(4):653–664, 2019. doi:10.1002/rsa.20811. [5] Béla Bollobás. Chromatic number, girth and maximal degree. Discrete Mathematics, 24(3):311–314, 1978. doi:10.1016/0012-365X(78)90102-4. [6] Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed lovász local lemma. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 479–488, 2016. doi:10.1145/2897518.2897570. [7] Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. Distributed edge coloring and a special case of the constructive lovász local lemma. ACM Transactions on Algorithms (TALG), 16(1):1–51, 2019. [8] Yi-Jun Chang, Wenzheng Li, and Seth Pettie. Distributed (∆+1)-coloring via ultrafast graph shattering. SIAM Journal on Computing, 49(3):497–539, 2020. doi:10.1137/19M1249527. [9] Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the LOCAL model. SIAM Journal on Computing, 48(1):33–69, 2019. doi:10.1137/17M1157957. [10] Kai-Min Chung, Seth Pettie, and Hsin-Hao Su. Distributed algorithms for the lovász local lemma and graph coloring. Distrib. Comput, 30:261–280, 2017. [11] Peter Davies. Improved distributed algorithms for the lovász local lemma and edge coloring. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4273–4295, 2023. doi:10.1137/1.9781611977554.ch163. [12] Peter Davies-Peck. On the locality of the lovász local lemma. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1271–1282, 2025. [13] Manuela Fischer and Mohsen Ghaffari. Sublogarithmic distributed algorithms for lovász local lemma, and the complexity hierarchy. In 31st International Symposium on Distributed Computing (DISC 2017), volume 91 of LIPIcs, pages 18:1–18:16, 2017. doi:10.4230/ LIPIcs.DISC.2017.18. [14] Mohsen Ghaffari and Christoph Grunau. Near-optimal deterministic network decomposition and ruling set, and improved mis. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 2148–2179, 2024. doi:10.1109/FOCS61266.2024.00007. [15] Mohsen Ghaffari, Christoph Grunau, and Václav Rozhoň. Improved deterministic network decomposition. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2211–2231, 2021. doi:10.1137/1.9781611976465.131. 34

[16] Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. On derandomizing local distributed algorithms. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 662–673, 2018. doi:10.1109/FOCS.2018.00069. [17] David A. Grable and Alessandro Panconesi. Fast distributed algorithms for Brooks-Vizing colorings. Journal of Algorithms, 37(1):85–120, 2000. [18] Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin, and Tigran Tonoyan. Near-optimal distributed degree+1 coloring. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 450–463, 2022. doi:10.1145/3519935.3520023. [19] Magnús M Halldórsson and Yannic Maus. Distributed delta-coloring under bandwidth limitations. In 38th International Symposium on Distributed Computing (DISC 2024), pages 31–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2024. [20] Magnús M Halldórsson, Yannic Maus, and Alexandre Nolin. Fast distributed vertex splitting with applications. In 36th International Symposium on Distributed Computing (DISC 2022), pages 26–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2022. [21] David G. Harris, Johannes Schneider, and Hsin-Hao Su. Distributed (∆ + 1)-coloring in sublogarithmic rounds. Journal of the ACM, 65(4):19:1–19:21, 2018. doi:10.1145/3178120. [22] Mohammad Shoaib Jamall. A coloring algorithm for triangle-free graphs, 2011. Preprint. [23] Öjvind Johansson. Asymptotic choice number for triangle-free graphs. Technical Report 91-5, DIMACS, 1996. [24] Öjvind Johansson. Simple distributed ∆ + 1-coloring of graphs. Information Processing Letters, 70(5):229–232, 1999. [25] Jeong Han Kim. On brooks’ theorem for sparse graphs. Combinatorics, Probability and Computing, 4(2):97–132, 1995. doi:10.1017/S0963548300001638. [26] A. V. Kostochka. Degree, girth and chromatic number. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, volume 18 of Colloq. Math. Soc. János Bolyai, pages 679–696. North-Holland, 1978. [27] Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193–201, 1992. doi:10.1137/0221015. [28] Michael Molloy. The list chromatic number of graphs with small clique number. Journal of Combinatorial Theory, Series B, 134:264–284, 2019. doi:10.1016/j.jctb.2018.06.007. [29] Robin A. Moser and Gábor Tardos. A constructive proof of the general lovász local lemma. Journal of the ACM, 57(2):11:1–11:15, 2010. doi:10.1145/1667053.1667060. [30] Seth Pettie and Hsin-Hao Su. Distributed coloring algorithms for triangle-free graphs. Information and Computation, 243:263–280, 2015. doi:10.1016/j.ic.2014.12.018. [31] Václav Rozhoň and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 350–363, 2020. doi: 10.1145/3357713.3384298.

35

A

Auxiliary One-Round Concentration Bounds

Throughout this appendix, after fixing ϵ > 0, we assume ∆ ≥ ∆ε is large enough for all asymptotic inequalities below. This appendix records the one-round concentration bounds used in Section 4.2 and in Section 5.3. The first lemma concerns triangle-free graphs from Section 4.3, where the relevant one-round events are Qi (u), Hi (u), and Mi (u). The second lemma concerns the girth-5 graphs from Section 5.3. Lemma 23. Assume G is triangle-free, and fix a round i of Algorithm 3. Suppose Fi−1 holds and d′i−1 > dstop . Then, for every active vertex u, P[Qi (u)], P[Hi (u)], P[Mi (u)] ≤ ∆−300 , Proof. Fix an active vertex u. In our notation, the palette lower-tail event Qi (u) is exactly the event treated in [30, Lemma 5], and the averaged c-degree event Hi (u) is exactly the event treated in [30, Lemma 6]. Therefore P[Qi (u)], P[Hi (u)] ≤ exp −Ω(δ 2 p′i ) .

For Mi (u), let Zu := |Ni (u)| = Eu :=

\

¬Qi (v),

v∈Ni−1 (u) Iv , where Iv := 1{v∈Ui } , and expose

P

G := σ Xi (x) : x ∈ / Ni−1 (u), Ki (v) : v ∈ Ni−1 (u) .

v∈Ni−1 (u)

Because Gi−1 is triangle-free, vertices of Ni−1 (u) are pairwise non-adjacent. Hence, for each v ∈ Ni−1 (u), once G is fixed, the indicator Iv depends only on Xi (v); therefore {Iv : v ∈ Ni−1 (u)} are independent Bernoulli variables conditioned on G. By the bound for Qi (·) established above and a union bound over |Ni−1 (u)| ≤ d′i−1 ≤ 2∆, we have
P[¬Eu ] ≤ exp −Ω(δ 2 p′i ) . Now fix a realization of G for which Eu holds. Then for every v ∈ Ni−1 (u), 

|Pei (v)| ≥ |Pi−1 (v)|βi 1 − Also, Fact 15 from Section 4 gives |Pi−1 (v)| ≥ i = O(log ∆). Therefore,



δ |Pi−1 (v)|βi 1 − ≥ 8 

1 2 − o(1)



δ . 8 pi−1 , and p′i = (1 − δ/7)i βi pi−1 with

(1 + δ)i−1 1− 2

!

p′i .

Since Pei (v) is G-measurable and Seli (v) is independent of G, we obtain P[Iv = 1 | G] = (1 − πi )|Pi (v)| ≤ αi . e

Hence µu := E[Zu | G, Eu ] ≤ αi d′i−1 . Applying the Chernoff bound conditional on G, with η = δ/40, we obtain P [Mi (u) | G, Eu ] ≤ P [Zu > (1 + η)µu | G, Eu ] ≤ exp −Ω(δ 2 d′i−1 ) ,

since (1 + η)µu ≤ αi (1 + δ/5)d′i−1 . Averaging over G and adding the failure probability of Eu yields

P[Mi (u)] ≤ exp −Ω(δ 2 p′i ) + exp −Ω(δ 2 d′i−1 ) . As δ = 1/ log4 ∆, Theorem 11 gives p′i = Ω(T ) with T = ∆ε1 /3 , and d′i−1 > dstop = ∆/(log ∆)6 . Hence δ 2 p′i = Ω(∆ε1 /3 / log8 ∆) and δ 2 d′i−1 ≥ ∆/(log ∆)14 , so both exponents dominate 302 log ∆. Therefore P[Qi (u)], P[Hi (u)], and P[Mi (u)] ≤ ∆−300 . 36

Lemma 24. Assume G has girth at least 5, and fix a round i of Algorithm 4. Suppose Fi−1 holds and d′i−1 > dstop . For every active vertex u and color c ∈ Pi−1 (u), let bi,c (u) := {x ∈ Ni−1,c (u) ∩ Ui : c ∈ Pbi (x)}. N

Then

h

i

bi,c (u)| > t′ (1 + δ)αi β ′ + δT ≤ ∆−200 , P |N i−1 i bi,c (u)| is exactly the quantity controlled in [30, Lemma 10], Proof. In the notation of this paper, |N and [30, Corollary 5] therefore gives h

i

bi,c (u)| > t′ (1 + δ)αi β ′ + δT ≤ exp −Ω(δ 2 T ) . P |N i−1 i

In our settings, δ = 1/ log4 ∆ and T = ∆ε1 /3, so δ 2 T = Θ(∆ε1 / log8 ∆) ≫ log ∆. Hence exp(−Ω(δ 2 T )) ≤ ∆−200 , which proves the lemma.

37

Related documents

• Contribution à l'étude de quelques problèmes de coloration de graphes#370924
• Bounds for B-coloring planar and outerplanar graphs#818487
• $(2,\mathcal{F})$-Avoiding Coloring and B-Coloring under Bipartite Exclusions#1144883
• A Fast Deterministic Algorithm for $(Δ+1)$-edge coloring in CONGEST#467095
• Fixed-parameter algorithms for the cocoloring problem#326488