{"id":"ce137418-c088-4ce7-a698-2ebcbd69ee3f","arxiv_id":"2607.26271","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For d-degenerate C4-free graphs, the fractional chromatic number is at most (1+o(1))d/log d, and for every fixed girth at least 4 there are d-degenerate graphs with fractional chromatic number at least (1−o(1))d/log d.","lead":"Sharp bounds for the fractional chromatic number of sparse graphs with large girth are proved, confirming a conjecture for graphs with no triangles or 4-cycles and giving matching lower-bound examples for any fixed girth. An efficient randomized coloring algorithm is part of the upper-bound proof; the lower-bound examples come from a random uniform-attachment graph.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; C4-free assumption is explicit and the proof supports the theorem.","rationale":"The paper's central claims are Theorem 1.3 (upper bound for C4-free d-degenerate graphs) and Theorem 1.4 (lower bound via uniform attachment). I read the full proof. The upper bound's Algorithm 1 and the supermartingale S_i are the delicate part. The use of C4-freeness is explicit and correct: it ensures |N_L(u)∩N_L(v)|≤1 for adjacent pairs, hence η_{i,j,k}∈{0,1} and the unique-v_j claims in the case analysis. I checked the deterministic inequalities and the constant choices; they hold for d large enough. The only imprecision is the overlapping case noted above, where the proof says S_i=S_{i-1} but actually S_i≤S_{i-1}; since the Claim needs only ≤, this does not affect the conclusion. The lower bound uses LP duality with the explicit harmonic-tail fractional clique f. Lemma 3.2's first-moment estimate is sound (I verified the optimization of h(x)-d/2 x^2 and the final inequality). Lemma 3.3's cycle-count bound via Catalan numbers is correct. Deleting one vertex per short cycle preserves d-degeneracy and girth, and the small ℓ_n(R) condition is met by the union-bound estimate. Thus the theorems are well-supported. The abstract's sentence about lacking computational complexity barriers is weaker than the formal content; Section 4 labels it heuristic. This warrants the reader's CONDITIONAL verdict on presentation but not a mathematical rejection.","tokens_in":22011,"tokens_out":45420,"duration_ms":366368,"concrete_test":"Independently verify the Claim in Lemma 2.2 for the overlapping case v_i∈B_{i-1}∩N_L(v_k)∩N_L(X) by writing S_i explicitly in terms of S_{i-1} and confirming S_i≤S_{i-1}; this settles the only soft spot in the upper bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I found no load-bearing flaw in the central theorems. Theorem 1.3 is explicitly for C4-free graphs, and the proof's use of |N_R(v_i)∩N_L(v_k)|≤1 is justified by C4-freeness; the supermartingale S_i is a genuine supermartingale. One minor imprecision: in Lemma 2.2's Claim, the case v_i∈N_L(X)∩B_{i-1} with v_i also in N_L(v_k) cannot have S_i=S_{i-1} (the factor for i disappears and η coefficients decrease), but S_i≤S_{i-1} holds, which is all the argument requires. The lower bound is coherent: the LP-duality certificate via f is valid, and the deletion of R preserves girth and degeneracy. The abstract's computational-barrier remark is heuristic (as Section 4 states) and should not be read as a formal finding; this is a presentation issue, not a mathematical one.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves sharp bounds for the fractional chromatic number of sparse degenerate graphs. Theorem 1.3 shows that every n-vertex d-degenerate C4-free graph satisfies χ_f(G) ≤ (1+ε)d/log d for large d, via a poly(n,d)-time randomized algorithm that outputs a fractional coloring of that weight. This confirms the Martinsson–Steiner upper-bound conjecture under the additional C4-free (girth at least 5) hypothesis. Theorem 1.4 constructs, for every g ≥ 4 and δ > 0, a d-degenerate graph with girth at least g and χ_f(G) ≥ (1−δ)d/(W(d)+1), confirming the matching lower bound in a stronger form. The lower bound is proved by analyzing a uniform-attachment random graph, using the LP dual (fractional clique) with an explicit harmonic-tail weight function, and then deleting one vertex from each short cycle.","tokens_in":22234,"tokens_out":27251,"duration_ms":214583,"significance":"If correct, the paper substantially advances the Martinsson–Steiner program: it gives the optimal leading constant for the fractional chromatic number of C4-free d-degenerate graphs, and it confirms the conjectured lower bound for all triangle-free degenerate graphs, in fact for every fixed girth g ≥ 4. A notable strength is that the upper-bound proof is fully constructive and yields an efficient randomized algorithm with an explicit O_ε(d log n / log d)-size witness. The lower bound is self-contained and uses no fitted parameters; the LP-duality certificate is explicit. The paper also correctly identifies the structural role of C4-freeness in the supermartingale analysis. The computational-complexity discussion in Section 4 is explicitly heuristic, and the main theorems do not depend on it. Overall this is a solid, significant contribution.","major_comments":[],"minor_comments":[{"comment":"In the deterministic inequalities used in the final cases of the supermartingale proof, the justification is stated as '0 ≤ p_{i-1}(v_i) ≤ p̂ ≤ ε/40'. This alone does not imply 1/(1−x) ≤ 1 + (1+ε')x for x as large as ε/40; the needed condition is roughly x ≤ ε'/2, i.e. p̂ ≤ ε/120. The actual p̂ = d^{-ε/20} is much smaller than this for d ≥ d0 by the displayed choice of d0, so the argument is repairable, but the proof should state the stronger bound on p̂ explicitly and derive it from the d0 condition.","section":"§2, proof of Lemma 2.2"},{"comment":"The sentence 'If v_i ∉ N_L(X∪{v_k}), or v_i ∈ N_L(X)∩B_{i-1}, ... we get S_i = S_{i-1}' is not correct in the subcase v_i ∈ N_L(v_k) ∩ N_L(X) ∩ B_{i-1}: the factor for v_i in the product defining S_{i-1} disappears when passing to S_i, so S_i < S_{i-1}. The desired supermartingale inequality S_i ≤ S_{i-1} still holds, so the proof is unaffected once this is corrected.","section":"§2, proof of Lemma 2.2, second easy case"},{"comment":"The abstract states that the results 'reveal that this model lacks the typical computational complexity barriers found in Erdős–Rényi graphs.' Section 4 explicitly characterizes the relevant discussion as 'quite heuristic' and does not prove any algorithmic lower bound. I recommend softening the abstract to say that the model does not exhibit the conjectured barrier for this algorithm, or that the observation is heuristic.","section":"Abstract and §4"},{"comment":"The definition q = ceil(400^2 · 20 ε^{-4} d log n / log d) gives q = 0 when n = 1. The theorem is trivial for n = 1, but for formal correctness one should take q = max(1, ...).","section":"Theorem 1.3"}],"recommendation":"minor_revision","confidential_remarks":"The paper is mathematically sound in its main claims. The only issue I see that touches a central proof is the p̂/ε/40 justification in Lemma 2.2, and that is a local fix (state a stronger bound on p̂). The rest is minor presentation. The lower-bound construction and LP-duality argument are particularly clean. I recommend minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nWhat you should know: this paper proves the sharp leading constant for the fractional chromatic number of d-degenerate C4-free graphs, and constructs matching lower-bound examples with arbitrary fixed girth. Both directions are new and the main arguments hold up.\n\nThe upper bound (Theorem 1.3) improves Martinsson–Steiner's (4+o(1))d/log d to (1+o(1))d/log d for C4-free graphs, using a careful analysis of Dhawan's algorithm. The supermartingale argument in Lemma 2.2 is detailed; the C4-free assumption is exactly what gives |N_R(v_i)∩N_L(v_k)|≤1, and the second-moment bound follows. I checked the key inequalities and they are sound. The algorithm runs in poly(n,d) time and outputs an (α,q)-coloring, which is a nice constructive witness.\n\nThe lower bound (Theorem 1.4) uses a uniform attachment random graph and LP duality. The fractional clique f(i) based on the harmonic tail function is explicit. The proof of Lemma 3.2 (first moment over independent sets) and Lemma 3.3 (cycle count via trace of a Hardy kernel matrix) are coherent; the Catalan recurrence in the trace estimate is standard. Deleting one vertex per short cycle preserves degeneracy and girth, and the duality certificate survives. This gives (1−o(1)) d/(W(d)+1), which is (1−o(1)) d/log d.\n\nSoft spots are minor. The abstract's claim that the model \"lacks the typical computational complexity barriers\" is heuristic; Section 4 explicitly frames it as informal intuition, not a theorem. The reader is right to flag that. The authors disclose AI assistance for part of the lower-bound proof; that does not affect validity, but it means a referee should re-check the algebraic steps in Lemma 3.2. There is also a tiny imprecision in Lemma 2.2's claim: in the case v_i∈N_L(X)∩B_{i-1} with v_i also in N_L(v_k), the inequality is S_i≤S_{i-1} rather than equality; the argument only needs the inequality, so no harm.\n\nIf I had to guess, the triangle-free conjecture remains open because the Co-Neighbor Path configuration breaks the supermartingale; the paper says so honestly. That is the right way to frame it.\n\nWho is this for? Researchers in extremal graph theory, randomized algorithms, and fractional coloring. It deserves a serious referee. The central theorems are important, the proofs repay checking, and the presentation is mostly clean.\n\nI would accept this for peer review.","headline":"Solid, important paper: sharp fractional chromatic bounds for d-degenerate C4-free graphs and matching high-girth lower bounds; only real issue is an overstated heuristic remark in the abstract.","tokens_in":22708,"tokens_out":2032,"would_cite":true,"duration_ms":18663,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C80","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every large d, every 4-cycle-free d-degenerate graph has fractional chromatic number at most (1+o(1))d/log d, and there exist d-degenerate graphs of any fixed girth meeting this bound; an efficient randomized algorithm finds the colorin","keywords":["fractional chromatic number","d-degenerate graphs","C4-free graphs","girth","randomized algorithm","uniform attachment model","LP duality","fractional clique"],"falsifier":"Simulate Algorithm 1 many times on a large 4-cycle-free d-degenerate graph, and check that every vertex is selected with frequency at least (1−ε/40)log d/((1+ε/2)d); Theorem 1.3 predicts this for all vertices. A sharper test targets the structural premise: start from an otherwise 4-cycle-free graph and add a single Co-Neighbor Path 4-cycle (two early vertices whose later neighborhoods share a common pair), then measure the selection probability of the affected late vertex; the paper's analysis says this is precisely where the supermartingale inequality can fail, so a constant-factor drop in in","tokens_in":21907,"feed_emoji":"🎨","tokens_out":11404,"duration_ms":98865,"temperature":0.7,"pith_summary":"The paper aims to pin down the exact leading constant in the fractional chromatic number of d-degenerate graphs with no short cycles. It proves that every d-degenerate graph with no 4-cycles has fractional chromatic number at most (1+o(1))d/log d, and that this bound is witnessed by a polynomial-time randomized algorithm that actually outputs the fractional coloring. It also constructs d-degenerate graphs of arbitrarily large fixed girth whose fractional chromatic number is at least (1−o(1))d/log d, using a random uniform-attachment graph and an explicit fractional clique. Together these results confirm the conjectured sharp constant 1 for girth at least 5 and resolve the lower-bound half of the Martinsson–Steiner conjecture in a stronger form. The paper further explains why this random model has no algorithmic gap of the kind conjectured for bounded-degree triangle-free graphs.","feed_headline":"4-cycle-free graphs hit the sharp d/log d fractional coloring bound","feed_subtitle":"A new algorithm and matching lower bound settle the sharp constant for high-girth d-degenerate graphs","key_machinery":"Upper bound: Algorithm 1, a randomized independent-set sampler that processes vertices in degeneracy order and maintains a weight p_i(v) starting at α=(log d)/((1+ε/2)d). Updates are designed so E[p_i(v) | past]=p_{i−1}(v), with a threshold p̂=d^{−ε/20} and equalizing coin flips that restore the martingale when a weight would exceed the threshold; vertices at the threshold are never selected. The analysis uses the supermartingale S_i = p_i(v_k)^2 ∏_{i<j≤k−1, v_j∈N_L(v_k)} (1+(1+(1+2η_{i,j,k})ε′)p_i(v_j)), where η_{i,j,k}=|N_L(v_j)∩N_L(v_k)∩{v_{i+1},...,v_{j−1}}|; 4-cycle-freeness forces η∈{0,1} and |N_R(v_i)∩N_L(v_k)|≤1, yielding E[p_{k−1}(v_k)^2]≤α^2 exp((1+o(1))dα). Lower bound: the unifor","core_discovery":"The central claim is that the sharp constant 1 in the Martinsson–Steiner conjecture is correct for graphs of girth at least 5, and that the lower bound holds with arbitrarily large fixed girth. Concretely, Theorem 1.3 says that for each ε>0 and all large d, every n-vertex d-degenerate C4-free graph satisfies χ_f(G)≤(1+ε)d/log d, with a poly(n,d)-time randomized algorithm that outputs, with high probability, an (α,q)-coloring at weight (1+ε)d/log d. The proof runs a weight-thresholding independent-set sampler in degeneracy order; C4-freeness enters exactly where the analysis needs |N_R(v_i)∩N_L(v_k)|≤1, which controls the second moment of the sampler's weights. Theorem 1.4 says that for fixed","pith_inferences":["The obstacle to the full triangle-free conjecture is pinpointed as the Co-Neighbor Path configuration of a 4-cycle in the degeneracy ordering; we conjecture that a proof of the sharp bound under a mild codegree condition, as posed in Problem 4.1, would carry over to all triangle-free d-degenerate graphs and unify the result with recent codegree-based independence bounds.","Because the paper's lower-bound graph is built from uniform attachment, the harmonic-tail fractional clique is essentially a statement about age-biased random graphs; we suspect the same dual construction gives χ_f=(1+o(1))d/log d for any model in which each new vertex connects to uniformly random earlier vertices, suggesting the threshold is robust to details of the model.","The second-moment supermartingale technique, which controls the probability that the sampler's weights hit the threshold, seems transferable to other algorithmic random-weight settings such as list fractional coloring or K_{t,t}-free graphs as in Problem 4.2, although the paper does not develop those extensions."],"forward_implications":["The upper bound is constructive: for any 4-cycle-free d-degenerate graph, a polynomial-time randomized algorithm outputs an explicit fractional coloring of weight (1+o(1))d/log d with high probability, so the sharp bound is not merely existential.","The lower-bound construction fixes the leading constant: no upper bound of the form cd/log d with c<1 can hold for all d-degenerate graphs of girth at least 4, since the constructed graphs reach (1−o(1))d/log d.","The lower-bound half of the Martinsson–Steiner conjecture is resolved in a stronger form: the lower-bound examples can have arbitrary constant girth g≥4, not just triangle-freeness.","As the paper notes, a corollary of the upper bound via an earlier result is that every 4-cycle-free graph with minimum degree d contains an induced bipartite subgraph with average degree at least (1−o(1))log d.","In the uniform attachment model the fractional chromatic number is asymptotically d/log d and matches the algorithmic upper bound, so this random model does not exhibit the conjectured factor-2 algorithmic gap for bounded-degree triangle-free graphs."],"fun_headline_variants":["New algorithm and matching lower bound settle high-girth coloring","High-girth d-degenerate graphs achieve sharp fractional chromatic number","Constructive proof confirms optimal d/log d bound for C4-free graphs","Uniform attachment graphs show no algorithmic gap in fractional coloring"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is 4-cycle-freeness: the proof needs that for every pair of vertices v_i and v_k, the set of right-neighbors of v_i that are also left-neighbors of v_k has size at most 1, because this is what keeps the second-moment supermartingale from drifting upward; without it—even in a triangle-free graph with one Co-Neighbor Path 4-cycle—a vertex's selection probability can drop by a constant factor and the upper bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["New algorithm and matching lower bound settle high-girth coloring","High-girth d-degenerate graphs achieve sharp fractional chromatic number","Constructive proof confirms optimal d/log d bound for C4-free graphs","Uniform attachment graphs show no algorithmic gap in fractional coloring"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000286,"raw_usage":{"total_tokens":1540,"prompt_tokens":786,"completion_tokens":754,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":530,"completion_tokens_details":{"reasoning_tokens":684}},"tokens_in":530,"tokens_out":754,"duration_ms":7586,"temperature":1.0,"reasoning_tokens":684,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T00:17:39.102660+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate Algorithm 1 many times on a large 4-cycle-free d-degenerate graph, and check that every vertex is selected with frequency at least (1−ε/40)log d/((1+ε/2)d); Theorem 1.3 predicts this for all vertices. A sharper test targets the structural premise: start from an otherwise 4-cycle-free graph and add a single Co-Neighbor Path 4-cycle (two early vertices whose later neighborhoods share a common pair), then measure the selection probability of the affected late vertex; the paper's analysis says this is precisely where the supermartingale inequality can fail, so a constant-factor drop in in","supporting_citations":[],"review_version":1}