A sparse canonical van der Waerden theorem

2025/10/03 by Alvarado, José D., Kohayakawa, Yoshiharu, Morris, Patrick +2
#Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2510.03084

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⊆ [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.

Citations

• A canonical Ramsey theorem for even cycles in random graphs
• Resolution of the Kohayakawa-Kreuter conjecture
• A canonical Ramsey theorem with list constraints in random (hyper-)graphs
• Canonical colourings in random graphs
• A short proof of the canonical polynomial van der Waerden theorem
• A Canonical Polynomial Van der Waerden's Theorem
• Towards the Kohayakawa--Kreuter conjecture on asymmetric Ramsey properties
• Independent sets in hypergraphs
• Combinatorial theorems in sparse random sets

Related

• A canonical Ramsey theorem with list constraints in random (hyper-)graphs
• A canonical Ramsey theorem for even cycles in random graphs
• Canonical colourings in random graphs
• Monochromatic products in random integer sets
• Sharp thresholds for Ramsey properties