  If we want to color $1,2,\ldots,n$ with the property that all 3-term
arithmetic progressions are rainbow (that is, their elements receive 3 distinct
colors), then, obviously, we need to use at least $n/2$ colors. Surprisingly,
much fewer colors suffice if we are allowed to leave a negligible proportion of
integers uncolored. Specifically, we prove that there exist $\alpha,\beta<1$
such that for every $n$, there is a subset $A$ of $\{1,2,\ldots,n\}$ of size at
least $n-n^{\alpha}$, the elements of which can be colored with $n^{\beta}$
colors with the property that every 3-term arithmetic progression in $A$ is
rainbow. Moreover, $\beta$ can be chosen to be arbitrarily small. Our result
can be easily extended to $k$-term arithmetic progressions for any $k\ge 3$.
  As a corollary, we obtain the following result of Alon, Moitra, and Sudakov,
which can be used to design efficient communication protocols over shared
directional multi-channels. There exist $\alpha',\beta'<1$ such that for every
$n$, there is a graph with $n$ vertices and at least
$\binom{n}{2}-n^{1+\alpha'}$ edges, whose edge set can be partitioned into at
most $n^{1+\beta'}$ induced matchings.
