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
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
for \(W(8; 2,2,2,2,2,2,3,3) \gt 24\text{.}\) Notice that the colours \(0,1,2,3,4,5\) are used exactly once. As such, there are \(6!\) equivalent certificates which simply permute the locations of \(0,1,2,3,4,5\text{.}\) The certificate can be transformed into
where \(0\)'s are any permutation of \(0,1,2,3,4,5\) and \(6,7\) get reduced to colours \(1\) and \(2\text{.}\) This turns the \(8\)–ary backtracking tree to a \(3\)–ary tree and greatly reduces the search space. More generally, for \(W(r; k_0, \ldots, k_{j-1}, k_j, \ldots, k_{r-1})\) where \(k \geq j + 2\) with \(k_0 = k_1 = \cdots = k_{j-1} = 2\) and \(k_i \geq 3\) for \(i \geq j\) this turns a \(r\)–ary search tree into a \(r-j+1\)–ary tree.
Consider the reduced certificate
and notice this is also equivalent to
Clearly the search space here can be halved by simply ignoring certificates that swap the order of the colours.
More generally, for \(W(r; k_0, \ldots, k_{j-1}, k_j, \ldots, k_{r-1})\) with \(k_0 = k_1 = \cdots = k_{j-1} = 2\) and \(t_i = t \geq 3\) for \(i = j, j+1, \ldots, r-1\) a maximal certificate, due to symmetry, will contain an equal number of colours \(k_{j}, k_{j+1}, \ldots, k_{r-1}\) which will be isomorphic to \((r-j)!\) other certificates. Ignoring these equivalent certificates greatly reduces the search space again.
These optimizations greatly increase the space of numbers computable in a reasonable amount of time.