4
$\begingroup$

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.

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you very much. I would like to credit you if your proof is used in a publication. If you like to tell me your real name for that, please e-mail me at [email protected]. $\endgroup$
    – Abel Stolz
    Jun 3, 2012 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.