Arithmetic progressions in sequences with bounded gaps (Q1352863)

A celebrated theorem of van der Waerden states that for every pair of positive integers \(k\) and \(r\) there exists \(W(k,r)\) such that for the least integer \(w\geq W(k,r)\), any partition of \([1,w]\) into \(r\) parts has a part that contains a \(k\)-term arithmetic progression. Let \(G(k,r)\) denote the smallest positive integer \(g\) such that if \(A= \{1= a_1,a_2,\dots,a_g\}\) is a strictly increasing sequence of integers with \(a_{j+1}- a_j\leq r\), \(1\leq j\leq r-1\), then \(A\) contains a \(k\)-term arithmetic progression. An interesting (and easy) consequence of the theorem of van der Waerden implies the existence of \(G(k,r)\). M. Nathanson gave a quantitative connection between \(W(k,r)\) and \(G(k,r)\). He proved \(G(k,r)\leq W(k,r)\leq G((k-1)r+1,2r-1)\). In the present paper, the authors prove: For every \(k\geq 3\), \[ G(k,2)> \sqrt{(k-1)/2}\cdot (4/3)^{(k-1)/2}. \] Furthermore, they prove that for every \(k\geq 3\), \(r\geq 2\), \[ G(k,2r-1)>(1+ o(1)){r^{k-2}\over ek}. \] Both proofs are probabilistic; in the second one the regular form of the Lovász local lemma is used. Nathanson's inequalities show that it will require hard work to find a reasonable upper bound for \(G(k,3)\).