Anti-van der Waerden Numbers of 3-Term Arithmetic Progression

Zhanar Berikkyzy, Alex Shulte, Michael Young


The anti-van der Waerden number, denoted by $aw([n],k)$, is the smallest $r$ such that every exact $r$-coloring of $[n]$ contains a rainbow $k$-term arithmetic progression. Butler et. al. showed that $\lceil \log_3 n \rceil + 2 \le aw([n],3) \le \lceil \log_2 n \rceil + 1$, and conjectured that there exists a constant $C$ such that $aw([n],3) \le \lceil \log_3 n \rceil + C$. In this paper, we show this conjecture is true by determining $aw([n],3)$ for all $n$. We prove that for $7\cdot 3^{m-2}+1 \leq n \leq 21 \cdot 3^{m-2}$,
                m+2, & \mbox{if $n=3^m$} \\
                m+3, & \mbox{otherwise}.


Arithmetic progression; Rainbow coloring; Unitary coloring; Behrend construction

Full Text: