pith. sign in

arxiv: 2605.02793 · v1 · submitted 2026-05-04 · 🧮 math.CO

Ramsey numbers and Gallai--Ramsey numbers of disjoint unions of cherries

Yanbo Zhang , Qian Chen , Yaojun Chen This is my paper

Pith reviewed 2026-05-08 18:04 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C55
keywords Ramsey numbersGallai-Ramsey numbersdisjoint unions of P3cherriesedge coloringsmulticolor Ramsey numbersgraph theory conjectures
0
0 comments X

The pith

The conjectured formula for Ramsey numbers of cherry unions fails in general, but holds for Gallai-Ramsey numbers.

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

This paper studies multicolour Ramsey numbers for the disjoint union of ni copies of P3, called cherries, across k colours. It shows that the conjectured value N = 2 max{ni} + sum ni - k + 1 does not always give the exact Ramsey number R(n1P3, ..., nkP3), by exhibiting colorings of smaller complete graphs that avoid the required monochromatic subgraphs in each colour. The authors supply additional conditions on the ni that make the equality hold. In contrast, they prove that the same formula always gives the exact Gallai-Ramsey number GR(n1P3, ..., nkP3) when colourings are restricted to those without rainbow triangles.

Core claim

The Ramsey number R(n1P3,…,nkP3) is not always equal to N = 2 max{ni} + sum ni - k + 1, as shown by the existence of specific k-edge-colorings of K_{N-1} that avoid a monochromatic niP3 in colour i for each i. Sufficient conditions on the ni are given under which the equality does hold. Every Gallai colouring of KN, however, must contain a monochromatic niP3 in some colour i, so the Gallai-Ramsey number GR(n1P3,…,nkP3) equals N for all positive integers ni and k.

What carries the argument

The quantity N = 2 max{n1,…,nk} + sum ni - k + 1, which the paper shows is always the exact value of the Gallai-Ramsey number but only sometimes the exact value of the ordinary Ramsey number for these cherry unions.

Load-bearing premise

Specific k-edge-colorings of K_{N-1} exist that avoid a monochromatic niP3 in each prescribed colour i.

What would settle it

A Gallai k-edge-coloring of K_{N-1} containing no monochromatic niP3 in colour i for any i would show that the Gallai-Ramsey number is smaller than N.

Figures

Figures reproduced from arXiv: 2605.02793 by Qian Chen, Yanbo Zhang, Yaojun Chen.

Figure 1
Figure 1. Figure 1: A 6-edge-coloring of K10 witnessing R6(3P3, P3, . . . , P3) ≥ 11. It remains to prove the upper bound. For k = 2, the stronger identity R(tP3, P3) = 3t is immediate. Hence we may assume that k ≥ 3. Let N =    9, if k ∈ {3, 4}, k + 4, if k ≥ 5 is odd, 11, if k = 6, k + 3, if k ≥ 8 is even. Consider an arbitrary k-edge-coloring of KN . Suppose that there is no monochromatic copy of P3 in any c… view at source ↗
read the original abstract

For graphs $G_1,\ldots,G_k$, the Ramsey number $R(G_1,\ldots,G_k)$ is the smallest positive integer $N$ such that every $k$-edge-coloring of $K_N$ contains a monochromatic copy of $G_i$ in color $i$ for some $i\in[k]$. The Gallai--Ramsey number $GR(G_1,\ldots,G_k)$ is defined analogously, with the colorings restricted to Gallai colorings (i.e., edge-colorings with no rainbow triangle). A copy of $P_3$ is called a cherry. Let $n_iP_3$ denote the disjoint union of $n_i$ cherries. Wu, Magnant, Nowbandegani, and Xia (Discrete Appl. Math., 2019) proposed two conjectures: \[ R(n_1P_3,\ldots,n_kP_3)=N\ \text{and}\ GR(n_1P_3,\ldots,n_kP_3)=N\,, \] where $N=2\max\{n_1,\ldots,n_k\}+\sum_{i=1}^kn_i-k+1$. We disprove the Ramsey conjecture and provide some sufficient conditions for determining the exact value of $R(n_1P_3,\ldots,n_kP_3)$. In contrast, we confirm the Gallai--Ramsey conjecture.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript disproves the Ramsey conjecture of Wu et al. on R(n1P3,…,nkP3) by exhibiting counterexamples for certain tuples (n1,…,nk), supplies sufficient conditions under which the exact value of this multicolor Ramsey number can be determined, and proves that the corresponding Gallai–Ramsey number GR(n1P3,…,nkP3) equals the conjectured expression N=2max{ni}+∑ni−k+1.

Significance. If the counterexamples are correct, the work shows that the conjectured formula is not always exact for ordinary Ramsey numbers while holding under the Gallai-coloring restriction; the sufficient conditions and the GR proof together give a partial resolution of the two conjectures and new tools for evaluating Ramsey numbers of disjoint unions of P3’s.

major comments (2)
  1. [§3, Theorem 3.2] §3, Theorem 3.2 (counterexamples): the disproof of the Ramsey conjecture rests on the explicit construction of k-edge-colorings of K_{N−1} with no monochromatic niP3 in color i. The manuscript must supply the full definition of these colorings (including how the edges are partitioned) together with a self-contained argument that the matching number of each color class (in the P3 sense) is strictly less than ni; any gap in this verification would invalidate the disproof while leaving the GR result intact.
  2. [§4, Theorem 4.1] §4, Theorem 4.1 (sufficient conditions): the stated conditions for exact determination of R(n1P3,…,nkP3) are applied only after the counterexamples; it is unclear whether these conditions recover the conjectured value N precisely when the counterexamples do not apply, or whether additional cases remain open. A clarifying statement or table listing the tuples covered by each regime would strengthen the claim.
minor comments (2)
  1. [§2] Notation: the symbol n_iP_3 is introduced in the abstract but the precise definition (disjoint union of n_i copies of P_3, i.e., a matching of n_i edges) should be restated at the beginning of §2 for readers unfamiliar with the prior literature.
  2. [§5] The proof of the Gallai–Ramsey result in §5 invokes several auxiliary lemmas; a short roadmap paragraph at the start of the section would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the thorough review and constructive comments. We address each major point below and will revise the manuscript accordingly to enhance clarity and rigor.

read point-by-point responses

  1. Referee: [§3, Theorem 3.2] §3, Theorem 3.2 (counterexamples): the disproof of the Ramsey conjecture rests on the explicit construction of k-edge-colorings of K_{N−1} with no monochromatic niP3 in color i. The manuscript must supply the full definition of these colorings (including how the edges are partitioned) together with a self-contained argument that the matching number of each color class (in the P3 sense) is strictly less than ni; any gap in this verification would invalidate the disproof while leaving the GR result intact.

    Authors: We agree that the construction requires a fully explicit and self-contained presentation. In the revised version, we will expand Theorem 3.2 to include the complete definition of the k-edge-coloring of K_{N-1} (specifying the partition of all edges into the k colors) together with a detailed, self-contained proof that the largest set of vertex-disjoint P3's in color i is at most n_i−1. This will eliminate any potential gaps and make the disproof of the Ramsey conjecture fully rigorous. revision: yes

  2. Referee: [§4, Theorem 4.1] §4, Theorem 4.1 (sufficient conditions): the stated conditions for exact determination of R(n1P3,…,nkP3) are applied only after the counterexamples; it is unclear whether these conditions recover the conjectured value N precisely when the counterexamples do not apply, or whether additional cases remain open. A clarifying statement or table listing the tuples covered by each regime would strengthen the claim.

    Authors: We thank the referee for highlighting this point. The sufficient conditions of Theorem 4.1 are intended to apply exactly to those tuples (n1,…,nk) that avoid the counterexample families identified in Theorem 3.2, thereby recovering the conjectured value N. In the revision we will insert a clarifying paragraph immediately after Theorem 4.1 that explicitly relates the two results and add a short table (or enumerated list) of representative tuples covered by the sufficient conditions, together with the corresponding value of N. This will make the scope of each regime transparent and confirm that no further open cases are left under the stated conditions. revision: yes

Circularity Check

0 steps flagged

No circularity: disproof via explicit avoiding colorings and independent confirmation of Gallai-Ramsey conjecture

full rationale

The paper cites the 2019 conjectures of Wu et al. (distinct authors) as external statements to be tested. It disproves the Ramsey conjecture by constructing explicit k-edge-colorings of K_{N-1} that avoid monochromatic n_i P_3 in each color i, together with a direct combinatorial argument that each color class has matching number strictly less than n_i. It confirms the Gallai-Ramsey conjecture by a separate proof under the Gallai-coloring restriction. Neither step reduces to a self-definition, a fitted parameter renamed as prediction, a load-bearing self-citation, or an ansatz smuggled from prior work by the same authors. The derivation chain is self-contained against the stated external conjectures and does not rely on renaming known results or uniqueness theorems imported from the present authors.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on the standard definitions of Ramsey numbers, Gallai colorings, and the conjectured formula; no free parameters, new entities, or non-standard axioms are introduced in the abstract.

axioms (1)
  • domain assumption Standard definitions of multicolor Ramsey numbers and Gallai colorings (no rainbow triangle) are used without modification.
    Invoked to state the conjectures and the results.

pith-pipeline@v0.9.0 · 5561 in / 1255 out tokens · 104114 ms · 2026-05-08T18:04:41.642705+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Bondy, Pancyclic graphs I,J

    J.A. Bondy, Pancyclic graphs I,J. Combin. Theory Ser. B11(1971), 80–84. 22

    work page 1971

  2. [2]

    Cockayne, P.J

    E.J. Cockayne, P.J. Lorimer, The Ramsey number for stripes,J. Austral. Math. Soc.19(1975), 252–256

    work page 1975

  3. [3]

    DeBiasio, A

    L. DeBiasio, A. Gy´ arf´ as, G.N. S´ ark¨ ozy, Ramsey numbers of path-matchings, covering designs, and 1-cores,J. Combin. Theory Ser. B146(2021), 124–140

    work page 2021

  4. [4]

    Dirac, Some theorems on abstract graphs,Proc

    G.A. Dirac, Some theorems on abstract graphs,Proc. London Math. Soc. (3)2(1952), 69–81

    work page 1952

  5. [5]

    Erd˝ os, Welcoming address,Ann

    P. Erd˝ os, Welcoming address,Ann. Discrete Math.28(1985), 1–5

    work page 1985

  6. [6]

    Erd˝ os, A

    P. Erd˝ os, A. R´ enyi, Asymmetric graphs,Acta Math. Acad. Sci. Hungar.14(1963), 295–315

    work page 1963

  7. [7]

    Faudree, R.H

    R.J. Faudree, R.H. Schelp, Ramsey numbers for all linear forests,Discrete Math.16(1976), 149–155

    work page 1976

  8. [8]

    Gallai, Transitiv orientierbare Graphen,Acta Math

    T. Gallai, Transitiv orientierbare Graphen,Acta Math. Acad. Sci. Hungar.18(1967), 25–66

    work page 1967

  9. [9]

    Harary,Graph Theory, Addison–Wesley, 1969

    F. Harary,Graph Theory, Addison–Wesley, 1969

    work page 1969

  10. [10]

    Irving, Generalised Ramsey numbers for small graphs,Discrete Math.9(1974), 251–264

    R.W. Irving, Generalised Ramsey numbers for small graphs,Discrete Math.9(1974), 251–264

    work page 1974

  11. [11]

    Maffray, M

    F. Maffray, M. Preissmann, A translation of Gallai’s paper: ‘Transitiv Orientierbare Graphen’, in:Perfect Graphs(J.L. Ramirez-Alfonsin and B.A. Reed, Eds.), Wiley, New York, 2001, pp. 25–66

    work page 2001

  12. [12]

    Olejniczak, Variations in Ramsey Theory, PhD thesis, Western Michigan University, Kala- mazoo, MI, 2019

    D. Olejniczak, Variations in Ramsey Theory, PhD thesis, Western Michigan University, Kala- mazoo, MI, 2019

    work page 2019

  13. [13]

    Scobee, On the Ramsey numberr(m 1P3, m2P3, m3P3) and related results, M.A

    M.W. Scobee, On the Ramsey numberr(m 1P3, m2P3, m3P3) and related results, M.A. thesis, University of Louisville, 1993

    work page 1993

  14. [14]

    Sudakov, J

    B. Sudakov, J. Volec, Properly colored and rainbow copies of graphs with few cherries,J. Combin. Theory Ser. B122(2017), 391–416

    work page 2017

  15. [15]

    H. Wu, C. Magnant, P.S. Nowbandegani, S. Xia, All partitions have small parts–Gallai-Ramsey numbers of bipartite graphs,Discrete Appl. Math.254(2019), 196–203

    work page 2019

  16. [16]

    Zhang, Z.-X

    F. Zhang, Z.-X. Song, Y. Chen, Gallai-Ramsey number of even cycles with chords,Discrete Math.345(3)(2022), 112738

    work page 2022

  17. [17]

    Zhang, Z.-X

    F. Zhang, Z.-X. Song, Y. Chen, Gallai-Ramsey number of odd cycles with chords,European J. Combin.107(2023), 103598. 23

    work page 2023