pith. sign in

arxiv: 2511.16656 · v2 · submitted 2025-11-20 · 🧮 math.CO

The multicolour size Ramsey number of a path

Csongor Beke , Anqi Li , Julian Sahasrabudhe This is my paper

Pith reviewed 2026-05-17 20:23 UTC · model grok-4.3

classification 🧮 math.CO
keywords size Ramsey numbermulticolour Ramsey numberpathasymptotic boundsextremal graph theoryRamsey theoryedge colourings
0
0 comments X

The pith

For fixed r and paths of length k at least 100 log r, the r-colour size Ramsey number of P_k is asymptotically r squared log r times k.

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

The paper establishes the precise order of magnitude for the multicolour size Ramsey number of a path. It proves that when the number of colors r is fixed and the path P_k is long enough relative to r, any r-edge-coloured graph with enough edges must contain a monochromatic copy of P_k, and this threshold number of edges is on the order of r squared log r multiplied by k. This pins down the minimal edge density needed to force long monochromatic paths across multiple colors. The result comes from strengthening a lower-bound construction to match existing upper bounds up to constant factors.

Core claim

The r-colour size Ramsey number of the path satisfies hat{R}_r(P_k) = Theta((r^2 log r) k) for every fixed r greater than or equal to 2 and every k at least 100 log r. The authors obtain this by improving the lower bound construction, which now meets the previously known upper bound up to constants.

What carries the argument

The multicolour size Ramsey number hat{R}_r(P_k), the smallest number of edges in a graph such that every r-edge-colouring contains a monochromatic copy of the path P_k.

If this is right

  • The required number of edges grows linearly with the path length k.
  • The dependence on the number of colours r is quadratic, with an extra logarithmic factor.
  • The bound holds uniformly once k exceeds a multiple of log r.
  • Lower-bound constructions can be tuned to achieve the matching order for this family of graphs.

Where Pith is reading between the lines

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

  • The same asymptotic shape may persist for k smaller than 100 log r, possibly with different implicit constants.
  • The technique of refining lower-bound constructions could determine size Ramsey numbers for other trees or sparse graphs.
  • The log r factor may reflect an inherent multicolour phenomenon that appears in related Ramsey problems for paths and cycles.

Load-bearing premise

The path length k must be at least roughly 100 times the logarithm of the number of colours r.

What would settle it

An explicit r-edge-coloured graph with substantially fewer than c r squared log r times k edges, for small enough constant c, that still forces a monochromatic P_k in every colouring.

Figures

Figures reproduced from arXiv: 2511.16656 by Anqi Li, Csongor Beke, Julian Sahasrabudhe.

Figure 1
Figure 1. Figure 1: Round i of the colouring process. We terminate this recursive procedure at round t when we may no longer apply Lemma 2.1 to Gt . That is, we obtain Gt ⊂ G0 satisfying one of the following two conditions: e(Gt) ⩽ r 7/4 k or ∆(Gt) ⩽ r/7. (6) We then take care of Gt by two other colouring techniques, which we describe in a moment. Overall, our colouring process can be summarised by the following diagram. 4 [… view at source ↗
Figure 2
Figure 2. Figure 2: The complete colouring process. 2.3. Other colouring techniques. We now describe two other colouring techniques which we will use for the clean-up step at the end of each round and to colour the graph Gt in (6). To apply Lemma 2.1, we need control on v(G) and ∆(G). This next lemma helps us achieve the required bound on v(G). Lemma 2.2 (Vizing-type colouring). Let r be sufficiently large and G be a graph sa… view at source ↗
read the original abstract

In this paper, we determine the $r$-colour size Ramsey number of the path $P_k$, up to constants. In particular, for every fixed $r \geq 2$ and $k \geq 100\log r$, we have \[ \widehat{R}_r(P_k)=\Theta((r^2 \log r) \, k).\] Perhaps surprisingly, we do this by improving the lower bound on $\widehat{R}_r(P_k)$.

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

1 major / 2 minor

Summary. The manuscript determines the multicolour size Ramsey number of the path asymptotically, claiming that for every fixed r ≥ 2 and k ≥ 100 log r, the r-colour size Ramsey number satisfieswidehat{R}_r(P_k) = Θ((r² log r) k). The new contribution is an improved probabilistic lower bound; the matching upper bound is inherited from prior work.

Significance. If the lower-bound argument is correct, the result gives a tight asymptotic for the size Ramsey number of paths in the multicolour setting, closing the gap between previous lower and upper bounds and yielding a clean Θ statement. The explicit threshold k ≥ 100 log r is a concrete improvement over earlier logarithmic factors.

major comments (1)
  1. [Lower-bound construction] Lower-bound section (the probabilistic construction): the argument takes a random r-edge-coloured graph on m ≈ c r² log r ⋅ k edges and applies a union bound to show that the probability of a monochromatic P_k is less than 1. The union bound must absorb an r-factor for the colour choice together with the number of potential embeddings of P_k (which contributes roughly (m choose k) ⋅ k! or equivalent counting terms). When k = Θ(log r) these overhead terms can cancel the main exponential decay; the manuscript asserts that the constant 100 suffices but supplies no explicit numerical verification that 100 dominates the hidden constants arising from the r-colour union bound and the embedding count. This calculation is load-bearing for the claim that the Θ statement holds already at k ≥ 100 log r.
minor comments (2)
  1. The abstract states the result cleanly but does not indicate which previous bounds are being improved; a single sentence comparing the new lower bound to the best prior lower bound would help readers gauge the advance.
  2. [Introduction] Notation: ensure that the precise definition of the size Ramsey numberwidehat{R}_r(H) (minimum number of edges guaranteeing a monochromatic copy of H in any r-edge-colouring) appears explicitly before the main theorem.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough reading and for identifying the need for greater explicitness in the lower-bound argument. We address the major comment below and will revise the manuscript accordingly to strengthen the presentation.

read point-by-point responses

  1. Referee: Lower-bound section (the probabilistic construction): the argument takes a random r-edge-coloured graph on m ≈ c r² log r ⋅ k edges and applies a union bound to show that the probability of a monochromatic P_k is less than 1. The union bound must absorb an r-factor for the colour choice together with the number of potential embeddings of P_k (which contributes roughly (m choose k) ⋅ k! or equivalent counting terms). When k = Θ(log r) these overhead terms can cancel the main exponential decay; the manuscript asserts that the constant 100 suffices but supplies no explicit numerical verification that 100 dominates the hidden constants arising from the r-colour union bound and the embedding count. This calculation is load-bearing for the claim that the Θ statement holds already at k ≥ 100 log r.

    Authors: We agree that an explicit verification of the constants would improve clarity. In the proof, the union bound is taken over the r colours and over all ordered sequences of k distinct vertices (at most n^k terms, with n chosen linear in k to support m edges). Each potential path has probability at most (C m / n^2)^k ⋅ r^{-(k-1)} of appearing monochromatically in a fixed colour, where the edge probability is controlled by the random selection of m edges. Substituting m = C r² log r ⋅ k and k ≥ 100 log r yields an overall bound of the form r ⋅ (e C r log r / 100)^k ⋅ r^{-k} times lower-order factors. The base of the exponential is at most (C r log r / 100) ⋅ r^{-1} < 1/2 once C is fixed at a moderate absolute constant (e.g., C=10) and the 100 absorbs the remaining logarithmic and polynomial overhead in r (which is fixed). We will add a short paragraph after the union-bound estimate that carries out this comparison explicitly, confirming that the inequality holds for all r ≥ 2 and k ≥ 100 log r. This does not alter the asymptotic statement but makes the threshold fully rigorous. revision: yes

Circularity Check

0 steps flagged

No circularity: direct combinatorial determination via probabilistic lower bound

full rationale

The paper determines the multicolour size Ramsey number up to constants by improving the lower bound on the extremal function for paths in r-edge-coloured graphs. This proceeds from standard random-graph techniques and union-bound estimates on monochromatic paths, without any self-definitional reduction, fitted parameter renamed as prediction, or load-bearing self-citation chain that collapses the central claim to its own inputs. The threshold k >= 100 log r is an explicit hypothesis chosen to ensure the probabilistic estimates are positive; it does not create a circular dependency. The result is therefore self-contained against external benchmarks in Ramsey theory.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard facts from graph theory and Ramsey theory together with a new explicit colouring construction for the lower bound; no free parameters or invented entities are introduced in the abstract statement.

axioms (1)
  • standard math Basic facts about paths and edge colourings in finite graphs
    Invoked implicitly when defining size Ramsey numbers and monochromatic subgraphs.

pith-pipeline@v0.9.0 · 5367 in / 1172 out tokens · 51316 ms · 2026-05-17T20:23:22.957484+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [1]

    On size Ramsey number of paths, trees, and circuits

    J´ ozsef Beck. On size Ramsey number of paths, trees, and circuits. I.J. Graph Theory, 7(1):115–129, 1983

    work page 1983

  2. [2]

    Recent developments in graph Ramsey theory

    David Conlon, Jacob Fox, and Benny Sudakov. Recent developments in graph Ramsey theory. InSurveys in combinatorics 2015, volume 424 ofLondon Math. Soc. Lecture Note Ser., pages 49–118. Cambridge Univ. Press, Cambridge, 2015

    work page 2015

  3. [3]

    On some multicolor Ramsey properties of random graphs.SIAM J

    Andrzej Dudek and Pawe l Pra lat. On some multicolor Ramsey properties of random graphs.SIAM J. Discrete Math., 31(3):2079–2092, 2017

    work page 2079

  4. [4]

    Erd˝ os, R

    P. Erd˝ os, R. J. Faudree, C. C. Rousseau, and R. H. Schelp. The size Ramsey number.Period. Math. Hungar., 9(1-2):145–161, 1978

    work page 1978

  5. [5]

    Gaston H. Gonnet. Expected length of the longest probe sequence in hash code searching.J. Assoc. Comput. Mach., 28(2):289–304, 1981

    work page 1981

  6. [6]

    Random Graphs ’93

    Lars Holst. The general birthday problem. InProceedings of the Sixth International Seminar on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science, “Random Graphs ’93” (Pozna´ n, 1993), volume 6, pages 201–208, 1995

    work page 1993

  7. [7]

    Keˇ cki´ c and Petar M

    Jovan D. Keˇ cki´ c and Petar M. Vasi´ c. Some inequalities for the gamma function.Publ. Inst. Math. (Beograd) (N.S.), 11(25):107–114, 1971

    work page 1971

  8. [8]

    Long cycles in locally expanding graphs, with applications.Combinatorica, 39(1):135–151, 2019

    Michael Krivelevich. Long cycles in locally expanding graphs, with applications.Combinatorica, 39(1):135–151, 2019

    work page 2019

  9. [9]

    Marshall and Ingram Olkin.Inequalities: Theory of Majorization and Its Applications

    Albert W. Marshall and Ingram Olkin.Inequalities: Theory of Majorization and Its Applications. Aca- demic Press, New York, 1979

    work page 1979

  10. [10]

    D. S. Mitrinovi´ c.Analytic inequalities, volume Band 165 ofDie Grundlehren der mathematischen Wis- senschaften. Springer-Verlag, New York-Berlin, 1970. In cooperation with P. M. Vasi´ c

    work page 1970

  11. [11]

    Cambridge University Press, Cam- bridge, second edition, 2017

    Michael Mitzenmacher and Eli Upfal.Probability and computing. Cambridge University Press, Cam- bridge, second edition, 2017. Randomization and probabilistic techniques in algorithms and data anal- ysis

    work page 2017

  12. [12]

    Balls into bins

    Martin Raab and Angelika Steger. “Balls into bins”—a simple and tight analysis. InRandomization and approximation techniques in computer science (Barcelona, 1998), volume 1518 ofLecture Notes in Comput. Sci., pages 159–170. Springer, Berlin, 1998. AppendixA.Deferred analysis of balls-and-bins In this appendix, we study theballs and bins problem, and we re...

    work page 1998

  13. [13]

    We first quote an estimate from [7], which is a generalisation of Stirling’s approximation

    Therefore, EI (1) t I(2) t ⩽ n−tX k=t n k pk(1−p) n−kep2n+pP[Bin (n, p)⩾t] = exp n q2 + 1 q EI (1) t 2 .□ We will also need the following inequalities to analyse the tails of certain binomial ran- dom variables. We first quote an estimate from [7], which is a generalisation of Stirling’s approximation. Theorem A.8.Forx∈R ⩾0, we have √ 2πxx+ 1 2 e−x+ 1 12x...

    work page