Random Van der Waerden theorem

Ohad Zohar¹

¹Tel-Aviv University

The electronic journal of combinatorics, Tome 29 (2022) no. 1

Résumé

In this paper, we prove a sparse random analogue of the Van der Waerden Theorem. We show that, for all $r > 2$ and all $q_1 \geq q_2 \geq \dotsb \geq q_r \geq 3 \in \mathbb{N}$, $n^{-\frac{q_2}{q_1(q_2-1)}}$ is a threshold for the following property: For every $r$-coloring of the $p$-random subset of $\{1,\dotsc,n\}$, there exists a monochromatic $q_i$-term arithmetic progression colored $i$, for some $i$. This extends the results of Rödl and Ruciński for the symmetric case $q_1 = q_2 = \dotsb = q_r$. The proof of the 1-statement is based on the Hypergraph Container Method by Balogh, Morris and Samotij and Saxton and Thomason. The proof of the 0-statement is an extension of Rödl and Ruciński's argument for the symmetric case.

Détail

DOI : 10.37236/9744

Classification : 05C80, 05C69, 05C55, 05D10
Mots-clés : sparse random graphs, extremal graph theory, Ramsey theory