Random Van der Waerden theorem (Q2073318): Difference between revisions

Summary: 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 \geqslant q_2 \geqslant \cdots \geqslant q_r \geqslant 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,\ldots,n\}\), there exists a monochromatic \(q_i\)-term arithmetic progression colored \(i\), for some \(i\). This extends the results of \textit{V. Rödl} and \textit{A. Ruciński} [Random Struct. Algorithms 5, No. 2, 253--270 (1994; Zbl 0790.05079)] for the symmetric case \(q_1 = q_2 = \cdots = q_r\). The proof of the 1-statement is based on the Hypergraph Container by \textit{J. Balogh} et al. [in: Proceedings of the international congress of mathematicians 2018, ICM 2018, Rio de Janeiro, Brazil, August 1--9, 2018. Volume IV. Invited lectures. Hackensack, NJ: World Scientific; Rio de Janeiro: Sociedade Brasileira de Matemática (SBM). 3059--3092 (2018; Zbl 1448.05147)] and \textit{D. Saxton} and \textit{A. Thomason} [Invent. Math. 201, No. 3, 925--992 (2015; Zbl 1320.05085)]. The proof of the 0-statement is an extension of Rödl and Ruciński's argument for the symmetric case.