Pith. sign in

REVIEW 2 minor 22 references

For any r and any tuple of graphs, a precise number of random edges added to any dense graph makes it (H1,...,Hr)_v-Ramsey with high probability.

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.3

2026-07-01 06:28 UTC pith:MI5P3XA6

load-bearing objection This paper settles the general threshold for making dense graphs (H1,...,Hr)v-Ramsey by adding random edges, for arbitrary r and arbitrary fixed Hi.

arxiv 2606.30548 v2 pith:MI5P3XA6 submitted 2026-06-29 math.CO

The threshold for the asymmetric vertex-Ramsey property in randomly perturbed graphs

Asier Calbet , Victor Falgas-Ravry , Joseph Hyde This is my paper
classification math.CO
keywords vertex-Ramsey propertyrandomly perturbed graphsthreshold functionsasymmetric Ramseydense graphsvertex coloring
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.

The paper determines the exact threshold number of random edges that must be added to any dense n-vertex graph so the resulting perturbed graph is (H1,...,Hr)_v-Ramsey with probability 1-o(1), for every r at least 2 and every choice of graphs H1 to Hr. This means that after the addition, every r-coloring of the vertices produces a copy of some Hj that is entirely color j. Earlier results covered only the case r=2 where at least one Hi is a clique; the new work removes those restrictions and settles the general problem. A reader cares because the result shows exactly how much randomness is required to force the Ramsey-type guarantee once a graph already has linear minimum degree.

Core claim

For any r ≥ 2 and any r-tuple of graphs (H1,…,Hr), we determine the number of random edges one must add to a dense graph to ensure that with probability 1-o(1) the resulting graph is (H1,…,Hr)_v-Ramsey.

What carries the argument

The threshold function for the number of random edges added to a dense graph, which forces the existence of a monochromatic Hj in color j under every vertex r-coloring.

Load-bearing premise

The initial graph has minimum degree linear in n.

What would settle it

A dense graph plus fewer than the threshold number of random edges that admits, with probability bounded away from zero, an r-coloring of the vertices with no monochromatic copy of Hj in color j for any j.

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

If this is right

  • The same threshold works uniformly for every dense starting graph.
  • The threshold is determined for arbitrary graphs Hj, not only cliques.
  • The perturbed graph satisfies the vertex-Ramsey property with probability tending to 1.
  • The result extends the r=2 clique case to all r and all tuples.

Where Pith is reading between the lines

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

  • The same perturbation technique may yield thresholds for edge-Ramsey properties.
  • The linear-degree assumption might be weakened for some choices of the Hj.
  • The result links classical random-graph Ramsey thresholds to the perturbed setting.

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

Summary. The manuscript determines the threshold number of random edges to add to any dense n-vertex graph G so that the perturbed graph becomes (H1,…,Hr)_v-Ramsey with probability 1-o(1), for arbitrary fixed graphs H1,…,Hr and any r≥2. This resolves the general asymmetric case left open by Das-Morris-Treglown (who treated r=2 with one Hi a clique) and extends the classical thresholds of Łuczak-Ruciński-Voigt and Kreuter from the pure random-graph model.

Significance. If the claimed threshold holds, the result supplies a complete characterization of the vertex-Ramsey property in the randomly perturbed model for arbitrary fixed graphs and any number of colours. The generality to non-clique graphs and r>2 is a clear advance over prior work; the paper also supplies an explicit threshold expression that reduces to known quantities when the Hi are cliques.

minor comments (2)
  1. Abstract, final paragraph: the threshold is described only qualitatively ('the number of random edges'); stating the explicit functional form (presumably max over certain Ramsey densities of the Hi) already in the abstract would improve immediate readability.
  2. The introduction cites the Das-Morris-Treglown result for cliques but does not explicitly contrast the new threshold expression with the earlier one; a short comparison paragraph would clarify the extension.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report, which accurately summarizes the contribution of the manuscript and recommends acceptance. We are pleased that the generality of the result for arbitrary fixed graphs and any number of colours is viewed as a clear advance.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper determines thresholds for the asymmetric vertex-Ramsey property in randomly perturbed dense graphs for arbitrary r≥2 and fixed graphs H1,...,Hr. It explicitly builds on independent prior results by Luczak-Ruciński-Voigt, Kreuter, and Das-Morris-Treglown (distinct authors) for the random-graph and r=2 clique cases, then extends via new arguments for the general perturbed setting. No self-citations, no fitted parameters renamed as predictions, no self-definitional reductions, and no ansatz or uniqueness claims imported from the authors' own prior work. The density assumption on the host graph is stated as an explicit part of the setting rather than derived from the result itself. The central claim therefore rests on external benchmarks and fresh embedding control rather than reducing to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only abstract available; no explicit free parameters, axioms, or invented entities are stated.

pith-pipeline@v0.9.1-grok · 5897 in / 1033 out tokens · 30133 ms · 2026-07-01T06:28:49.211689+00:00 · methodology

0 comments
read the original abstract

For $r \geq 2$ and graphs $H_1, \ldots, H_r, G$, we say that $G$ is $(H_1, \ldots, H_r)$ vertex-Ramsey, or $(H_1, \ldots, H_r)_v$-Ramsey, if whenever we colour the vertices of $G$ with colours from the set $[r]=\{1,2, \ldots, r\}$ there exists $j \in [r]$ such that some copy of $H_j$ in $G$ is monochromatic in colour $j$. Given any fixed collection of graphs $H_1, \ldots, H_r$, Luczak, Ruci\'{n}ski and Voigt and Kreuter determined in the 1990s the threshold edge probability $p$ at which the binomial random graph $G(n,p)$ becomes $(H_1, \ldots, H_r)_v$-Ramsey. More recently, Das, Morris and Treglown investigated the vertex-Ramsey property in the randomly perturbed setting. When $r=2$ they determined the number of random edges one must add to a dense graph to ensure that with probability $1-o(1)$ the resulting graph is $(H_1, H_2)_v$-Ramsey whenever one of $H_1$ or $H_2$ is a clique. They posed the problem of extending their results to all pairs of graphs $(H_1, H_2)$. In this paper we resolve a more general form of their problem and determine for any $r\geq 2$ and $r$-tuple of graphs $(H_1, \ldots, H_r)$ the number of random edges one must add to a dense graph to ensure that with probability $1-o(1)$ the resulting graph is $(H_1, \ldots, H_r)_v$-Ramsey.

Review history (2 revisions) →

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

22 extracted references · 22 canonical work pages · 2 internal anchors

  1. [1]

    Large rainbow cliques in randomly perturbed dense graphs.SIAM J

    Elad Aigner-Horev, Oran Danon, Dan Hefetz, and Shoham Letzter. Large rainbow cliques in randomly perturbed dense graphs.SIAM J. Discrete Math., 36(4):2975–2994, 2022

    work page 2022

  2. [2]

    Bohman, A

    T. Bohman, A. Frieze, and R. Martin. How many random edges make a dense graph Hamilto- nian?Random Structures Algorithms, 22(1):33–42, 2003

    work page 2003

  3. [3]

    Bollobás and A

    B. Bollobás and A. Thomason. Threshold functions.Combinatorica, 7(1):35–38, 1987

    work page 1987

  4. [4]

    Bowtell, R

    C. Bowtell, R. Hancock, and J. Hyde. Proof of the Kohayakawa–Kreuter conjecture for the majority of cases, 2025. arXiv:2307.16760

    work page arXiv 2025

  5. [5]

    Christoph, A

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

    work page 2025

  6. [6]

    S. Das, P. Morris, and A. Treglown. Vertex Ramsey properties of randomly perturbed graphs. Random Structures Algorithms, 57(4):983–1006, 2020

    work page 2020

  7. [7]

    Das and A

    S. Das and A. Treglown. Ramsey properties of randomly perturbed graphs: cliques and cycles. Combin. Probab. Comput., 29(6):830–867, 2020

    work page 2020

  8. [8]

    Erdős and M

    P. Erdős and M. Simonovits. A limit theorem in graph theory.Studia Sci. Math. Hungar., 1:51–57, 1966

    work page 1966

  9. [9]

    Erdős and A

    P. Erdős and A. H. Stone. On the structure of linear graphs.Bull. Amer. Math. Soc., 52:1087– 1091, 1946

    work page 1946

  10. [10]

    Janson, T

    S. Janson, T. Łuczak, and A. Rucinski.Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000

    work page 2000

  11. [11]

    Kohayakawa and B

    Y. Kohayakawa and B. Kreuter. Threshold functions for asymmetric Ramsey properties in- volving cycles.Random Structures Algorithms, 11(3):245–276, 1997

    work page 1997

  12. [12]

    Komlós and M

    J. Komlós and M. Simonovits. Szemerédi’s regularity lemma and its applications in graph theory. InCombinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), volume 2 ofBolyai Soc. Math. Stud., pages 295–352. János Bolyai Math. Soc., Budapest, 1996

    work page 1993

  13. [13]

    B. Kreuter. Threshold functions for asymmetric Ramsey properties with respect to vertex colorings.Random Structures Algorithms, 9(3):335–348, 1996

    work page 1996

  14. [14]

    Krivelevich, B

    M. Krivelevich, B. Sudakov, and P. Tetali. On smoothed analysis in dense graphs and formulas. Random Structures Algorithms, 29(2):180–193, 2006

    work page 2006

  15. [15]

    Kuperwasser, W

    E. Kuperwasser, W. Samotij, and Y. Wigderson. On the Kohayakawa–Kreuter conjecture. Math. Proc. Cambridge Philos. Soc., 178(3):293–320, 2025

    work page 2025

  16. [16]

    The list-Ramsey threshold for families of graphs

    Eden Kuperwasser and Wojciech Samotij. The list-Ramsey threshold for families of graphs. Combin. Probab. Comput., 33(6):829–851, 2024

    work page 2024

  17. [17]

    Łuczak, A

    T. Łuczak, A. Ruciński, and B. Voigt. Ramsey properties of random graphs.J. Combin. Theory Ser. B, 56(1):55–68, 1992

    work page 1992

  18. [18]

    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

  19. [19]

    Ramsey properties of randomly perturbed dense graphs

    E. Powierski. Ramsey properties of randomly perturbed dense graphs, 2019. arXiv:1902.02197

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  20. [20]

    Szemerédi

    E. Szemerédi. Regular partitions of graphs. InProblèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), volume 260 ofColloq. Internat. CNRS, pages 399–401. CNRS, Paris, 1978

    work page 1976

  21. [21]

    P. Turán. On an extremal problem in graph theory (in Hungarian).Math. Fiz. Lapok., 48:436– 452, 1941

    work page 1941

  22. [22]

    M. Yancey. Resolving the Kohayakawa–Kreuter conjecture for families, 2026. arXiv:2603.03086. 13

    work page internal anchor Pith review Pith/arXiv arXiv 2026