{"id":"6145d900-c929-46cf-9ae2-c4bc8cdbbc8b","arxiv_id":"2501.18238","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every triangle-free d-degenerate graph has fractional chromatic number at most (4+o(1))d/ln d, confirming Harris's conjecture.","lead":"A graph theorist has proved a conjecture by Harris: every triangle-free graph with degeneracy d has fractional chromatic number at most O(d/log d). The proof also settles the related Esperet, Kang and Thomassé conjecture on bipartite induced subgraphs.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 2.6 is false as written: X sums final weights of left neighbors, but the probability ratio in Claim 2.2 gives the sum of their weights just before each is processed; these differ already on a triangle-free path.","rationale":"The reader's ACCEPT is not supported by the manuscript as written. The central probability estimate relies on Claim 2.6, and Claim 2.6 is false for a 3-vertex triangle-free path unless the definition of X is changed. The error is internal, not a matter of consensus: the proof itself compares two different quantities and equates them. The triangle-free condition is still essential for the martingale step, but it is not the source of this failure. I found no issue with the degeneracy bound or the deduction of Theorem 1.2 from Theorem 2.1; those parts are clean. Because a one-line correction to the definition of X appears to repair the proof and preserve the theorem, I would not reject the paper or question the conjecture; however, an acceptance should be conditional on the authors fixing the mismatch and supplying the corrected Claim 2.6. The consequence for the Esperet–Kang–Thomassé conjecture is unaffected once Theorem 1.2 is established.","tokens_in":7142,"tokens_out":18893,"duration_ms":162073,"concrete_test":"Compute the original process and the claimed identity for G = the path on {v1,v2,v3} with edges v1v2 and v1v3, vertex order (v1,v2,v3), k=3, and w0(v1)=w0(v2)=w0(v3)=1. Directly: P(v3∈I)=e^{-1}(1-e^{-e})≈0.344. Under the paper's modified process, X=∑_{v_i∈NL(v3)} tilde w_{2}(v_i) equals 0 with probability 1−e^{−e} and e^e otherwise, so the Claim 2.6 right side is (1−e^{−e})(1−e^{−1})+e^{−e}(1−e^{−e^{e^e}})e^{−e^e}≈0.590. The mismatch shows the identity is false as written. As a second check, re-derive Claim 2.2 keeping the exponent ∑ w^a_{i−1}(vi) instead of replacing it by ∑ w^a_{k−1}(vi); this is the exact ratio and the corrected X should be defined from it.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Claim 2.2's proof compares transition probabilities and obtains the factor exp(−∑_{vi∈NL(vk)} w^a_{i−1}(vi)); it then replaces i−1 by k−1, asserting that no vertex is updated after its own step. This is false. In a triangle-free graph a left neighbor vi of vk can be updated by a later vertex vj∉NL(vk), so its final weight differs from its weight at step i−1. Concretely, take the 3-vertex path with edges v1v2 and v1v3, ordering v1,v2,v3, k=3, and weights w0≡1. Then NL(v3)={v1}; step 2 updates v1 (to 0 or to e^e) without touching v3. The paper defines X=∑_{vi∈NL(vk)} tilde w_{k−1}(vi), so here X is 0 with probability 1−e^{−e} and e^e otherwise. Direct computation gives P(v3∈I)=e^{−1}(1−e^{−e})≈0.344, whereas the right side of Claim 2.6 is ≈0.590. Thus the change-of-measure identity, and consequently the proof of Theorem 2.1, is not valid as written. The proof is repairable: define X:=∑_{vi∈NL(vk)} tilde w_{i−1}(vi), the sum of left-neighbor weights just before their own steps; then the ratio exponent, Claim 2.5, Claim 2.6, and the Markov argument line up, and Theorem 1.2 follows. But the submitted text must be corrected before the result is established.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves Harris's conjecture that every triangle-free d-degenerate graph has fractional chromatic number O(d/log d), with the explicit bound (4+o(1))d/log d. The proof introduces a random weight-propagation process that generates an independent set I, and establishes a lower bound (Theorem 2.1) on the probability that a fixed vertex vk belongs to I under a condition on the initial weights of its left neighbours. This yields Theorem 1.2 by taking constant weights, and also a more general local version (Theorem 1.3) that implies the local Shearer bound. As a corollary, the Esperet–Kang–Thomassé conjecture on dense induced bipartite subgraphs follows.","tokens_in":7503,"tokens_out":20301,"duration_ms":159948,"significance":"Resolving a long-standing conjecture with an elegant, self-contained argument gives this paper high significance. The proof is genuinely novel: it uses a change-of-measure identity and a martingale argument rather than the standard entropy or naive first-moment methods. Theorem 1.3 is a natural strengthening that is likely to be of independent interest. I carefully checked the potentially delicate steps (Claims 2.2–2.6) and they are correct. In particular, the equality in Claim 2.2 relating the sums of weights before and after the process is valid because updates in the process only flow from a vertex to its right neighbours (higher indices). The paper correctly derives the known implications for induced bipartite subgraphs, and the constants are computed correctly.","major_comments":[{"comment":"A potential objection to the change-of-measure identity is that the exponent should involve the weight of each left neighbour vi just before its own step, not at time k-1. This concern does not land: in the process, step i only modifies the weights of right neighbours, i.e., vertices with larger index. Hence once all left neighbours of vi (which have index < i) have been processed, the weight of vi is fixed for the rest of the run up to step k-1. Therefore tilde-w_{i-1}(vi)=tilde-w_{k-1}(vi) for every vi in N_L(vk), and the equality in Claim 2.2 is valid. The counterexample on a 3-vertex path misidentifies the update direction: a later vertex vj with j>i cannot update vi, since that would require vi to be a right neighbour of vj, forcing j= (1/4-o(1)) ln d / d to the fractional chromatic number is clear, but it may be worth adding a sentence spelling out that one obtains an independent-set distribution with vertex probabilities at least this value, so that the reciprocal gives the claimed upper bound.","section":"Proof of Theorem 1.2"}],"recommendation":"minor_revision","confidential_remarks":"The paper is a significant and correct advance, and the only required changes are typographical and presentational. The stress-test concern about Claim 2.2 does not survive a careful reading: the equality in question is valid because of the direction of updates in the process. I recommend minor revision, with the understanding that the mathematical content is sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is the real thing, and it deserves a serious referee. The paper proves Harris's conjecture with a (4+o(1)) d/ln d bound, and Theorem 1.3 is a genuinely broader statement that recovers the local Shearer bound. The proof technique is new to this area: a random weight process where the weights of left neighbors form a martingale, combined with a change-of-measure that expresses the inclusion probability as an expectation involving an exponential factor. That is not a routine tweak of existing methods.\n\nThe central lemma, Theorem 2.1, is proved carefully. Claims 2.2 through 2.6 all check out. In particular, the step that the stress-test note flags—replacing w_{i-1}(vi) with w_{k-1}(vi) for left neighbors of vk—is valid. Updates in the process only flow to right neighbors, so once we pass step i-1, no later step can touch vi. The concrete path example in the stress test is wrong: with ordering v1,v2,v3, step 2 updates v3, not v1, because v1 is not a right neighbor of v2. So the martingale identity and Claim 2.6 stand. The application to Theorem 1.2 is a direct substitution, and the derivation of the Esperet-Kang-Thomassé conjecture follows exactly as the reader's report says.\n\nThere are no serious soft spots. The constant 4 is probably not optimal, and the paper says so; Conjecture 1.4 about the optimal constant being 1 is clearly labeled as a conjecture. Remark 2.7 notes that the constant in Theorem 1.3 can likely be improved with more work. These are minor. The citation pattern is clean: Harris is cited as the source of the conjecture, and the few self-citations are comparisons with earlier work, not inputs to the argument. The proof is self-contained and does not assume any equivalent form of the target result.\n\nThis is a major within-field result: a well-known conjecture that had seen no asymptotic improvement over the trivial O(d) bound is now settled, with a compact and apparently correct proof. It belongs in a strong combinatorics journal. Send it to serious referees. I would be glad to see it cited and would bring it to a reading group.\n\nRecommendation: accept after the usual refereeing, with attention to presentation and the exact constants, but no fundamental worry about the main argument.","headline":"Harris's conjecture is proved by a clean change-of-measure argument, and the stress-test concern about Claim 2.6 does not survive a reading of the actual update rule.","tokens_in":7992,"tokens_out":2976,"would_cite":true,"duration_ms":30890,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C69","60G42"],"pacs":[],"model":"deepseek-v4-flash","headline":"A random weight process proves that triangle-free d-degenerate graphs have fractional chromatic number at most (4+o(1))d/ln d.","keywords":["fractional chromatic number","degeneracy","triangle-free graphs","random independent set","martingale","local triangle bound","induced bipartite subgraph","local Shearer bound"],"falsifier":"Find a sequence of triangle-free $d$-degenerate graphs $G_d$ with $d\\to\\infty$ and $\\chi_f(G_d) > (4+\\varepsilon) d/\\ln d$ for some fixed $\\varepsilon>0$; for example, solve the fractional chromatic number linear program on explicit high-girth or random sparse triangle-free constructions. Since the theorem is asymptotic, a single counterexample at one value of $d$ would not refute it.","tokens_in":6947,"feed_emoji":"📐","tokens_out":18458,"duration_ms":154238,"temperature":0.7,"pith_summary":"Fractional chromatic number relaxes ordinary coloring: it is the smallest real $k$ for which independent sets can be weighted so that every vertex is covered with total weight at least $1/k$. For $d$-degenerate triangle-free graphs, only the trivial $O(d)$ upper bound was known despite a well-known conjecture that $O(d/\\ln d)$ should hold. This paper proves that conjecture, showing $\\chi_f(G) \\le (4+o(1))\\, d/\\ln d$ for every triangle-free $d$-degenerate graph. A direct consequence is the conjecture that every triangle-free graph of minimum degree $d$ has an induced bipartite subgraph of minimum degree $\\Omega(\\ln d)$. The proof constructs a random independent set with uniform vertex-inclusion probability about $(1/4)\\ln d / d$, which is exactly what a fractional coloring needs.","feed_headline":"Triangle-free d-degenerate graphs now have fractional chromatic bound d/log d","feed_subtitle":"A martingale argument proves the long-open conjecture and yields an induced bipartite subgraph of degree Ω(log d) in every triangle-free…","key_machinery":"The central object is a random weight process on vertices in a fixed degeneracy ordering, together with a martingale comparison and a change-of-measure identity. For a fixed target $v_k$, the paper runs a modified process in which every left-neighbor of $v_k$---a neighbour earlier in the order---is forced to take the multiplicative branch; triangle-freeness guarantees that no two left-neighbors of $v_k$ are adjacent, so their weights are never killed and form martingales. The change-of-measure identity relates the original and modified processes and gives $\\mathrm{P}(v_k \\in I)=\\mathbb{E}[(1-e^{-w_0(v_k)e^X})e^{-X}]$, where $X$ is the sum of the modified left-neighbor weights. Markov's inequality bounds $X$ with probability at least $1/2$, and the choice $w_0\\equiv (\\ln d - 2\\ln\\ln d)/(2d)$ makes $w_0(v_k)e^X \\le (1/2)\\ln d$ on that event, yielding the uniform inclusion bound.","core_discovery":"The central claim is Theorem 1.2: if $G$ is triangle-free and $d$-degenerate, then $\\chi_f(G) \\le (4+o(1))\\, d/\\ln d$, where the $o(1)$ term goes to $0$ as $d$ goes to infinity. The proof fixes a degeneracy ordering $v_1,\\ldots,v_n$ and runs a random weight process: at step $i$, with probability $1-e^{-w(v_i)}$ the vertex $v_i$ joins the independent set $I$ and all weights of its later neighbours are set to $0$, while otherwise the later neighbours' weights are multiplied by $e^{w(v_i)}$. For each vertex $v_k$, the analysis gives $\\mathrm{P}(v_k \\in I) \\ge (1/4-o(1))\\ln d/d$, uniformly over vertices, and the fractional chromatic bound follows because $\\chi_f(G)$ is the reciprocal of the best uniform inclusion probability. The same process is stated more generally in Theorem 1.3: for any triangle-free graph and any $p$ satisfying $p(v_i) \\le \\prod_{v_j \\in N_L(v_i)} (1-p(v_j))$, where $N_L(v_i)$ is the set of neighbours of $v_i$ that appear earlier in the order, the random independent set includes $v_i$ with probability at least $\\alpha p(v_i)$, with $\\alpha=(1-e^{-1/2})/2 \\approx 0.196$. Ordering vertices by decreasing degree and taking $p(v_i)=\\Theta(\\ln d(v_i)/d(v_i))$ recovers the local Shearer bound up to constants.","pith_inferences":["The only place triangle-freeness enters is the martingale claim, so analogous bounds should hold for any vertex ordering in which left-neighbors of a vertex are pairwise non-adjacent; the local-triangle-bound result is a first step in that direction.","Theorem 1.3 can be read as a feasible-region statement: a target inclusion vector $p$ is realizable up to constant $\\alpha$ by a random independent set whenever each $p(v_i)$ is at most the product of $(1-p(v_j))$ over earlier neighbors. This resembles a hard-core occupancy condition and may support sampling or approximate fractional-coloring algorithms for sparse triangle-free graphs.","If the leading constant is indeed $1$, the proof strategy would need to extract more from the distribution of $X$; the paper's remark that $\\alpha$ can be raised to $1/4$ is a hint that the current analysis is not tight."],"forward_implications":["The main conjecture is confirmed: every triangle-free $d$-degenerate graph has fractional chromatic number at most $(4+o(1))d/\\ln d$, giving the first improvement over the trivial $O(d)$ bound.","The induced bipartite subgraph conjecture follows directly: every triangle-free graph of minimum degree $d$ has an induced bipartite subgraph of average degree at least $(1/4-o(1))\\ln d$, hence of minimum degree $\\Omega(\\ln d)$.","For graphs with local triangle bound $y$, combining the theorem with a known lemma gives $\\chi_f(G)=O(d/\\ln(d^2/y))$, extending the result to locally sparse graphs.","The general Theorem 1.3 recovers, up to constant factors, the local Shearer bound when vertices are ordered by decreasing degree.","The optimal leading constant is now known to lie between $1/2$ and $4$, with $1$ conjectured as the true value."],"supporting_citations":[{"why":"States the conjecture being proved and supplies the lemma used to derive the locally sparse version of the theorem.","marker":"[14]"},{"why":"Provides the theorem converting a fractional chromatic bound into an induced bipartite subgraph of large average degree, so the bipartite-subgraph consequence follows directly.","marker":"[13]"},{"why":"Supplies the previous best bound in the bipartite-subgraph application, the result the new theorem improves by a factor $\\Theta(\\log\\log d)$.","marker":"[22]"},{"why":"Gives the lower bound for the leading constant, yielding $1/2 \\le C \\le 4$ when combined with the new upper bound.","marker":"[4]"},{"why":"Formulates the local Shearer bound that Theorem 1.3 recovers up to constant factors.","marker":"[20]"},{"why":"Proves the local Shearer bound; Theorem 1.3 is presented as the more general statement from which it follows.","marker":"[24]"}],"fun_headline_variants":["Harris' χ_f conjecture proved for triangle-free d-degenerate graphs","Triangle-free d-degenerate graphs meet Harris' χ_f bound","Triangle-free d-degenerate graphs: χ_f ≤ (4+o(1)) d/ln d","Solving Harris: χ_f of triangle-free d-degenerate graphs is O(d/log d)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the graph is triangle-free: the proof's martingale step fails if two left-neighbors of the same vertex are adjacent, because then one could kill the other's weight during the process and the probability identity would no longer yield the lower bound.","fun_headline_variants_meta":{"raw":{"variants":["Harris' χ_f conjecture proved for triangle-free d-degenerate graphs","Triangle-free d-degenerate graphs meet Harris' χ_f bound","Triangle-free d-degenerate graphs: χ_f ≤ (4+o(1)) d/ln d","Solving Harris: χ_f of triangle-free d-degenerate graphs is O(d/log d)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002241,"raw_usage":{"total_tokens":8754,"prompt_tokens":1123,"completion_tokens":7631,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":739,"completion_tokens_details":{"reasoning_tokens":7545}},"tokens_in":739,"tokens_out":7631,"duration_ms":55280,"temperature":1.0,"reasoning_tokens":7545,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T00:14:18.391243+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a sequence of triangle-free $d$-degenerate graphs $G_d$ with $d\\to\\infty$ and $\\chi_f(G_d) > (4+\\varepsilon) d/\\ln d$ for some fixed $\\varepsilon>0$; for example, solve the fractional chromatic number linear program on explicit high-girth or random sparse triangle-free constructions. Since the theorem is asymptotic, a single counterexample at one value of $d$ would not refute it.","supporting_citations":[{"cited_title":"Harris: Some results on chromatic number as a funct ion of triangle count, SIAM Journal on Discrete Mathematics 33(1), 2019, 546-–563","cited_arxiv_id":null,"evidence_quote":"States the conjecture being proved and supplies the lemma used to derive the locally sparse version of the theorem."},{"cited_title":"Esperet, R","cited_arxiv_id":null,"evidence_quote":"Provides the theorem converting a fractional chromatic bound into an induced bipartite subgraph of large average degree, so the bipartite-subgraph consequence follows directly."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the previous best bound in the bipartite-subgraph application, the result the new theorem improves by a factor $\\Theta(\\log\\log d)$."},{"cited_title":"Bollob´ as: The independence ratio of regular graphs, Proc","cited_arxiv_id":null,"evidence_quote":"Gives the lower bound for the leading constant, yielding $1/2 \\le C \\le 4$ when combined with the new upper bound."},{"cited_title":"Kelly, L","cited_arxiv_id":null,"evidence_quote":"Formulates the local Shearer bound that Theorem 1.3 recovers up to constant factors."},{"cited_title":"Local Shearer bound","cited_arxiv_id":"2501.00567","evidence_quote":"Proves the local Shearer bound; Theorem 1.3 is presented as the more general statement from which it follows."}],"review_version":1}