Partitioning finite ordered sets

Question

Let $n$ be a natural number and assume for a start that $n$ is divisible by $3$. Let $\sigma$ be a permutation of the set $\{1,2,\ldots, n\}$. I want to partition the vector $S=(\sigma(1),\sigma(2),\ldots, \sigma(n))$ into three vectors $(a_1,\ldots, a_{n/3})=A$, $(b_1,\ldots, b_{n/3})=B$ and $(c_1,\ldots, c_{n/3})=C$ of equal length. Because this is boring, I impose some restrictions. First, I don't want to have consecutive numbers in one vector, so for example $a_i=3$, $a_j=4$ for some $i,j$ is not allowed. Second, I require that for all $i$, $a_i=\sigma(j)$ implies $|3i-j|\leq k$, where $k$ is some constant independent of $n$ (and the same for $B$ and $C$).

Consider the following example. If $\sigma$ is the identical permutation, I choose $A=(1,4,7,\ldots)$, $B=(2,5,8,\ldots)$, $C=(3,6,9,\ldots)$. Then for each vector every pair of components has distance $2$, and $A$, $B$ and $C$ have "uniform density", because I roughly "chose every third number".

The question is, whether there is $k$ such that the above construction is possible for all $n$ and $\sigma$.

The second question is, if partitioning into $3$ vectors fails, does it work for $4$ instead of $3$ or an even larger number?

NOTE: I set the graph-theory tag, because using graph theory seems like a reasonable approach to me.

Answer 1

The answer to your question is yes with $k=2$.

I came up with a proof using the fact that the Strong Chromatic Number $(s{\chi})$ of a cycle of size multiple of $3$ is $3$ $( s\chi(C_{3t}) = 3)$ see this reference for more details.

The argument goes like this:

Let $C_n$ be the standard cycle $(1, 2, 3, ...,n-1, n)$. Label the vertices of $C_n$ as follows:

Vertex $\rho(j)$ gets labeled with the integer $ \lfloor \frac{j+2}{3} \rfloor$ (it comes from the second requirement).

Notes that the labels come from the set {1, 2, 3, ..., $\frac{n}{3}$} and that the labeling partition the vertices into $\frac{n}{3}$ parts each of size $3$.

Since $s\chi(C_{n}) = 3$, there is a proper $3$-coloring of $C_n$ such that vertices with the same label get different colors. The coloring gives the three different vectors and the labeling define the indices for the vectors.