Progressions in Sequences of Nearly Consecutive Integers

AbstractFork>2 andr⩾2, letG(k,r) denote the smallest positive integergsuch that every increasing sequence ofgintegers {a1,a2,…,ag} with gapsaj+1−aj∈{1,…,emsp14;r}, 1⩽j⩽g−1 contains ak-term arithmetic progression. Brown and Hare proved thatG(k,2)>(k−1)/2(34)(k−1)/2and thatG(k,2s−1)>(sk−2/ek)(1+o(1)) for alls⩾2. Here we improve these bounds and prove thatG(k,2)>2k−O(k)and, more generally, that for every fixedr⩾2 there exists a constantcr>0 such thatG(k,r)>rk−crkfor allk