A sparse canonical van der Waerden theorem
Abstract
The canonical van der Waerden theorem asserts that, for sufficiently large n n , every colouring of [ n ] [n] contains either a monochromatic or a rainbow arithmetic progression of length k k ( k k -AP, for short). In this paper, we determine the threshold at which the binomial random subset [ n ] p [n]_p almost surely inherits this canonical Ramsey type property. As an application, we show the existence of sets A ⊆ [ n ] A\subseteq [n] such that the k k -APs in A A define a k k -uniform hypergraph of arbitrarily high girth and yet any colouring of A A induces a monochromatic or rainbow k k -AP.
Fields of Study & Subjects
Limits and Structures in Graph Theory
Computability
Logic
AI Algorithms
Advanced Topology and Set Theory
Publication details
- Journal / source
- Proceedings of the American Mathematical Society
- Volume
- 154
- Issue
- 10
- Pages
- 4191–4204
- Publication date
- 13 May 2026
- Language
- EN