Originator: Bruce Landman (presented by S. Vijay - REGS 2008)
Definitions: The Van der Waerden number W(k) is the least n such that every 2-coloring of [n] (the set {1,…,n}) contains a monochromatic arithmetic progression of length n. A quasi-progression of diameter d is a list {x1,…,xk} for which there exists a positive integer L such that L≤xi-xi-1≤L+d for 2≤i≤k. In particular, an ordinary arithmetic progression is a quasi-progression of diameter 0. This suggests an analogue of the Van der Waerden numbers for quasi-progressions. Let Qd(k) denote the least integer n such that every 2-coloring of [n] contains a monochromatic k-term quasi-progression of diameter d; note that Q0(k)=W(k). By definition, Qd(k)≤W(k) for all d.
Background: Since W(k)>2k (proved by using a random coloring), it is well-known that Q0(k) is at least exponential in k. Also, it is easy to show that Qk-1(k)=2k-1.
Question 1: Can reasonable upper and lower bounds be obtained for diameters between 0 and k-1? Can anything be said about the transition of Qd(k) from an exponential to a polynomial function of k as d increases? (It is also conjectured that Q1(k)≤2k².)
Question 2: Is it true that Qk/2(k)=k²-2k+3 when k is even? This has been verified for k≤10.
Comments: The best lower bounds until recently were quadratic, even for Q1(k). Landman and Robertson [LR] proved that Q1(k)≥2(k-1)²+1 using the coloring consisting of k-1 repetitions of k-1 reds followed by k-1 blues (this generalizes to show Qk-i(k)=Ω(ki)). Vijay [V] proved an exponential lower bound: Q1(k)≥1.08k. The proof technique does not appear to generalize to d=O(1). For upper bounds, the only significant result is due to Landman [L], who proved that Q⌈2k/3⌉(k)=O(k³). Any upper bound when d=o(k) that does not use W(k) (or uses it nontrivially) would be interesting. Quadratic lower bounds are known when d=ck with c<1. It is conjectured that there is also a quadratic upper bound. It would be nice to prove this for some c, no matter how close to 1.
References:
[L]
B. M. Landman; Ramsey functions for quasiprogressions. Graphs and
Combinatorics 14 (1998), no. 2, 131--142.
[LR]
B. M. Landman and A. Robertson; Ramsey Theory on the Integers.
Student Mathematical Library, Vol.24, American Mathematical Society, 2004.
[V]
S. Vijay; On a variant of Van der Waerden's Theorem (preprint).