Ramsey functions for quasi-progressions with large diameter

A $k$-term quasi-progression of diameter $d$ is a sequence\[x_1 \lt \cdots \lt x_k\]of positive integers for which there exists a positive integer $l$ such that $l \leq x_{j}-x_{j-1} \leq l+d$, for all $j=2, \ldots, k$. Let $Q (d,k)$ be the least positive integer such that every $2$-coloring of $\{ 1, \ldots,Q (d,k) \}$ contains a monochromatic $k$-term quasi-progression of diameter $d$. We prove that\[Q(k-i,k) = 2ik-4i+2r-1,\]if $k=mi+r$ for integers $m,r$ such that $3 \le r \lt \frac{i}{2}$ and $r-1 \le m$. We also prove that, if $k \geq 2i \geq1$, then\[Q ( k-i,k ) =\begin{cases}2ik - 4i + 3 & \text{if } k \equiv 0 \: \text{or} \: 2 \: (\operatorname{mod} i) \\2ik - 2i + 1 & \text{if } k \equiv 1 \: (\operatorname{mod} i)\end{cases}\]These results partially settle several conjectures due to Landman [“Ramsey Functions for Quasi-Progressions”, Graphs and Combinatorics 14 (1998), 131–142].

Keywords

Ramsey, coloring, arithmetic progression, van der Waerden

2010 Mathematics Subject Classification

Primary 05D10. Secondary 11B25.

Full Text (PDF format)

Published 6 April 2012