I was reading a problem list by Erdos (doi). On page 144 (which is the 12-th page of the pdf), a problem stuck out to me.
For positive integer $n$, let $h(n)$ be the smallest $k$ such that $[n] := \{1,\dots,n\}$ can be partitioned into $k$ parts $A_1,\dots,A_k$ so that $A_i \cup A_j$ lacks arithmetic progressions of length four for each $i,j \in [k]$. I was wondering if this quantity $h(n)$ has been studied, and if so what bounds are known.
Observations: A simple upper bound is the following. Let $c:[k] \to [n]$ be a coloring (which obviously corresponds to a partition of $[n]$ into $k$ parts). If there exists a monochromatic arithmetic progression of length 3, $P = \{n,n+d,n+2d\} \subset [1,2n/3]$, then we have $d<n/3$ implying $n+3d \in [n]$ meaning there exists an arithmetic progression of length four.
Hence we must have $W_{h(n)}(3) > 2n/3$. I am not too familiar with the bounds for the multicolor van der Waerden numbers, but by Bloom and Sisak's density result this implies $h(n) \gg \log^{1+c}(n)$ for some $c>0$.
Also, I'm pretty sure a bound of $h(n)\ll n^{1-\epsilon}$ for some $\epsilon > 0$ should follow by appropriately modifying the work of Tomon and Pach on rainbow arithmetic progressions.
Best Answer
The bound $h(n) \ll n^{2/3}$ is achievable by the following twisted cubic construction: Let $X=\mathbb{F}_p^3$ ($p\geq5$) and $Y_{ij}=\{(t,t^2+i,t^3+j): t \in \mathbb{F}_p\}$. The sets $Y_{ij}$ partition $X$ and $Y_{ij} \cup Y_{kl}$ never contains any 4-AP.
If there were a 4-AP, $\{a,b,c,d\}$, there must be two elements belonging to $Y_{ij}$ and two belonging to $Y_{kl}$, since none of $Y_{ij}$ contains a 3-AP. We may assume $\{a,b\} \in Y_{ij}$ and $\{c,d\} \in Y_{kl}$. In this case, the vectors $a-b$ and $c-d$ would be parallel, but a twisted cubic does not contain any pair of secants that are parallel.
We can "project" $\mathbb{F}_p^3$ on $\mathbb{Z}$ by sending $(a,b,c)$ (taking values in $0 ... p-1$) to $4ap^2+2bp+c$. In this projection, if a subset of $\mathbb{F}_p^3$ does not contain a 4-AP, the image would not contain a 4-AP either. So we can project the $Y_{ij}$s on $\mathbb Z$ without creating any 4-APs. By translating the projected $Y_{ij}$s by $4xp^3+2yp^2+zp$ $(x,y,z \in \{0,1\})$ and renaming the variables, we can partition $0 ... 8p^3-1$ by $8p^2$ sets.
Thus the bound $h(n) \ll n^{2/3}$ is achievable.