{"id":"8f44e13f-f3b8-4a92-8689-399ca2bd21d6","arxiv_id":"2507.09832","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Sparse connected graphs with at most n(1+1/(204k^3+126k^2)) edges are shown to have Ramsey number 2n-1 against fans F_k, with a similar result for multiple fans.","lead":"This paper proves that connected graphs with n vertices and up to roughly n plus n over a polynomial in k edges are fan-good: their Ramsey number with a fan graph F_k is exactly 2n minus 1. The result makes the threshold c(n) in Brennan's question arbitrarily large for large n, and it extends to disjoint unions of fans.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7, Case 1: the claimed equality a ≥ (2k^2+3k+1)t−1 = (k+1)t((2k+1)t−1)+kt is false for t ≥ 2, so Lemma 3's hypothesis a ≥ b(c−1)+d is not met and the proof of the multi-fan theorem fails as written.","rationale":"The reader's verdict is CONDITIONAL, and the strongest concrete reason is the Case 1 algebra in Theorem 7. I verified the computation: for t ≥ 2 the claimed equality is false by a positive amount (t−1)[(2k^2+3k+1)t−1], so Lemma 3's numerical hypothesis is not met by the stated suspended-path lower bound. This is a genuine internal inconsistency, not a disagreement with consensus, and it is more decisive than the reliance on the same-author preprints: even if Lemmas 2, 9, and 13 are all correct, the written proof of Theorem 7 fails at this step. I did not find a comparable error in Theorem 5; its Lemma 3 application is the t=1 case where the equality holds. Because the flaw is localized and a quadratic path threshold or repeated Lemma 3 applications would likely repair it, CONDITIONAL is the appropriate verdict rather than REJECT. The preprint borrowings should still be independently verified, but they are not the single load-bearing issue for this pass.","tokens_in":19145,"tokens_out":13385,"duration_ms":133650,"concrete_test":"Independently recompute the claimed equality in §5, Case 1. For k=1, t=2, the lower bound on the suspended path is a = (2+3+1)·2−1 = 11, while b(c−1)+d = 4·5+2 = 22, so Lemma 3's hypothesis a ≥ b(c−1)+d fails. More generally, expand b(c−1)+d to see it is (2k^2+3k+1)t^2−t, not (2k^2+3k+1)t−1, for t ≥ 2. If the authors intend to repair the proof, check whether replacing the path-length threshold with (2k^2+3k+1)t^2−t, or applying Lemma 3 iteratively t times, preserves the subsequent inequalities in Case 3.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The decisive load-bearing concern is internal to Theorem 7, not dependent on the cited preprints. In §5, Case 1, when KN−H′ contains a blue tK1,k, the proof sets b=(k+1)t, c=(2k+1)t, d=kt and asserts that the red suspended path P′ has length a ≥ (2k^2+3k+1)t−1 = b(c−1)+d. This equality is false for t ≥ 2: b(c−1)+d = (k+1)t((2k+1)t−1)+kt = (2k^2+3k+1)t^2−t, which exceeds (2k^2+3k+1)t−1 by (t−1)[(2k^2+3k+1)t−1] > 0. Consequently the hypothesis a ≥ b(c−1)+d of Lemma 3 is not guaranteed by the stated lower bound, so the dichotomy \"blue K_{(2k+1)t} or K_{kt}+tK_{1,k}\" does not follow, and the resulting blue tF_k is not obtained in this subcase. Since this is the first subcase of Case 1, Theorem 7 is not established as written. The analogous step in Theorem 5 is the t=1 case, where the equality does hold, so the single-fan theorem appears unaffected by this particular error.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Ramsey goodness of sparse connected graphs with respect to fans. For a connected graph G on n vertices with at most n(1+1/(204k^3+126k^2)) edges and n ≥ 36k^4, it claims r(G,F_k)=2n−1 (Theorem 5), showing that Brennan's threshold c(n) is at least ε(k)n. It further proves an exact formula for stars versus disjoint fans (Theorem 6) and claims r(G,tF_k)=2n+t−2 for n ≥ 161t^2k^4 under a similar edge bound (Theorem 7). The proofs use a trichotomy lemma, path-extension arguments, Hall-type matchings, and upper bounds for Ramsey numbers of sparse graphs versus fans.","tokens_in":19413,"tokens_out":14196,"duration_ms":155868,"significance":"If correct, Theorem 5 answers Brennan's problem in a strong form by showing that c(n) grows linearly in n, and Theorem 7 extends the result to multiple fans. The paper also provides a general upper-bound lemma (Lemma 6) and a star-fan Ramsey formula (Theorem 6) that are of independent interest. The main caveat is that several load-bearing lemmas (Lemmas 2, 9, 13) are taken from the authors' own preprints; I did not find circularity, but the theorems' validity is contingent on those results.","major_comments":[{"comment":"The displayed equality a ≥ (2k^2+3k+1)t − 1 = (k+1)t((2k+1)t − 1) + kt is false for t ≥ 2: the right-hand side equals (2k^2+3k+1)t^2 − t, which exceeds the left-hand side by (t−1)[(2k^2+3k+1)t − 1] > 0. Consequently the hypothesis a ≥ b(c−1)+d of Lemma 3 is not guaranteed, so the dichotomy 'blue K_{(2k+1)t} or K_{kt}+tK_{1,k}' does not follow and the first subcase of Case 1 does not establish a blue tF_k. Since this is the first case in the proof of Theorem 7, the multi-fan theorem is not established as written. The analogous step in Theorem 5 is the t=1 case, where the equality holds. Repairing the proof will likely require a longer suspended path (quadratic in t), which in turn forces changes in the parameters q and s in Lemma 2 and in the inequalities of Case 3.","section":"§5, Case 1"},{"comment":"In both Theorem 7 and Theorem 5, the application of Lemma 3 yields only that certain vertices of the red suspended path are blue-adjacent to every vertex of the blue tK1,k (or K1,k); it does not yield a blue clique among those path vertices. Therefore the stated conclusion 'a blue subgraph Kkt + tK1,k' (and similarly 'Kk + K1,k') is not justified. The desired tF_k (or F_k) can be recovered by pairing the path vertices with the leaves of the stars, so this is a gap rather than a fatal flaw, but the proof should be rewritten accordingly.","section":"§5, Case 1; §3, Case 1"}],"minor_comments":[{"comment":"The expression 'r(G, kK2) + |t − 1)Fk|' should read 'r(G, kK2) + |(t − 1)Fk|'.","section":"§5, Case 3"},{"comment":"In the sentence 'there must be a red H0 in F', the symbol 'F' should be 'KN[S]'.","section":"§5, Case 1"},{"comment":"Lemmas 2, 9, and 13 are taken from preprints by the same author group; the manuscript cites their arXiv numbers, but because the main theorems rely heavily on these results, it would be helpful to state explicitly how each lemma is verified or made available.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The central issue is that Theorem 7 is not established because of the false algebraic equality in Case 1; the fix is likely to require a longer suspended path and a reworking of the parameter estimates. If the authors can repair this, the paper would be a solid contribution. I also recommend that the editor ensure the relied-upon preprints (especially Lemmas 2, 9, and 13) are independently verified, since the main theorems depend on them."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Main take: the paper's headline result is substantive. For connected n-vertex graphs with at most n(1+ε(k)) edges, Theorem 5 proves r(G,F_k)=2n-1, answering Brennan's threshold question by showing c(n) can be arbitrarily large (at least ε(k)n). The proof is long, but I traced the key inequalities in Cases 1–3 and they appear consistent. The structural trichotomy (Lemma 2) is load-bearing and comes from the same authors' preprint, but it is an independent result, not a circular use of the theorem. Same for Lemmas 9 and 13. That reliance is a self-containedness concern, not a fatal one, provided those preprints check out.\n\nThe multi-fan part is where the trouble is. In §5 Case 1, the proof assumes the red suspended path length a ≥ (2k^2+3k+1)t − 1 and claims this equals (k+1)t((2k+1)t−1)+kt. That equality is false for t ≥ 2: the right-hand side is (2k^2+3k+1)t^2 − t, which exceeds the left-hand side by (t−1)[(2k^2+3k+1)t − 1] > 0. So the hypothesis of Lemma 3 (a ≥ b(c−1)+d) is not guaranteed, and the blue K_{(2k+1)t} or K_{kt}+tK_{1,k} dichotomy does not follow. Since this is the first subcase of Case 1, the proof of Theorem 7 fails as written. For t=1 the equality holds, so this particular error does not touch Theorem 5. The gap looks repairable—for instance, requiring a path of length at least (2k^2+3k+1)t^2 − t, or iterating Lemma 3—but as it stands the multi-fan theorem is unproved.\n\nTheorem 6 (star vs tF_k) is proved by induction and appears internally consistent; I did not find an error there. The concluding remark about the trade-off between n and e(G) is honest.\n\nWho this is for: anyone working on Ramsey goodness of sparse graphs. The main theorem is worth serious referee time; the flaw in Theorem 7 should be caught and fixed in revision. I would send it to review, with a clear request that the authors repair the multi-fan proof or remove the claim.","headline":"Theorem 5 looks right and answers Brennan's question; Theorem 7 has a concrete algebraic gap in Case 1, so the multi-fan result is not established as written.","tokens_in":19953,"tokens_out":2620,"would_cite":true,"duration_ms":27217,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C55","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that every connected n-vertex graph with at most n(1+1/(204k^3+126k^2)) edges satisfies r(G,F_k)=2n−1 for n ≥ 36k^4, and the analogous tF_k formula 2n+t−2 under a similar edge bound.","keywords":["Ramsey number","fan graph","sparse graph","Ramsey goodness","suspended path","trichotomy lemma","disjoint unions of fans","edge surplus"],"falsifier":"Substitute k=1,t=2 into the identity in Theorem 7, Case 1: the left side ($2k^{2}$+3k+1)t−1 equals 11, while the right side (k+1)t((2k+1)t−1)+kt equals 22, so the asserted equality fails and the path-extension lemma cannot be applied with the stated length. A corrected proof of Theorem 7 must either provide a longer suspended path or replace that step; for Theorem 5, checking the Trichotomy Lemma [27] and the star-Ramsey bounds [16] on small sparse graphs would settle the load-bearing ingredients.","tokens_in":18896,"feed_emoji":"🧩","tokens_out":16430,"duration_ms":158687,"temperature":0.7,"pith_summary":"The Ramsey number r(G,H) is the smallest N such that every red-blue coloring of K_N contains a red copy of G or a blue copy of H. This paper studies the case where H is a fan F_k, k triangles sharing one common vertex, and asks which sparse connected graphs G are fan-good, meaning r(G,F_k) equals the smallest value 2n−1 allowed by the standard lower bound for connected graphs. The main theorem says that if G has n vertices and at most n(1+1/($204k^{3}$+$126k^{2}$)) edges, then r(G,F_k)=2n−1 for n ≥ $36k^{4}$. Since adding an edge to a connected graph creates at least one cycle, this makes the threshold c(n) in Problem 1 at least a constant multiple of n, so the number of cycles needed to break fan-goodness grows linearly. A second pair of results gives the analogous exact value r(G,tF_k)=2n+t−2 for t disjoint copies of the fan, and the star case r(K_{1,n−1},tF_k)=2n+t−2.","feed_headline":"Sparse graphs stay fan-good up to a linear edge surplus","feed_subtitle":"Connected n-vertex graphs with few extra edges keep the exact Ramsey number 2n−1 against fans, so the failure threshold grows linearly.","key_machinery":"The central object is the fan F_k=K_1+kK_2, k triangles sharing one common vertex, so a blue F_k is exactly a vertex whose blue neighborhood spans k pairwise disjoint edges. The argument is organized by the Trichotomy Lemma [27]: a connected sparse graph either has a long suspended path, or a matching of many end-edges, or a vertex attached to many degree-1 leaves. The long-path case uses a path-extension lemma [3] that either lengthens a red path or forces a blue fan; the matching case uses the bipartite matching lemma [14]; and the leaf-rich case uses the known star value r(K_{1,n−1},F_k)=2n−1 [25] together with a size bound r(G,F_k) ≤ n+2mk−2m/n (Lemma 6). Ramsey bounds for matchings and stars [13, 10, 16] supply the blue structures needed inside neighborhoods.","core_discovery":"The central claim is that fan-goodness is controlled by edge surplus rather than by the particular cycle arrangement. A connected graph G on n vertices with e(G) ≤ n(1+1/($204k^{3}$+$126k^{2}$)) satisfies r(G,F_k)=2n−1 once n ≥ $36k^{4}$, and the same statement is proved for t disjoint fans: r(G,tF_k)=2n+t−2 whenever e(G) ≤ n(1+1/($204tk^{3}$+$147tk^{2}$)) and n ≥ $161t^{2}$$k^{4}$. The paper also proves r(K_{1,n−1},tF_k)=2n+t−2 for n ≥ max{12tk+2k, $4tk^{2}$}. The authors note in the concluding remark that the displayed thresholds are not tight and can be traded off through explicit parameter functions, but that significantly improving them would require different methods.","pith_inferences":["The same three-case structure should transfer to other fixed target graphs of chromatic surplus 1, with the cited star-goodness input replaced by the corresponding goodness statement.","Because the surplus enters the bounds only through constants, the method likely extends to other sparse graph classes defined by a linear edge bound, provided the matching and star Ramsey bounds are adjusted.","A sharpening of the Trichotomy Lemma [27] or the star-Ramsey bounds [16] would automatically improve the linear coefficient in the threshold c(n), since those lemmas are used with slack in the main cases."],"forward_implications":["For every fixed k, the threshold c(n) in Problem 1 is at least n/(204k^3+126k^2), so fan-goodness can fail only after a graph has accumulated linearly many cycles.","Trees and unicyclic graphs are covered by the new edge condition, so the previous F_k-good families are recovered as special cases with a unified proof for n ≥ 36k^4.","For disjoint fans, r(G,tF_k)=2n+t−2 holds for connected n-vertex graphs with at most n(1+1/(204tk^3+147tk^2)) edges and n ≥ 161t^2k^4, and for stars when n ≥ max{12tk+2k, 4tk^2}.","The concluding remark gives trade-off functions showing that the lower bound on n and the upper bound on e(G) can be exchanged, so the clean constants 36k^4 and 161t^2k^4 are conveniences rather than intrinsic boundaries."],"supporting_citations":[{"why":"defines the cycle-count threshold problem and proves the unicyclic base case that the new result extends.","marker":"[4]"},{"why":"supplies the Trichotomy Lemma (Lemma 2) and the kK2 Ramsey bound (Lemma 8) that organize and power the case analysis.","marker":"[27]"},{"why":"supplies the star Ramsey bounds (Lemmas 9 and 13) used to force blue fans in the suspended-path cases.","marker":"[16]"},{"why":"proves stars and trees are F_k-good, providing the base values used in the leaf-rich case and in the t=1 star theorem.","marker":"[25]"},{"why":"provides the path-extension lemma that lengthens red suspended paths or produces a blue fan.","marker":"[3]"},{"why":"provides the bipartite matching alternative used to embed end-edge matchings or force a blue biclique.","marker":"[14]"},{"why":"gives the sparse-graph lemma bounding degree-1 vertices, used to control the reduced graph in Lemma 10 and Case 3.","marker":"[6]"},{"why":"gives the matching Ramsey bound r(G,kK2) used inside Lemma 6 and the matching cases.","marker":"[13]"},{"why":"gives the multiple-copy bound r(G,tH) ≤ r(G,H)+(t−1)|H| used for Corollaries 1 and 2 in the tF_k proof.","marker":"[7]"},{"why":"gives the exact star-versus-matching value r(K_{1,n−1},kK2)=n+k−1 used in Claim 4.1.","marker":"[15]"}],"fun_headline_variants":["Fan-good threshold tied to edge count, not cycle layout","Sparse graphs keep exact Ramsey number against fans","Edge surplus fixes fan-goodness in sparse graphs","Ramsey bound 2n−1 holds for sparse fan-good graphs","Fan-goodness hinges on sparse edge counts"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on the Trichotomy Lemma [27] and the star-Ramsey bounds [16], both cited as preprints, and the displayed identity in Case 1 of the proof of Theorem 7 is algebraically false for t ≥ 2, so Theorem 7 is not established as written even if those lemmas are correct.","fun_headline_variants_meta":{"raw":{"variants":["Fan-good threshold tied to edge count, not cycle layout","Sparse graphs keep exact Ramsey number against fans","Edge surplus fixes fan-goodness in sparse graphs","Ramsey bound 2n−1 holds for sparse fan-good graphs","Fan-goodness hinges on sparse edge counts"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001291,"raw_usage":{"total_tokens":5298,"prompt_tokens":999,"completion_tokens":4299,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":615,"completion_tokens_details":{"reasoning_tokens":4222}},"tokens_in":615,"tokens_out":4299,"duration_ms":37717,"temperature":1.0,"reasoning_tokens":4222,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:53:34.403886+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Substitute k=1,t=2 into the identity in Theorem 7, Case 1: the left side ($2k^{2}$+3k+1)t−1 equals 11, while the right side (k+1)t((2k+1)t−1)+kt equals 22, so the asserted equality fails and the path-extension lemma cannot be applied with the stated length. A corrected proof of Theorem 7 must either provide a longer suspended path or replace that step; for Theorem 5, checking the Trichotomy Lemma [27] and the star-Ramsey bounds [16] on small sparse graphs would settle the load-bearing ingredients.","supporting_citations":[{"cited_title":"Brennan, Ramsey numbers of trees and unicyclic graphs versus fans, Discrete Math","cited_arxiv_id":null,"evidence_quote":"defines the cycle-count threshold problem and proves the unicyclic base case that the new result extends."},{"cited_title":"Zhang and Y","cited_arxiv_id":null,"evidence_quote":"supplies the Trichotomy Lemma (Lemma 2) and the kK2 Ramsey bound (Lemma 8) that organize and power the case analysis."},{"cited_title":"Minimum degree and sparse connected spanning subgraphs","cited_arxiv_id":"2507.03264","evidence_quote":"supplies the star Ramsey bounds (Lemmas 9 and 13) used to force blue fans in the suspended-path cases."},{"cited_title":"Zhang, H","cited_arxiv_id":null,"evidence_quote":"proves stars and trees are F_k-good, providing the base values used in the leaf-rich case and in the t=1 star theorem."},{"cited_title":"Bondy and P","cited_arxiv_id":null,"evidence_quote":"provides the path-extension lemma that lengthens red suspended paths or produces a blue fan."},{"cited_title":"Hall, On representatives of subsets, J","cited_arxiv_id":null,"evidence_quote":"provides the bipartite matching alternative used to embed end-edge matchings or force a blue biclique."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the sparse-graph lemma bounding degree-1 vertices, used to control the reduced graph in Lemma 10 and Case 3."},{"cited_title":"Faudree, R.H","cited_arxiv_id":null,"evidence_quote":"gives the matching Ramsey bound r(G,kK2) used inside Lemma 6 and the matching cases."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the multiple-copy bound r(G,tH) ≤ r(G,H)+(t−1)|H| used for Corollaries 1 and 2 in the tF_k proof."},{"cited_title":"Hu and Y","cited_arxiv_id":null,"evidence_quote":"gives the exact star-versus-matching value r(K_{1,n−1},kK2)=n+k−1 used in Claim 4.1."}],"review_version":1}