pith. sign in

arxiv: 2510.03084 · v2 · submitted 2025-10-03 · 🧮 math.CO · math.NT

A sparse canonical van der Waerden theorem

Jos\'e D. Alvarado , Yoshiharu Kohayakawa , Patrick Morris , Guilherme O. Mota , Miquel Ortega This is my paper

Pith reviewed 2026-05-18 10:04 UTC · model grok-4.3

classification 🧮 math.CO math.NT
keywords canonical van der Waerdenrandom subsetsarithmetic progressionsRamsey theorysparse setshypergraph girthbinomial random sets
0
0 comments X

The pith

The binomial random subset [n]_p almost surely inherits the canonical van der Waerden property above a specific density threshold.

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

The canonical van der Waerden theorem guarantees that any coloring of the integers from 1 to n contains either a monochromatic or a rainbow arithmetic progression of fixed length k, once n is large enough. This paper identifies the precise probability threshold p at which the random subset obtained by including each number independently with probability p will almost surely satisfy the same guarantee. A reader should care because the result yields explicit sparse sets that retain strong Ramsey-type behavior while controlling the structure of their arithmetic progressions.

Core claim

The canonical van der Waerden theorem asserts that, for sufficiently large n, every colouring of [n] contains either a monochromatic or a rainbow arithmetic progression of length k. We determine the threshold at which the binomial random subset [n]_p almost surely inherits this canonical Ramsey type property.

What carries the argument

The critical probability threshold for the binomial random subset [n]_p together with probabilistic deletion and embedding arguments that transfer the dense canonical property to the sparse regime.

If this is right

  • There exist subsets A of [n] in which the k-term arithmetic progressions form a k-uniform hypergraph of arbitrarily high girth.
  • Any coloring of such an A still produces either a monochromatic or a rainbow k-AP.
  • The canonical Ramsey property survives the passage to the sparse random model at the identified density.

Where Pith is reading between the lines

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

  • Similar thresholds may exist for other canonical Ramsey statements such as canonical Schur or Rado theorems in random sets.
  • The high-girth constructions could be used to study extremal problems that combine additive structure with forbidden subconfigurations.
  • One could test whether the same threshold governs the property in non-binomial models of sparse sets.

Load-bearing premise

The dense canonical van der Waerden theorem transfers to the sparse random setting via standard probabilistic deletion or embedding arguments without additional structural obstructions at the critical density.

What would settle it

A coloring of [n]_p with neither a monochromatic nor a rainbow k-AP that occurs with positive probability below the claimed threshold would falsify the threshold determination.

read the original abstract

The canonical van der Waerden theorem asserts that, for sufficiently large $n$, every colouring of $[n]$ contains either a monochromatic or a rainbow arithmetic progression of length $k$ ($k$-AP, for short). In this paper, we determine the threshold at which the binomial random subset $[n]_p$ almost surely inherits this canonical Ramsey type property. As an application, we show the existence of sets $A\subseteq [n]$ such that the $k$-APs in $A$ define a $k$-uniform hypergraph of arbitrarily high girth and yet any colouring of $A$ induces a monochromatic or rainbow $k$-AP.

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

2 major / 2 minor

Summary. The paper determines the threshold probability p such that the binomial random subset [n]_p almost surely satisfies the canonical van der Waerden property: every coloring of its elements contains either a monochromatic or a rainbow k-term arithmetic progression. The proof transfers the known dense canonical van der Waerden theorem to the sparse random setting via probabilistic deletion methods. As an application, the authors construct subsets A ⊆ [n] in which the k-APs form a k-uniform hypergraph of arbitrarily high girth, yet every coloring of A still induces a monochromatic or rainbow k-AP.

Significance. If the threshold result holds, it gives a precise sparse analogue of a canonical Ramsey theorem for arithmetic progressions, clarifying the density at which random sets inherit strong Ramsey-type guarantees. The high-girth application separates structural sparseness (girth) from the forced existence of canonical configurations, which may be useful for extremal hypergraph problems and random combinatorial constructions. The manuscript employs standard probabilistic tools (deletion, first- and second-moment methods) to achieve the transfer.

major comments (2)
  1. [§4] §4, proof of the main threshold (Theorem 1.1): the probabilistic deletion step removes potential obstructing substructures before invoking the dense canonical vdW theorem, but the argument does not explicitly bound the variance or dependencies among overlapping k-APs when their expected count is O(1) or polylog at the critical p. This leaves open the possibility that local fluctuations permit a residual coloring with neither monochromatic nor rainbow k-APs after deletion.
  2. [Application section (Theorem 1.2)] Application section (Theorem 1.2): the high-girth construction is obtained by further random deletions on a set above the threshold, yet the proof does not verify that these additional deletions preserve the almost-sure canonical property or that the resulting hypergraph still forces the desired configurations in every coloring.
minor comments (2)
  1. [Introduction] The introduction could state the explicit form of the threshold p more prominently (e.g., the leading constant or the precise exponent) rather than deferring it entirely to the statement of Theorem 1.1.
  2. Notation for the random subset [n]_p and the coloring is standard but the paper occasionally switches between 2-colorings and r-colorings without explicit remark; a uniform statement would improve clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and insightful comments on our paper. We address the major comments point by point below, providing clarifications and indicating where revisions will be made to strengthen the manuscript.

read point-by-point responses

  1. Referee: [§4] §4, proof of the main threshold (Theorem 1.1): the probabilistic deletion step removes potential obstructing substructures before invoking the dense canonical vdW theorem, but the argument does not explicitly bound the variance or dependencies among overlapping k-APs when their expected count is O(1) or polylog at the critical p. This leaves open the possibility that local fluctuations permit a residual coloring with neither monochromatic nor rainbow k-APs after deletion.

    Authors: We thank the referee for highlighting this aspect of the proof. In Section 4, the probabilistic deletion is used to remove a negligible number of elements that could participate in obstructing configurations. While the manuscript relies on standard concentration inequalities and the transfer from the dense case, we agree that an explicit bound on the variance of the number of overlapping k-APs at the threshold would enhance clarity. We will add a detailed calculation in the revised version showing that the dependency graph has bounded degree relative to the expectation, ensuring that the probability of any residual bad coloring is exponentially small. This addresses the concern about local fluctuations. revision: partial

  2. Referee: [Application section (Theorem 1.2)] Application section (Theorem 1.2): the high-girth construction is obtained by further random deletions on a set above the threshold, yet the proof does not verify that these additional deletions preserve the almost-sure canonical property or that the resulting hypergraph still forces the desired configurations in every coloring.

    Authors: For the application in Theorem 1.2, the high-girth set is constructed by starting with a random subset well above the threshold probability and then performing additional deletions to eliminate short cycles in the hypergraph of k-APs. The current proof sketch assumes that the canonical property is robust under small perturbations, but we acknowledge that this robustness is not explicitly verified. In the revision, we will include an argument showing that if a set satisfies the property with high probability at p = ω(p_threshold), then after deleting o(n) elements randomly, the property is preserved with high probability, as the number of potential colorings or bad configurations remains controlled. This will confirm that the resulting hypergraph forces monochromatic or rainbow k-APs in every coloring. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation transfers external dense theorem via standard probabilistic methods

full rationale

The paper determines the threshold at which [n]_p a.s. inherits the canonical van der Waerden property by applying the known dense theorem through probabilistic deletion or embedding arguments. No load-bearing step reduces by the paper's own equations or self-citation to a fitted input or definitional loop; the dense result serves as an independent external benchmark, and the sparse threshold follows from standard random hypergraph techniques without renaming or smuggling ansatzes. The application to high-girth sets is a direct consequence rather than a self-referential construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the dense canonical van der Waerden theorem plus standard probabilistic tools for random subsets; no free parameters or invented entities are visible in the abstract.

axioms (1)
  • domain assumption The canonical van der Waerden theorem holds for the dense interval [n].
    Invoked as the base property that the random subset inherits above the threshold.

pith-pipeline@v0.9.0 · 5646 in / 1144 out tokens · 46805 ms · 2026-05-18T10:04:13.113082+00:00 · methodology

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

29 extracted references · 29 canonical work pages

  1. [1]

    MR 3524748

    N.AlonandJ.H.Spencer,The probabilistic method, fourthed., WileySeriesinDiscreteMathematicsandOptimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. MR 3524748

    work page 2016

  2. [2]

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

    work page 2023

  3. [3]

    Available as arXiv:2411.14566

    ,A canonical Ramsey theorem for even cycles in random graphs, 2024. Available as arXiv:2411.14566

    work page arXiv 2024

  4. [4]

    Balogh, R

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

    work page 2015

  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(2025), no. 1, Paper No. e70013, 34. MR 4840711

    work page 2025

  6. [6]

    Conlon and W

    D. Conlon and W. T. Gowers,Combinatorial theorems in sparse random sets, Ann. of Math. (2)184(2016), no. 2, 367–454. MR 3548529

    work page 2016

  7. [7]

    Erdős and R

    P. Erdős and R. L. Graham,Old and new problems and results in combinatorial number theory, Monographies de L’Enseignement Mathématique [Monographs of L’Enseignement Mathématique], vol. 28, Université de Genève, L’Enseignement Mathématique, Geneva, 1980. MR 592420

    work page 1980

  8. [8]

    Erdős,Problems and results in combinatorial number theory, Journées Arithmétiques de Bordeaux (Conf., Univ

    P. Erdős,Problems and results in combinatorial number theory, Journées Arithmétiques de Bordeaux (Conf., Univ. Bordeaux, Bordeaux, 1974), Astérisque, No. 24-25, Soc. Math. France, Paris, 1975, pp. 295–310. MR 374075

    work page 1974

  9. [9]

    J. Fox, Y. Wigderson, and Y. Zhao,A short proof of the canonical polynomial van der Waerden theorem, C. R. Math. Acad. Sci. Paris358(2020), no. 8, 957–959. MR 4183180

    work page 2020

  10. [10]

    Frankl and V

    P. Frankl and V. Rödl,Large triangle-free subgraphs in graphs withoutK4, Graphs Combin.2(1986), no. 2, 135–144. MR 932121

    work page 1986

  11. [11]

    Friedgut, E

    E. Friedgut, E. Kuperwasser, W. Samotij, and M. Schacht,Sharp thresholds for Ramsey properties, 2022. Available as arXiv:2207.13982

    work page arXiv 2022

  12. [12]

    Girão,A canonical polynomial van der Waerden’s theorem, 2020

    A. Girão,A canonical polynomial van der Waerden’s theorem, 2020. Available as arXiv:2004.07766

    work page arXiv 2020

  13. [13]

    Kamčev and M

    N. Kamčev and M. Schacht,Canonical colourings in random graphs, J. Lond. Math. Soc. (2)112(2025), no. 2, Paper No. e70239, 29. MR 4938284

    work page 2025

  14. [14]

    Lefmann,A canonical version for partition regular systems of linear equations, J

    H. Lefmann,A canonical version for partition regular systems of linear equations, J. Combin. Theory Ser. A41(1986), no. 1, 95–104. MR 826940

    work page 1986

  15. [15]

    X. Li, H. Broersma, and L. Wang,Integer colorings with no rainbow 3-term arithmetic progression, Electron. J. Combin.29(2022), no. 2, Paper No. 2.28, 15. MR 4417188

    work page 2022

  16. [16]

    H. Lin, G. Wang, and W. Zhou,Integer colorings with no rainbowk-term arithmetic progression, European J. Combin. 104(2022), Paper No. 103547, 12. MR 4414806

    work page 2022

  17. [17]

    Łuczak, A

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

    work page 1992

  18. [18]

    Mousset, R

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

    work page 2020

  19. [19]

    Nenadov and A

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

    work page 2016

  20. [20]

    Nešetřil and V

    J. Nešetřil and V. Rödl,Van der Waerden theorem for sequences of integers not containing an arithmetic progression ofkterms, Comment. Math. Univ. Carolinae17(1976), no. 4, 675–681. MR 441906

    work page 1976

  21. [21]

    5, Springer, Berlin, 1990, pp

    ,Partite construction and Ramsey space systems, Mathematics of Ramsey theory, Algorithms Combin., vol. 5, Springer, Berlin, 1990, pp. 98–112. MR 1083596

    work page 1990

  22. [22]

    H. J. Prömel and B. L. Rothschild,A canonical restricted version of van der Waerden’s theorem, Combinatorica7 (1987), no. 1, 115–119. MR 905158

    work page 1987

  23. [23]

    Rödl,On Ramsey families of sets, Graphs Combin.6(1990), no

    V. Rödl,On Ramsey families of sets, Graphs Combin.6(1990), no. 2, 187–195. MR 1073689

    work page 1990

  24. [24]

    Rödl and A

    V. Rödl and A. Ruciński,Threshold functions for Ramsey properties, J. Amer. Math. Soc.8(1995), no. 4, 917–942. MR 1276825

    work page 1995

  25. [25]

    Saxton and A

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

    work page 2015

  26. [26]

    Schacht,Extremal results for random discrete structures, Ann

    M. Schacht,Extremal results for random discrete structures, Ann. of Math. (2)184(2016), no. 2, 333–365. MR 3548528

    work page 2016

  27. [27]

    Spencer,Restricted Ramsey configurations, J

    J. Spencer,Restricted Ramsey configurations, J. Combinatorial Theory Ser. A19(1975), no. 3, 278–286. MR 382058

    work page 1975

  28. [28]

    B. L. van der Waerden,Beweis einer Baudetschen Vermutung, Nieuw Arch. Wiskd., II. Ser.15(1927), 212–216 (German)

    work page 1927

  29. [29]

    Varnavides,On certain sets of positive density, J

    P. Varnavides,On certain sets of positive density, J. London Math. Soc.34(1959), 358–360. MR 106865 11 (J.D. Alvarado)Faculty of Mathematics and Physics, University of Ljubljana, Slovenia Email address:jose.alvarado@fmf.uni-lj.si (Y. Kohayakawa and G.O. Mota)Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–090 São...

    work page 1959