{"id":"c08b0e8e-8842-4570-9adb-6eb2320377d7","arxiv_id":"2501.00567","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Resolves the Kelly-Postle local Shearer conjecture by constructing, for every triangle-free graph, a distribution over independent sets with vertex inclusion probability (1-o(1)) ln d(v)/d(v).","lead":"This paper proves a local strengthening of Shearer's independence bound for triangle-free graphs: every vertex can be covered with probability about (ln d)/d by a random independent set. The authors use it to settle two conjectures in fractional coloring and to give a spectral-radius upper bound on the fractional chromatic number.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Theorem 2.1 drops a term by asserting without proof that x f'(x) z - 2ε² ≤ 0, but this quantity can be positive when the neighborhood weight exceeds the vertex weight, so the displayed step is not justified.","rationale":"The reader's verdict is CONDITIONAL, and the reader's weakest_assumption is exactly the same sign step I identify: the displayed inequality before 'Rearranging yields' requires T = x f'(x) z - 2ε² ≤ 0, but this is neither proved nor generally true. My independent check confirms that T can be positive when the neighborhood weight exceeds the vertex weight; for example, with x=3, w(v)=0.2, w(N)=0.6, and ε=0.01, T is positive. The proof's final contradiction depends on dropping the nonnegative term -εaT, so the gap is load-bearing rather than cosmetic. All other parts of the paper—the induction setup, the compactness argument, the random process, and the deductions of Theorems 1.2, 1.4, 1.5, and 1.6 from Theorem 2.1—appear internally coherent provided Theorem 2.1 holds. Because the issue is a specific unproved inequality in the key proof and the result may well be repairable, the appropriate verdict remains CONDITIONAL, matching the reader's assessment.","tokens_in":14207,"tokens_out":19878,"duration_ms":196201,"concrete_test":"Compute T = x z f'(x) - 2ε² for a star graph with w(center)=0.6, w(v)=0.2, w(other leaf)=0.2, and ε=0.01, taking v to be the leaf. Then x=3, z=-0.004, and T≈3.9·10⁻⁴ > 0, directly falsifying the asserted inequality T≤0. Independently re-derive the displayed chain before 'Rearranging yields' while keeping the term -ε(w(v)+w(N_G(v)))T; if T>0, the resulting inequality δ₀-δ > εδ₀-2ε² does not follow and the contradiction collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Theorem 2.1, after bounding f(x exp(z)) from below, the authors need to replace (1 - εa)(f(x) + T) by f(x) + T - εa f(x), where a = w(v) + w(N_G(v)) and T = x z f'(x) - 2ε². This replacement is valid only when T ≤ 0. The manuscript inserts an underbrace '<0' but gives no proof of T ≤ 0. The assertion is not generally true: taking x = 3, w(v) = 0.2, w(N_G(v)) = 0.6, and ε = 0.01 gives z = -0.004, f'(3) ≈ -0.0493, and T = 3·(-0.004)·(-0.0493) - 2·10⁻⁴ ≈ 3.9·10⁻⁴ > 0. This is a legitimate configuration (e.g., a star with center weight 0.6, the tested leaf weight 0.2, and another leaf weight 0.2, all normalized). The subsequent simplification uses the differential equation to cancel the main terms, but the removed term -εaT is nonnegligible when T > 0, and the final contradiction δ₀²/8 > δ₀²/8 relies exactly on T ≤ 0. The proof neither derives T ≤ 0 from the choice of the violating vertex nor offers an alternative. Without repairing this sign step, Theorem 2.1 is not established as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves a local strengthening of Shearer's independence bound for triangle-free graphs: for every triangle-free graph there is a probability distribution on its independent sets such that each vertex v is included with probability (1-o(1)) ln d(v)/d(v). The proof is organized around a weighted technical theorem, Theorem 2.1, proved by induction together with a compactness/linear-programming argument. From Theorem 2.1 the authors derive the conjectured fractional chromatic number bound of Cames van Batenburg et al. for n-vertex triangle-free graphs, an edge-count analogue, and the spectral bound chi_f(G) <= (1+o(1)) rho(G)/ln rho(G).","tokens_in":14589,"tokens_out":15265,"duration_ms":148006,"significance":"If the main theorem is correct, it resolves a 2018 conjecture of Kelly and Postle and confirms the subsequent conjectures of Cames van Batenburg et al.; the spectral application is also a natural and notable strengthening of the fractional version of Molloy's bound. The deduction of Theorems 1.2, 1.4, 1.5, and 1.6 from Theorem 2.1 is clean and mostly self-contained, with no fitted parameters. The key proof is, however, invalid at a load-bearing sign step, as detailed below.","major_comments":[{"comment":"The displayed chain immediately after 'Plugging this estimate into the above lower bound' replaces (1 - epsilon a)(f(x) + T) by f(x) + T - epsilon a f(x), where a = w(v) + w(N_G(v)) and T = x z f'(x) - 2 epsilon^2. This is a valid lower bound only if T <= 0, as the manuscript's underbrace '<0' asserts. No proof of T <= 0 is given, and the assertion is not generally true for the admissible positive weight assignments: for example, with w(v) = 0.2, w(N_G(v)) = 0.6 (so x = 3), and epsilon = 0.01, one has z = -0.004, f'(3) approximately -0.0493, and T approximately 3.9 x 10^-4 > 0. Such weights are compatible with the proof because the weights are arbitrary strictly positive functions normalized to total weight 1. The subsequent 'Rearranging yields' step and the final contradiction delta_0^2/8 > delta_0^2/8 rely exactly on this sign: if T > 0, the same computation gives delta_0^2/8 > delta_0^2/8 - epsilon a T, which is true rather than absurd. Since the proof of Theorem 2.1 neither derives T <= 0 from the choice of the violating vertex nor offers an alternative argument, Theorem 2.1 is not established as written.","section":"Section 2, proof of Theorem 2.1"}],"minor_comments":[{"comment":"The notation N_G is overloaded: in the statement of Theorem 2.1 it denotes the open neighborhood, while in the proof N_G(u) is explicitly redefined as the closed neighborhood. This makes later expressions such as x in V(G) \\ N_G(v) ambiguous and should be clarified.","section":"Section 2 and Theorem 2.1"},{"comment":"In the Claim, the inequality replacing 1/(1 - epsilon w(N_G(v))) by 1 uses that w(N_G(y)) - w(v) >= 0 for y in N_G(v); this follows from v in N_G(y) and positivity of w, but it is not stated and should be made explicit.","section":"Section 2, proof of the Claim"},{"comment":"There is a typographical error in the line 'chi_f(G) <= 1/f(rho(G)))': an extra closing parenthesis appears after rho(G).","section":"Proof of Theorem 1.6"},{"comment":"The abstract contains several typographical artifacts, including 'W e' and 'cl assic'; these should be corrected in the final version.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The sign error in the proof of Theorem 2.1 is genuine and central; I verified the algebra around the dropped term -epsilon a T. The surrounding framework is plausible and the derivation of the corollaries from Theorem 2.1 is essentially correct, so I am not recommending rejection. The authors should be asked either to prove T <= 0 under a justified choice of the violating vertex and weight assignment, or to modify the induction/contradiction argument so that the sign of the dropped term is handled. If the step cannot be repaired, the main theorem is unproved. I see no circularity or hidden parameter fitting in the manuscript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What you should know: this paper claims the local Shearer bound, resolving Kelly–Postle's main conjecture and the Cames van Batenburg et al. conjecture on fractional chromatic number, plus a spectral-radius bound. The structure is sound: all the corollaries (Theorems 1.2, 1.4, 1.5, 1.6) follow from the weighted Theorem 2.1, and I checked those derivations—they are clean and plausible. The weighted theorem itself is genuinely new, and the induction-plus-LP compactness argument is a natural and clever framework. The spectral application is a nice touch, not a routine extension.\n\nThe problem is in the proof of Theorem 2.1. After the Taylor estimate, the authors have a lower bound of the form (1 − εa)(f(x)+T), with T = x f'(x) z − 2ε². They replace this by f(x)+T−εa f(x), dropping the term −εa T. That is valid only if T ≤ 0. The text puts an underbrace '<0' on the bracket, but no proof. And it is not generally true: take x = 3, w(v)=0.2, w(N(v))=0.6, ε=0.01; then z = −0.004, f'(3)≈−0.0493, and T≈3.9·10⁻⁴ > 0. This is a legitimate configuration in a triangle-free graph (e.g., a leaf with a heavy neighbor and one other vertex). So the displayed inequality does not hold as written. The final contradiction δ0²/8 > δ0²/8 depends exactly on that step.\n\nI don't see anything in the choice of the violating vertex that forces T ≤ 0. The proof of Theorem 2.1 is therefore not established as written. The gap is load-bearing, but I would not call the paper incoherent or the approach hopeless. The rest of the writing is careful, the literature is handled honestly, and the corollary work shows real skill. The likely fix is to handle positive T separately or to modify the random process/choice of ε; my guess is the result is true.\n\nVerdict: this deserves serious refereeing, not a desk reject. Send it out, but the referee should demand a repaired sign argument. I would not cite the weighted theorem as a proven result until that appears; the conjecture resolutions are conditional on it.","headline":"A serious and likely correct line of attack on two 2018 conjectures, but the proof of the key weighted theorem has an unproven sign step that needs repair.","tokens_in":15080,"tokens_out":6299,"would_cite":false,"duration_ms":56996,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C35","05C69","05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every triangle-free graph admits a probability distribution on independent sets that contains each degree-$d$ vertex with probability at least $(1-o(1))\\ln d/d$.","keywords":["triangle-free graphs","independence number","fractional chromatic number","Shearer bound","local demands","spectral radius","independent sets","weighted graph coloring"],"falsifier":"Take a triangle-free graph and positive weights with $w(N_G(v))>w(v)$ at some vertex $v$, and check the sign of $x f'(x) z-2\\varepsilon^2$ with $x=w(N_G(v))/w(v)$ and $z=\\varepsilon(w(v)-w(N_G(v)))$ for small $\\varepsilon$; when it is positive, the inequality before \"Rearranging yields\" in the proof is invalid, so the stated weighted theorem would need a different argument.","tokens_in":14021,"feed_emoji":"🎲","tokens_out":13545,"duration_ms":118690,"temperature":0.7,"pith_summary":"The paper proves a local, degree-by-degree strengthening of Shearer's independence bound: in every triangle-free graph, one can choose a probability distribution over independent sets so that each vertex $v$ is included with probability at least $(1-o(1))\\ln d(v)/d(v)$, where $d(v)$ is its degree. This is exactly the guarantee conjectured in 2018 for fractional coloring with local demands. As a consequence the paper confirms the predicted bound $\\chi_f(G)\\le(\\sqrt{2}+o(1))\\sqrt{n/\\ln n}$ for $n$-vertex triangle-free graphs, proves an analogous bound in terms of the number of edges, and obtains a spectral bound $\\chi_f(G)\\le(1+o(1))\\rho(G)/\\ln\\rho(G)$. A weighted version of the result is the engine behind all four applications.","feed_headline":"Local Shearer bound holds for every triangle-free graph","feed_subtitle":"One random independent set covers each degree-d vertex with chance about ln d / d, settling a 2018 coloring conjecture.","key_machinery":"The carrying object is the function $f(x)$, the continuous extension of $(1-x+x\\ln x)/(x-1)^2$ to $[0,\\infty)$, with $f(0)=1$, $f(1)=1/2$, and $f(x)=(1-o(1))\\ln x/x$ as $x\\to\\infty$; it satisfies the differential equation $x(x-1)f'(x)+(x+1)f(x)=1$. The proof of Theorem 2.1 inducts on the number of vertices, maintaining the smallest possible uniform slack $\\delta_0$. At the contradiction step it perturbs weights by $w'(v)=w(v)\\exp(\\varepsilon w(N_G(v)))$ and mixes the distribution on $G$ with distributions on $G-N_G[u]$, using convexity of $f$ and the differential equation to make all lower-order terms cancel.","core_discovery":"The central claim is Theorem 2.1: for every triangle-free graph $G$ and every strictly positive vertex weight function $w$, there exists a probability distribution on the independent sets of $G$ with $\\mathbb{P}_{I\\sim D}[v\\in I]\\ge f(w(N_G(v))/w(v))$ for all $v$, where $f$ is Shearer's function, the continuous extension of $(1-x+x\\ln x)/(x-1)^2$. The all-weights-one case gives the local Shearer bound of Theorem 1.2, and choosing weights from a Perron–Frobenius eigenvector gives the spectral bound. The authors view the weighted theorem as the real contribution, from which the $n$-vertex, edge, and spectral bounds follow by short arguments.","pith_inferences":["The sign condition that appears unproved in Theorem 2.1 may be repairable by letting $\\varepsilon$ shrink with $x-1$ or by using a higher-order Taylor expansion; whether the weighted theorem survives this repair is independent of the truth of its corollaries.","The spectral proof only uses triangle-freeness to keep neighborhoods disjoint; the same eigenvector-weighting trick may extend to $K_{r+1}$-free graphs with the corresponding Shearer-type function.","The paper's existential compactness argument suggests an LP formulation; an efficient rounding algorithm for the independent-set distribution would make the local bound algorithmic, which the current proof does not provide.","Because the theorem's applications rely only on two specific weight choices, a counterexample to the full weighted statement would not necessarily refute any of Theorems 1.2, 1.4, 1.5, or 1.6."],"forward_implications":["The local demand version of fractional coloring is confirmed: each vertex $v$ can be assigned a measurable subset of $[0,1]$ of measure $(1-o(1))\\ln d(v)/d(v)$ so that adjacent vertices receive disjoint subsets.","The fractional chromatic number of every $n$-vertex triangle-free graph is at most $(\\sqrt{2}+o(1))\\sqrt{n/\\ln n}$, matching the conjectured maximum.","For triangle-free graphs with $m$ edges, the fractional chromatic number is at most $(18^{1/3}+o(1))m^{1/3}/(\\ln m)^{2/3}$, close to the conjectured $16^{1/3}$ version.","Every triangle-free graph satisfies $\\chi_f(G)\\le (1+o(1))\\rho(G)/\\ln\\rho(G)$, saving a logarithmic factor over the classical spectral bound on the chromatic number.","The all-ones and Perron–Frobenius weight choices recover the original Shearer bound and the spectral bound from the same weighted theorem."],"supporting_citations":[{"why":"Supplies the original bound and the function $f$ being localized.","marker":"[44]"},{"why":"Provides the degree-sequence strengthening whose expected size the new distribution reproduces.","marker":"[45]"},{"why":"Raises the local conjecture, gives its equivalence with local-demand h-colorings, and supplies the bridge to the $n$-vertex fractional chromatic number bound.","marker":"[35]"},{"why":"Poses the conjectured fractional chromatic number bounds in terms of $n$ and $m$ that Theorems 1.4 and 1.5 target.","marker":"[12]"},{"why":"Gives the maximum-degree fractional bound that the local result extends.","marker":"[40]"},{"why":"Supplies the Perron–Frobenius theorem used to turn the spectral radius eigenvector into a positive vertex weighting.","marker":"[30]"}],"fun_headline_variants":["Local Shearer bound proven for all triangle-free graphs","Random independent sets hit each vertex with local probability","Settling 2018 coloring conjecture with local Shearer","Weighted Shearer theorem yields spectral bound","Triangle-free graphs: local independence bound resolved"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a certain error term at the single vertex that violates the claimed probability is automatically nonpositive; the paper does not prove this sign condition, and it can fail when a vertex's neighborhood carries more total weight than the vertex itself.","fun_headline_variants_meta":{"raw":{"variants":["Local Shearer bound proven for all triangle-free graphs","Random independent sets hit each vertex with local probability","Settling 2018 coloring conjecture with local Shearer","Weighted Shearer theorem yields spectral bound","Triangle-free graphs: local independence bound resolved"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000156,"raw_usage":{"total_tokens":1236,"prompt_tokens":984,"completion_tokens":252,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":600,"completion_tokens_details":{"reasoning_tokens":179}},"tokens_in":600,"tokens_out":252,"duration_ms":7402,"temperature":1.0,"reasoning_tokens":179,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:51:46.393223+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a triangle-free graph and positive weights with $w(N_G(v))>w(v)$ at some vertex $v$, and check the sign of $x f'(x) z-2\\varepsilon^2$ with $x=w(N_G(v))/w(v)$ and $z=\\varepsilon(w(v)-w(N_G(v)))$ for small $\\varepsilon$; when it is positive, the inequality before \"Rearranging yields\" in the proof is invalid, so the stated weighted theorem would need a different argument.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the original bound and the function $f$ being localized."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the degree-sequence strengthening whose expected size the new distribution reproduces."},{"cited_title":"Kelly and L","cited_arxiv_id":null,"evidence_quote":"Raises the local conjecture, gives its equivalence with local-demand h-colorings, and supplies the bridge to the $n$-vertex fractional chromatic number bound."},{"cited_title":"Cames van Batenburg, R","cited_arxiv_id":null,"evidence_quote":"Poses the conjectured fractional chromatic number bounds in terms of $n$ and $m$ that Theorems 1.4 and 1.5 target."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the maximum-degree fractional bound that the local result extends."}],"review_version":1}