pith. sign in

arxiv: 2605.22395 · v1 · pith:ZCVN2PY5new · submitted 2026-05-21 · 🧮 math.CO

A random version of the Burr-ErdH{o}s-Spencer theorem

Andrea Freschi , Ryan R. Martin , Andrew Treglown This is my paper

Pith reviewed 2026-05-22 04:30 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C5505C80
keywords random graphsRamsey numbersBurr-Erdős-Spencer theoremRödl-Ruciński theoremdisjoint copiesgraph coloringextremal graph theory
0
0 comments X

The pith

The 2-color Ramsey number for large disjoint unions of a fixed graph H extends to the random graph G(n,p) in an intermediate density range.

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

The paper proves a random version of the Burr-Erdős-Spencer theorem on the Ramsey number for sufficiently many vertex-disjoint copies of a fixed graph H without isolated vertices. It shows this holds in the binomial random graph when the edge probability p lies between the threshold where the Rödl-Ruciński random Ramsey theorem applies and the sparser regime where the effect of taking many copies remains visible. A sympathetic reader would care because the result bridges deterministic Ramsey theory with random graph models, confirming that the extremal behavior for these multi-component graphs survives the introduction of randomness.

Core claim

We prove that for a fixed graph H with no isolated vertices and all sufficiently large s, there is a range of p such that with high probability every 2-edge-coloring of G(n,p) contains a monochromatic copy of the disjoint union of s copies of H, generalizing the random Ramsey theorem of Rödl and Ruciński by incorporating the Burr-Erdős-Spencer determination of the relevant Ramsey number.

What carries the argument

The binomial random graph G(n,p) in a density window that is dense enough for the Rödl-Ruciński theorem to force monochromatic copies of H but sparse enough for the Ramsey number to grow with the number of disjoint copies s.

If this is right

  • The random Ramsey property for G(n,p) holds for target graphs that are large disjoint unions when s is large enough.
  • The threshold density for forcing monochromatic copies in random graphs can be read off from the deterministic Ramsey numbers for multiple copies.
  • Random-graph analogues exist for other Ramsey statements whose deterministic versions are known only for sufficiently many copies of a base graph.

Where Pith is reading between the lines

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

  • Similar techniques might yield random versions for other classical Ramsey results that require many copies or multiple components.
  • The precise location of the p-interval boundaries could be sharpened by examining the transition between single-copy and multi-copy behavior more closely.
  • One could test whether the same extension works when the host graph is not binomial but another random model with comparable density.

Load-bearing premise

The edge probability p must be high enough for the single-copy random Ramsey property to hold with high probability yet low enough that the Ramsey number still increases when the number of disjoint copies grows.

What would settle it

Finding a density p inside the claimed interval and a large s such that with positive probability G(n,p) admits a 2-edge-coloring with no monochromatic copy of the disjoint union of s copies of H.

Figures

Figures reproduced from arXiv: 2605.22395 by Andrea Freschi, Andrew Treglown, Ryan R. Martin.

Figure 1
Figure 1. Figure 1: The extremal construction of Theorem 1.1. Burr [7], and subsequently Buci´c and Sudakov [6], provided methods for computing the value of C in Theorem 1.1 exactly. Buci´c and Sudakov [6] also obtained the current best bounds for m0. In the case of Kk-tilings, their work states that there is a constant D > 0 such that R(mKk) = (2k − 1)m + R(Kk−1) − 2 provided m ≥ 2 Dk. Moreover, the bound on m is essentially… view at source ↗
read the original abstract

A well-known result of Burr, Erd\H{o}s and Spencer [Transactions of the American Mathematical Society, 1975] determines the $2$-colour Ramsey number for any sufficiently large collection of vertex-disjoint copies of a fixed graph $H$ without isolated vertices. In this short note we prove a random version of this result, thereby generalising the random Ramsey theorem of R\"odl and Ruci\'nski [Journal of the American Mathematical Society, 1995].

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

0 major / 2 minor

Summary. The paper proves a random analogue of the Burr-Erdős-Spencer theorem: for a fixed graph H with no isolated vertices and all sufficiently large k, the 2-color Ramsey property for the disjoint union k·H holds with high probability in G(n,p) precisely when p ≫ n^{-1/m_2(H)}, thereby generalizing the Rödl-Ruciński random Ramsey theorem. The argument invokes the classical Burr-Erdős-Spencer result and the Rödl-Ruciński theorem as black boxes; below the threshold the claim is immediate, while above the threshold the random graph contains polynomially many monochromatic copies of H and a greedy extraction yields k vertex-disjoint copies with high probability.

Significance. If the result holds, it cleanly extends random Ramsey theory to the multiple-copy setting of Burr-Erdős-Spencer while preserving the same density threshold, since m_2(k·H) = m_2(H). The approach is short and modular, relying on existing theorems plus a standard greedy argument; this structure makes the generalization transparent and suggests similar extensions may be possible for other Ramsey-type statements in sparse random graphs.

minor comments (2)
  1. [Introduction] The main theorem statement should be displayed explicitly (e.g., as Theorem 1) rather than left implicit in the abstract and proof sketch, to aid readability.
  2. Recall or cite the precise definition of the 2-density m_2(H) when first used, for readers who may not have the Rödl-Ruciński paper at hand.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and supportive report, which accurately summarizes the main result and its relation to the classical Burr-Erdős-Spencer theorem and the Rödl-Ruciński random Ramsey theorem. We are pleased that the referee finds the modular approach transparent and recommends acceptance.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes a random analogue of the Burr-Erdős-Spencer theorem in G(n,p) by treating the classical Burr-Erdős-Spencer result and the Rödl-Ruciński random Ramsey theorem as independent external black boxes. The below-threshold direction follows directly from the observation that any 2-edge-coloring avoiding monochromatic H also avoids monochromatic k·H. The above-threshold direction proceeds by noting that G(n,p) contains polynomially many monochromatic copies of H and applying a greedy extraction of k vertex-disjoint copies, which succeeds with high probability for fixed k. Because m_2(k·H) equals m_2(H), the threshold remains unchanged and no step reduces by construction to a fitted parameter, self-citation, or definitional equivalence. The derivation is self-contained against these external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the classical Burr-Erdős-Spencer theorem (domain assumption) and the Rödl-Ruciński random Ramsey theorem (domain assumption). No free parameters or new entities are introduced in the abstract.

axioms (2)
  • domain assumption Burr-Erdős-Spencer theorem holds for any fixed H without isolated vertices and sufficiently many disjoint copies.
    The paper states it determines the 2-colour Ramsey number for such collections.
  • domain assumption Rödl-Ruciński random Ramsey theorem applies to single copies of H in G(n,p).
    The new result is presented as a generalization of this theorem.

pith-pipeline@v0.9.0 · 5605 in / 1086 out tokens · 44113 ms · 2026-05-22T04:30:57.402490+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

30 extracted references · 30 canonical work pages · 1 internal anchor

  1. [1]

    Ramsey properties for tilings in random graphs

    L. Arag˜ ao, X. Cheng, R. Filipe, R. Miyazaki, D. Peng and Z. Yan, Ramsey properties for tiling in random graphs, arXiv:2605.21471

    work page internal anchor Pith review Pith/arXiv arXiv

  2. [2]

    Ara´ ujo, M

    P. Ara´ ujo, M. Pavez-Sign´ e and N. Sanhueza-Matamala, Ramsey numbers of cycles in random graphs,Random Structures & Algorithms66(2025), e21253

    work page 2025

  3. [3]

    Balister, B

    P. Balister, B. Bollob´ as, M. Campos, S. Griffiths, E. Hurley, R. Morris, J. Sahasrabudhe and M. Tiba, Upper bounds for multicolour Ramsey numbers, arXiv:2410.17197

    work page arXiv

  4. [4]

    Balogh, A

    J. Balogh, A. Freschi and A. Treglown, Ramsey-type problems for tilings in dense graphs,Euro. J. Combin.131 (2026), 104228

    work page 2026

  5. [5]

    Balogh, R

    J. Balogh, R. Morris and W. Samotij, Independent sets in hypergraphs,J. Amer. Math. Soc.28(2015), 669–709

    work page 2015

  6. [6]

    Buci´ c and B

    M. Buci´ c and B. Sudakov, Tight Ramsey bounds for multiple copies of a graph,Adv. Combin.(2023), 22pp

    work page 2023

  7. [7]

    Burr, On the Ramsey numbersr(G, nH) andr(nG, nH) whennis large,Discr

    S.A. Burr, On the Ramsey numbersr(G, nH) andr(nG, nH) whennis large,Discr. Math.65(1987), 215–229

    work page 1987

  8. [8]

    S.A. Burr, P. Erd˝ os, and J.H. Spencer, Ramsey theorems for multiple copies of graphs,Trans. Amer. Math. Soc. 209(1975), 87–99

    work page 1975

  9. [9]

    Campos, S

    M. Campos, S. Griffiths, R. Morris and J. Sahasrabudhe, An exponential improvement for diagonal Ramsey, Ann. Math., to appear

    work page

  10. [10]

    Cockayne and P.J

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

    work page 1975

  11. [11]

    Conlon, A new upper bound for diagonal Ramsey numbers,Ann

    D. Conlon, A new upper bound for diagonal Ramsey numbers,Ann. Math., 170(2009), 941–960

    work page 2009

  12. [12]

    Conlon, W.T

    D. Conlon, W.T. Gowers, W. Samotij and M. Schacht, On the K LR conjecture in random graphs,Israel J. Math. 203(2014), 535–580

    work page 2014

  13. [13]

    Dudek and P

    A. Dudek and P. Pra lat, An alternative proof of the linearity of the size-Ramsey number of paths,Combin. Probab. Comput.24(2015), 551–555

    work page 2015

  14. [14]

    Erd˝ os, Some unsolved problems in graph theory and combinatorial analysis, inCombinatorial Mathematics and Its Applications (Proc

    P. Erd˝ os, Some unsolved problems in graph theory and combinatorial analysis, inCombinatorial Mathematics and Its Applications (Proc. Conf. Oxford 1969), Academic Press, London, 1971, pp. 97–109

    work page 1969

  15. [15]

    Erd˝ os, Some remarks on the theory of graphs,Bull

    P. Erd˝ os, Some remarks on the theory of graphs,Bull. Amer. Math. Soc.,53(1947), 292–294

    work page 1947

  16. [16]

    Erd˝ os and G

    P. Erd˝ os and G. Szekeres, A combinatorial problem in geometry,Compos. Math.,2(1935), 463–470

    work page 1935

  17. [17]

    Gerencs´ er and A

    L. Gerencs´ er and A. Gy´ arf´ as, On Ramsey-type problems,Ann. Univ. Sci. Budapest. E¨ otv¨ os Sect. Math10(1967), 167–170

    work page 1967

  18. [18]

    Gishboliner, M

    L. Gishboliner, M. Krivelevich and P. Michaeli, Color-biased Hamilton cycles in random graphs,Random Struc- tures & Algorithms,60(2022), 289–307

    work page 2022

  19. [19]

    Gupta, N

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

    work page arXiv

  20. [20]

    Kohayakawa, Szemer´ edi’s Regularity Lemma for sparse graphs, inFoundations of computational mathematics: Rio da Janeiro, 1997, Springer, pp

    Y. Kohayakawa, Szemer´ edi’s Regularity Lemma for sparse graphs, inFoundations of computational mathematics: Rio da Janeiro, 1997, Springer, pp. 216–230

    work page 1997

  21. [21]

    Krivelevich, G

    M. Krivelevich, G. Kronenberg, A. Mond, Tur´ an-type problems for long cycles in random and pseudo-random graphs,J. London Math. Soc.107(2023), 1519–1551

    work page 2023

  22. [22]

    Letzter, Path Ramsey number for random graphs,Combin

    S. Letzter, Path Ramsey number for random graphs,Combin. Probab. Comput.25(2016), 612–622

    work page 2016

  23. [23]

    Ramsey, On a problem of formal logic,Proc

    F.P. Ramsey, On a problem of formal logic,Proc. Lond. Math. Soc.30(1) (1930), 264–286

    work page 1930

  24. [24]

    R¨ odl and A

    V. R¨ odl and A. Ruci´ nski, Lower bounds on probability thresholds for Ramsey properties, inCombinatorics, Paul Erd˝ os is Eighty, Vol. 1, 317–346, Bolyai Soc. Math. Studies, J´ anos Bolyai Math. Soc., Budapest, 1993

    work page 1993

  25. [25]

    R¨ odl and A

    V. R¨ odl and A. Ruci´ nski, Random graphs with monochromatic triangles in every edge coloring,Random Struc- tures & Algorithms5(2)(1994), 253–270

    work page 1994

  26. [26]

    R¨ odl and A

    V. R¨ odl and A. Ruci´ nski, Threshold functions for Ramsey properties,J. Amer. Math. Soc.8(1995), 917–942

    work page 1995

  27. [27]

    Sah, Diagonal Ramsey via effective quasirandomness,Duke Math

    A. Sah, Diagonal Ramsey via effective quasirandomness,Duke Math. J.,172(2023), 545–567

    work page 2023

  28. [28]

    Saxton and A

    D. Saxton and A. Thomason, Hypergraph containers,Invent. Math.201(2015), 925–992

    work page 2015

  29. [29]

    Sulser and M

    A. Sulser and M. Truji´ c, Ramsey numbers for multiple copies of sparse graphs,J. Graph Theory,106(2024), 843–870

    work page 2024

  30. [30]

    Thomason, An upper bound for some Ramsey numbers,J

    A. Thomason, An upper bound for some Ramsey numbers,J. Graph Theory,12(1988), 509–517. 8

    work page 1988