Method of Computing van der Waerden Numbers

Section 18.3 Method of Computing van der Waerden Numbers

The work done in this paper is primarily based on the work of Tanbir Ahmed in his 2013 paper “Some More van der Waerden Numbers” utilizing a backtracking algorithm for computing van der Waerden Numbers of the form

$W(r; k_0, k_1, \ldots, k_{r-1})$ where

$k_0 = k_1 = \cdots = k_{j-1} = 2$ where

$r \geq j + 2$ and

$k_i \geq 3$ for

$i \geq j\text{.}$ [18.6.2] While backtracking is the approach taken for the results in this paper, note that many other papers, include Ahmed's, utilize SAT solvers in solving for more general forms of van der Waerden numbers.

🔗

For any

$w = W(r; k_0, k_1, \ldots, k_{r-1})\text{,}$ one can demonstrate

$w \geq l$ with a certificate of length

$l$ which is a colouring of

$\{1, 2, \ldots, l\}$ containing no monochromatic arithmetic progression of length

$k_i$ for all

$i\text{.}$ For example, the certificate that

$W(8; 2,2,2,2,2,2,3,3) \gt 24$ is

$\begin{equation*} 067766776162347576677667 \end{equation*}$

🔗

as it is an 8 colouring of

$\{1, \ldots, 24\}$ contains no two long arithmetic progression is colours

$0,1,2,3,4,5$ and no three long arithmetic progression in colours

$6,7\text{.}$ One can compute van der Waerden numbers by building these certificates. Once a certificate of length

$l$ is not possible, then by definition

$W(r; k_0, k_1, \ldots, k_{r-1}) = l$ as a monochromatic arithmetic progression becomes unavoidable.

🔗

In this paper, these certificates are built using a brute force backtracking approach. It is an exponential time algorithm that tries permutations of a length

$l$ to check if a certificate exists. If a certificate exists, it then tries permutations of length

$l+1$ and so on until a certificate can no longer be found. However speedups can still be achieved with 2 key optimizations based on symmetry.

🔗

Consider again the certificate

$\begin{equation*} 067766776162347576677667 \end{equation*}$

🔗

for