PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic $(\Delta+1)$ Vertex Coloring with Adaptive Adversaries: Entropy Compression to the Rescue

Sepehr Assadi, Helia Yazdanyar

arXiv:2610.38787v1cs.DS

TL;DR

Maintaining a fully dynamic (∆+1) coloring against an adaptive adversary with sublinear update time remained an open question. The paper continuously handles sparse vertices using dynamic entropy compression, and gives an algorithm with eO(√n) amortized update time. Its Resample analysis does not guarantee fixing a flaw when all neighbors have small available-color sets.

  • Problem

    Earlier fast (∆+1)-coloring algorithms worked against oblivious adversaries, while the best adaptive update time was eO(n2/3), leaving open whether o(n2/3) was possible.

    Source: §1 · p. 3

  • Method

    The algorithm complements prior dense-graph techniques by continuously maintaining sparse-vertex coloring without restarts, using dynamic entropy compression to analyze a dynamic process.

    Source: §1.1 · p. 4

  • Results

    eO(√n) amortized update time maintains a (∆+1) coloring against an adaptive adversary with high probability, answering 's open question and reaching its identified fundamental limit.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The result settles [FH25]'s question about improving on eO(n2/3) update time for adaptive (∆+1) coloring.

    Source: §1 · p. 3

    Resample(v) is not guaranteed to fix v when every neighbor has a small available-color set.

    Source: Our Algorithm for Coloring Sparse… · p. 10

Abstract

from arXiv · show

We present a randomized algorithm for maintaining a $(\Delta+1)$ vertex coloring of a fully dynamic graph against an adaptive adversary with $\tilde{O}(\sqrt{n})$ amortized update time. Our algorithm improves upon the recent randomized algorithms of Behnezhad, Rajaraman, and Wasim (SODA 2025) with $\tilde{O}(n^{8/9})$ and Flin and Halld\'orsson (ICALP 2025) with $\tilde{O}(n^{2/3})$ amortized update time. Our result (nearly) matches a fundamental limit of $O(\sqrt{n})$ update time identified by Flin and Halld\'orsson and settles their main open question. The previous algorithms' main improvement came from efficient coloring of the dense parts of the graph. Our approach complements these prior work by handling the sparse parts more efficiently, using ideas inspired by the recently developed dynamic entropy compression method. A key new aspect of our work is to tailor this method specifically to dynamic algorithms---as opposed to original local search algorithms---and achieve update times that can be sublinear in the number of involved constraints per update.

1 Introduction

Dynamic (∆+1) coloring against adaptive adversaries remained open beyond the naive O(∆) update time. This paper answers the open question of with an eO(√n) amortized update-time algorithm and replaces the fragile sparse-vertex approach with dynamic entropy compression.

1 Introduction

  • For (∆+1)-coloring against adaptive adversaries, gave randomized eO(n8/9) update time, improved by to randomized eO(n2/3), prompting the question of achieving o(n2/3) update time.The cited results [BCHN18] work only against oblivious adversaries, meaning edge updates are fixed in advance and cannot adapt to the algorithm’s output.Source: §1 · p. 3
  • eO(√n) amortized update time maintains a (∆+1) coloring against an adaptive adversary with high probability, answering the open question of.The result reaches the fundamental limit identified in.Source: §1 · p. 3
  • A randomized algorithm maintains a (1−Θ(γ))∆-coloring of dynamic γ-sparse graphs in eO(√n/γ) amortized update time with high probability.This corollary gives a dynamic counterpart to the classical sparse-graph coloring result of.Source: §1 · p. 4

1.1 Our Techniques

  • Prior approaches relied on fragile sparse-vertex coloring that needs a full rerun every Θ(∆) updates, with a sparse-coloring run costing nearly Θ(n2/∆).This yields an Ω(n2/3) worst-case barrier for those approaches, identified by.Source: §1.1 · p. 4
  • The paper complements by continuously maintaining sparse-vertex coloring without restarts, using dynamic entropy compression inspired by and developed in [AY26] [HMR+26].A key contribution is adapting the method to analyze an inherently dynamic process and obtain update times sublinear in the number of involved constraints.Source: §1.1 · p. 4
  • The algorithm also changes dense-vertex handling, removes phases and restarts there, and obtains high-probability guarantees amortized over updates.These are three distinctions from, alongside the new sparse-vertex approach.Source: §1.1 · p. 5

2 Preliminaries

The preliminaries define the dynamic graph, coloring, adversary, and performance conventions used in the paper. They also introduce random color trials, whose expected runtime depends on the number of colors available to the vertex.

Definitions

  • A partial coloring assigns colors or blank status to vertices; blanks may be adjacent, and slack counts extra available colors, with slack at least one for every (∆+1) coloring.The color class Cc is the set of vertices assigned color c.Source: §2 · p. 5

Background

  • A Θ(√n) vertex-recoloring cost is described as a limit of current random-trial-based algorithms, not as a formal lower bound.The passage separately notes a formal Ω(n√n) lower bound for static (∆+1) coloring time.Source: §2 · p. 5

Dynamic graphs

  • The dynamic graph starts empty and changes by one edge insertion or deletion per update; ∆ is known in advance and bounds every vertex degree throughout.An adaptive adversary may choose updates from prior algorithm outputs, while recourse counts output changes after one update.Source: §2 · p. 6

Concentration Inequalities

  • The paper invokes Chernoff-Hoeffding bounds and later uses specialized concentration tools, including Talagrand’s inequality and adaptive Chernoff bounds.The stated standard bound applies to independent random variables in [0,b].Source: §2 · p. 6

Random Color Trials

  • RandomColorTrial repeatedly samples a color for v and assigns it if no neighbor has that color, finding an available color in expected O(n/availφ(v)) time.The runtime analysis uses the expected color-class size and the probability that a sampled color is available.Source: §2 · pp. 6–7

3 Technical Overview

The overview explains how the algorithm handles sparse and dense vertices to achieve eO(√n) amortized update time, using need-based resampling and dynamic entropy compression for sparse vertices and adapting the dense-vertex approach.

Background: Sparse-Dense Decompositions and One-Shot Coloring

  • Sparse-dense decomposition gives sparse vertices Ω(∆) coloring slack through one-shot coloring, while grouping dense vertices into almost-cliques that can be colored using their structure.Sparse vertices have Ω(∆²) missing neighborhood edges; almost-cliques can be turned into (∆+1)-cliques by adding or removing an o(1) fraction of vertices and edges.Source: Background: Sparse-Dense… · pp. 7–8

Sparse-Dense Decompositions and One-Shot Coloring in [BRW25,FH25]

  • [BRW25] and use Θ(∆)-update phases to refresh sparse-vertex slack, making eO(n²/∆²) amortized time the bottleneck and yielding an eO(n²/³) bound.Maintaining the decomposition takes O(log n) amortized update time for and this work, but the phased one-shot coloring cost dominates the prior sparse-vertex approach.Source: Sparse-Dense Decompositions and… · p. 8

Coloring Sparse Vertices without Phases and Restarts?

  • Avoiding phases requires preserving Ω(∆) slack at all times; although dynamic entropy compression [HMR+26] ensures convergence, its O(∆²) or O(∆³) update cost defeats the goal, motivating a dynamic, need-based alternative.Local fixes can propagate violations; the paper instead notes that this problem need not be treated as a static LLL problem.Source: Coloring Sparse Vertices without… · pp. 8–9

Our Algorithm for Coloring Sparse Vertices

  • The algorithm maintains a partial coloring φ⋆ and fixes flaws only when needed: after AttemptColor fails, it resamples a vertex’s neighbors, cleans up conflicts, and resamples updated-edge endpoints.AttemptColor samples Θ(log n) colors and takes eO(n/∆) expected time when the vertex has Ω(∆) slack; Resample samples neighbors using φ⋆, followed by cleanup in the output coloring φ.Source: Our Algorithm for Coloring Sparse… · pp. 9–10
  • With Ω(∆²) anti-edges and blocked sets of size at most ∆/4, the resampling process leaves fewer than Ω(∆) same-colored anti-edges with probability at most 2^-Ω(∆).When every neighbor has at least 3∆/4 available colors, this guarantee makes Resample fix the sparse vertex’s flaw with high probability.Source: Our Algorithm for Coloring Sparse… · pp. 10–11

The Analysis of Our Algorithm for Coloring Sparse Vertices

  • O(t/∆) Resample calls over t updates with high probability, at eO(n) expected work per call, imply eO(n/∆) amortized update time and eO(√n) after balancing against O(∆).A Resample call takes O(n) expected time and uncolors O(∆) vertices in expectation; the analysis accounts for subsequent cleanup and AttemptColor work.Source: The Analysis of Our Algorithm for… · pp. 11–12
  • The call-count proof uses a per-vertex randomness table and an algorithm–adversary log to reconstruct φ⋆, then bounds long consistent logs by counting logs and checking their probability.The table supplies each vertex’s sampling decisions and colors; the log records updates and Resample calls, enabling the consistency analysis.Source: The Analysis of Our Algorithm for… · pp. 12–13
  • For r ≳ (t·log n)/∆, the probability of more than r Resample calls in t updates is negligibly small, assuming ∆ ≳ log n.The bound is n^O(r+t) · 2^-Ω(r·∆); the analysis uses a per-call flaw probability of 2^-Ω(∆).Source: The Analysis of Our Algorithm for… · p. 13

3.3 Handling Dense Vertices

  • Dense vertices remain technically challenging, but the paper identifies handling sparse vertices—not dense vertices—as its main conceptual novelty.The dense-vertex techniques largely follow prior work and.Source: §3.3 · p. 14

Prior Approach of [FH25] for Dense Vertices

  • [FH25] treats almost-cliques with average out or anti at least η as sparse, using Θ(η)-length phases; for the rest, inlier-outlier partitioning and anti-edge matching support an eO(n^2/3) bound.For the remaining almost-cliques, the method bounds out and anti per vertex by O(η), and anti-edge matching limits the search to out(v) external neighbors; η = n^2/3 balances against O(∆).Source: Prior Approach of [FH25] for Dense… · pp. 14–15

A Challenge for Improving Update Time on Dense Vertices?

  • Delegating almost-cliques with sparsity γ ≈ η/∆ creates a bottleneck: resampling still uncolors O(∆) vertices, and coloring the resulting O(∆/η) vertices can prevent improvement over eO(n^2/3).The authors’ key observation is that these delegated almost-cliques have additional structure beyond arbitrary γ-sparse vertices.Source: A Challenge for Improving Update Time… · p. 15

Our Approach for Dense Vertices

  • For out-heavy almost-cliques, Resample(v) leaves an expected O(out(v)) uncolored vertices outside the clique, while a new sublinear-time method colors all but O(η) vertices in eO(n) time.The approach separately handles high-average-anti cliques with prior dense-vertex methods and uses entropy compression for out-heavy cliques.Source: Our Approach for Dense Vertices · pp. 15–16
  • With η = √n, the dense-vertex algorithm achieves eO(√n) amortized update time, balanced against the O(∆)-time algorithm.The passage states this bound for coloring dense vertices.Source: Our Approach for Dense Vertices · p. 16

Oversimplified Details and High Probability Guarantees

  • The analysis assigns costs to logs to handle varying sparsities, and uses [KQ25, Proposition 4.17] for runtime concentration over an adaptive sequence rather than a per-update high-probability guarantee.Overall success remains only with high polynomial probability because the decomposition subroutine’s existing proof gives only that bound.Source: Oversimplified Details and High… · p. 16

4 A Fully Dynamic Algorithm for (∆+ 1) Coloring

The algorithm maintains a proper (∆+1) coloring against adaptive adversaries by combining a sparse-dense decomposition with separate procedures for sparse and dense vertices.

4 A Fully Dynamic Algorithm for (∆+ 1) Coloring

  • O(√n · log3 n) amortized update time maintains a (∆+1) coloring against adaptive adversaries with high probability.Theorem 1 formalizes the paper’s main result.Source: §4 · p. 17

4.1 The Sparse-Dense Decomposition

  • The sparse-dense decomposition partitions vertices into sparse vertices and almost-cliques, and a dynamic algorithm maintains this structure.The maintained decomposition tracks almost-clique membership and each vertex’s ANTI and OUT sets.Source: §4.1 · pp. 17–18

Classification of Almost-Cliques

  • Almost-cliques are classified as anti-heavy, out-heavy, or out-light; the dynamic classification changes classes only O(1/(ε2η∆)) times per update amortized.The paper also generalizes the out-heavy sparsity guarantee to depend on out(v) separately.Source: Classification of Almost-Cliques · pp. 18–19

4.2 Setup and Invariants

  • The algorithm maintains the decomposition and classification alongside a partial coloring φ⋆, then treats sparse vertices and out-heavy vertices as sparser and the remaining classes as denser.The output coloring agrees with φ⋆ on colored vertices.Source: §4.2 · p. 19, Sparser Vertices S := Vsparse ∪KOH · p. 19

Sparser Vertices S := Vsparse ∪KOH

  • For sparser vertices, flaws identify vertices with high sparser-neighbor degree but insufficient slack; the algorithm fixes these flaws only when needed.The relevant conditions combine graph-determined vertex categories with slack measured under φ⋆.Source: Sparser Vertices S := Vsparse ∪KOH · pp. 19–20

Vertices in D := V (KAH) ∪V (KOL)

  • For each almost-clique in KAH ∪ KOL, the algorithm maintains a colorful anti-matching whose uniquely used paired colors preserve colors for other vertices.A colorful anti-matching pairs same-colored anti-edges, with each pair’s color absent from other vertices in the almost-clique.Source: Vertices in D := V (KAH) ∪V (KOL) · p. 20

Old Subroutines

  • ExpandAntiMatching restores the anti-matching invariant, ColorDenser colors denser vertices without creating blanks, and AttemptColorSparser tries to color sparse vertices but can fail.Their expected runtimes are O(b · n/∆), O(n/∆ + n/η + η), and O(n log n/η), respectively.Source: Old Subroutines · pp. 21–22

New Subroutines

  • New routines include PartialColorOH, which colors all but 4 · out(K) blanks, and UpdateSparserColor, which dynamically handles sparse vertices when AttemptColorSparser fails.The paper also introduces SampleColor for sparser vertices; the new approach departs from prior work by handling this part dynamically.Source: New Subroutines · pp. 22–23

4.4 The Dynamic Algorithm

After each edge update, the algorithm updates its decomposition and processes blank vertices until the coloring is proper and complete. Its analysis bounds the total time and blank-vertex generation across updates.

4.4 The Dynamic Algorithm

  • Each update samples colors for affected sparser vertices, refreshes the decomposition, processes blank sparser vertices, restores anti-matching invariants, and colors denser blanks.If AttemptColorSparser fails, UpdateSparserColor is called; the algorithm maintains a proper (∆+1) coloring with high probability when it terminates.Source: §4.4 · pp. 23–24

4.5 Proof of Theorem 1

  • With η = √n · log n, UpdateSparserColor takes O(t · n log4 n/η) total time over t updates, yielding O(t√n · log3 n).The proof uses concentration bounds that allow successive random-variable distributions to depend on prior outcomes.Source: §4.4 · p. 24, §4.5 · pp. 24–25

5 Update Time Analysis of our Dynamic Algorithm

This section analyzes UpdateSparserColor, including its dynamic entropy-compression log for resampling and bounds on its runtime and the number of vertices left uncolored. It also describes how the algorithm monitors Flaw 3.

5.1 The UpdateSparserColor Subroutine

  • SampleColor(v) takes expected O(n/∆) time and uncolors O(1) vertices in expectation.It samples a color class and assigns the sampled color only when that class contains no neighbor of v.Source: §5.1 · p. 26
  • When UpdateSparserColor(v) terminates, it preserves proper partial colorings and invariants 1 and 2, returns changed or uncolored vertices, and does not color denser vertices in φ⋆.Source: §5.1 · p. 27
  • A Resample(v) call, with PartialColorOH(K(v)) when applicable, takes expected O(n log n) time and uncolors O(cost(v)) vertices in expectation.For v ∈ V(KOH), Resample leaves at least 4∆/5 vertices of K(v) uncolored with high probability, enabling the PartialColorOH runtime bound.Source: §5.1 · pp. 27–28

5.2 Avoiding Yet Another Flaw

  • TestFlaw3 detects Flaw 3 or confirms a vertex is far from it with high probability in O(log n) time with certainty; CheckFlaw3 takes O(log^2 n) time with high probability, excluding Resample calls.CheckFlaw3 uses lazy neighborhood checks, invoking TestFlaw3 on sampled neighbors after changes to G[S] or φ⋆.Source: §5.2 · p. 30
  • With high probability, CheckFlaw3 triggers Resample before a vertex exceeds 5δ · ∆ colored vertices in φ⋆ during the first polynomially many calls.This maintains an approximately Flaw 3-free state; Flaw 3 is defined by more than 4δ · ∆ colored vertices.Source: §5.2 · pp. 30–31

5.3 Dynamic Entropy Compression: Bounding Number of Calls to Resample

  • The journal representation yields at most n^5(t+r+d) distinct logs with t graph updates, d decomposition changes, and r Resample calls.The log records graph updates, decomposition changes, and Resample calls from UpdateSparserColor or CheckFlaw3.Source: §5.3 · pp. 31–32
  • A fixed log L is consistent with the random table, conditioned on E, with probability at most 2^-cost(L).The analysis assigns fresh, independent table entries to each resampling call and bounds consistency call by call.Source: §5.3 · pp. 34, 36
  • At most 2^{6(t+r+d) log n} possible (log, cost(L)) pairs arise for t updates, d decomposition changes, and r resampling calls.The proof combines the bound on possible logs with the number of possible cost values per fixed log.Source: §5.3 · p. 37

5.4 Proof of Lemmas 4.15 and 4.16

  • O(t log^2 n) uncolored vertices are caused by UpdateSparserColor over t updates with high probability.Each joint Resample and PartialColorOH call causes O(cost(v)) uncolored vertices in expectation.Source: §5.4 · p. 38
  • UpdateSparserColor causes O(t · log2 n) uncolored vertices over t updates with high probability.The bound applies over t = poly(n) updates.Source: §5.4 · p. 39
  • With high probability, UpdateSparserColor takes O(t · n log4 n/η) time over t updates.The bound combines O(t · n log3 n/η) for its main routines with the additional CheckFlaw3 cost.Source: §5.4 · pp. 39–40
  • With high probability, joint Resample and PartialColorOH calls take O(t · n log3 n/η) time, and AttemptColorSparser takes the same total time.Both bounds hold over t updates; the Resample and PartialColorOH bound assumes η = o(n) and t = Ω(m).Source: §5.4 · p. 40
  • TestFlaw3 takes O(t · ∆log3 n/η) time with high probability, while background CheckFlaw3 costs O(t log3 n) + O(t · ∆log2 n).The CheckFlaw3 bound accounts for graph updates, decomposition changes, and SampleColor calls.Source: §5.4 · p. 40

6 Handling Remaining Sparser Vertices

The section colors remaining sparser vertices without restarting, using random color trials for individual vertices and uncolored vertices in out-heavy almost-cliques. The guarantees bound both expected work and the number of vertices left uncolored.

6.1 The AttemptColorSparser Subroutine

  • AttemptColorSparser takes O(n log n/η) time in expectation and, absent Flaw 1 or Flaw 2, colors a sparser vertex with high probability while uncoloring O(1) denser vertices in expectation.The subroutine makes O(∆·log n/η) trials; the available-color conditions provide a probability of success.Source: §6.1 · p. 41

6.2 The PartialColorOH Subroutine

  • PartialColorOH uses random color trials on uncolored vertices, processing them in non-increasing order of out-degree until at most 4·out(K) remain.The expected number of trials for a vertex is O(∆/(i − 4·out(K))) while the process continues.Source: §6.2 · pp. 42–43
  • PartialColorOH colors all but 4·out(K) vertices of an out-heavy almost-clique in expected O(n log n) time, without recoloring or uncoloring any vertex.The guarantee applies when K has at least 4∆/5 uncolored vertices.Source: §6.2 · p. 42
  • For the first half of the processed vertices, at least (1/5 − 3ε)∆ colors are available, giving expected O(n/∆) time per vertex.The bound uses the initial number of colored vertices in K and out(vi) ≤ ε∆.Source: §6.2 · pp. 42–43

7 Handling Dense Vertices

The dense-vertex routines modify prior approaches by using an expanded anti-matching to maintain an invariant in almost-cliques, then coloring remaining dense vertices while preserving properness. Their expected costs depend on the number of anti-edges added and the vertex’s clique type.

7.1 The ExpandAntiMatching Subroutine

  • ExpandAntiMatching samples an anti-edge not incident on the current anti-matching and a color that is not overused in K or used in the endpoints’ outside neighborhoods.Adding an anti-edge can require recoloring at most one vertex in K and uncoloring at most one new vertex.Source: §7.1 · pp. 44–45
  • ExpandAntiMatching restores Invariant 3 by adding b anti-edges in expected O(b·n/∆) time, while preserving properness and creating O(b) uncolored vertices.The routine may recolor vertices in K and returns the new uncolored vertices.Source: §7.1 · p. 44

7.2 The ColorDenser Subroutine

  • ColorDenser handles inliers and outliers separately, using available colors for inliers and random trials satisfying conditions R1–R3 for outliers.The outlier case has at least ∆/8 remaining colors for sufficiently small constant ε, yielding expected O(n/∆) time to find an available color.Source: §7.2 · pp. 45–47
  • ColorDenser colors an uncolored denser vertex in expected O(n/∆ + n/η + η) time without creating new uncolored vertices, assuming Invariant 3 holds for its almost-clique.It may recolor vertices inside K while maintaining properness.Source: §7.2 · p. 46

A Omitted Proofs

The appendix contains proofs of results omitted from the paper’s main body.

A Omitted Proofs

A.1 Proof of Corollary 1.1

For dynamic γ-sparse graphs, the corollary gives an adaptive-adversary algorithm maintaining a (1 − Θ(γ))∆-coloring. Its amortized update time is eO(√n/γ) with high probability.

A.1 Proof of Corollary 1.1

  • eO(√n/γ) amortized update time suffices to maintain a (1 −Θ(γ))∆-coloring on dynamic γ-sparse graphs against an adaptive adversary, with high probability.The maximum degree ∆ must be sufficiently large with respect to γ.Source: §A.1 · p. 52
  • The proof runs Algorithm 1 without decomposition, treats every vertex as γ-sparse, and samples colors from a palette of (1 −Θ(γ))∆ colors.The modification yields Ω(γ·∆) slack for vertices.Source: §A.1 · p. 52
  • The proof bounds Resample calls by O(t/(γ·∆)) over t updates, using a 2^-Ω(γ∆) probability per call.It balances the resulting update-time bound at ∆ = √n.Source: §A.1 · p. 52

A.2 Proof of Lemma 4.4

The proof establishes that every vertex in an out-heavy almost-clique is γ-sparse, using a prior result for one degree case and a counting argument for the other.

A.2 Proof of Lemma 4.4

  • Every vertex in an out-heavy almost-clique is γ-sparse, as stated in the restatement of Lemma 4.4.The proof invokes the result of for out-heavy almost-cliques.Source: §A.2 · p. 52
  • When out(v) is at most 4·out(K), the prior lemma gives the required sparsity directly.The proof then uses that sparsity to infer γ-sparsity.Source: §A.2 · p. 53
  • For the larger-degree case, the proof considers neighbors of v in K and counts edges to OUT(v) against anti-edges.The counting uses almost-clique size bounds to obtain a contradiction when ε is sufficiently small, yielding the desired sparsity.Source: §A.2 · p. 53

A.3 Proof of Lemma 4.5

The algorithm maintains an η-classification alongside the sparse-dense decomposition. It bounds classification changes by using the amount of edge or anti-edge change needed before a class can change.

A.3 Proof of Lemma 4.5

  • The dynamic algorithm maintains the sparse-dense decomposition and its η-classification, with almost-clique class changes amortized O(1/(ε^2ηΔ)) per update.The classification-maintenance algorithm also provides the guarantees of Proposition 4.2.Source: §A.3 · p. 53
  • Newly formed almost-cliques are assigned to a class, while collapsed cliques are removed and remaining cliques are re-evaluated after each update.A clique that is removed from its current list is reassigned using the formation criteria.Source: §A.3 · pp. 53–54
  • A clique added to KAH needs Ω(ε^2ηΔ) dedicated updates before changing class again, bounding its KAH movements by O(1/(ε^2ηΔ)) per update.The argument uses the anti-edge threshold gap and the amortized rate of anti-set changes from Proposition 4.2.Source: §A.3 · p. 54
  • The same type of analysis bounds changes between other classes, and maintaining the η-classification adds only a constant-factor overhead over maintaining the decomposition.An edge update, like an anti-edge update, affects at most two almost-cliques.Source: §A.3 · p. 54

A.4 Proof of Proposition 4.17

The proposition extends an adaptive concentration result from to allow the sum of conditional means to exceed its threshold with small probability. Its proof truncates the process at that threshold and applies the γ=0 result.

A.4 Proof of Proposition 4.17

  • The proposition extends a result of from γ=0 to a setting where the adaptive sum of conditional means exceeds μ with probability at most γ.The variables are chosen sequentially by an adaptive adversary and lie in [0,c].Source: §A.4 · p. 54
  • The proof sets subsequent variables to zero once the running sum of conditional means exceeds μ, then applies the γ=0 result to the truncated sequence.The proof compares the original and truncated sums and uses a union bound.Source: §A.4 · pp. 54–55
  • The resulting tail bound for X includes an additive γ term: Pr(X ≥ (1 + δ)μ) is at most γ plus an exponential term.The displayed bound is obtained from the probability that the original and truncated sequences differ and the tail bound for the truncated sum.Source: §A.4 · p. 55

A.5 Proof of Lemma 4.18

The proof bounds the total runtime and uncolored vertices generated by the algorithm’s subroutines over t updates. In particular, it aggregates per-subroutine costs and bounds the calls to ExpandAntiMatching and ColorDenser.

A.5 Proof of Lemma 4.18

  • AttemptColorSparser takes O(t·n·log^3 n/η) time and causes O(t·log^2 n) uncolored vertices; SampleColor takes O(t·n·log n/Δ) time and causes O(t·log n) vertices.The SampleColor bounds account for calls associated with decomposition changes and direct updates.Source: §A.5 · p. 55
  • ExpandAntiMatching takes O(t·log^2 n·n/Δ) time and causes O(t·log^2 n) uncolored vertices; ColorDenser takes O(t·log^2 n·(n/Δ+η)) time and causes none.ColorDenser does not uncolor any vertex.Source: §A.5 · pp. 55–56
  • Across the relevant subroutines, the total uncolored vertices that may trigger ExpandAntiMatching are O(t·log^2 n) with high probability.The bound combines contributions from SampleColor, AttemptColorSparser, and UpdateSparserColor.Source: §A.5 · pp. 55–56
  • With high probability, total ExpandAntiMatching runtime is O(t·n·log n/Δ), with at most O(t·log^2 n) uncolored vertices generated.This follows by applying Proposition 4.17 to the aggregate subroutine costs and uncolored-vertex counts.Source: §A.5 · p. 56

A.6 Proof of Lemma 5.1

The proof analyzes randomly sampled colors among the neighbors of v. It uses concentration to relate sampled candidates to the neighbors that remain colored.

A.6 Proof of Lemma 5.1

  • For each neighbor u, the process samples a color with probability δ and assigns it only if it is outside B(u) and wins the stated time-and-order tie-break against conflicting neighbors.All other vertices are marked blank.Source: §A.6 · p. 56
  • A Chernoff-bound step is used to control the sum X of indicators for neighbors in S that sampled a color.Each indicator records whether the corresponding neighbor exists in S and sampled a color.Source: §A.6 · p. 56
  • Every neighbor that remains colored must have sampled a color, so the sampled-neighbor count X is at least the number of colored neighbors.This comparison supplies the proof’s final step.Source: §A.6 · p. 56

A.7 Proof of Lemma 5.2

The proof of Lemma 5.2 bounds same-color pairs among a sparse vertex’s neighbors by counting selected anti-edges with uniquely sampled, unblocked colors. It uses Talagrand concentration for that count.

A.7 Proof of Lemma 5.2

  • For a γ-sparse v with degS(v) > ∆−δ·γ·∆ and |B(u)| ≤ ∆/4, the lemma considers a partial coloring formed by probabilistic sampling and conflict-based rejection.A sampled color is assigned only if it is not blocked and no earlier-priority neighbor in S∩N(u) sampled it.Source: §A.7 · p. 57
  • The proof reduces the slack bound to showing that the number of same-color pairs among v’s sparser neighbors is bounded with high probability.The number of such pairs is at most slackχ(v).Source: §A.7 · p. 57
  • The proof selects anti-edges among v’s sparser neighbors and counts those whose endpoints sample and keep the same color, yielding a lower-bound quantity X for the pair count.It uses s = δ²·γ·∆² anti-edges and notes that X counts only a restricted subset of same-color pairs.Source: §A.7 · p. 57
  • The concentration argument applies Talagrand’s inequality to Y and Z, which are functions of independent color choices and are both 2-Lipschitz.Y is 2-certifiable and Z is 3-certifiable; the proof states that both are concentrated with the indicated probability.Source: §A.7 · p. 58

A.8 Proof of Lemma 5.7

TestFlaw3 estimates how many sampled neighbors are colored to distinguish vertices with Flaw 3 from those far from it. The test runs in O(log n) time with certainty.

A.8 Proof of Lemma 5.7

  • The test samples random neighbor indices and counts how many sampled neighbors exist and are colored under φ⋆.That count is R; the procedure returns Fail when R exceeds 3 log n/δ.Source: §A.8 · p. 58
  • O(log n) time with certainty; TestFlaw3 returns Fail with high probability for vertices with Flaw 3 and Pass with high probability for vertices far from it.The stated condition for being far from Flaw 3 is coloredφ⋆(v) < 2δ·∆.Source: §A.8 · p. 59
  • When v has Flaw 3, it has more than 4δ·∆ colored neighbors under φ⋆, which underlies the test’s high-probability Fail result.The proof analyzes the sampled count using independent uniform samples and a Chernoff bound.Source: §A.8 · p. 59
Loading 2610.38787v1…