Pith. sign in

REVIEW 4 minor 35 references

In three-edge-coloured complete graphs a path of length n with one colour change is already forced once the graph has only about 3n/2 vertices.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-12 03:51 UTC pith:37WTE4X7

load-bearing objection Clean three-colour colour-change Ramsey numbers for paths (additive constant) and even cycles (o(n)), with solid combinatorial proofs that inherit only the known large-n cycle Ramsey thresholds.

arxiv 2607.03243 v1 pith:37WTE4X7 submitted 2026-07-03 math.CO

On Ramsey-type problems for paths and cycles with few colour changes

Peter Allen , Julia B\"ottcher , Dennis Clemens , Fabian Hamann , Jozef Skokan , Anusch Taraz This is my paper
classification math.CO MSC 05C5505C38
keywords Ramsey numberscolour changespathscyclesthree-edge-colouringsmonochromatic path coverssplit colourings
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Classical Ramsey theory asks for monochromatic copies of a graph. This paper relaxes that demand for paths and cycles: it allows a handful of colour changes and measures how many vertices are then needed to force the structure. The new parameter R_q^k(G) is the smallest N such that every q-edge-colouring of K_N contains a copy of G with at most k colour-change vertices. For three colours the authors prove that a path on n vertices with at most one colour change appears already at N = 3n/2 + O(1). For even cycles the same asymptotic threshold works when two colour changes are allowed. The results sit between the classical three-colour Ramsey numbers (which grow like 2n) and the two-colour path Ramsey number (which is already 3n/2), showing that one extra colour change exactly cancels the cost of the third colour. The proofs combine known large-n Ramsey numbers for monochromatic cycles with elementary splitting arguments and a bipartite matching lemma that produces long paths or cycles once a colouring has a rigid four-partite structure.

Core claim

For every sufficiently large n one has floor((3n-2)/2) ≤ R_3^1(P_n) ≤ 3⌈n/2⌉ + 2 (and ≤ 3n/2 when 4 divides n). For every sufficiently large even n one has R_3^2(C_n) = (3/2 + o(1))n. In other words, allowing a single colour change for paths, or two for even cycles, reduces the three-colour Ramsey threshold from roughly 2n down to the classical two-colour threshold 3n/2.

What carries the argument

The auxiliary parameter R_q^k(G) together with a two-step reduction: first a Ramsey-plus-splitting lemma that either produces the desired path/cycle or forces a rigid four-partite colouring of the complete graph; second an elementary counting argument (via Pokrovskiy’s three-path cover) that extracts a short colour-change path or cycle from every such four-partite colouring.

Load-bearing premise

The upper-bound arguments rely on the known three-colour Ramsey numbers for cycles, which themselves hold only for sufficiently large n and rest on the regularity lemma.

What would settle it

An explicit three-edge-colouring of a complete graph on roughly 3n/2 + ω(1) vertices that contains neither a path of length n with one colour change nor (for even n) a cycle of length n with two colour changes would refute the claimed asymptotic thresholds.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Allowing one colour change exactly offsets the penalty of a third colour for paths, recovering the classical two-colour growth rate.
  • The same asymptotic holds for even cycles with two colour changes, suggesting a broader pattern for sparse graphs.
  • A Hamilton path with at most two colour changes in any three-edge-coloured K_n would imply a cover by three monochromatic paths, recovering a known theorem of Pokrovskiy.
  • The four-partite split colourings that arise as extremal candidates become the natural objects for studying the remaining odd-cycle case.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the odd-cycle case can be settled at the same 3n/2 threshold, colour-change Ramsey numbers for cycles would behave uniformly, in contrast to ordinary Ramsey numbers where odd cycles require roughly twice as many vertices.
  • The same four-partite template that supplies the lower bound may be the only obstruction; a refined analysis of edges inside the parts could replace the o(n) error by an absolute constant for even cycles.
  • The definition of κ_q(G) (the minimal number of colour changes needed for a spanning copy) opens a new extremal question for trees, planar graphs and regular graphs that the paper only sketches.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 4 minor

Summary. The paper introduces the Ramsey-type parameter R_q^k(G), the smallest N such that every q-edge-colouring of K_N contains a copy of G with at most k colour-change vertices. Focusing on three colours, it proves that floor((3n-2)/2) ≤ R_3^1(P_n) ≤ 3⌈n/2⌉ + 2 (and ≤ 3n/2 when 4|n) for all sufficiently large n (Theorem 8), and that R_3^2(C_n) = (3/2 + o(1))n for all sufficiently large even n (Theorem 9). The lower bound is realised by an explicit four-partite colouring whose template is a 2-coloured K_4. The upper bounds proceed by a reduction (Lemmas 15 and 19) that either produces a good path/cycle directly or forces a split four-partite colouring; the latter case is settled by an elementary counting argument that invokes Pokrovskiy’s three-path cover and a bipartite path-extension lemma (Lemmas 13 and 16).

Significance. The work cleanly interpolates between classical multicolour Ramsey numbers for paths and cycles and the monochromatic-path-cover conjectures of Gyárfás and Erdős–Gyárfás–Pyber. The asymptotic coincidence of R_3^1(P_n) with the two-colour path Ramsey number is striking and suggests that a single colour change exactly offsets the third colour. All arguments after the invocation of the known large-n three-colour cycle Ramsey numbers are fully combinatorial, constructive, and free of further regularity; the lower-bound construction is elementary and exact. The new parameter R_q^k and the open problems posed in the concluding section (odd cycles, spanning trees, κ_q) open a natural research direction.

minor comments (4)
  1. [Abstract / Theorem 8] The abstract and Theorem 8 state the path upper bound as 3⌈n/2⌉ + 2, while the body (after Lemma 15) notes that N ≥ 3⌈n/2⌉ + 2 already forces the hypotheses of the reduction; a single sentence clarifying the precise additive constant for all residue classes of n would improve readability.
  2. [Lemma 15] In the proof of Lemma 15 the case k = ⌈n/2⌉ + 1 allows the two monochromatic cycles to share a single vertex; the subsequent argument that this immediately yields a good path of length > n is correct but slightly terse—one extra sentence would help the reader.
  3. [Remark 20 / Section 6] Remark 20 correctly isolates the only parity-dependent steps in Lemma 19; it would be useful to restate explicitly that Theorem 21 already holds for odd n, so that the sole remaining obstacle for odd cycles is the bipartite-endpoint argument of Case 1.
  4. [Throughout] A few typographical inconsistencies appear (e.g., “Theoren 5”, “Op 1q”, missing spaces around some set-builder braces). A light copy-edit pass would remove them.

Circularity Check

0 steps flagged

No circularity: bounds derived from independent external Ramsey theorems plus elementary counting on split colourings.

full rationale

The paper defines R_q^k(G) in the standard way and proves concrete upper/lower bounds for paths and even cycles by an explicit four-partite lower-bound colouring (Section 3) together with a reduction (Lemmas 15 and 19) that either produces a good path/cycle directly or forces a split colouring of the form required by Theorems 17 and 21. Those theorems then invoke only Pokrovskiy’s three-path cover (Lemma 13, external) and an elementary bipartite path-extension argument (Lemma 16). The sole non-elementary inputs are the three-colour cycle Ramsey numbers of Benevides–Skokan and Kohayakawa–Simonovits–Skokan (Theorem 2), which are independent published results used solely to force the colouring into the split form; they are not redefined or fitted inside the present paper. No quantity is defined in terms of the claimed bounds, no parameter is fitted to data and then re-predicted, and no uniqueness or ansatz is smuggled via self-citation. The derivation is therefore self-contained once the cited large-n cycle numbers are granted.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 2 invented entities

The paper is pure extremal combinatorics. It rests on standard graph-theoretic notions, three previously published theorems (Pokrovskiy’s three-path partition, the three-colour cycle Ramsey numbers, and a bipartite Dirac-type theorem), and the newly defined colour-change parameter. No numerical free parameters are fitted; the only asymptotic thresholds are inherited from the regularity-based cycle Ramsey results.

axioms (4)
  • domain assumption Every 3-edge-coloured complete graph admits a vertex partition into three monochromatic paths of which at most two share a colour (Pokrovskiy, Theorem 5).
    Invoked as Lemma 13 to produce monochromatic path covers inside each part of the template colouring.
  • domain assumption For all sufficiently large n the three-colour Ramsey numbers of even and odd cycles equal 2n and 4n-3 respectively (Benevides–Skokan / Kohayakawa–Simonovits–Skokan).
    Used in Lemmas 15 and 19 to locate two large monochromatic cycles that seed the template colouring.
  • standard math A balanced bipartite graph of minimum degree at least n/2 contains a Hamilton cycle (Moon–Moser).
    Applied inside the bipartite red graph of Lemma 18 to finish the cycle extraction.
  • ad hoc to paper Definition of colour changes and of the Ramsey number R_q^k(G).
    The entire paper is built around these two new definitions (Definitions 6 and 7).
invented entities (2)
  • R_q^k(G) (Ramsey number with at most k colour changes) no independent evidence
    purpose: To quantify the order that forces a copy of G whose edges change colour at most k times.
    Central object of study; no prior literature uses this exact parameter.
  • good path / good cycle no independent evidence
    purpose: Shorthand for a path with ≤1 colour change or a cycle with ≤2 colour changes.
    Convenience terminology introduced after Definition 6; purely notational.

pith-pipeline@v1.1.0-grok45 · 25407 in / 2532 out tokens · 22648 ms · 2026-07-12T03:51:11.410756+00:00 · methodology

0 comments
read the original abstract

In 1967, Gerencser and Gy\'arf\'as determined the exact values of the two-colour Ramsey numbers of paths. In a footnote, they made the following observation: Every $2$-edge-coloured complete graph contains a Hamilton path with at most one colour change. Later, this led to a challenging and still wide open conjecture about covering edge-coloured complete graphs with monochromatic paths. Inspired by the original statement, we study paths and cycles with few colour changes in $3$-edge-coloured complete graphs. For this, we introduce a new Ramsey-type parameter: For $q,k \in \mathbb{N}$ and a graph $G$, let $R_q^k(G)$ denote the smallest $N \in \mathbb{N}$ such that every $q$-edge-coloured complete graph on $N$ vertices contains a copy of $G$ with at most $k$ vertices that are incident to edges in $G$ of different colours. For paths, we show that $R_3^1(P_n) = \frac{3n}{2} + O(1)$, and for even cycles, we show that $R_3^2(C_n) = \frac{3n}{2} + o(n)$.

Figures

Figures reproduced from arXiv: 2607.03243 by Anusch Taraz, Dennis Clemens, Fabian Hamann, Jozef Skokan, Julia B\"ottcher, Peter Allen.

Figure 1
Figure 1. Figure 1: The lower bound construction and its template: Dots represent blue, lines represent green, and red is without pattern. 3. The Lower Bound Construction In this section, we provide an edge-colouring of KN with N “ X 3n´2 2 \ ´ 1 using exactly three colours, such that every copy of Pn has at least two colour changes, yielding the required lower bounds for Theorem 8 and Theorem 9. Proof of the lower bounds for… view at source ↗

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

35 extracted references · 1 linked inside Pith

  1. [1]

    Allen,Coveringtwo-edge-colouredcompletegraphswithtwodisjointmonochromaticcycles, Combinatorics, Probability and Computing17(2008), no

    P. Allen,Coveringtwo-edge-colouredcompletegraphswithtwodisjointmonochromaticcycles, Combinatorics, Probability and Computing17(2008), no. 4, 471–486

    2008

  2. [2]

    Balister, B

    P. Balister, B. Bollobás, M. Campos, S. Griffiths, E. Hurley, R. Morris, J. Sahasrabudhe, and M. Tiba,Upper bounds for multicolour Ramsey numbers, Journal of the American Mathematical Society39(2026), no. 3, 765–780

    2026

  3. [3]

    Benevides and J

    F.S. Benevides and J. Skokan,The 3-colored Ramsey number of even cycles, Journal of Combinatorial Theory, Series B99(2009), no. 4, 690–708

    2009

  4. [4]

    Bessy and S

    S. Bessy and S. Thomassé,Partitioning a graph into a cycle and an anticycle, a proof of Lehel’sconjecture, Journal of Combinatorial Theory, Series B100(2010), no. 2, 176–180

    2010

  5. [5]

    Bialostocki and P

    A. Bialostocki and P. Dierker,On simple hamiltonian cycles in a 2-colored complete graph, Ars Combinatoria 32(1991), 13–16

    1991

  6. [6]

    Bondy and P

    J.A. Bondy and P. Erdős,Ramsey numbers for cycles in graphs, Journal of Combinatorial Theory, Series B 14(1973), no. 1, 46–54

    1973

  7. [7]

    Burr and P

    S.A. Burr and P. Erdős,On the magnitude of generalized Ramsey numbers for graphs, Infinite and Finite Sets, Vol. 1, Colloquia Mathematica Societatis János Bolyai, 10, North-Holland, Amsterdam / London, 1975, pp. 214–240

    1975

  8. [8]

    Campos, S

    M. Campos, S. Griffiths, R. Morris, and J. Sahasrabudhe,An exponential improvementfor diagonal Ramsey, Annals of Mathematics. Second Series203(2026), no. 3, 869–932

    2026

  9. [9]

    Chvátal, V

    V. Chvátal, V. Rödl, E. Szemerédi, and W.T. Trotter Jr,The Ramsey number of a graph with bounded maximum degree, Journal of Combinatorial Theory, Series B34(1983), no. 3, 239–243

    1983

  10. [10]

    Dvořák,A note on Norine’santipodal-colouring conjecture, The Electronic Journal of Combinatorics (2020), 2–26

    V. Dvořák,A note on Norine’santipodal-colouring conjecture, The Electronic Journal of Combinatorics (2020), 2–26

    2020

  11. [11]

    Erdős,Some remarks on the theory of graphs, Bulletin of the American Mathematical Society53(1947), no

    P. Erdős,Some remarks on the theory of graphs, Bulletin of the American Mathematical Society53(1947), no. 4, 292–294

    1947

  12. [12]

    Erdős, A

    P. Erdős, A. Gyárfás, and L. Pyber,Vertexcoverings by monochromatic cycles and trees, Journal of Combi- natorial Theory, Series B51(1991), no. 1, 90–95

    1991

  13. [13]

    Erdős and G

    P. Erdős and G. Szekeres,A combinatorial problem in geometry, Compositio Mathematica2(1935), 463–470

    1935

  14. [14]

    Faudree and R.H

    R.J. Faudree and R.H. Schelp,All Ramsey numbers for cycles in graphs, Discrete Mathematics8(1974), no. 4, 313–329

    1974

  15. [15]

    Feder and C

    T. Feder and C. Subi, On hypercube labellings and antipodal monochromatic paths, Discrete Applied Mathematics161(2013), no. 10-11, 1421–1426

    2013

  16. [16]

    Gerencsér and A

    L. Gerencsér and A. Gyárfás,On Ramsey-type problems, Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae. Sectio Mathematica10(1967), 167–170

    1967

  17. [17]

    Gupta, N

    P. Gupta, N. Ndiaye, S. Norin, and L. Wei,Optimizing the CGMS upper bound on Ramsey numbers, arXiv:2407.19026, 2024

    Pith/arXiv arXiv 2024

  18. [18]

    Gyárfás,Vertex coverings by monochromatic paths and cycles, Journal of Graph Theory7(1983), no

    A. Gyárfás,Vertex coverings by monochromatic paths and cycles, Journal of Graph Theory7(1983), no. 1, 131–135

    1983

  19. [19]

    8, Springer, Berlin, 1989, pp

    , Covering complete graphs by monochromatic paths, Irregularities of partitions (Fertőd, 1986), Algorithms and Combinatorics: Study and Research Texts, vol. 8, Springer, Berlin, 1989, pp. 89–91

    1986

  20. [20]

    Gyárfás and J

    A. Gyárfás and J. Lehel,A Ramsey-type problem in directed and bipartite graphs, Periodica Mathematica Hungarica3(1973), no. 3-4, 299–304

    1973

  21. [21]

    Gyárfás, M

    A. Gyárfás, M. Ruszinkó, G. Sárközy, and E. Szemerédi,Three-color Ramsey numbers for paths, Combina- torica27(2007), no. 1, 35–70. 20 P. ALLEN, J. BÖTTCHER, D. CLEMENS, F. HAMANN, J. SKOKAN, AND A. TARAZ

    2007

  22. [22]

    Knierim and P

    C. Knierim and P. Su,Improved bounds on the multicolor Ramsey numbers of paths and even cycles, The Electronic Journal of Combinatorics26(2019), no. 1, 1–26

    2019

  23. [23]

    Kohayakawa, M

    Y. Kohayakawa, M. Simonovits, and J. Skokan,The 3-colored Ramsey number of odd cycles, Proceedings of GRACO 2005, Electronic Notes in Discrete Mathematics, vol. 19, Elsevier, Amsterdam, 2005, pp. 397–402

    2005

  24. [24]

    Leader and E

    I. Leader and E. Long,Long geodesics in subgraphs of the cube, Discrete Mathematics326(2014), 29–33

    2014

  25. [25]

    Lee,Ramsey numbers of degenerate graphs, Annals of Mathematics185(2017), no

    C. Lee,Ramsey numbers of degenerate graphs, Annals of Mathematics185(2017), no. 3, 791–829

    2017

  26. [26]

    Łuczak, V

    T. Łuczak, V. Rödl, and E. Szemerédi,Partitioning two-coloured complete graphs into two monochromatic cycles, Combinatorics, Probability and Computing7(1998), no. 4, 423–436

    1998

  27. [27]

    Manoussakis, M

    Y. Manoussakis, M. Spyratos, and Zs. Tuza,Cycles of given color patterns, Journal of Graph Theory21 (1996), no. 2, 153–162

    1996

  28. [28]

    Moon and L

    J. Moon and L. Moser,On Hamiltonian bipartite graphs, Israel Journal of Mathematics1(1963), no. 3, 163–165

    1963

  29. [29]

    Norine, Edge-antipodal colorings of cubes, 2008, http://www.openproblemgarden.org/op/edge_ antipodal_colorings_of_cubes

    S. Norine, Edge-antipodal colorings of cubes, 2008, http://www.openproblemgarden.org/op/edge_ antipodal_colorings_of_cubes

    2008

  30. [30]

    Pokrovskiy,Partitioning edge-coloured complete graphs into monochromatic cycles and paths, Journal of Combinatorial Theory, Series B106(2014), 70–97

    A. Pokrovskiy,Partitioning edge-coloured complete graphs into monochromatic cycles and paths, Journal of Combinatorial Theory, Series B106(2014), 70–97

    2014

  31. [31]

    Ramsey,On a problem of formal logic, Proceedings of the London Mathematical Society2(1930), no

    F.P. Ramsey,On a problem of formal logic, Proceedings of the London Mathematical Society2(1930), no. 1, 264–286

    1930

  32. [32]

    Raynaud,Sur le circuit hamiltonien bi-coloré dans les graphes orientés, Periodica Mathematica Hungarica 3(1973), no

    H. Raynaud,Sur le circuit hamiltonien bi-coloré dans les graphes orientés, Periodica Mathematica Hungarica 3(1973), no. 3-4, 289–297

    1973

  33. [33]

    Rosta,On a Ramsey-type problem of JA Bondyand P

    V. Rosta,On a Ramsey-type problem of JA Bondyand P. Erdös. I, Journal of Combinatorial Theory, Series B15(1973), no. 1, 94–104

    1973

  34. [34]

    West,Introduction to graph theory, 2nd ed., Prentice Hall, Inc., Upper Saddle River, NJ, 2001

    D.B. West,Introduction to graph theory, 2nd ed., Prentice Hall, Inc., Upper Saddle River, NJ, 2001

    2001

  35. [35]

    Yongqi, Y

    S. Yongqi, Y. Yuansheng, X. Feng, and L. Bingxi,New lower bounds on the multicolor Ramsey numbers RrpC2mq, Graphs and Combinatorics22(2006), no. 2, 283–288. (PA|JB|JS) London School of Economics, Department of Mathematics, Houghton Street, London WC2A 2AE, UK Email address:p.d.allen|j.boettcher|j.skokan@lse.ac.uk (DC|FH|AT) Technische Universität Hamburg,...

    2006