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

  • Zhanar Berikkyzy
  • Alex Shulte
  • Michael Young
Keywords: Arithmetic progression, Rainbow coloring, Unitary coloring, Behrend construction

Abstract

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}$,
        \begin{equation*}
            aw([n],3)=\left\{\begin{array}{ll}
                m+2, & \mbox{if $n=3^m$} \\
                m+3, & \mbox{otherwise}.
            \end{array}\right.
        \end{equation*}

Published
2017-06-16
Article Number
P2.39