Journal of Combinatorics

Volume 2 (2011)

Number 4

Ramsey functions for quasi-progressions with large diameter

Pages: 557 – 573

DOI: http://dx.doi.org/10.4310/JOC.2011.v2.n4.a5

Authors

Adam S. Jobson (University of Louisville, Kentucky, U.S.A.)

André E. Kézdy (University of Louisville, Kentucky, U.S.A.)

Hunter S. Snevily (Department of Mathematics, University of Idaho, Moscow, Id., U.S.A.)

Susan C. White (Department of Mathematics, Bellarmine University, Louisville, Kentucky, U.S.A.)

Abstract

A $k$-term quasi-progression of diameter $d$ is a sequence%\[x_1 < \cdots< x_k\]%of positive integers for which there exists a positive integer $l$ suchthat $l \leq x_{j} - x_{j-1} \leq l+d$, for all $j=2,\ldots,k$. Let$Q\left(d,k\right)$ be the least positive integer such that every$2$-coloring of $\left\{1,\ldots,Q\left(d,k\right)\right\}$ contains amonochromatic $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$ suchthat $3 \le r < \frac{i}{2}$ and $r-1 \le m$. We also prove that,if $k\geq2i \geq1$, then%\[Q\left(k-i,k\right) =%\begin{cases}2ik-4i+3 &\mbox{if } $\Mod{k}{0\mbox{ or }2}{i}$2ik-2i+1 &\mbox{if } $\Mod{k}{1}{i}$\end{cases}%\]%These results partially settle several conjecturesdue to Landman [Ramsey Functions for Quasi-Progressions, Graphs andCombinatorics 14 (1998) 131–142].

Keywords

Ramsey, coloring, arithmetic progression, van der Waerden

2010 Mathematics Subject Classification

Primary 05D10. Secondary 11B25.

Full Text (PDF format)