pith. sign in

arxiv: 2605.21471 · v1 · pith:4EARCA6Lnew · submitted 2026-05-20 · 🧮 math.CO

Ramsey properties for tilings in random graphs

Lucas Arag\~ao , Xinbu Cheng , Rafael Filipe , Rafael Miyazaki , Danni Peng , Zhifei Yan This is my paper

Pith reviewed 2026-05-21 03:04 UTC · model grok-4.3

classification 🧮 math.CO
keywords Ramsey theoryrandom graphsthreshold functionsgraph tilingsmonochromatic copiesedge colorings2-density
0
0 comments X

The pith

The threshold probability for a random graph G(n,p) to force a monochromatic tiling of about n/(2k-α) disjoint copies of H in any 2-edge-coloring is n to the power of minus one over the maximum of the 2-density of H and one.

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

This paper establishes that the random graph property G(n,p) arrow (mH)_2 holds with high probability exactly above the probability threshold n to the minus one over max of m2(H) and 1, where m is linear in n and chosen according to the independence number alpha of H. A reader would care because this pins down the same exponent that Rödl and Ruciński found for single copies of H, now for a linear number of vertex-disjoint copies, and it directly extends the deterministic tiling result of Burr, Erdős and Spencer into the random setting. The work shows that the 2-density continues to dictate the threshold even when the target is a large packing rather than one copy.

Core claim

We prove that n^{-1/max{m_2(H),1}} is the threshold for the property G(n,p) → (mH)_2, where m∼n/(2k−α). This threshold matches the one found by Rödl and Ruciński for most graphs H, extending their result in the case r=2.

What carries the argument

The 2-density m2(H), which sets the exponent in the threshold function for the monochromatic Ramsey property in the same manner as the single-copy case.

If this is right

  • For any H with m2(H) greater than 1, the threshold exponent stays exactly 1/m2(H) even when the target consists of linearly many disjoint copies.
  • The deterministic bound m ∼ n/(2k−α) from Burr, Erdős and Spencer carries over unchanged to the random-graph threshold statement.
  • The result holds for all but a few exceptional graphs H, matching the scope of the Rödl-Ruciński theorem for r=2.

Where Pith is reading between the lines

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

  • The same exponent may govern the threshold when the number of colors r exceeds 2, provided the deterministic tiling number is adjusted accordingly.
  • For specific families such as cycles or complete graphs, direct computation of the threshold could confirm whether the max with 1 is ever triggered in the tiling regime.
  • The absence of lower-order corrections suggests that sparse random graphs already contain the necessary expansion properties for large monochromatic packings once the 2-density threshold is crossed.

Load-bearing premise

The 2-density of H governs the threshold for the large tiling exactly as it does for one copy, with the linear size m introducing no extra logarithmic corrections to the exponent.

What would settle it

Observe a graph H and a probability p slightly smaller than n^{-1/max{m_2(H),1}} such that with positive probability a random graph G(n,p) admits a 2-edge-coloring with no monochromatic mH tiling, where m is asymptotically n/(2k-α).

read the original abstract

Let $mH$ be the graph formed by $m$ vertex-disjoint copies of a graph $H$. Let $G \to (H)_r$ denote that, in any $r$-colouring of the edges of $G$, there exists a monochromatic copy of $H$. In 1975, Burr, Erd\H{o}s, and Spencer showed that if $H$ is a graph on $k$ vertices whose independence number is $\alpha$, then $K_n \to (mH)_2$, where $m\sim n/(2k-\alpha)$, and that the $1/(2k-\alpha)$ factor is best possible. In the 1990s, R\"{o}dl and Ruci\'{n}ski proved that, for all but a few graphs~$H$, the threshold for the property $\mathbb{G}(n,p) \to (H)_r$ is $n^{-1/m_2(H)}$. In this paper, generalizing the result of Burr, Erd\H{o}s, and Spencer, we prove that $n^{-1/\max\{m_2(H),1\}}$ is the threshold for the property $\mathbb{G}(n,p) \to (mH)_2$, where $m\sim n/(2k-\alpha)$. This threshold matches the one found by R\"{o}dl and Ruci\'nski for most graphs $H$, extending their result in the case $r=2$.

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 / 3 minor

Summary. The manuscript proves that for a fixed graph H on k vertices with independence number α, the threshold probability p such that G(n,p) → (mH)_2 (every 2-edge-coloring admits a monochromatic packing of m vertex-disjoint copies of H) with m ∼ n/(2k−α) is exactly p = n^{-1/max{m_2(H),1}}. This extends the deterministic Burr-Erdős-Spencer tiling bound to the random-graph model and matches the Rödl-Ruciński threshold for single copies of H (for most H) in the r=2 case.

Significance. If the result holds, it is a clean and useful extension of classical Ramsey theory: it shows that the 2-density parameter continues to control the threshold even when one seeks a linear-sized monochromatic packing rather than a single copy, without introducing logarithmic corrections to the exponent. The proof combines the deterministic m-bound of Burr-Erdős-Spencer with the Rödl-Ruciński 1-statement and a greedy embedding that exploits the minimum-degree properties of the random graph above the threshold; this combination is technically economical and confirms the robustness of the m_2(H) regime for tiling problems.

minor comments (3)
  1. §1 (Introduction): the statement of the main result would be clearer if it were isolated as a numbered theorem immediately after the abstract, rather than being described only in prose.
  2. §4 (Proof of the 1-statement): the argument that the greedy embedding introduces no extra logarithmic factor in the exponent is central but is only sketched; a short paragraph making the degree calculations explicit would improve readability.
  3. The paper correctly excludes the exceptional graphs H for which the Rödl-Ruciński threshold differs, but a one-sentence reminder of which graphs are excluded (and why) at the beginning of the main theorem would help readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our manuscript, which correctly identifies the main result as a natural extension of the Burr-Erdős-Spencer tiling theorem to the random-graph setting while matching the Rödl-Ruciński threshold for most graphs H. We appreciate the recommendation for minor revision.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper extends the Rödl-Ruciński threshold for single H to the multiple disjoint copies mH by invoking the deterministic Burr-Erdős-Spencer bound on m and applying a greedy embedding argument in the random graph regime above the known 1-statement threshold. m2(H) is imported from external literature as an independent quantity, the scaling m ∼ n/(2k−α) is taken directly from the 1975 deterministic result, and no parameter is fitted to the target property then renamed as a prediction. The derivation chain remains self-contained against external benchmarks with no self-definitional, fitted-input, or self-citation load-bearing reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The argument rests on standard probabilistic method tools and the definition of 2-density; no new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math The 2-density m2(H) is the standard quantity max over subgraphs of (e(F)-1)/(v(F)-2) used in random graph Ramsey theory.
    Invoked when stating the threshold exponent.
  • domain assumption The scaling m ~ n / (2k - alpha) carries over from the deterministic Burr-Erdős-Spencer theorem without modification in the random setting.
    Used to define the number of copies in the target property.

pith-pipeline@v0.9.0 · 5814 in / 1370 out tokens · 31886 ms · 2026-05-21T03:04:26.686437+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.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A random version of the Burr-Erd\H{o}s-Spencer theorem

    math.CO 2026-05 unverdicted novelty 7.0

    Establishes that the 2-color Ramsey number for sufficiently many vertex-disjoint copies of H remains asymptotically the same in the random graph G(n,p) for appropriate p.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · cited by 1 Pith paper

  1. [1]

    Alvarado, Y

    J. Alvarado, Y. Kohayakawa, P. Morris, and G. O. Mota. A canonical Ramsey theorem with list constraints in random graphs.Procedia Comput. Sci., 223:13–19, 2023

    work page 2023

  2. [2]

    J. D. Alvarado, Y. Kohayakawa, P. Morris, and G. O. Mota. A canonical Ramsey theorem for even cycles in random graphs.arXiv:2411.14566, 2024

    work page arXiv 2024

  3. [3]

    Arag˜ ao, M

    L. Arag˜ ao, M. Campos, G. Dahia, R. Filipe, and J. P. Marciano. An exponential upper bound for induced ramsey numbers.arXiv:2509.22629, 2025

    work page arXiv 2025

  4. [4]

    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.J. Amer. Math. Soc., 39(3):765–780, 2026. 19

    work page 2026

  5. [5]

    Balogh, A

    J. Balogh, A. Freschi, and A. Treglown. Ramsey-type problems for tilings in dense graphs.European J. Combin., 131:Paper No. 104228, 2026

    work page 2026

  6. [6]

    Balogh, R

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

    work page 2015

  7. [7]

    Buci´ c and B

    M. Buci´ c and B. Sudakov. Tight Ramsey bounds for multiple copies of a graph.Advances in Combinatorics, pages 1–22, 2023

    work page 2023

  8. [8]

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

    work page 1987

  9. [9]

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

    work page 1975

  10. [10]

    Campos, S

    M. Campos, S. Griffiths, R. Morris, and J. Sahasrabudhe. An exponential improvement for diagonal Ramsey. Ann. of Math. (2), 203(3):869–932, 2026

    work page 2026

  11. [11]

    Christoph, A

    M. Christoph, A. Martinsson, R. Steiner, and Y. Wigderson. Resolution of the Kohayakawa-Kreuter conjec- ture.Proc. Lond. Math. Soc. (3), 130(1):Paper No. e70013, 34, 2025

    work page 2025

  12. [12]

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

    work page 2009

  13. [13]

    Conlon, J

    D. Conlon, J. Fox, and B. Sudakov. Recent developments in graph Ramsey theory. InSurveys in combi- natorics 2015, volume 424 ofLondon Math. Soc. Lecture Note Ser., pages 49–118. Cambridge Univ. Press, Cambridge, 2015

    work page 2015

  14. [14]

    P. Erd˝ os. Some unsolved problems in graph theory and combinatorial analysis. InCombinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), pages 97–109. Academic Press, London-New York, 1971

    work page 1969

  15. [15]

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

    work page 1947

  16. [16]

    Erd˝ os and G

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

    work page 1935

  17. [17]

    Friedgut, E

    E. Friedgut, E. Kuperwasser, W. Samotij, and M. Schacht. Sharp thresholds for Ramsey properties.Forum Math. Sigma, 14:Paper No. e32, 57, 2026

    work page 2026

  18. [18]

    Gishboliner, S

    L. Gishboliner, S. Glock, P. Michaeli, and A. Sgueglia. Defect and transference versions of the Alon–Frankl–Lov´ asz theorem.Combinatorics, Probability and Computing, page 1–12, 2026

    work page 2026

  19. [19]

    Gishboliner, M

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

    work page 2022

  20. [20]

    Kohayakawa, M

    Y. Kohayakawa, M. Schacht, and R. Sp¨ ohel. Upper bounds on probability thresholds for asymmetric Ramsey properties.Random Structures&Algorithms, 44(1):1–28, July 2012

    work page 2012

  21. [21]

    K´ ovari, V

    T. K´ ovari, V. S´ os, and P. Tur´ an. On a problem of K. Zarankiewicz.Colloquium Mathematicae, 3(1):50–57, 1954

    work page 1954

  22. [22]

    Lov´ asz and M

    L. Lov´ asz and M. Simonovits. On the number of complete subgraphs of a graph. II. InStudies in pure mathematics, pages 459–495. Birkh¨ auser, Basel, 1983

    work page 1983

  23. [23]

    R. Morris. Some recent results in Ramsey theory.arXiv:2601.05221, 2026

    work page arXiv 2026

  24. [24]

    Mousset, R

    F. Mousset, R. Nenadov, and W. Samotij. Towards the Kohayakawa-Kreuter conjecture on asymmetric Ramsey properties.Combin. Probab. Comput., 29(6):943–955, 2020

    work page 2020

  25. [25]

    Nenadov and A

    R. Nenadov and A. Steger. A short proof of the random Ramsey theorem.Combin. Probab. Comput., 25(1):130–144, 2016

    work page 2016

  26. [26]

    F. P. Ramsey. On a Problem of Formal Logic.Proc. London Math. Soc. (2), 30(4):264–286, 1929

    work page 1929

  27. [27]

    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, Bolyai Soc. Math. Stud., pages 317–346. J´ anos Bolyai Math. Soc., Budapest, 1993

    work page 1993

  28. [28]

    R¨ odl and A

    V. R¨ odl and A. Ruci´ nski. Random graphs with monochromatic triangles in every edge coloring.Random Structures&Algorithms, 5(2):253–270, 1994

    work page 1994

  29. [29]

    R¨ odl and A

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

    work page 1995

  30. [30]

    R¨ odl, A

    V. R¨ odl, A. Ruci´ nski, and M. Schacht. Ramsey properties of random graphs and Folkman numbers.Discuss. Math. Graph Theory, 37(3):755–776, 2017

    work page 2017

  31. [31]

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

    work page 2023

  32. [32]

    Saxton and A

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

    work page 2015

  33. [33]

    Schacht and F

    M. Schacht and F. Schulenburg. Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs.Random Structures&Algorithms, 52(1):3–40, 2018

    work page 2018

  34. [34]

    J. Spencer. Ramsey’s theorem—a new lower bound.J. Combinatorial Theory Ser. A, 18:108–115, 1975. 20

    work page 1975

  35. [35]

    Thomason

    A. Thomason. An upper bound for some Ramsey numbers.J. Graph Theory, 12(4):509–517, 1988. Departamento de Matem´atica Aplicada, Instituto de Matem´atica, Universidade Federal do Rio de Janeiro, Rio de Janeiro, 21941-909, Brasil Email address:aragao@im.ufrj.br IMPA, Estrada Dona Castorina 110, Jardim Bot ˆanico, Rio de Janeiro, 22460-320, Brasil Email addr...

    work page 1988