Lower bound on Van der Waerden number W(r,k)

701 Views Asked by At

The Van der Waerden number $W(r,k)$ is the smallest positive integer $n$ such that every $r$-color of $\{1,2,3,\dots,n\}$ contains a monochromatic arithmetic progression of length $k$.

I am looking for the best known lower bound for $W(r,k)$. In the case $r=2$ the best bound is due to Berlekamp: for $p$ a prime, $p \cdot 2^p \leq W(2,p+1)$, which can be extended to a general bound for this $r=2$ case.

I can not find a reference for general $r$, though. I have checked recent surveys, Wikipedia, Rudiments of Ramsey theory (by Graham and Butler), Ramsey Theory (by Graham, Rothschild and Spencer), and have found no reference to a general lower bound.

Has no one found any reasonable lower bound? Or am I skipping over it somehow?

Any help or reference would be greatly appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

Landman and Robertson's Ramsey Theory on the Integers cites Everts's 1977 Ph.D. thesis Colorings of sets (which, as usual, is hard to find online) for the bound

$$W(r,k) > \frac{k r^k}{e(k+1)^2}$$

and also gives the mostly-tighter result, due to Shabanov (which might be this article, though they cite a different paper from 2010), that $$W(r,k) > \left(\frac{\sqrt{6}-2}{4}\right) \frac{r^{k-1}}{\sqrt{k\ln k}}\left(1 - \frac1k\right).$$ The above, they say, is the best known bound for general $r$ and $k$, but for primes $p$ and $q$, the bound $W(q,p+1) \ge p(q^p-1)+1$ "can be easily derived from a similar proof" in Graham, Rothschild, and Spencer's Ramsey Theory.

It's worth comparing all this to the naive probabilistic lower bound: the set $\{1,2,\dots,n\}$ contains fewer than $\binom{n}{2}$ progressions of length $k$ (because $\binom{n}{2}$ is the number of ways to choose a start and end with no regard to whether that's valid), each of which is monochromatic with probability $r^{-(k-1)}$. So if $n < r^{\frac{k-1}{2}}$, then the expected number of monochromatic arithmetic progressions in a random coloring is less than $1$, and with positive probability a random coloring avoids them all.