Progressions in Sequences of Nearly Consecutive Integers

✍ Scribed by Noga Alon; Ayal Zaks

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 255 KB
• Volume: 84
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1998.2886

✦ Synopsis

For k>2 and r 2, let G(k, r) denote the smallest positive integer g such that every increasing sequence of g integers [a 1 , a 2 , ..., a g ] with gaps a j+1 &a j # [1, ..., r], 1 j g&1 contains a k-term arithmetic progression. Brown and Hare proved that G(k, 2)>-(k&1)Â2 ( 43 ) (k&1)Â2 and that G(k, 2s&1)>(s k&2 Âek)(1+o( 1)) for all s 2. Here we improve these bounds and prove that G(k, 2)>2 k&O (-k) and, more generally, that for every fixed r 2 there exists a constant c r >0 such that G(k, r)>r k&c r -k for all k.