Ramsey functions for quasi-progressions

Bruce M. Landman

doi:10.1007/s003730050021

Ramsey functions for quasi-progressions

Bruce M. Landman

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

3 Scopus citations

Abstract

A quasi-progression of diameter n is a finite sequence {x₁ , . . . , x_k} for which there exists a positive integer L such that L ≤ x_i - x_i-1 ≤ L + n for i = 2, . . . , k. Let Q_n(k) be the least positive integer such that every 2-coloring of {1 , . . . , Q_n(k)} will contain a monochromatic k-term quasi-progression of diameter n. We give a lower bound for Q_k-i(k) in terms of k and i that holds for all k > i ≥ 1. Upper bounds are obtained for Q_n(k) in all cases for which n ≥ [2k/3]. In particular, we show that Q_[2k/3](k) ≤ 43/324 k³(1 + o(1)). Exact formulae are found for Q_k-1(k) and Q_k-2(k). We include a table of computer-generated values of Q_n(k), and make several conjectures.

Original language	English (US)
Pages (from-to)	131-142
Number of pages	12
Journal	Graphs and Combinatorics
Volume	14
Issue number	2
DOIs	https://doi.org/10.1007/s003730050021
State	Published - Jan 1 1998
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s003730050021

Cite this

@article{de4d73e0bec84095b62ff7985bf3a836,

title = "Ramsey functions for quasi-progressions",

abstract = "A quasi-progression of diameter n is a finite sequence {x1 , . . . , xk} for which there exists a positive integer L such that L ≤ xi - xi-1 ≤ L + n for i = 2, . . . , k. Let Qn(k) be the least positive integer such that every 2-coloring of {1 , . . . , Qn(k)} will contain a monochromatic k-term quasi-progression of diameter n. We give a lower bound for Qk-i(k) in terms of k and i that holds for all k > i ≥ 1. Upper bounds are obtained for Qn(k) in all cases for which n ≥ [2k/3]. In particular, we show that Q[2k/3](k) ≤ 43/324 k3(1 + o(1)). Exact formulae are found for Qk-1(k) and Qk-2(k). We include a table of computer-generated values of Qn(k), and make several conjectures.",

author = "Landman, {Bruce M.}",

year = "1998",

month = jan,

day = "1",

doi = "10.1007/s003730050021",

language = "English (US)",

volume = "14",

pages = "131--142",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "2",

}

TY - JOUR

T1 - Ramsey functions for quasi-progressions

AU - Landman, Bruce M.

PY - 1998/1/1

Y1 - 1998/1/1

N2 - A quasi-progression of diameter n is a finite sequence {x1 , . . . , xk} for which there exists a positive integer L such that L ≤ xi - xi-1 ≤ L + n for i = 2, . . . , k. Let Qn(k) be the least positive integer such that every 2-coloring of {1 , . . . , Qn(k)} will contain a monochromatic k-term quasi-progression of diameter n. We give a lower bound for Qk-i(k) in terms of k and i that holds for all k > i ≥ 1. Upper bounds are obtained for Qn(k) in all cases for which n ≥ [2k/3]. In particular, we show that Q[2k/3](k) ≤ 43/324 k3(1 + o(1)). Exact formulae are found for Qk-1(k) and Qk-2(k). We include a table of computer-generated values of Qn(k), and make several conjectures.

AB - A quasi-progression of diameter n is a finite sequence {x1 , . . . , xk} for which there exists a positive integer L such that L ≤ xi - xi-1 ≤ L + n for i = 2, . . . , k. Let Qn(k) be the least positive integer such that every 2-coloring of {1 , . . . , Qn(k)} will contain a monochromatic k-term quasi-progression of diameter n. We give a lower bound for Qk-i(k) in terms of k and i that holds for all k > i ≥ 1. Upper bounds are obtained for Qn(k) in all cases for which n ≥ [2k/3]. In particular, we show that Q[2k/3](k) ≤ 43/324 k3(1 + o(1)). Exact formulae are found for Qk-1(k) and Qk-2(k). We include a table of computer-generated values of Qn(k), and make several conjectures.

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

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

U2 - 10.1007/s003730050021

DO - 10.1007/s003730050021

M3 - Article

AN - SCOPUS:10044296697

SN - 0911-0119

VL - 14

SP - 131

EP - 142

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 2

ER -

Ramsey functions for quasi-progressions

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this