Let G(k, r) denote the smallest positive integer g such that if 1 = a(
1), a(2),..., a(g) is a strictly increasing sequence of integers with
bounded gaps a(j+1)-a(j) less than or equal to r, 1 less than or equal
to j less than or equal to g-1, then {a(1), a(2),..., a(g)} contains
a k-term arithmetic progression. It is shown that G(k, 2)>root(k-1)/2(
4/3)((k-1)/2), G(k, 3)>(2(k-2)/ek)(1+o(1)),G(k, 2r-1)>(r(k-2)/ek)(1+o(
1)), r greater than or equal to 2. (C) 1997 Academic Press.