Ramsey functions for quasi-progressions (Q1393027)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Ramsey functions for quasi-progressions |
scientific article |
Statements
Ramsey functions for quasi-progressions (English)
0 references
2 December 1998
0 references
The Ramsey function corresponding to finite-length quasi-progressions of a fixed diameter is discussed. Quasi-progressions were introduced by \textit{T. C. Brown, P. Erdős} and \textit{A. R. Freedman} [J. Comb. Theory, Ser. A 53, No. 1, 81-95 (1990; Zbl 0699.10069)] who defined a quasi-progression of diameter \(n\) as a finite sequence of integers \((x_1,\ldots,x_k)\) for which a positive integer \(L\) exists such that \(L \leq x_i - x_{i-1} \leq L+n\) for all \(i=2,\ldots,k\). Then the Ramsey function \(Q_n(k)\) is defined as the least positive integer such that every 2-coloring of \((1,\ldots,Q_n(k))\) contains a monochromatic \(k\)-term quasi-progression of diameter \(n\). Lower bounds for the Ramsey function \(Q_n(k)\) are derived for \(1 \leq n < k\) whereas upper bounds are given only for \(n \geq \lceil \frac{2k}{3} \rceil\). Furthermore an exact formula is developed for \(Q_{k-1}(k)\) and \(Q_{k-2}(k)\). The paper is concluded with a table of computer-generated values of \(Q_n(k)\) for small values of \(n\) and \(k\) and with several conjectures on the behaviour of \(Q_n(k)\) for greater values of \(n\) and \(k\).
0 references
Ramsey theory
0 references
arithmetic progressions
0 references
quasi-progressions
0 references