Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
    
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 stolz@math.uni-leipzig.de. –  Abel Stolz Jun 3 '12 at 14:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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