Improving the use of cyclic zippers in finding lower bounds for van der Waerden numbers

John Rabung¹ ; Mark Lotts¹

¹Randolph-Macon College

The electronic journal of combinatorics, Tome 19 (2012) no. 2

Résumé

For integers $k$ and $l$, each greater than $1$, suppose that $p$ is a prime with $p\equiv1\,(\textrm{mod}\, k)$ and that the $k^{\rm th}$-power classes $\textrm{mod}\, p$ induce a coloring of the integer segment $[0,\, p-1]$ that admits no monochromatic occurrence of $l$ consecutive members of an arithmetic progression. Such a coloring can lead to a coloring of $[0,\,(l-1)p]$ that is similarly free of monochromatic $l$-progressions, and, hence, can give directly a lower bound for the van der Waerden number $W(k,l)$. P. R. Herwig, M. J. H. Heule, P. M. van Lambalgen, and H. van Maaren have devised a technique for splitting and "zipping" such a coloring of $[0,\, p-1]$ to yield a coloring of $[0,\,2p-1]$ which, for even values of $k$, is sometimes extendable to a coloring of $[0,\,2(l-1)p]$ where both new colorings still admit no monochromatic $l$-progressions. Here we derive a fast procedure for checking whether such a zipped coloring remains free of monochromatic $l$-progressions, effectively reducing a quadratic-time check to a linear-time check. Using this procedure we find some new lower bounds for van der Waerden numbers.

Détail

DOI : 10.37236/2363

Classification : 05D10, 05C15
Mots-clés : van der Waerden numbers