Progressions in Sequences of Nearly Consecutive Integers

Noga Alon, Ayal Zaks

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Fork 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 constantcr0 such thatG(k,r)rk-crk for allk.

Original languageEnglish (US)
Pages (from-to)99-109
Number of pages11
JournalJournal of Combinatorial Theory. Series A
Volume84
Issue number1
DOIs
StatePublished - Oct 1 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Progressions in Sequences of Nearly Consecutive Integers'. Together they form a unique fingerprint.

Cite this