{"id":"b8ba941f-80e5-43db-ac07-82c3fbdcae37","arxiv_id":"2607.20360","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Hyperbolic random graphs can be coloured in the CONGEST model with (1+ε)κ, hence at most 4/3 χ, colours in O((log log n)^2) rounds a.a.s.","lead":"A new CONGEST algorithm colours hyperbolic random graphs with roughly 4/3 times the chromatic number in O((log log n)^2) rounds, and with χ^{1+ε} colours in O(1) rounds. It cuts the colour count of the previous constant-round algorithm by at least n^{1/6}.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Radius estimator silently assumes exact knowledge of n and α (Sec. 6.1); no distributed estimation procedure is supplied, so Lemma 6.5's o(1) radius accuracy and the pseudo-band phase analysis rest on an unproven implementation premise.","rationale":"The reader and I identify the same load-bearing gap. The algorithm's pseudo-bands are defined through br(v)=dbar^{-1}(deg(v)), and the entire structural phase (Lemmas 6.5, 6.7, 6.9, 6.15, 6.17, Corollaries 6.10/6.13) depends on br being within o(1) of r. That accuracy is only proved for the exact dbar, which requires global model parameters. The manuscript concedes the point in Section 6.1 with the unsupported phrase 'possible to estimated', but supplies no distributed estimation protocol, complexity bound, or reference. This is a genuine missing support in the central claim, exactly as the reader's weakest_assumption states. I do not see a deeper internal inconsistency in the recurrence or clique-colouring analysis; the stochastic-domination arguments are plausible and the clique lower bounds are coherent. The concern is therefore not a refutation but an unproven implementation premise. A conditional verdict is appropriate: if the authors add an explicit 'vertices know n and α' assumption or a valid estimation subroutine, the main theorem stands; without it, the algorithm is not fully specified for the CONGEST model. I agree with the reader's verdict, so no adjustment is needed.","tokens_in":52396,"tokens_out":22782,"duration_ms":176168,"concrete_test":"Concrete test: Recompute Lemma 6.5 with α̂ = α + 1/log n in place of α. Using dbar(r;α)≈c(α)n e^{-r/2}, we have br(v;α̂)≈r + 2 log(c(α̂)/c(α)) = r + O(1/log n), which is o(1/log log n), so a 1/log n-accurate α-estimate would suffice for the fine-band widths. Then check whether any CONGEST protocol in the literature can estimate α to this accuracy in O((log log n)^2) rounds (the paper provides none). If such a protocol exists, the concern is resolved; if not, Theorem 1.1 must be restated with n and α as global inputs or the radius-estimation premise remains unproven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central decomposition of SRC is degree-based: br(v)=dbar^{-1}(deg(v)) determines the pseudo-clique and pseudo-bands. Lemma 6.5 proves |br(v)-r(v)|<sqrt(delta_n)=o(1), but only for the true expected-degree function dbar. Evaluating dbar requires n and α (and effectively the model intensity/C) as exact inputs. Section 6.1 says only: 'We assume that the vertices known and α, which is possible to estimated' — no protocol, no citation, no error analysis. This is load-bearing, not cosmetic: dbar(r) ≈ (2α/(π(α-1/2))) n e^{-r/2}, so a constant error in α changes the prefactor by a constant and shifts br by Θ(1). The fine pseudo-bands near the core have width 1/log log n (Section 6.1), so a Θ(1) shift moves vertices across many band boundaries. Corollary 6.13 (pseudo-band sizes), Lemma 6.15 (dpre), and Lemma 6.17 (dint) all rely on the o(1) radius accuracy; with constant misassignment, dpre≤(1+o(1))κ and dint≤χ/√log log n can fail, and Lemma 6.18's available-colour argument collapses. Thus the theorem is not yet a self-contained distributed algorithm unless parameter knowledge is explicitly assumed or an estimation procedure is provided. This is an omitted/unsupported premise rather than a demonstrated contradiction, so it warrants a conditional verdict, not rejection.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies distributed vertex colouring of Hyperbolic Random Graphs (HRGs) in the CONGEST model. It introduces Sequential Radial Colouring (SRC), which estimates the radial coordinate of each vertex from its degree, partitions the vertices into radial pseudo-regions, and colours these regions from the core outward using the RCTDEG protocol of Maus and Ruff. The main theorem (Theorem 1.1) claims: with (1+ε)κ colours, SRC colours the graph in O((log log n)^2) rounds a.a.s.; with O(χ log log n) colours, Parallel Radial Colouring (PRC) colours in O(log log n) rounds; and with χ^{1+ε} colours, SRC colours in O(1) rounds. Combined with the external bound κ ≤ ((4/3)^α + o(1))χ from [2], the first item yields a ((4/3)^α + ε)χ palette, motivating the '4/3χ' headline. The paper also proves sharp upper and lower bounds for RCTDEG on a clique as a function of the additive slack s = |Ψ| − |C|, using concentration inequalities for self-bounding functions.","tokens_in":52797,"tokens_out":21593,"duration_ms":169486,"significance":"If the result holds, it is a substantial advance over the previous CONGEST algorithm of Maus and Ruff, reducing the palette from at least n^{1/6}χ colours to O(χ) colours while keeping round complexity polyloglogarithmic, and achieving O(1) rounds with χ^{1+ε} colours. The structural message—that degeneracy κ, rather than maximum degree, is the right bottleneck for colouring HRGs—is interesting and likely to influence further work on random geometric graphs. The paper is carefully argued: the one-round domination lemma (Corollary 5.12), the pseudo-band size estimates, and the clique lower-bound analysis via self-bounding functions are explicit and checkable. No parameters are fitted to data; all statements are a.a.s. with quantified ε. The main caveats are that the radius estimator assumes knowledge of the model parameters n, α, and C, and that the PRC palette partition as described assumes knowledge of χ. These are implementation premises that need to be stated or proved. The constant 4/3 is inherited from the external structural result [2], which is legitimate.","major_comments":[{"comment":"The radius estimator in Section 6.1 requires vertices to know the exact expected-degree function d̄(r), which depends on the model parameters n, α, and C: Lemma 5.3 gives d̄(r) = (2α/(π(α−1/2))) n e^{−r/2} + o(...). The only implementation statement is the sentence 'We assume that the vertices known and α, which is possible to estimated' in the main text and footnote 19. No distributed estimation procedure, citation, or error analysis is provided. This is load-bearing: Lemma 6.5's guarantee |br(v)−r(v)| < √δ_n = o(1) is what allows pseudo-bands of width 1/log log n near the core to be aligned with true radial bands. A constant error in α or C changes d̄ by a constant factor and shifts the estimated radius by Θ(1), which would cross many fine-band boundaries. Lemmas 6.15, 6.17, 6.18 and Theorem 6.21 all rely on this o(1) radius accuracy. As stated, Theorem 1.1 is therefore a conditional r","section":"§6.1, Lemmas 6.3–6.5"},{"comment":"The proof of PRC prescribes subpalettes of sizes ⌈(1+ε_n)χ⌉ and χ. This requires the vertices to know the chromatic number χ (or at least an asymptotic value) in order to partition the input palette. The theorem statement, however, is expressed in terms of κ, and no way to compute or estimate χ in CONGEST is given. Since the paper claims a distributed algorithm using only local computation and the input graph, this is an implementation gap. It can be fixed by describing an equal split of the given palette into O(log log n) parts and verifying the constants, possibly processing a constant number of batches sequentially, or by explicitly assuming knowledge of χ. Please make the PRC implementation independent of exact χ.","section":"§7, Theorem 7.1"}],"minor_comments":[{"comment":"The phrase '4/3χ colours' is stronger than the actual guarantee ((4/3)^α + ε)χ stated in Section 3 and in the introduction's discussion of the interval (√(4/3), 4/3). The abstract should qualify the factor accordingly.","section":"Abstract / §3"},{"comment":"The notation in Table 1 is garbled: '|C| 1+εn,|C| εn → ∞' should be '|C|^{1+ε_n} with |C|^{ε_n} → ∞'. Similar formatting issues appear in Table 4.","section":"Table 1 and Table 4"},{"comment":"The sentence 'We assume that the vertices known and α, which is possible to estimated' is grammatically garbled and should be rewritten. More importantly, this assumption should be stated in the main text and in the statement of Theorem 1.1, not only in a footnote.","section":"§6.1, footnote 19"},{"comment":"References [36] and [37] appear to have identical bibliographic data (same title, journal, volume, pages, and year). If they are intended to be two different papers, the entries need to be corrected; otherwise the duplicate should be removed.","section":"References [36] and [37]"},{"comment":"The expectation bound jumps to O(n^{(1−α)(1+ε)} (log n)^{−c_in(1−α)}) without showing the intermediate algebra. The bound is quite loose and a one-line derivation would help the reader verify that the exponent is correct for every band i.","section":"§8.4, Lemma 8.8"}],"recommendation":"major_revision","confidential_remarks":"The main concern is the parameter-knowledge premise in §6.1, which is load-bearing for the whole pseudo-band analysis. I believe this is fixable either by an explicit assumption or by a distributed estimation protocol, so I do not recommend rejection. The dependence on [2] for the 4/3 factor is standard and acceptable. The PRC implementation gap in §7 should also be resolved in revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: this is a real advance over Maus–Ruff, not a repackaging. SRC/PRC get O(χ) colours in O((log log n)^2) rounds in CONGEST for HRGs, and the clique slack analysis — constant rounds iff slack is |C|^{1+Ω(1)} — is new and tight. The 4/3χ constant is inherited from Baguley et al., so the headline constant isn't proved here, but the contribution is the distributed algorithm, not the structural bound.\n\nWhat's well done: the degree-based pseudo-band decomposition is genuinely clever; the sequential domination lemma (Cor 5.12) gives a clean way to handle dependencies; the band analysis is explicit and mostly self-contained after standard HRG lemmas. The lower bounds for RCTDEG on a clique, via self-bounding concentration, look right.\n\nWhere it's soft: Section 6.1, the radius estimator inverts the expected-degree function and requires vertices to know n and α exactly. The paper says 'We assume that the vertices known and α, which is possible to estimated' — typo aside, this is an unsupported premise. The fine bands have width 1/log log n, and a constant error in α shifts the estimated radius by Θ(1), which would scramble the band assignment. The proof of Lemma 6.5 relies on the exact inverse. This isn't a contradiction, but the theorem as stated is conditional on exact parameter knowledge. If CONGEST algorithms routinely assume knowledge of n and the model parameters, then this is a minor clarification; but the paper doesn't say that, and the 'possible to estimate' comment is not a proof. I'd want this patched — either formally assume the parameters as input, or give a distributed estimation procedure with error analysis.\n\nOther notes: the pseudo-clique is not actually a clique, but the treatment via the general graph lemma covers it. The external lemmas from [2] and [47] are load-bearing but legitimate. No circularity.\n\nBottom line: this deserves a serious referee. The central argument holds up modulo the parameter-knowledge assumption. I would accept it conditionally and ask for that patch.","headline":"A real advance over Maus–Ruff: SRC/PRC get O(χ) colours in (log log n)^2 rounds for HRGs, with a genuinely new clique-slack tradeoff; the main gap is the unsupported parameter-knowledge assumption in the radius estimator.","tokens_in":53239,"tokens_out":2028,"would_cite":true,"duration_ms":19730,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","05C15","05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"Hyperbolic random graphs can be coloured in the CONGEST model with a palette only 4/3 times the chromatic number, in O((log log n)^2) rounds.","keywords":["distributed vertex colouring","hyperbolic random graphs","CONGEST model","chromatic number","degeneracy","random colour trial","degree ordering","clique colouring"],"falsifier":"Run SRC on an HRG in which vertices are given only their own degree and not the parameters α and n; if the estimated radius deviates from the true radius by more than √δ_n = O((log n)^{-1/4}) at any band boundary, the uncoloured-degree recurrence no longer drops doubly exponentially and the O((log log n)^2) round guarantee fails. For the clique-colouring claim, attempt to colour a clique with (1+1/log n)n colours using any distributed protocol; the paper predicts Ω(log log n) rounds a.a.s., so a protocol finishing in a constant number of rounds with o(1) uncoloured vertices would refute the lo","tokens_in":52295,"feed_emoji":"🎨","tokens_out":7377,"duration_ms":58025,"temperature":0.7,"pith_summary":"This paper establishes that distributed vertex colouring of hyperbolic random graphs—a realistic model of scale-free networks—can be done with a palette that is only a constant factor larger than the chromatic number χ, namely ((4/3)^α + ε)χ where α∈(1/2,1), in O((log log n)^2) rounds in the CONGEST model. The key move is to replace the maximum degree Δ by the degeneracy κ as the bottleneck: degrees in an HRG give an almost optimal ordering, and κ ≤ ((4/3)^α + o(1))χ. The algorithm, Sequential Radial Colouring, delays low-degree vertices by processing radial pseudo-bands from the centre outwards, so that colour choices of low-degree vertices never block high-degree ones. If the palette has polynomial slack χ^{1+ε}, the same framework colours in O(1) rounds. The clique-colouring analysis inside the proof also settles the exact round complexity of a classical random colour-trial protocol on a clique as a function of palette slack.","feed_headline":"Hyperbolic graphs colour with 4/3 of the optimal palette","feed_subtitle":"The palette drops from n^{1/6}χ to O(χ) because the bottleneck is degeneracy, not maximum degree.","key_machinery":"The central object is the degree-based radius estimator r̂(v) = d̄⁻¹(deg(v)), which inverts the expected-degree function—strictly decreasing in radius—to place every vertex within a radial pseudo-band up to an o(1) error. The algorithm processes pseudo-bands from the centre outwards with RCTDEG (Random Colour Trial with degree priorities). The load-bearing analysis tool is the one-step failure bound: conditional on any history, a vertex remains uncoloured with probability at most (number of higher-priority uncoloured neighbours)/(available colours), which via sequential stochastic domination yields a doubly-exponential drop of the maximum uncoloured degree to O(log n) within O(log log n) rou","core_discovery":"The paper proves Theorem 1.1: for any ε>0, with |Ψ| ≥ (1+ε)κ colours, Sequential Radial Colouring colours an HRG a.a.s. in O((log log n)^2) rounds; with |Ψ| = Ω(κ log log n), Parallel Radial Colouring uses O(log log n) rounds; and with |Ψ| ≥ κ^{1+ε}, SRC uses O(1) rounds. Since κ ≤ ((4/3)^α + o(1))χ, this yields a ((4/3)^α + ε)χ-colouring in CONGEST. The mechanism at the core is that, in an HRG, every vertex has at most (1+o(1))κ neighbours of larger degree, so the degree ordering is an almost optimal degeneracy ordering; processing bands sequentially ensures that each active vertex retains a constant-factor surplus of colours, and the maximum uncoloured degree drops doubly exponentially.","pith_inferences":["If the paper's conjecture χ = (1+o(1))ω (clique number) holds, the same algorithm becomes a (1+ε)-approximation to the chromatic number itself, and the 4/3 factor is an artifact of the known κ-vs-χ bounds rather than a fundamental limit.","A natural testable extension is whether a parameter-free version—estimating α and n from the local degree distribution instead of assuming them known—can keep the pseudo-band boundaries within the o(1) tolerance required by the radius-accuracy lemma.","The band-decomposition technique is not obviously limited to HRGs: any graph where the degree ordering is a near-optimal degeneracy ordering and where radial bands can be recovered from local information should exhibit the same poly-log-log colouring behaviour; this could be tested empirically on other geometric inhomogeneous random graphs or real network datasets.","The tight clique-colouring bounds suggest a general 'slack threshold' for random colour-trial protocols: below polynomial slack, the doubly-exponential decay phase is unavoidable, which may inform protocol design for dense subgraphs in other geometric graph models."],"forward_implications":["Colouring with O(χ) colours in CONGEST is possible for hyperbolic random graphs, improving the previous constant-round n^{1/6}χ-colour algorithm by a polynomial factor in palette size.","The degeneracy κ, not the maximum degree Δ, is identified as the natural parameter limiting distributed colouring of scale-free networks; the algorithm achieves a (1+ε)-approximation to κ arbitrarily closely.","The clique-colouring analysis pins down the exact round complexity of RCTDEG on a clique: Θ(log log n) rounds for (1+o(1))n colours, and constant rounds if and only if the palette has polynomial slack.","The O(1)-round χ^{1+ε} variant transfers a result previously known only in the LOCAL model to CONGEST with efficient local computation."],"fun_headline_variants":["Hyperbolic graphs colour with 4/3 of the optimal palette","Distributed colouring of hyperbolic networks with 4/3 optimal palette","Beat worst-case colouring with hyperbolic geometry","Hyperbolic graphs: colouring with 4/3χ in O(log log n) rounds"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The entire decomposition hinges on vertices recovering their radial position by inverting the expected-degree function, which requires them to know the model parameters n and α exactly; if vertices only know their own degree, the pseudo-band assignment can be wrong by more than o(1) and the phase analysis collapses (the paper states this assumption without a distributed estimation procedure).","fun_headline_variants_meta":{"raw":{"variants":["Hyperbolic graphs colour with 4/3 of the optimal palette","Distributed colouring of hyperbolic networks with 4/3 optimal palette","Beat worst-case colouring with hyperbolic geometry","Hyperbolic graphs: colouring with 4/3χ in O(log log n) rounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000929,"raw_usage":{"total_tokens":3906,"prompt_tokens":922,"completion_tokens":2984,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":666,"completion_tokens_details":{"reasoning_tokens":2919}},"tokens_in":666,"tokens_out":2984,"duration_ms":20501,"temperature":1.0,"reasoning_tokens":2919,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T10:02:12.249523+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SRC on an HRG in which vertices are given only their own degree and not the parameters α and n; if the estimated radius deviates from the true radius by more than √δ_n = O((log n)^{-1/4}) at any band boundary, the uncoloured-degree recurrence no longer drops doubly exponentially and the O((log log n)^2) round guarantee fails. For the clique-colouring claim, attempt to colour a clique with (1+1/log n)n colours using any distributed protocol; the paper predicts Ω(log log n) rounds a.a.s., so a protocol finishing in a constant number of rounds with o(1) uncoloured vertices would refute the lo","supporting_citations":[],"review_version":1}