{"id":"cff5a68f-62de-44b6-ae24-19244229c58c","arxiv_id":"2507.21560","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Deterministic and randomized online edge-coloring algorithms achieve (1+o(1))Delta colors for Delta=omega(log n) and Delta=omega(sqrt(log n)), respectively, matching Bar-Noy-Motwani-Naor lower bounds.","lead":"Online edge coloring means every arriving edge must be colored before the future edges are seen. This paper proves near-optimal colorings are possible exactly once the maximum degree is large enough, matching three-decade-old lower bounds for both deterministic and randomized algorithms.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.16's proof applies Corollary 4.18 to an event that does not imply the corollary's hypotheses; this gap threatens Lemma 4.6 and the randomized Δ=ω(√log n) guarantee.","rationale":"The deterministic result (Theorem 3.1) rests on Lemma 3.10 (Few Bad Colors), whose proof is long but largely self-contained. The randomized result (Theorem 4.1) depends on a longer chain: Lemma 4.9 (Few Bad Colors in oblivious setting) → Lemma 4.15 → Lemma 4.17 (Matching Lemma) → Corollary 4.18 → Lemma 4.16 → Lemma 4.6 (Few Bad Vertices) → Lemma 4.7 → Theorem 4.8. The reader's verdict flagged Lemma 4.9's proof sketch as a concern. Our stress-test found a more specific invalidity: the proof of Lemma 4.16 invokes Corollary 4.18 on an event that does not satisfy the corollary's hypotheses, so the probability bound for annoying edges is not proven. If this gap cannot be closed, the randomized guarantee Δ + O(Δ^{15/16} log^{1/32} n) for Δ = ω(√log n) is unsupported, and the claimed sharp threshold below Δ = ω(log n) is not established. The concern is internal to the main probabilistic analysis and does not affect the lower-bound appendices or the deterministic reduction; it is a proof-repair issue rather than a refutation of the underlying algorithmic idea. We therefore recommend keeping the paper CONDITIONAL until Lemma 4.16's proof is repaired or replaced.","tokens_in":41393,"tokens_out":24060,"duration_ms":257042,"concrete_test":"Verify the implication in Lemma 4.16 by simulating Algorithm 2 on a small graph with a matching M′ = {e1,e2}: let e1 arrive with Z below 1−c_K·ε and both endpoints good, then add enough extra edges incident to one endpoint of e1 to make it bad, and let e2 arrive later. At a common time t before e2 arrives, check whether 'all edges in M′ low-annoying at arrival' holds while Σ_{e∈M′} Z_e(t) ≥ (1−c_K·ε)|M′| or an endpoint of M′ is bad. If any such trajectory occurs with non-negligible probability, the proof step fails. Analytically, re-derive Lemma 4.16 with τ = first time an endpoint of M′ becomes bad and verify whether the stopped version of Corollary 4.18's Azuma bound remains valid.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 4.4, Lemma 4.16 purports to bound the number of 'annoying' edges in a matching M, where an edge e is annoying if, at its arrival time t_e, no endpoint is bad and Z_e(t_e−1) ∉ [1−c_K·ε, 1]. In the proof, for a submatching M′ of size εα∆, the authors write (page 33) Pr[all e∈M′ are low-annoying] ≤ Pr[Σ_{e∈M′} Z_e(t) < (1−c_K·ε)|M′| and there are no bad endpoints of M], citing Corollary 4.18. This implication is not justified. The low-annoying condition is evaluated at each edge's own arrival time; Z_e is a supermartingale and can move upward before a common time t, so the sum condition need not hold at any fixed t. Moreover, endpoints of M′ can become bad after their matching edge arrives, because badness is driven by other incident edges; thus 'no bad endpoints' need not hold. Consequently the union-bound estimate for annoying edges is not established, and Lemma 4.6 (Few Bad Vertices), used in Theorem 4.8 to bound |C_greedy|, lacks its stated proof. Since Lemma 4.6 is the core of the oblivious-adversary result, this is load-bearing.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies online edge coloring with known maximum degree Δ. It presents a deterministic algorithm using Δ+O(Δ^{15/16} log^{1/16} n) colors for Δ = ω(log n), and a randomized oblivious-adversary algorithm using Δ+O(Δ^{15/16} log^{1/32} n) colors for Δ = ω(√log n). Both algorithms are history-dependent P-value schemes with a backup greedy palette; the analysis uses supermartingale concentration and 'few bad colors'/'few bad vertices' lemmas. The deterministic result follows from an adaptive-adversary randomized algorithm via the BDBK+94 reduction. The paper claims these results match the BNMN92 lower bounds, establishing sharp thresholds.","tokens_in":41607,"tokens_out":9661,"duration_ms":105700,"significance":"If correct, the results resolve the deterministic and randomized thresholds for online edge coloring, showing (1+o(1))Δ-colorings exist deterministically for Δ = ω(log n) and randomly for Δ = ω(√log n), matching known lower bounds. The technical framework, exploiting concentration over Θ(Δ^2) edge-color pairs to obtain error exp(−Δ^2), is a notable departure from prior Chernoff-based approaches and may be influential. The paper's strengths include a self-contained adaptive analysis with explicit constants and a clean reduction to deterministic algorithms.","major_comments":[{"comment":"The proof of Lemma 4.16 bounds Pr[all e in M' are low-annoying] by Pr[Σ Z_e(t) < (1−c_K ε)|M'| and no bad endpoints of M] for a fixed time t, citing Corollary 4.18, but the low-annoying condition is evaluated at each edge's own arrival time; since Z_e is a supermartingale that can move upward after t_e, and endpoints of M' can become bad after their matching edge arrives, the event does not imply the corollary's hypotheses at any fixed t. Consequently the union bound estimating the number of annoying edges is not established, and Lemma 4.6 (Few Bad Vertices) lacks its stated proof; as Lemma 4.6 is used in Theorem 4.8 to bound |C_greedy|, this gap is load-bearing for Theorem 4.1.","section":"Section 4.4, proof of Lemma 4.16"},{"comment":"Lemma 4.9 is presented with a proof sketch that refers to the adaptive analysis. The sketch asserts that Lemmas 3.19–3.21 remain valid for Algorithm 2, but it does not verify that the supermartingale property and step-size bound of Lemma 3.24 for the Q variables hold when Algorithm 2's bad-vertex logic (Lines 5–9) zeroes out all colors without scaling; since Lemma 4.9 feeds into Lemma 4.15 and then into the Matching Lemma 4.17, this adaptation should be proved in full detail.","section":"Section 4.3.1, Lemma 4.9"}],"minor_comments":[{"comment":"The sum over 'f ∈ F' uses an undefined set F; it should be 'f ∈ G_t'. Also, 'and then use the fact fact' is a typo for 'and then use the fact'.","section":"Section 3.4.3, proof of Lemma 3.24"},{"comment":"The statement says 'during the execution of Algorithm 1' but the lemma concerns Algorithm 2.","section":"Section 4.4, statement of Lemma 4.6"},{"comment":"The displayed splitting of '∃2εαΔ annoying edges' should read '∃ at least 2εαΔ annoying edges' for the subsequent split into εαΔ low-annoying and εαΔ high-annoying to be formally correct.","section":"Section 4.4, proof of Lemma 4.16"},{"comment":"There is a typo 'colrs' for 'colors', and 'Thm A.1' should be 'Theorem A.1'.","section":"Appendix A.1"},{"comment":"The equality 'c·ε = 2 + 20c_A ε = 2 + 20ε^5 Δ^2 A^2' does not follow from A = c_A/(ε^2 Δ); the algebra appears to need a correction (the term should likely be 20 c_A^2 ε).","section":"Section 3.2, Lemma 3.14 proof"}],"recommendation":"major_revision","confidential_remarks":"The gap in Lemma 4.16 is confined to Section 4; if the authors can fix it, the paper is likely to be acceptable for a strong venue. The deterministic result (Section 3) appears sound and may be publishable on its own, but as submitted the randomized oblivious-adversary theorem is not proven."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the deterministic result in Section 3 is real and worth your time. The randomized result in Section 4, Theorem 4.1, currently rests on a proof gap in Lemma 4.16 that I don't see a quick way around.\n\nWhat's new and good: the deterministic (1+o(1))Δ-coloring for Δ=ω(log n), obtained via the BDBK+94 reduction from an adaptive-adversary algorithm, closes a gap left open for decades. The probability-scaling framework with capped updates and the 'few bad colors' martingale analysis is a genuine technical achievement. Section 3 seems sound; the constants check out and the union bound over n^{Θ(Δ)} potential neighborhoods is handled with care. That alone is a significant paper.\n\nThe soft spot is Section 4.4. Lemma 4.16 tries to bound the number of 'annoying' edges in a matching by invoking Corollary 4.18 at some fixed time t. The implication is not justified. Low-annoying is defined per edge at its own arrival time; while each Z_e freezes after arrival (so the sum condition can be made to hold at a common late t), the 'no bad endpoints' condition in the corollary is different. An endpoint that was good when its matching edge arrived can become bad later, so the corollary's hypothesis need not hold. This gap is load-bearing: Lemma 4.6 (Few Bad Vertices) depends on it, and Theorem 4.8, hence Theorem 4.1, depends on Lemma 4.6. I could not find a repair in the text.\n\nMinor issues: Lemma 4.9 is only a proof sketch, and there are small typos in a couple of displayed inequalities (e.g., the 1/(1−2A) bound in Lemma 3.7). These are secondary.\n\nWho should read this: anyone working on online edge coloring, randomized online algorithms, or the BNMN92 conjecture. The deterministic contribution alone justifies a serious referee. The randomized theorem should not be accepted as proven as is; the authors need to fix Lemma 4.16 or give a different proof of Lemma 4.6. I'd send it to review, but with the expectation that a major revision is likely.","headline":"The deterministic half is a solid, significant advance; the randomized Δ=ω(√log n) theorem has a genuine proof gap in Lemma 4.16.","tokens_in":42250,"tokens_out":5693,"would_cite":true,"duration_ms":63233,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","68W20","68W27","60G42"],"pacs":[],"model":"deepseek-v4-flash","headline":"A deterministic online algorithm can edge-color any graph with maximum degree Δ using only Δ+o(Δ) colors once Δ grows faster than log n, and a randomized version does so already when Δ grows faster than √log n.","keywords":["online edge coloring","greedy algorithm","maximum degree thresholds","randomized algorithms","deterministic algorithms","martingale concentration","adversarial edge arrivals","backup palette"],"falsifier":"Run Algorithm 2 (or Algorithm 1) on large random and adversarial instances at the threshold Δ≈√log n, and measure the maximum number of backup-palette colors used per vertex over many trials. The theorems predict that with high probability every vertex has O(εΔ) marked edges; observing a vertex with, say, more than 2c_K εΔ marked edges with probability well above n^−100 would contradict the Few Bad Vertices lemma. Alternatively, construct an explicit neighborhood in which the sum Q_UwC exceeds its initial value by $ε^{6}$Δ/2 with probability larger than 2^−110Δ n^−110; that would directly falsify the Few Bad Colors concentration bound.","tokens_in":41104,"feed_emoji":"🎨","tokens_out":7945,"duration_ms":92136,"temperature":0.7,"pith_summary":"Edges of an unknown graph arrive one by one, and each must be colored immediately so that touching edges differ. The simple greedy rule uses at most 2Δ−1 colors, roughly twice the offline optimum of Δ+1 colors. This paper proves that greedy can be beaten exactly when the maximum degree Δ is large enough: a deterministic online algorithm achieves Δ+o(Δ) colors once Δ=ω(log n), and a randomized algorithm achieves the same guarantee already when Δ=ω(√log n). These two thresholds match lower bounds from three decades ago, so they are sharp. The algorithms use a primary palette of Δ colors sampled with carefully maintained probabilities, plus a small emergency palette that stays o(Δ) with high probability.","feed_headline":"Two thresholds decide when greedy can be beaten online","feed_subtitle":"Deterministic algorithms use only Δ+o(Δ) colors once degree passes log n; randomization pushes the threshold down to √log n.","key_machinery":"The central mechanism is a history-dependent probability table: for every potential future edge e and every color c in a primary palette of size Δ, the algorithm maintains a probability P_ec, initialized near 1/Δ. When a neighboring edge is colored, all affected probabilities are rescaled so that the expected value of each probability is preserved, except that updates are capped when a probability exceeds a small threshold A to keep the process's step size bounded. An arriving edge samples a color from this table; if the total probability exceeds 1 or the sample fails, the edge is marked and sent to a separate greedy backup palette. The proof's load-bearing objects are the 'bad colors' (probabilities above A) and, in the randomized case, 'bad vertices' (vertices with many marked incident edges). The paper shows, via carefully chosen supermartingales and a standard martingale tail bound, that these bad objects are few with failure probability exp(−Θ(εΔ²)), which is small enough to union bound over all edges and, after decomposing edge sets into matchings, over all vertices. That concentration is what forces the backup palette to stay o(Δ).","core_discovery":"The paper establishes two theorems. The first (Theorem 3.1) is a deterministic online algorithm that edge-colors any n-node graph of known maximum degree Δ using Δ + O($Δ^{{15/16}}$ $log^{{1/16}}$ n) colors, which is (1+o(1))Δ whenever Δ=ω(log n). The second (Theorem 4.1) is a randomized online algorithm, correct against oblivious adversaries, using Δ + O($Δ^{{15/16}}$ $log^{{1/32}}$ n) colors, which is (1+o(1))Δ whenever Δ=ω(√log n). Together with the earlier lower bounds, these are sharp phase transitions: below the respective thresholds no online algorithm can improve on the greedy 2Δ−1 guarantee by even one color, while above them near-optimal colorings are achievable. The deterministic result is obtained by first designing a randomized algorithm that works even against adaptive adversaries and then applying a standard derandomization reduction, while the oblivious-adversary result adapts the same probability-maintenance technique to the smaller degree regime.","pith_inferences":["A transferable lesson, not stated by the paper, is that replacing uniform random choice by rescaling-maintained unequal probabilities may be a general recipe for online allocation problems: it prevents adaptive adversaries from amplifying bias, which the paper's experiments suggest is what breaks plain randomized greedy.","The exp(−Δ²) concentration and matching-decomposition trick may extend to other online problems where the objects to be controlled are edges of a graph, such as online matching or online independent set; if the same step-size control works there, thresholds of order √log n could appear.","The sharp separation between edge coloring and list edge coloring in the appendix suggests the positive thresholds are tied to the availability of a global backup palette; designing an analog with per-edge lists would need a genuinely different mechanism."],"forward_implications":["Deterministic online edge coloring can use (1+o(1))Δ colors for every graph with Δ=ω(log n), settling that greedy can be surpassed exactly in this regime.","Randomized online edge coloring can use (1+o(1))Δ colors already for Δ=ω(√log n), a regime where previous methods required Δ=ω(log n).","Both thresholds are tight: below them, the earlier lower bounds say every online algorithm needs 2Δ−1 colors, so the problem exhibits sharp phase transitions.","The specific color counts are Δ+O(Δ^{15/16} log^{1/16} n) deterministically and Δ+O(Δ^{15/16} log^{1/32} n) randomly, both with high probability in n.","The appendix's lower bounds show these sharp thresholds do not extend to online list edge coloring, where palettes of size 2Δ−1 can remain necessary at larger degrees."],"supporting_citations":[{"why":"Supplies the lower bounds that the paper proves sharp: no online algorithm beats 2Δ−1 for Δ=O(log n) deterministically or Δ=O(√log n) randomly.","marker":"[BNMN92]"},{"why":"Gives the derandomization reduction that converts a randomized algorithm working against adaptive adversaries into a deterministic algorithm with the same guarantee; this is the source of Result 1.1.","marker":"[BDBK+94]"},{"why":"Previous near-optimal randomized algorithm for Δ=ω(log n); its history-dependent probability and martingale framework is adapted and sharpened here.","marker":"[BSVW24a]"},{"why":"Establishes the offline baseline of Δ+1 colors that the online algorithms aim to approximate.","marker":"[Viz64]"},{"why":"Shows that knowledge of Δ is necessary and that online algorithms need at least Δ+Ω(√Δ) colors, setting the context for near-optimality.","marker":"[CPW19]"}],"fun_headline_variants":["Online greedy beaten past log n or √log n","Deterministic and randomized online edge coloring at sharp thresholds","Two thresholds: when greedy loses online","Online edge coloring: surpassing greedy exactly when it's possible","Randomization lowers the bar for beating greedy online"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire analysis rests on the claim that the random fluctuations in the maintained probabilities concentrate as sharply as independent trials, giving failure probabilities around $e^{{−Θ(εΔ²)}}$; if correlations among 'bad' colors or vertices are stronger than the paper's martingale bounds allow, the backup palette could grow beyond the promised o(Δ).","fun_headline_variants_meta":{"raw":{"variants":["Online greedy beaten past log n or √log n","Deterministic and randomized online edge coloring at sharp thresholds","Two thresholds: when greedy loses online","Online edge coloring: surpassing greedy exactly when it's possible","Randomization lowers the bar for beating greedy online"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001496,"raw_usage":{"total_tokens":6061,"prompt_tokens":1058,"completion_tokens":5003,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":674,"completion_tokens_details":{"reasoning_tokens":4929}},"tokens_in":674,"tokens_out":5003,"duration_ms":43654,"temperature":1.0,"reasoning_tokens":4929,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T12:38:44.688372+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 2 (or Algorithm 1) on large random and adversarial instances at the threshold Δ≈√log n, and measure the maximum number of backup-palette colors used per vertex over many trials. The theorems predict that with high probability every vertex has O(εΔ) marked edges; observing a vertex with, say, more than 2c_K εΔ marked edges with probability well above n^−100 would contradict the Few Bad Vertices lemma. Alternatively, construct an explicit neighborhood in which the sum Q_UwC exceeds its initial value by $ε^{6}$Δ/2 with probability larger than 2^−110Δ n^−110; that would directly falsify the Few Bad Colors concentration bound.","supporting_citations":[],"review_version":1}