Ramsey numbers of sparse graphs versus disjoint books

Ting Huang; Yanbo Zhang; Yaojun Chen

REVIEW 2 major objections 3 minor 21 references

Ramsey numbers of sparse graphs versus disjoint books

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 For all sufficiently large connected sparse graphs $G$, the Ramsey number against $t$ disjoint books $B_k$ is exactly $2n+t-2$.

desk verdict The exact Ramsey formula for sparse graphs versus disjoint books is new and the proof is coherent, but the main theorem's fate hangs on two unrefereed companion preprints used at their exact stated bounds. read the letter →

arxiv 2507.09827 v1 pith:J2MI4NZ3 submitted 2025-07-13 math.CO

Ting Huang , Yanbo Zhang , Yaojun Chen This is my paper · ORCID

classification math.CO MSC 05C5505C35

keywords Ramseynumbersparsegraphbookgoodnessdisjointbookssuspendedpathstructuraltrichotomy

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

This paper proves exact Ramsey numbers for all sufficiently large connected sparse graphs against disjoint books. A book $B_k$ is $k$ triangles sharing a common edge, and $tB_k$ is $t$ disjoint copies. The main theorem states that if $G$ is connected with $n\ge 111t^3k^3$ vertices and at most $n(1+1/(127t^2k^2+79t^2k))$ edges, then $r(G,tB_k)=2n+t-2$. Since the general lower bound from Theorem 1 gives exactly $2n+t-2$ for $H=tB_k$, the theorem says every such graph is $tB_k$-good. It thereby extends the 1988 tree-versus-book result to arbitrary sparse connected graphs and to any number of books, and its proof also settles the single-book case and the star case.

What carries the argument

The central object is the book $B_k=K_2+\overline{K_k}$ (equivalently, $k$ triangles sharing a common edge), and the load-bearing tool is the companion Trichotomy Lemma. It asserts that a connected sparse graph either has a suspended path of a specified length, or has a matching of a specified number of end-edges, or has a small set of vertices of degree at least $2$ together with a vertex adjacent to many leaves. Each branch is settled by a different mechanism: the path-extension lemma to lengthen a suspended path, a matching lemma (Lemma 4) combined with the star bound $r(G,K_{1,k})\le n+k-1$ to attach end-edges, and an embedded star $K_{1,n-1}$ whose center absorbs all remaining leaves greedily. A self-contained bound $r(G,B_k)\le n+2km-2m/n$ controls the size of the graph that survives after pruning and is combined with the star bound to obtain the intermediate lemma $r(G,B_k)\le 2n+k-2$.

What would settle it

Search, for the smallest admissible $k$ and $t$, for a connected graph $G$ with $n\ge 111t^3k^3$ vertices and at most $n(1+1/(127t^2k^2+79t^2k))$ edges such that some red-blue coloring of $K_{2n+t-2}$ contains neither a red $G$ nor a blue $tB_k$; any such pair $(G,\text{coloring})$ would disprove the exact formula, and for moderate $n$ such a search is feasible by SAT-based Ramsey verification.

Watch

Extended reading notes

Core claim

The central claim is Theorem 10: for positive integers $k,t$ and $n\ge 111t^3k^3$, every connected graph $G$ on $n$ vertices with $e(G)\le n(1+1/(127t^2k^2+79t^2k))$ satisfies $r(G,tB_k)=2n+t-2$, where $B_k=K_2+\overline{K_k}$ is the book graph on $k+2$ vertices. Because $\chi(tB_k)=3$ and its chromatic surplus is $t$, the lower bound of Theorem 1 gives $(n-1)(3-1)+t=2n+t-2$; the theorem is therefore the statement that all such sparse connected graphs are $tB_k$-good. The upper-bound proof splits into three structural cases — a long suspended path, a large matching of end-edges, or a small core with a vertex adjacent to many leaves — and in every red-blue coloring of $K_{2n+t-2}$ one of the cases forces either a red copy of $G$ or a blue $tB_k$. Along the way the paper proves the single-book theorem $r(G,B_k)=2n-1$ and the star theorem $r(K_{1,n-1},tB_k)=2n+t-2$.

Load-bearing premise

The upper-bound argument stands on two companion lemmas taken from the authors' preprints and not reproved here: the Trichotomy Lemma and the bound $r(G,K_{1,k})\le n+k-1$; if either companion result has an unstated condition or a hidden gap, the proof of Theorem 10 fails even if the theorem is true.

Editorial extensions

If this is right

If the main theorem is correct, then for $n\ge 34k^3$ every connected graph with at most $n(1+1/(119k^2+62k))$ edges satisfies $r(G,B_k)=2n-1$: all such graphs are $B_k$-good.
For stars, $r(K_{1,n-1},tB_k)=2n+t-2$ whenever $n\ge 3tk+3t-5$, so stars of any size order are $tB_k$-good.
For the full range $n\ge 111t^3k^3$, the exact Ramsey number of a sparse connected graph against $tB_k$ depends only on $n$ and $t$, not on the graph's internal structure or on the page size $k$ beyond the hypotheses.
Consequently equality holds in the general lower bound $r(G,H)\ge(n-1)(\chi(H)-1)+s$ for every connected sparse graph $G$ in the stated range, i.e. all these graphs are $tB_k$-good in the sense of Ramsey goodness.

Reading between the lines

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

Because the value $2n+t-2$ never involves $k$, the page size of the book only enters through the hypotheses; a natural test is whether the same exact value persists for much larger edge allowances or for other 3-chromatic graphs with chromatic surplus $t$.
The edge budget is only about $n$ plus $n/(127t^2k^2+79t^2k)$ edges, so the class covered has average degree just above 2; the result implies book-goodness is a low-average-degree phenomenon rather than a tree-only or cycle-only phenomenon.
The concluding remark exposes a trade-off between the lower bound on $n$ and the upper bound on $e(G)$; an immediate next step, even within the same proof framework, is to determine the actual trade-off curve and whether constants such as $111$, $127$, and $79$ can be substantially reduced.

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.

Desk Editor's Note

read the letter

This is a solid, workmanlike contribution, and the main formula is genuinely new: r(G,tB_k)=2n+t-2 for every large connected sparse G, extending the 1988 tree-book theorem to multiple books and to graphs that are far from trees. Theorem 9, the star case, is also new and is proved with a clean induction using the Andrásfai–Erdős–Sós bound. The paper is clearly organized, and Lemma 5's self-contained bound on r(G,B_k) is a useful tool in its own right.

The soft spot is not in the internal logic—I saw no contradiction and the arithmetic checks are consistent—but in the load-bearing dependence on two companion preprints from the same group: Lemma 2 (trichotomy) and Lemma 6 (star Ramsey bound), plus Lemma 11 for tK2 in Theorem 10. The bounds are used exactly, with no slack. In particular, Lemma 6's r(G,K_{1,k}) ≤ n+k−1 is invoked in Lemma 7 and again in Cases 2 and 3 of Theorem 10; if the true constant were n+k, the final greedy arguments would lose their margin and the contradiction would not follow. That is a real verification gap, and the paper cannot be fully trusted until those preprints are checked. The hand-tuned thresholds make the result true but ugly; the concluding remark is honest that they are not tight.

One small internal gap: Lemma 7 asserts G0 has at least 3 vertices (ℓ≥3), which fails for trees, but the tree case is already covered by the classic theorem, so this is patchable and not a threat to the main claim.

Who should read this: anyone working on Ramsey goodness or book Ramsey numbers. It deserves a serious referee, but the referee must be asked to verify Lemma 2, Lemma 6, and Lemma 11, or to have the authors fold those proofs in. I would not desk-reject it.

Referee Report

2 major / 3 minor

Summary. The paper studies Ramsey numbers of connected sparse graphs versus disjoint books. Let B_k denote the book K_2+K_k and tB_k its disjoint union. The main result, Theorem 10, asserts that for positive integers k,t and n >= 111 t^3 k^3, every connected graph G on n vertices with at most n(1 + 1/(127 t^2 k^2 + 79 t^2 k)) edges satisfies r(G, tB_k) = 2n + t - 2. Theorem 8 establishes the single-book case t=1 with n >= 34 k^3 and the edge bound n(1 + 1/(119 k^2 + 62 k)), and Theorem 9 proves the star case r(K_{1,n-1}, tB_k) = 2n + t - 2 for n >= 3tk + 3t - 5. The lower bound is Burr's goodness bound; the upper bound is proved by induction on t, using a trichotomy lemma for sparse graphs to split into cases of a long suspended path, many end-edges, or a core of bounded size, and then either extending a red copy of a subgraph of G or forcing a blue book. The proofs are built on three key lemmas that are quoted from the authors' own companion preprints: Lemma 2 (Trichotomy), Lemma 6 (star Ramsey bound), and Lemma 11 (tK_2-goodness).

Significance. If the companion lemmas are correct, this is a substantial extension of the classical Erdős-Faudree-Rousseau-Schelp theorem that large trees are B_k-good, and it extends the Luo-Peng result on trees versus tK_k to sparse graphs versus disjoint books. The paper gives explicit polynomial lower bounds on n and explicit constants in the edge condition, and it is honest about the trade-off between n and e(G). The proofs are detailed and use appropriate standard tools: the Bondy-Erdős path lemma, Hall's theorem, the Andrásfai-Erdős-Sós theorem, and Burr's lower bound. I did not find an internal contradiction in the present text. The main weakness is verification: the exact numerical bounds in Lemma 2, Lemma 6, and Lemma 11 come from unreviewed preprints by the same authors, and the main theorem uses those bounds with no slack.

major comments (2)

[Sections 2, 3, and 5 (Lemmas 2, 6, and 11)] The main theorems depend on three lemmas quoted from the authors' own unreviewed preprints [16] and [21], and the dependence is exact rather than asymptotic. Lemma 6 is invoked in Lemma 7 and again in Cases 2 and 3 of Theorem 10 with the precise bound r(G, K_{1,k}) <= n + k - 1; in the final greedy step of Theorem 10, the blue-degree lower bound is n + k - 1 + |(t-1)B_k|, so if the true bound were n + k the contradiction would disappear. Lemma 2 supplies the structural trichotomy and the parameter gamma = (q-2)(2s + 3l - 2) + 1 that controls every later inequality in Case 3 of Theorems 8 and 10. Lemma 11 is used in Cases 1 and 2 of Theorem 10 to force a blue tK_2. To make the paper self-contained and the main theorem verifiable, the proofs of these three lemmas should be included in this manuscript (for example, in an appendix) or the lemmas should be replaced by published versions with identical hypotheses.
[Section 3, Lemma 7] The proof asserts 'since K_N contains no red G_0 and G_0 is connected, we must have l >= 3'. This is false when G is a tree: after deleting all degree-1 vertices recursively and shortening suspended paths, G_0 is a single vertex (l = 1). The subsequent estimates 2(l-1)/l >= 1 and the application of Lemma 5 to r(G_0, B_k) do not apply as written. The tree case is presumably covered by the classical theorem of Erdős, Faudree, Rousseau, and Schelp (Theorem 7 in the paper), but the proof of Lemma 7 should either handle this case explicitly or restrict the argument to the situation in which G_0 has at least two vertices.

minor comments (3)

[Section 3, Lemma 7] The graph G' is used before it is defined: the sentence 'let G_1 be a graph obtained from G' by deleting the vertices of degree 1' introduces G' only later. Please reorder the definitions for clarity.
[Section 6, Concluding Remark] Substituting c = 49 into g(k,c) = (2c+21)k^2 + (c+25/2)k gives 119k^2 + 61.5k, whereas Theorem 8 uses 119k^2 + 62k. The constants in the concluding remark should be reconciled with the statements of Theorems 8 and 10.
[Section 5, Theorem 10] In Cases 1 and 2, the use of Lemmas 10 and 11 to force a blue tK_2 requires checking the hypothesis e(G) <= n + n^2/(4t-5) - 2. This follows from n >= 111t^3k^3 and the given edge bound, but the verification is not shown and should be included.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main theorems are not restatements of the inputs; the cited companion lemmas are independent parameter-free statements, so the derivation chain is not circular.

full rationale

The paper's central claims, Theorem 8 and Theorem 10, are proved by constructing red copies of the sparse graph G or blue copies of tB_k. The lower bounds come from Burr's Theorem 1, and the upper-bound arguments are not definitions of the conclusion. The main external inputs are Lemma 2 and Lemma 11 from Zhang--Chen [21] and Lemma 6 from Huang--Zhang--Chen [16]. These are self-citations by overlapping authors, but they are not circular reductions: Lemma 6 asserts a bound on r(G,K_{1,k}), a different Ramsey number from r(G,tB_k), and Lemma 2 is a structural trichotomy for sparse graphs analogous to the 1982 Burr--Erdos--Faudree--Rousseau--Schelp lemma. Neither lemma assumes the target formula r(G,tB_k)=2n+t-2, and no equation in the paper defines the sparse-graph parameters in terms of that formula. Lemma 7 is proved in the paper using Bondy--Erdos Lemma 3 and the self-contained Lemma 5; Theorem 9 is proved independently by induction; Theorem 10 then uses Theorem 8, Theorem 9, Lemma 6, Lemma 11, and Hall/Bondy--Erdos tools. The proofs are constructive and do not rename a fitted parameter or an empirical pattern as a prediction. The reliance on unpublished companion preprints is a verification and correctness risk, not a circularity, because the cited results are independent statements with their own stated assumptions. Accordingly, the circularity score is 0.

Assumptions & free parameters 2 free parameters · 8 assumptions · 0 invented entities

The central claim depends on hand-chosen constants and on two structural lemmas from the authors' own unpublished preprints. No new mathematical entities are introduced.

free parameters (2)

Hand-chosen thresholds in Theorem 8 = n >= 34k^3; edge bound 1/(119k^2+62k)
These constants are selected to satisfy the inequalities in the proof, not fitted to data. Section 6 shows a general trade-off f(k,c) and states c=49 was chosen for presentation.
Hand-chosen thresholds in Theorems 9-10 = n >= 3tk+3t-5 for Theorem 9; n >= 111t^3k^3 and edge bound 1/(127t^2k^2+79t^2k) for Theorem 10
Again hand-picked to make induction and Case 3 estimates work; the exact statements depend on these values.

assumptions (8)

standard math Chvatal's theorem: every tree T_n is K_k-good, r(T_n,K_k) = (n-1)(k-1)+1.
Used in Lemma 5 to get r(K_n,K_{1,k}) <= nk.
standard math Burr-Erdos-Faudree-Rousseau-Schelp Trichotomy Lemma (Lemma 1).
Used in Lemma 7 to bound the size of the reduced graph G0.
standard math Rousseau-Sheehan theorem: r(K_{1,n-1},B_k) = 2n-1 for n >= 3k-3.
Used in Case 3 of Theorem 8 to guarantee a red star.
standard math Andrasfai-Erdos-Sos theorem (Lemma 8).
Used in Theorem 9 to show the blue graph in S is bipartite.
standard math Chvatal-Harary theorem: r(G,2K2) = n+1 for any non-complete graph without isolated vertices.
Used in Theorem 10 to find a blue tK2.
domain assumption Zhang-Chen Trichotomy Lemma (Lemma 2) holds as stated.
This is from arXiv:2505.04142 by two of the present authors. It is the structural backbone of Case 3 in Theorems 8 and 10.
domain assumption Huang-Zhang-Chen bound (Lemma 6): r(G,K_{1,k}) <= n+k-1 for sparse connected G.
From arXiv:2507.03264 by all three present authors. Used in Lemma 7, Cases 2-3 of Theorem 8, and the greedy embedding in Theorem 10.
domain assumption Zhang-Chen theorem (Lemma 11): r(G,tK2) = n+t-1 for connected sparse G.
From arXiv:2505.04142, used in Theorem 10 to locate a blue tK2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Ramsey numbers of sparse graphs versus disjoint books." pith.science (2026). https://pith.science/paper/J2MI4NZ3

@misc{pith2026250709827,
  author       = {Pith},
  title        = {Pith review of: Ramsey numbers of sparse graphs versus disjoint books},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J2MI4NZ3}},
  note         = {Machine review of arXiv:2507.09827}
}

abstract

Let $B_k$ denote a book on $k+2$ vertices and $tB_k$ be $t$ vertex-disjoint $B_k$'s. Let $G$ be a connected graph with $n$ vertices and at most $n(1+\epsilon)$ edges, where $\epsilon$ is a constant depending on $k$ and $t$. In this paper, we show that the Ramsey number $$r(G,tB_k)=2n+t-2$$ provided $n\ge 111t^3k^3$. Our result extends the work of Erd\H{o}s, Faudree, Rousseau, and Schelp (1988), who established the corresponding result for $G$ being a tree and $t=1$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 8 canonical work pages

[16]

Huang, Y

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

arXiv 2025
[21]

Zhang and Y

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

arXiv 2025
[1]

Andr´ asfai, P

B. Andr´ asfai, P. Erd˝ os, and V.T. S´ os, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Math. 8 (1974), 205–218

work page 1974
[2]

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

work page 1973
[3]

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

1981
[4]

S.A. Burr, P. Erd˝ os, R.J. Faudree, C.C. Rousseau, and R.H. Schelp, An extremal problem in generalized Ramsey theory, Ars Combin. 10 (1980), 193–203

work page 1980
[5]

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

1982
[6]

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

1975

Show all 21 references

[7]

Campos, S

M. Campos, S. Griffiths, R. Morris, and J. Sahasrabudhe, An exponential improvement for diagonal Ramsey, arXiv:2303.09521 (2023)

2023 arXiv
[8]

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

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

1977
[9]

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
[10]

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
[11]

Faudree, C

R. Faudree, C. Rousseau, and J. Sheehan, Cycle-book Ramsey numbers, Ars Combin., 31 (1991), 239-248

1991
[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
[13]

X. Guo, S. Hu, and Y. Peng, Ramsey numbers of trees versus multiple copies of books, Acta Math. Appl. Sin. (Engl. Ser.) 40(3) (2024), 600–612

2024
[14]

Hall, On representatives of subsets, J

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

1935
[15]

F. Hu, Q. Lin , T. Luczak, B. Ning, and X. Peng, Ramsey numbers of books versus long cycles, SIAM J. Discrete Math. 39(1) (2025)

2025
[17]

Lin and X

Q. Lin and X. Peng, Large book-cycle Ramsey numbers, SIAM J. Discrete Math. 35 (2021), 532–545

2021
[18]

Luo and Y

Z. Luo and Y. Peng, A large tree is tKm-good, Discrete Math. 346 (2023), 113502

2023
[19]

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
[20]

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

Pith tools

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

[1] [16]

Huang, Y

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

arXiv 2025

[2] [21]

Zhang and Y

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

arXiv 2025

[3] [1]

Andr´ asfai, P

B. Andr´ asfai, P. Erd˝ os, and V.T. S´ os, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Math. 8 (1974), 205–218

work page 1974

[4] [2]

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

work page 1973

[5] [3]

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

1981

[6] [4]

S.A. Burr, P. Erd˝ os, R.J. Faudree, C.C. Rousseau, and R.H. Schelp, An extremal problem in generalized Ramsey theory, Ars Combin. 10 (1980), 193–203

work page 1980

[7] [5]

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

1982

[8] [6]

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

1975