REVIEW 5 major objections 5 minor 7 references
Ramsey and Gallai-Ramsey numbers for stars with extra independent edges
T0 review · 5 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read For $t\ge 6r-5$, every red-blue coloring of $K_{2t+2r-1}$ contains a monochromatic copy of $S_t^r$, a star of order $t$ with $r$ extra independent leaf edges, and this threshold is sharp.
desk verdict The general theorem contradicts the paper's own r=2,3 results and is not proved; the small-case Gallai-Ramsey computations are new but need a careful check. 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 engine is the Gallai partition theorem: in any edge-coloring of a complete graph with no rainbow triangle, the vertices split into parts with at most two colors between parts, so the reduced graph is a 2-colored complete graph. The classical Ramsey proofs work vertex-by-vertex, splitting the neighborhood of a vertex into red and blue sets and forcing a monochromatic $S_t^r$ out of matchings, triangles, and fans inside those sets. The Gallai-Ramsey upper bounds iterate a base-5 blow-up construction: copies of a smaller color-free graph are arranged as the five parts of the unique 2-coloring of $K_5$ with no monochromatic triangle, which is what produces the $5^{k/2}$ factors in the bounds.
What would settle it
Search for a red-blue coloring of $K_{2t+2r-1}$ with no monochromatic $S_t^r$ at the first value $t=6r-5$; finding one refutes the theorem. In the absence of an exhaustive search, check whether the red graph $K_{t,t+2r-1}$ (minimum red degree $t$, no spanning cycle) can be completed to such a coloring, since the printed upper-bound proof relies on that spanning cycle.
Extended reading notes
Core claim
The central discovery is that for $t\ge 6r-5$ the 2-color Ramsey number of $S_t^r$ is exactly $2t+2r-1$: every red-blue coloring of $K_{2t+2r-1}$ contains a monochromatic $S_t^r$, while some coloring of $K_{2t+2r-2}$ avoids it. For $r=2$ and $r=3$ the paper obtains the smaller value $2t-1$ when $t\ge7$ and $t\ge15$, respectively. On the Gallai-Ramsey side, the paper proves lower bounds of order $2(t-1)5^{k/2}$ for even $k$ and $(t-1)5^{(k-1)/2}$ for odd $k$, with upper bounds differing only by constants linear in $r$, and in the cases $S^2_6$ and $S^2_8$ it derives exact formulas for every $k$.
Load-bearing premise
The general-$r$ proof depends on a spanning-cycle step that needs more red neighbors than the proof assumes, and on a lower-bound example that is smaller than the stated threshold.
Editorial extensions
If this is right
- For fixed $r$ and all $t\ge 6r-5$, the 2-color threshold is exactly $2t+2r-1$, so adding $r$ independent leaf edges raises the star Ramsey number by an additive term linear in $r$.
- For $r=2$ and $r=3$, the threshold is $2t-1$, meaning these extra edges do not raise the star Ramsey number in those regimes.
- The Gallai-Ramsey lower and upper bounds are within additive terms linear in $t$ and $r$, so the exponential-in-$k$ growth rate is $5^{k/2}$.
- The exact formulas for $S^2_6$ and $S^2_8$ give the first complete Gallai-Ramsey answers for non-star, non-fan members of this family.
Reading between the lines
- The printed lower-bound argument for the general case reuses the $2t-2$-vertex two-clique example, which is too small to support the stated $2t+2r-1$ threshold; supplying a genuine $2t+2r-2$-vertex construction is the most direct way to make the theorem self-contained.
- The spanning-cycle step used in the general upper-bound proof needs more red neighbors than the proof assumes; if that degree condition is tightened to about $t+r-1/2$, the same counting argument likely goes through and the theorem would survive in essentially the same form.
- Because every lower-bound construction uses the unique 2-colored $K_5$ with no monochromatic triangle, any graph in this family shares the $5^{k/2}$ growth; a natural testable extension is to seek exact Gallai-Ramsey formulas for $S_t^r$ with $r\ge3$ and small $t$.
- A computational Ramsey search targeted at the first case $t=6r-5$ could independently check the claimed equality before the proof gap is repaired.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies Ramsey and Gallai–Ramsey numbers for graphs S_t^r, obtained from a star K_{1,t-1} by adding r independent edges among leaves. It claims exact 2-color Ramsey numbers for r=2,3 and a general formula R(S_t^r,S_t^r)=2t+2r-1 for t≥6r-5, exact Gallai–Ramsey numbers for S_6^2 and S_8^2, and general upper and lower bounds for S_t^2 and S_t^r. The proofs use Gallai partitions, matching deletions, Dirac-type Hamiltonian arguments, and induction on the number of colors.
Significance. The family S_t^r interpolates between stars and fans, and exact values for small cases would be a useful addition to the Gallai–Ramsey literature. The paper's main structural idea—using the Gallai partition and bounding the number of large parts—is standard and potentially effective. However, the general base case in Theorem 2(3) is inconsistent with the paper's own r=2 theorem, and the lower bound for the stated value is absent. Because Theorem 4 inherits this base case, the paper's main general claims are not supported in its current form. No machine-checked proofs or reproducible code are provided; the contribution is entirely theoretical.
major comments (5)
- [Theorem 2(3); §2.1; §2.3] Theorem 2(3) states R(S_t^r,S_t^r)=2t+2r-1 for t≥6r-5, but this contradicts Theorem 2(1), which states R(S_t^2,S_t^2)=2t-1 for t≥7; since 6·2-5=7, both formulas apply at r=2 and differ. The proof in §2.3 also begins by saying the goal is to prove R(S_t^r,S_t^r)=2t-1 and works in K_{2t-1}, while the stated theorem concerns K_{2t+2r-1}. The lower-bound construction in §2.1, two copies of K_{t-1} joined in blue, has order 2t-2 and supports only R≥2t-1; no construction of order 2t+2r-2 is given. Thus the statement and proof of Theorem 2(3) are not about the same quantity, and the claimed value is unsupported.
- [§2.3, Case 1 and Case 2] The proof of the general-r upper bound contains two unproved pivotal steps. In Case 1, after obtaining a red fan F_{2r} centered at x, the text states "Since the degree of x is 2t-2, it follows that the red or blue degree of x is t-1+(2r+1)=t+2r"; no derivation is given for this either/or degree conclusion. In Case 2, the inference from d_R(v)>n/2+r to "every vertex v is contained in a red fan F_{2r}" is asserted to follow by a combinatorial counting argument that is never supplied. Both steps are essential for producing the forbidden monochromatic S_t^r.
- [Lemma 3; Theorem 3(1),(3)] The base case k=2 for the exact Gallai–Ramsey value of S_6^2 is stated in Lemma 3 as "precisely R(S_6^2,S_6^2)=15," but Theorem 2(1) only proves R(S_t^2,S_t^2)=2t-1 for t≥7. The value R(S_6^2,S_6^2)=15 is used without proof or reference, so the claimed exact value for gr_k(K_3;S_6^2) rests on an unestablished base case. The same gap affects Theorem 3(3) for t=6.
- [Theorem 4; Lemma 8] Theorem 4 is stated for t≥6r-5, and its proof in Lemma 8 uses "From Item (3) of Theorem 2, R(S_t^r,S_t^r)=2t+2r-1" as the k=2 base case. Since Theorem 2(3) is not established and is inconsistent with Theorem 2(1), the induction base for the general Gallai–Ramsey bounds in Theorem 4 fails. Consequently the upper bounds in Theorem 4 are unsupported even if the later partition arguments were correct.
- [§2.2, Case 3] The proof of Theorem 2(2) invokes R(F_3,F_3)=13 from the authors' own submitted paper [6]. With no published source or proof included, the r=3 result depends on an unavailable external result. If this is the only proof of that step, it needs a published reference or an independent argument within the paper.
minor comments (5)
- [Throughout Appendix A] The notation is inconsistent: S_t^+ and S^t appear in places that should read S_t^2 (e.g., A.1, Subcase 1.1), and R(S_8^2)=15 should be R(S_8^2,S_8^2)=15.
- [Lemma 3, k=3 case] In the q=0 paragraph, the text reads "R(S_6^2,S_6^2)=11"; this should presumably be 15, and as written it is inconsistent with the base case used elsewhere in the same lemma.
- [§2.2, Claim 2] The displayed triangles "uvu1v, u1u2w1u1 and u1u4w2u1" are garbled; the intended triangles should be written with standard vertex notation so the contradiction is readable.
- [Lemma 8] The parameter s appears in expressions such as n(k-2,s,t) in several places and should be r.
- [Introduction and Appendix] The introduction states that proofs of Item (3) of Theorem 3 and Theorem 4 are omitted, but they are included in Appendix A; the text should be updated to reflect the actual structure.
Circularity Check
No construction-level circularity: the paper's Ramsey and Gallai-Ramsey bounds are derived by explicit case analysis rather than by fitting or definitional equivalence.
full rationale
The derivation chain does not contain a fitted parameter renamed as a prediction, nor an object defined in terms of the quantity it is supposed to determine. The 2-color Ramsey results in Theorem 2 are proved from explicit lower-bound colorings and contradiction arguments on complete graphs; the lower-bound constructions are exhibited, and the upper-bound cases do not presuppose the equality they establish. The Gallai-Ramsey results in Theorems 3 and 4 use the standard induction over the number of colors via Gallai partitions, with the 2-color Ramsey numbers as genuine base cases rather than as circular inputs. The only self-referential input is the invocation of R(F3,F3)=13 from the authors' submitted manuscript [6] in Case 3 of the proof of Theorem 2(2); this is a small Ramsey number for a different graph (the fan F3), it is not a restatement of R(S_t^r,S_t^r), and it is not used to define S_t^r or to fit any numerical value, so it does not make the derivation circular. The manuscript also leaves R(S_6^2,S_6^2)=15 unproved as the k=2 base of Lemma 3, and Section 2.3 contains an internal inconsistency where the proof begins by claiming to prove R(S_t^r,S_t^r)=2t-1 while Theorem 2(3) states 2t+2r-1, with a Hamilton-cycle step via Dirac that is invalid as written. These are correctness defects or omitted justifications, not circularity: no equation is shown to equal its own input by construction.
Assumptions & free parameters
assumptions (4)
- standard math Gallai partition theorem (Theorem 1): every rainbow-triangle-free edge coloring of a complete graph has a nontrivial partition with at most two colors between parts and one color between each pair of parts.
- domain assumption R(F_3, F_3) = 13 for the fan of order 7.
- domain assumption R(S_6^2, S_6^2) = 15.
- standard math Dirac's theorem (minimum degree at least n/2 implies Hamiltonian).
Cite this review
Pith. "Pith review of Ramsey and Gallai-Ramsey numbers for stars with extra independent edges." pith.science (2026). https://pith.science/paper/NZO2GS65
@misc{pith2026190802348,
author = {Pith},
title = {Pith review of: Ramsey and Gallai-Ramsey numbers for stars with extra independent edges},
year = {2026},
howpublished = {\url{https://pith.science/paper/NZO2GS65}},
note = {Machine review of arXiv:1908.02348}
}
abstract
Given a graph $G$ and a positive integer $k$, define the \emph{Gallai-Ramsey number} to be the minimum number of vertices $n$ such that any $k$-edge coloring of $K_n$ contains either a rainbow (all different colored) triangle or a monochromatic copy of $G$. In this paper, we obtain general upper and lower bounds on the Gallai-Ramsey numbers for the graph $G = S_t^{r}$ obtained from a star of order $t$ by adding $r$ extra independent edges between leaves of the star so there are $r$ triangles and $t - 2r - 1$ pendent edges in $S_t^{r}$. We also prove some sharp results when $t = 2$.
Reference graph
Works this paper leans on
-
[6]
Y. Mao, Z. Wang, C. Magnant, and I. Schiermeyer. Gallai-R amsey num- bers for fans. Submitted. 27 A Appendix for review A.1 The case for r = 2 and general t In this section, we prove Item (3) of Theorem 3. First we prove the following lemma, which provides the lower bound. Lemma 6. grk(K3; S2 t ) ≥ { 2(t − 1) × 5 k−2 2 + 1, if k is even; (t − 1) × 5 k−1 2...
-
[1]
K. Cameron and J. Edmonds. Lambda composition. J. Graph Theory , 26(1):9–16, 1997
work page 1997
- [2]
- [3]
-
[4]
T. Gallai. Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hun- gar, 18:25–66, 1967
work page 1967
-
[5]
A. Gy´ arf´ as and G. Simonyi. Edge colorings of complete g raphs without tricolored triangles. J. Graph Theory , 46(3):211–216, 2004. 26
work page 2004
-
[7]
large” while other parts are called “sm all
This means that |G| = |H1| + |H2| ≤ n(k − 1, r, t ) − 1 + (2r − 2) + t − 1 < n, a contradiction. Finally if |H1| ≤ t − 1 and |H2| ≤ t − 1, then |G| = |H1| + |H2| ≤ 2(t − 1) < n , a contradiction. Thus, we may assume m ≥ 4 and by minimality of m, each part has edges to some other parts in both red and blue. If a part has order at least t, it can therefore ...
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.