REVIEW 6 minor 8 references
On the Ramsey number of a graph obtained by attaching a pendant to a path with length 1 modulo 4
T0 review · 0 major / 6 minor · reviewed 2026-08-01 · deepseek-v4-flash
Pith's one-line read For n ≡ 1 mod 4, the Ramsey number of a midpoint-pendant path equals (3n+1)/2 exactly.
desk verdict A genuine exact Ramsey result for an infinite caterpillar family, proven with standard tools and no load-bearing error that I could find; worth refereeing despite a few cosmetic typos. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument rests on two auxiliary lemmas about a longest path P in one colour class. Lemma 1 shows that for indices j in a certain range, the edges v_j v_{j-(n+1)/2} must lie in the opposite colour whenever the same-coloured copy would create a T_n. Lemma 2 is an alternating-path lemma: given a subpath L of P and a set C of off-path vertices with sufficiently many neighbours of the endpoint l_1 in the opposite colour, it builds an alternating path in that colour alternating between vertices of L and vertices of C, of length 2*floor((k+1)/2). These lemmas feed into three case constructions (z=0, 0<z≤(n-1)/4, z>(n-1)/4) that assemble a spine of length n with the pendant attached to its midpo
What would settle it
Exhibit a 2-colouring of K_{(3n+1)/2} with no monochromatic copy of T_n for any single n≡1 mod 4; for n=5 this means a search over all colourings of K_9, and any such colouring would refute the theorem.
Extended reading notes
Core claim
Theorem 1 states that R(T_n, T_n)=(3n+1)/2 for all odd n≡1 mod 4. The upper bound takes any two-colouring of K_{(3n+1)/2}, invokes the path-Ramsey theorem to find a monochromatic path of length at least n+1, and then, via two alternating-path lemmas, constructs a T_n in one of the two colour classes depending on the excess length of that path. The lower bound is an explicit colouring of K_{(3n-1)/2} whose colour classes are a disjoint union of cliques and a complete bipartite graph K_{n,(n-1)/2}, shown by parity to be T_n-free.
Load-bearing premise
The upper bound assumes the cited formula R(P_m,P_m)=floor((3m-2)/2) holds for m=n+1; if that were wrong for these m, the proof would not be able to guarantee a long monochromatic path and the case analysis would collapse.
Editorial extensions
If this is right
- For every n ≡ 1 mod 4, R(T_n, T_n) is exactly (3n+1)/2, so this infinite caterpillar family joins the short list of trees with known exact Ramsey numbers.
- The lower-bound colouring shows that the extremal example is a split graph: one colour is a clique plus an independent set, the other is the complete bipartite graph between them.
- Since the paper proves a matching upper bound for all n>5 and checks n=1,5 separately, the theorem covers all n in [1]_4 with no leftover cases.
- The proof's alternating-path construction yields the spined path in the second colour for every possible excess z, meaning the upper bound does not rely on any structural assumption about the colouring beyond the existence of a long monochromatic path.
Reading between the lines
- The same two-lemma approach may extend to pendants attached at positions other than the midpoint; the parity-sensitive alternating construction suggests the exact formula will depend on the attachment position modulo 4.
- For n ≡ 3 mod 4, the lower-bound colouring described here does not directly apply because the midpoint falls on an even-indexed vertex; a different extremal colouring may be needed, and the exact constant may differ.
- A computational search for n=9 (a 14-vertex clique) could validate the theorem's smallest open case and test whether the alternating-path construction is tight.
- The dependence on the path-Ramsey formula means improvements in path-Ramsey numbers for many colours would let the method generalise to multicolour Ramsey numbers of these trees.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies T_n, the caterpillar obtained from an n-vertex path by attaching one pendant leaf to the middle vertex, for n ≡ 1 mod 4. The main theorem states that R(T_n,T_n) = (3n+1)/2. The upper-bound proof colors K_{(3n+1)/2} with two colors, takes a longest monochromatic path guaranteed by the classical Gerencsér–Gyárfás formula for R(P_{n+1},P_{n+1}), and, assuming no monochromatic T_n, constructs a T_n in the opposite color through a case analysis on the number z of vertices of the longest path beyond n+1. The lower bound is a simple biclique construction. The cases n=1 and n=5 are checked separately.
Significance. If correct, this is an exact Ramsey number for a natural infinite family of non-broom caterpillars, a class for which exact results are scarce; it refines the recent asymptotic theorem of Montgomery–Pavez-Signé–Yan for this congruence class. The proof is largely self-contained: it relies only on the classical path-Ramsey theorem and on elementary longest-path arguments. The lower-bound construction is elegant, the two auxiliary lemmas (Lemmas 1 and 2) are reusable, and the finite case n=5 is verified explicitly. I found no circular dependence on the target theorem and no unjustified parametric assumptions.
minor comments (6)
- [§2.2, Lemma 4 (Claim 2 and following small cases)] The definition of B_3 has an off-by-one error. With L = (n−1)/2 − 2z, the tuple P_{(v_t,...,v_{t−((n−1)/2−2z+1)})} has L+2 vertices, but the subsequent equality |Q_3| = floor((|V(B_3)|+1)/2) requires |V(B_3)| = L, i.e. the endpoint should be v_{t−(L−1)}. The later instantiation for |Q_3|=2 uses exactly the four vertices v_t,...,v_{t−3}, so the intended definition is clear; nevertheless the displayed formula should be corrected.
- [§2.2, Lemma 4, first paragraph] The line '|Q_1| = ⌊(|V(P)|+1)/2⌋' should refer to V(B_1), not V(P). The equality claimed is |Q_1| = ⌊(|V(B_1)|+1)/2⌋ = (n−1)/4; with V(P) the displayed identity is false.
- [§2.2, Lemma 4, |Q_3|=2 and |Q_3|=1 cases] In the two final paragraphs of Lemma 4, the path P_{M1+(v_{(n−1)/2})+M2+M3,G2} and the phrase 'with midpoint v_{(n−1)/2}' should read v_{(n+1)/2}. The constructed T_n has n vertices, so the midpoint is v_{(n+1)/2}; the earlier part of the lemma uses this correct index.
- [§3, n=5, case k=6] The claim that v3v6 ∈ E(G2) is correct but is presented very tersely. A one-sentence justification would help: if v3v6 were in G1, the path v1−v2−v3−v6−v5 together with pendant v4 would be a T5 in G1, contradicting the assumption. Similar one-line justifications exist for the other displayed G2 edges in this finite check.
- [Notation, throughout] The paper uses 'length' to mean the number of vertices of a path ('2z-path', 'path of length n'), while standard graph theory often uses length for the number of edges. A brief note fixing this convention would prevent confusion, especially in Lemma 1 and the case analysis.
- [§1, definition of T_n for n=1] For n=1 the notation {x1x2,...,x_{n−1}x_n} is vacuous; the graph T_1 is a single edge via the pendant edge x_{(n+1)/2} x_{n+1} = x1x2. This is clear in context but worth a parenthetical remark.
Circularity Check
No significant circularity: proof relies only on the classical external path-Ramsey theorem and internally constructs the required upper and lower bounds.
full rationale
The paper's derivation is self-contained modulo an external classical result. The upper bound invokes the Gerencsér–Gyárfás path-Ramsey formula R(P_m,P_m)=floor((3m-2)/2), cited as [3], and applies it with m=n+1 to force a path on n+1 vertices; this theorem concerns paths, not T_n, and is not an input equivalent to the target Ramsey number. The subsequent longest-path and Lemma 2 inductive arguments construct a monochromatic T_n in the other colour class, and no fitted parameter is renamed as a prediction. The lower bound exhibits an explicit two-colouring by a biclique K_{n,(n-1)/2} plus disconnected colour-class components, directly verifying that neither colour class contains T_n. There are no self-citations, and no step reduces to the theorem being proved. The cited result [3] is an external benchmark, and [6] is only mentioned as context for extending existing large-n work, not as a load-bearing assumption. The noted Lemma 4 subpath indexing issue is a typographical slip, not a circular or definitional reduction.
Assumptions & free parameters
assumptions (4)
- standard math Ramsey's theorem guarantees R(H_1,...,H_k) is finite and well-defined.
- domain assumption R(P_m,P_m)=⌊(3m−2)/2⌋ for the needed m (m=n+1 with n≥5, and m=6 for n=5).
- standard math Longest-path maximality: if P is a longest path in G_1, then off-path vertices are not adjacent in G_1 to endpoints of P, and no off-path vertex is adjacent in G_1 to two consecutive vertices of P.
- standard math In a biclique K_{n,(n−1)/2}, a path on n vertices alternates partite sets and cannot contain a pendant attached to the midpoint.
Cite this review
Pith. "Pith review of On the Ramsey number of a graph obtained by attaching a pendant to a path with length 1 modulo 4." pith.science (2026). https://pith.science/paper/YB42KUT7
@misc{pith2026260719554,
author = {Pith},
title = {Pith review of: On the Ramsey number of a graph obtained by attaching a pendant to a path with length 1 modulo 4},
year = {2026},
howpublished = {\url{https://pith.science/paper/YB42KUT7}},
note = {Machine review of arXiv:2607.19554}
}
abstract
In this paper, for odd $n$, we consider the graph $T_n$ with vertex set $\{x_1,....,x_n,x_{n+1}\}$ and edge set $\{x_{1}x_{2},x_{2}x_{3},...,x_{n-1}x_{n}\} \cup \{x_{\frac{n+1}{2}}x_{n+1}\}$ and prove that the Ramsey number $R(T_n,T_n)$ is equal to $\frac{3n+1}{2}$ for $n \in [1]_{4}$.
Reference graph
Works this paper leans on
-
[6]
R. Montgomery, M. Pavez-Sign´ e and J. Yan. Ramsey numbers of trees. arXiv preprint arXiv:2509.07934, 2025
arXiv 2025
-
[1]
Chen and S
G. Chen and S. Liu. On the Ramsey numbers of even-linked double stars.Australasian Journal of Combinatorics, 94:385–402, 2026
2026
-
[2]
Erd˝ os, R
P. Erd˝ os, R. Faudree, C. Rousseau and R. Schelp. Ramsey num- bers for brooms.Congressus Numerantium, 35:283–293, 1982
1982
-
[3]
Gerencs´ er and A
L. Gerencs´ er and A. Gy´ arf´ as. On Ramsey-type problems.Ann. Univ. Sci. Budapest. E¨ otv¨ os Sect. Math, 10:167–170, 1967
1967
-
[4]
Li and P
Y. Li and P. Yu. All Ramsey Numbers for Brooms in Graphs. Electronic Journal of Combinatorics, 2016
2016
-
[5]
V. Lozin. Graph Theory Notes. Lecture notes, Institute of Math- ematics, University of Warwick, UK, 2018
2018
-
[7]
Z.H. Sun. Ramsey numbers for trees II.Czechoslovak Mathematical Journal, 71:351–372, 2021
2021
-
[8]
West.Introduction to Graph Theory
D.B. West.Introduction to Graph Theory. Prentice Hall, 1996. 18
1996
Reviewed August 1, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.