Pith. sign in

REVIEW 2 major objections 3 minor 27 references

Fan-goodness of sparse graphs

T0 review · 2 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2507.09832 v1 pith:42C6UZQA submitted 2025-07-13 math.CO

Ting Huang , Yanbo Zhang , Yaojun Chen This is my paper · ORCID
classification math.CO MSC 05C5505C35
keywords Ramseynumberfangraphsparsegoodnesssuspendedpathtrichotomylemmadisjointunionsoffansedgesurplus
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

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.

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 (2)
  1. [§5, Case 1] 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.
  2. [§5, Case 1; §3, Case 1] 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.
minor comments (3)
  1. [§5, Case 3] The expression 'r(G, kK2) + |t − 1)Fk|' should read 'r(G, kK2) + |(t − 1)Fk|'.
  2. [§5, Case 1] In the sentence 'there must be a red H0 in F', the symbol 'F' should be 'KN[S]'.
  3. [References] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the sparse-graph fan Ramsey bounds are derived from external structural and matching lemmas, and the same-author preprints cited are independent results whose hypotheses do not include the target theorem.

full rationale

The paper's lower bounds come from Burr's standard inequality (1), and the upper-bound proofs are explicit embedding arguments using Bondy-Erdos's Lemma 3, Hall's Theorem, Lemma 6 (proved in the paper by induction and Faudree-Schelp-Sheehan's Lemma 5), and external results such as Chvatal's tree theorem and Zhang-Broersma-Chen's star/fan theorem. No fitted parameter is renamed as a prediction, and no uniqueness theorem is imported from the authors to force a choice. Lemma 2 (Trichotomy), Lemma 9 (sparse star-fan Ramsey bound), and Lemma 13 (sparse multi-star Ramsey bound) are cited from the same authors' preprints [27] and [16]. These are load-bearing in the proof, but they are independent results: Lemma 2 is a structural statement about sparse graphs with no suspended paths or many end-edges, and Lemmas 9 and 13 assert Ramsey bounds for stars and disjoint unions of stars under explicit edge-density hypotheses. None of these hypotheses includes the conclusion r(G,F_k)=2n-1 or r(G,tF_k)=2n+t-2, so the citations are genuine evidence rather than a hidden assumption of the target statement. The same holds for Lemma 8 and the use of Lemmas 7 and 8 in the matching arguments. One non-circularity concern should be flagged: in Section 5, Case 1, the proof of Theorem 7 asserts "a ≥ (2k^2+3k+1)t−1 = (k+1)t((2k+1)t−1)+kt", but the right-hand side equals (2k^2+3k+1)t^2 − t, which exceeds the left-hand side for every t ≥ 2. Therefore the hypothesis a ≥ b(c−1)+d of Lemma 3 is not guaranteed by the displayed bound, so that subcase is not established as written. This is an internal algebraic error in a proof, not a circular dependence, so it does not affect the circularity score; it is a correctness risk. Because the central derivation is self-contained against external benchmarks and the same-author citations are independent supporting results, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The paper introduces no new entities or fitted parameters. It rests on a chain of recently established lemmas, several from the same authors' preprints, which are load-bearing but not proved here. No free parameters because the constants in the bounds are explicit functions of k and t with no fitting to data.

assumptions (7)
  • domain assumption Lemma 2 (Trichotomy Lemma) from Zhang-Chen [27] is correct as stated
    Used in Case 3 of Theorems 5 and 7 to bound the 2-core size and find a high-degree vertex adjacent to many leaves. Same-author preprint, not proved in this paper.
  • domain assumption Lemma 9 (r(G,K_{1,k}) bound) from Huang-Zhang-Chen [16] is correct
    Used in Lemma 10 and Case 1 of Theorem 5. Same-author preprint.
  • domain assumption Lemma 13 (r(G,tK_{1,k}) bound) from Huang-Zhang-Chen [16] is correct
    Used in Case 1 of Theorem 7. Same-author preprint.
  • domain assumption Theorem 2 (star-fan Ramsey numbers) from Zhang-Broersma-Chen [25] is correct
    Used to find red K_{1,n-1} in Case 3 of Theorem 5 and as base case in Theorem 6.
  • domain assumption Lemma 8 (r(G,kK2) exact value) from Zhang-Chen [27] is correct
    Used in Lemma 10 and Cases 2 and 3 of Theorem 5.
  • standard math Burr's general lower bound for Ramsey numbers (inequality (1))
    Gives r(G,F_k) ≥ 2n-1 and r(G,tF_k) ≥ 2n+t-2; the paper proves matching upper bounds.
  • standard math Hall's theorem, Lemma 3 (Bondy-Erdos path extension), Lemma 1 (Burr-Erdos-Faudree-Rousseau-Schelp), Lemma 4 (Hall-type bipartite matching), Lemma 5 (Faudree-Schelp-Sheehan), Lemma 7 (Chvatal-Harary), Lemma 11 (Hu-Peng), Lemma 12 (Burr-Erdos-Spencer)
    Standard or published external results used as tools in the case analyses.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fan-goodness of sparse graphs." pith.science (2026). https://pith.science/paper/42C6UZQA

@misc{pith2026250709832,
  author       = {Pith},
  title        = {Pith review of: Fan-goodness of sparse graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/42C6UZQA}},
  note         = {Machine review of arXiv:2507.09832}
}
abstract

Let $G$ be a connected graph of order $n$, $F_k$ be a fan consisting of $k$ triangles sharing a common vertex, and $tF_k$ be $t$ vertex-disjoint copies of $F_k$. Brennan (2017) showed the Ramsey number $r(G,F_k)=2n-1$ for $G$ being a unicyclic graph for $n \geq k^2-k+1$ and $k\ge 18$, and asked the threshold $c(n)$ for which $r(G,F_k) \geq 2n$ holds for any $G$ containing at least $c(n)$ cycles and $n$ being large. In this paper, we consider fan-goodness of general sparse graphs and show that if $G$ has at most $n(1+\epsilon(k))$ edges, where $\epsilon(k)$ is a constant depending on $k$, then $$r(G,F_k)=2n-1$$ for $n\ge 36k^4$, which implies that $c(n)$ is greater than $\epsilon(k) n$. Moreover, if $G$ has at most $n(1+\epsilon(k,t))$ edges, where $\epsilon(k,t)$ is a constant depending on $k,t$, then $$r(G,tF_k)=2n+t-2$$ provided $n\ge 161t^2k^4$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Ajtai, J

    M. Ajtai, J. Koml´ os, and E. Szemer´ edi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29 (1980), 354–360

    work page 1980

  2. [2]

    Ajtai, J

    M. Ajtai, J. Koml´ os, and E. Szemer´ edi, A dense infinite Sidon sequence, European J. Combin. 2 (1981), 1–11

    work page 1981

  3. [3]

    Bondy and P

    J.A. Bondy and P. Erd˝ os, Ramsey numbers for cycles in graphs, J. Combin. Theory Ser. B 14 (1973), 46–54. 23

    work page 1973

  4. [4]

    Brennan, Ramsey numbers of trees and unicyclic graphs versus fans, Discrete Math

    M. Brennan, Ramsey numbers of trees and unicyclic graphs versus fans, Discrete Math. 340 (2017), 969–983

    work page 2017

  5. [5]

    Burr, Ramsey numbers involving graphs with long suspended paths, J

    S.A. Burr, Ramsey numbers involving graphs with long suspended paths, J. London Math. Soc. (2) 3 (1981), 405–413

    work page 1981

  6. [6]

    S.A. Burr, P. Erd˝ os, R.J. Faudree, C.C. Rousseau, and R.H. Schelp, Ramsey numbers for the pair sparse graph-path or cycle, Trans. Amer. Math. Soc. 269 (1982), 501–512

    work page 1982

  7. [7]

    S.A. Burr, P. Erd˝ os, and J. H. Spencer, Ramsey theorems for multiple copies of graphs, Trans. Amer. Math. Soc. 209 (1975), 87–99

    work page 1975

  8. [8]

    Fan-complete Ramsey numbers

    F. Chung and Q. Lin, Fan-complete Ramsey numbers, arXiv:2208.05829v2 (2025)

    work page Pith review arXiv 2025

Show all 27 references
  1. [9]

    Chv´ atal, Tree-complete graph Ramsey numbers, J

    V. Chv´ atal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977), 93–93

    1977

  2. [10]

    Chv´ atal and F

    V. Chv´ atal and F. Harary, Generalized Ramsey theory for graphs. III. Small off diagonal numbers, Pacific J. Math. 41 (1972), 335–345

    1972

  3. [11]

    Erd˝ os, R.J

    P. Erd˝ os, R.J. Faudree, C.C. Rousseau, and R.H. Schelp, The book-tree Ramsey numbers, Scientia, Ser. A Math. 1 (1988), 111–117

    1988

  4. [12]

    Erd˝ os, R.J

    P. Erd˝ os, R.J. Faudree, C.C. Rousseau, and R.H. Schelp, Graphs with certain families of spanning trees, J. Combin. Theory Ser. B 32 (1982), 162–170

    1982

  5. [13]

    Faudree, R.H

    R.J. Faudree, R.H. Schelp, and J. Sheehan, Ramsey numbers for matchings, Discrete Math. 32 (1980), 105–123

    1980

  6. [14]

    Hall, On representatives of subsets, J

    P. Hall, On representatives of subsets, J. London. Math. Soc. (1) (1935), 26–30

    1935

  7. [15]

    Hu and Y

    S. Hu and Y. Peng, Ramsey numbers of stripes versus trees and unicyclic graphs, J. Oper. Res. Soc. China (2023), 1–16

    2023

  8. [16]

    Huang, Y

    T. Huang, Y. Zhang, and Y. Chen, Minimum degree and sparse connected spanning subgraphs, arXiv:2507.03264 (2025)

    2025 arXiv

  9. [17]

    Kadota, T

    S. Kadota, T. Onozuka, and Y. Suzuki, The graph Ramsey number R(Fl, K6), Discrete Math. 342 (2019), 1028–1037

    2019

  10. [18]

    J. H. Kim, The Ramsey number R(3, t) has order of magnitude t2/ log t, Random Struct. Alg. 7 (1995), 173–207

    1995

  11. [19]

    Li and C.C

    Y. Li and C.C. Rousseau, Fan-complete graph Ramsey numbers. J. Graph Theory 23 (1996), 413–420

    1996

  12. [20]

    Rousseau and J

    C.C. Rousseau and J. Sheehan, A class of Ramsey problems involving trees, J. London. Math. Soc. (2) 18 (1978), 392–396

    1978

  13. [21]

    Shearer, A note on the independence number of triangle-free graphs, Discrete Math

    J. Shearer, A note on the independence number of triangle-free graphs, Discrete Math. 46 (1983), 83–87

    1983

  14. [22]

    Shi, Ramsey numbers of long cycles versus books or wheels, European J

    L. Shi, Ramsey numbers of long cycles versus books or wheels, European J. Combin. 31 (2010), 828–838

    2010

  15. [23]

    Baskoro, and H.J

    Surahmat, E.T. Baskoro, and H.J. Broersma, The Ramsey numbers of fans versus K4, Bull. Inst. Com bin. Appl. 43 (2005), 96–102

    2005

  16. [24]

    Wang and J

    M. Wang and J. Qian, Ramsey numbers for complete graphs versus generalized fans, Graphs Comb. 38(6) (2022), 186. 24

    2022

  17. [25]

    Zhang, H

    Y. Zhang, H. Broersma, and Y. Chen, Ramsey numbers of trees versus fans, Discrete Math. 338 (6) (2015), 994–999

    2015

  18. [26]

    Zhang and Y

    Y. Zhang and Y. Chen, Ramsey goodness of fans, arXiv:2310.13204 (2023)

    2023 arXiv

  19. [27]

    Zhang and Y

    Y. Zhang and Y. Chen, Trichotomy and tKm-goodness of sparse graphs, arXiv:2505.04142 (2025). 25

    2025

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.