Progressions in Sequences of Nearly Consecutive Integers

Noga Alon; Ayal Zaks

doi:10.1006/jcta.1998.2886

Progressions in Sequences of Nearly Consecutive Integers

Noga Alon, Ayal Zaks

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

Fork 2 andr≥2, letG(k,r) denote the smallest positive integergsuch that every increasing sequence ofgintegers {a₁,a₂,...,a_g} with gapsa_j+1-a_j∈{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)(s^k-2/ek)(1+o(1)) for alls≥2. Here we improve these bounds and prove thatG(k,2)2^k-O(k)and, more generally, that for every fixedr≥2 there exists a constantc_r0 such thatG(k,r)r^k-c_r^k for allk.

Original language	English (US)
Pages (from-to)	99-109
Number of pages	11
Journal	Journal of Combinatorial Theory. Series A
Volume	84
Issue number	1
DOIs	https://doi.org/10.1006/jcta.1998.2886
State	Published - Oct 1998
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jcta.1998.2886

Cite this

@article{789fa18b6b7b48cfb04935091973fe39,

title = "Progressions in Sequences of Nearly Consecutive Integers",

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.",

author = "Noga Alon and Ayal Zaks",

note = "Funding Information: * Research supported in part by a USA Israeli BSF grant and by a grant from the Israel Science Foundation.",

year = "1998",

month = oct,

doi = "10.1006/jcta.1998.2886",

language = "English (US)",

volume = "84",

pages = "99--109",

journal = "Journal of Combinatorial Theory. Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Progressions in Sequences of Nearly Consecutive Integers

AU - Alon, Noga

AU - Zaks, Ayal

N1 - Funding Information: * Research supported in part by a USA Israeli BSF grant and by a grant from the Israel Science Foundation.

PY - 1998/10

Y1 - 1998/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0040679790&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0040679790&partnerID=8YFLogxK

U2 - 10.1006/jcta.1998.2886

DO - 10.1006/jcta.1998.2886

M3 - Article

AN - SCOPUS:0040679790

SN - 0097-3165

VL - 84

SP - 99

EP - 109

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

IS - 1

ER -

Progressions in Sequences of Nearly Consecutive Integers

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this