Edge-coloring of the complete graph without any rainbow paths

2013-01-28T21:22:44Z

For a given $2k-1$ edge coloring of the complete graph $K_{2k}$, say a Hamiltonian path $P$ is a rainbow path if every color appears exactly once in $P$.

My question is

"For each $2k (k \geq 2)$, is there a proper $2k-1$ edge coloring of $K_{2k}$ with no rainbow paths?"

It is easy to see that every proper edge-coloring of $K_4$ or $K_6$ does not contain any rainbow paths.

For $K_8$, the statement is still true but some proper 7-edge-coloring contains rainbow paths.

When the number of vertices is a power of 2, then the statement is true, but I do not know if it is true for every even number (I don't even know for $2k = 10$).

Here's why the statement is true for $2^k$.

Label the vertices of $K_{2^k}$ by the elements of the group $((Z_2)^k, +)$ and label each edge by the sum(or difference) between two ends. Then the edge-labels give us a proper $2^k-1$ edge coloring, and this coloring does not have any rainbow paths.

Answer by Ilhee Kim for Majority vote of total orders

2013-01-26T02:02:11Z

For $k=3$, the following paper shows an example of a non-3-majority tournament with 8 vertices.

http://www2.isye.gatech.edu/~ctovey/publications/papers/voting__19_may_08.pdf

A few years ago, I checked that every tournament with 7 vertices (even the Paley tournament) is 3-majority by using a computer.

Answer by Ilhee Kim for Does this poset have a unique minimal element?

2013-01-14T21:43:48Z

The answer is yes. With Ringi Kim and Paul Seymour, we proved this a few days ago, and the following is the proof. (I am not sure if this is already known or not. Please let me know if it is.)

Some definitions first. For a tree $T$ and $u,v \in V(T)$, $dist_T(u,v)$ is the length of the (unique) path from $u$ to $v$ in $T$. $T \setminus u$ denotes the forest obtained from $T$ by deleting the vertex $u$ (deleting all the edges incident to $u$ as well). $T \setminus uv$ denotes the forest obtained from $T$ by deleting the edge $uv$ (not deleting the vertices $u$ and $v$). For each $v \in V(T)$, $d_T(v) := \max_{u \in V(T) \setminus {v}} dist_T(u,v)$. We say $v \in V(T)$ is a center of $T$ if $d_T(v)$ attains its minimum over all vertices. The following are some easy facts about centers in a tree.

1) There are at most 2 centers in a tree.

2) If there are 2 centers $u$ and $v$, then $uv \in E(T)$. Moreover, every path of length $d_T(u)$ from $u$ passes $v$ and vise versa.

Now, here is our strategy. We are going to look at a minimal tree $T$ in the poset AFT. And we will choose special leaves $l_1$ and $l_2$ by certain methods, and use the fact that both $T \setminus l_1$ and $T \setminus l_2$ are not in AFT. From this, we will prove various properties of $T$. For instance, we will prove that $T$ must have two centers, and $T \setminus l_1$ must have exactly one center, and $T \setminus l_2$ must have two centers, etc. Eventually we will prove that $T$ must be isomorphic to $E_7$.

We first introduce the method of choosing a special leaf. Let $T$ be a tree with $|V(T)| \geq 2$, and let $u$ be a vertex in $T$. We are going to pick a leaf with respect to $u$ and $T$ as follows.

Consider all neighbors of $u$. Each one is in its own component $C_1,\cdots,C_k$ of $T \setminus u$. Among those components, we take one with the least number of vertices. (If there are more than one smallest components, just pick any one of those.) Let $C_1$ be the component we chose and let $w$ be the neighbor of $u$ in $C_1$. Now, look at all children of $w$ (the neighbors of $w$ except $u$). If there are no children of $w$, then we take $w$ as our special leaf. Otherwise we consider components $D_1,\cdots,D_m$ of $C_1 \setminus w$ and again, we pick the smallest component, and we move one step ahead. By this algorithm, we will end up with a leaf and we will take that leaf as our special leaf with respect to $u$ and $T$.

Theorem 1. Let $T$ be a minimal tree in the poset AFT. Then $T$ has exactly two centers.

Proof. For the sake of contradiction, suppose $T$ has a unique center $u$. Let $l_1$ be the special leaf with respect to $u$ and $T$ as described above.

Now, consider the tree $T' = T \setminus l_1$. In $T'$, $u$ is still a center because $d_{T'}(v)$ is either $d_{T}(v)$ or $d_{T}(v) - 1$ for every $v \in V(T) \setminus l_1$, and $d_T(u)$ used to be the unique minimum in $T$. (But there might be another center of $T'$.)

1) There is another center of $T'$.

Suppose $u$ is the unique center of $T'$. Let $\phi$ be a non-trivial automorphism in $T'$. Let $p(l_1)$ be the parent (the unique neighbor) of $l_1$ in $T$. Notice that $\phi$ does not fix $p(l_1)$ because otherwise we can extend $\phi$ to $T$ by assigning $\phi(l_1) = l_1$. On the other hand, $\phi$ fixes $u$ since it is the unique center of $T'$. Let $P$ be the path from $u$ to $p(l_1)$ in $T'$. Then, it is clear that $\phi$ fixes a sub-path $P'$ of $P$ containing $u$, and $\phi$ does not fix the other part of the path containing $p(l_1)$. Let $u'$ be the last vertex of $P'$. ($u'$ might be equal to $u$.) Then, $T' \setminus u'$ has (at least) two components which are isomorphic. And one of them must contain $p(l_1)$ since otherwise we can extend $\phi$ to $T$. Let $C_1$ and $C_2$ be those isomorphic components in $T' \setminus u'$ and say $p(l_1) \in C_1$. In particular $|C_1| = |C_2|$. But in $T$, $C_1 \cup l_1$ and $C_2$ are two components of $T \setminus u'$ and $|C_1 \cup l_1| > |C_2|$. This is a contradiction to our choice of $l_1$. This proves (1).

Let $v$ be the other center of $T'$. $u$ used to be the unique center of $T$, but now $u$ and $v$ are two centers in $T \setminus l_1$. Therefore it must be the case that $$d_{T'}(u) = d_T(u) = d_{T'}(v) = d_T(v) - 1$$

2) $l_1$ is not a neighbor of $u$.

Suppose $l_1$ is a child of $u$. Then, $d_{T'}(v) = d_T(v) - 1 = dist_T(v, l_1) - 1 = 1$. Therefore $T'$ has exactly two vertices $u$ and $v$. This is a contradiction to the fact that $T$ is in AFT. This proves (2).

3) $v$ is not in the component $C_1 \setminus l_1$ of $T' \setminus u$.

The path from $v$ to $l_1$ is the unique path of length $d_T(v)$ starting from $v$ in $T$. In particular, the path from $v$ to $p(l_1)$ is a path of length $d_T(v)-1 = d_{T'}(v)$. Recall that $u$ and $v$ are adjacent. Therefore if $v$ is in $C_1 \setminus l_1$, then the path from $v$ to $p(l_1)$ does not pass $u$. A contradiction. This proves (3).

4) $p(l_1)$ is a leaf in $T'$.

Suppose $p(l_1)$ has a child $w$ other than $l_1$ in $T$. Then, the path from $v$ to $w$ in $T'$ has length $d_{T'}(v)+1$ and this contradicts the definition of $d_{T'}$. This proves (4).

5) $\phi$ switches $u$ and $v$.

Notice that either $\phi$ fixes $u$ and $v$ or switches them since they are centers. But if $\phi$ fixes $u$, then by the same argument as in (1), we get a contradiction to our choice of $l_1$. This proves (5).

Let $T_u$ and $T_v$ be the two components of $T' \setminus uv$. ($T_u$ contains $u$ and $T_v$ contains $v$.) Since $\phi$ switches $u$ and $v$, $T_u$ and $T_v$ must be isomorphic. Note that $\phi$ does not fix any vertex. Recall that $p(l_1)$ is a leaf in $T_u$ from (4). Therefore $\phi(p(l_1))$ is also a leaf in $T_v$. Clearly it is a leaf in $T$ as well. Let $l_2 = \phi(p(l_1))$. (It is easy to see that this $l_2$ is actually the special leaf with respect to $v$ and $T$.)

We now consider $T'' = T \setminus l_2$.

6) $u$ is still a center of $T''$, but $v$ is not.

$u$ is still a center of $T''$ as it was in $T'$. But, $v$ is not a center of $T''$ since $d_{T''}(v) = dist_{T''}(v,l_1) = d_{T}(v) > d_{T}(u) \geq d_{T''}(u)$. This proves (6).

Again, there might be another center of $T''$. And if there is one, then it must be in $T_u$ since $v$ is not a center of $T''$.

Now consider a non-trivial automorphism $\phi'$ of $T''$.

7) $\phi'$ does not fix $v$.

For the sake of contradiction, suppose $\phi'$ fixes $v$. Then $u$ is fixed as well because $u$ is the unique center among the neighbors of $v$ (although $u$ might not be the unique center of $T''$.) By the similar argument as before, the parent of $l_2$ is not fixed by $\phi'$ and this yields a contradiction to the fact that $l_2$ is a special leaf with respect to $v$. This proves (7).

Clearly, $\phi'(v)$ is in $T_u$ since it is adjacent to a center of $T''$ and not equal to $v$. Then, there must be some component $C$ of $T'' \setminus u$ either isomorphic to $T_v \setminus l_2$ or contains it. In any case, $C$ has size at least $|T_v \setminus l_2|$. Let $n = |T_v|$.

8) $|C| = n$ or $n-1$.

$|C| \geq n-1$ since $\phi'(V(T_v) \setminus l_2) \subseteq C$. Recall that $|T_u| = |T_v|$ and $C$ is a subset of $V(T_u) \cup {l_1} \setminus {u}$. Therefore $|C| \leq |V(T_u) \cup {l_1} \setminus {u}| = n + 1 - 1 = n$. This proves (8).

9) The degree of $u$ is 2. In particular, $T''\setminus u$ consists of two isomorphic components, namely $C$ and $T_v \setminus l_2$.

Note that the union of all components of $T''\setminus u$ other than $T_v\setminus l_2$ has size $|V(T_u) \cup {l_1} \setminus {u}| = n$. Therefore if there is another component of $T'' \setminus u$ other than $C$ and $T_v\setminus l_2$, then it must be a single vertex. Therefore $u$ has degree either 2 or 3. If $u$ has degree 3, then it has a neighbor who has degree 1. Then this leaf must have been our choice $l_1$. But by (2), this is impossible. Therefore $u$ has exactly two neighbors. This proves (9).

Suppose there are some vertices of degree at least 3 in $C$. Now let $x$ be the shortest distance from $u$ to a vertex of degree at least 3 in $C$. And let $y$ be the shortest distance from $v$ to a vertex of degree at least 3 in $T_v$. Since $T_u$ and $T_v$ are isomorphic, $x = y$.

On the other hand, the shortest distance from $u$ to a vertex of degree at least 3 in $T_v$ is $y + 1$. Since $T_v \setminus l_2$ is isomorphic to $C$, the shortest distance from $u$ to a vertex of degree at least 3 in $C$ is $y+1$. Therefore $x = y+1$ and this is a contradiction.

Therefore no vertex has degree at least 3 in $C$. And this implies that $T$ is a path. And this is a contradiction to the fact that $T$ is in AFT. This proves Theorem 1.

Theorem 2. Let $T$ be a minimal tree in the poset AFT. Then $T$ is isomorphic to $E_7$

Proof. From Theorem 1, $T$ has two centers $u$ and $v$. Let $T_u$ and $T_v$ be the two sub-trees in $T \setminus uv$. ($T_u$ contains $u$ and $T_v$ contains $v$.)

Let $l_1$ be the special leaf with respect to $u$ and $T_u$ and let $l_2$ be the special leaf with respect to $v$ and $T_v$. Let $x$ be the shortest distance from $u$ to a vertex of degree at least 3 in $T_u$. (If there aren't any vertices of degree 3 in $T_u$, then $T_u$ is a path, and set this number $x$ as the length of the path.) Similarly, let $y$ be the shortest distance from $v$ to a vertex of degree at least 3 in $T_v$.

Without loss of generality, we may assume $|T_u| \leq |T_v|$. And further we may assume if $|T_u| = |T_v|$ then $x \leq y$ by switching $u$ and $v$ if necessary.

We first look at $T' = T \setminus l_2$.

1) $u$ and $v$ are still two centers of $T'$.

Note that every path of length $d_T(v)$ starting from $v$ passes $u$ in $T$. Therefore this path still exists in $T'$ since $l_2 \in T_v$. Therefore $d_{T'}(v) = d_T(v)$. This means that $u$ is still a center of $T'$.

Suppose $u$ is the unique center of $T'$. Let $\phi$ be a non-trivial automorphism of $T'$. Then, $\phi$ does not fix $v$ since otherwise we get a contradiction to our choice of $l_2$.

Then the component $T_v \setminus l_2$ of $T' \setminus u$ is isomorphic to some other component $C$ of $T' \setminus u$. Note that $$|C| = |T_v \setminus l_2| = |T_v| - 1$$ Since $C$ is a subset of $V(T_u) \setminus {u}$, $$|T_u| \geq |C| + 1 = |T_v|$$ Therefore $|T_u| = |T_v|$. And $T' \setminus u$ has exactly two components, namely $C$ and $T_v \setminus l_2$. We may assume there is a vertex of degree at least 3 in $T_v \setminus l_2$, since otherwise $T$ is a path. But then, $x \geq y+1$ and this is a contradiction to our assumption ($x \leq y$ if $|T_u| = |T_v|$). Therefore $u$ is not the unique center of $T'$. This means that $d_{T'}(u) = d_T(u)$ and $v$ is still a center as well. This proves (1).

2) $\phi$ switches $u$ and $v$. And $|T_u| = |T_v| -1$.

Again, if $\phi$ fixes $v$, then $\phi$ fixes $u$ as well and we get a contradiction to our choice of $l_2$. Since $\phi$ switches $u$ and $v$, $T_u$ and $T_v \setminus l_2$ are isomorphic. In particular, $|T_u| = |T_v| - 1$. This proves (2).

Now we consider $T'' = T \setminus l_1$. Let $\phi'$ be a non-trivial automorphism of $T''$.

3) $\phi'$ does not fix $u$. And $v$ is the unique center of $T''$.

Again, every path of length $d_T(u)$ starting from $u$ passes $v$ in $T$. Therefore this path still exists in $T''$ since $l_1 \in T_u$. Therefore $d_{T'}(u) = d_T(u)$. This means that $v$ is still a center of $T''$.

Note that either $d_{T'}(v) = d_T(v)-1$ or $d_{T'}(v) = d_T(v)$. In the former case, $v$ is the unique center of $T''$, and in the latter case, $u$ and $v$ are again two centers of $T''$. Therefore if there is another center, then it must be $u$.

Suppose $\phi'$ fixes $u$. Then, again $v$ is fixed as well and we get a contradiction to the choice of $l_1$. Therefore $\phi'$ does not fix $u$.

For the sake of contradiction, suppose $u$ is another center of $T''$. Since $\phi'$ does not fix $u$, it switches $u$ and $v$. Then, $T_u \setminus l_1$ is isomorphic to $T_v$, but $|T_u \setminus l_1| = |T_u| - 1 = |T_v| - 2 \neq |T_v|$. A contradiction. This proves (3).

Since $v$ is the unique center of $T''$ and $\phi'$ does not fix $u$, the component $T_u \setminus l_1$ of $T'' \setminus v$ is isomorphic to another component $C$ of $T'' \setminus v$.

Note that the union of all components of $T''\setminus v$ other than $T_u \setminus l_1$ is exactly $T_v \setminus v$. And $C$ has size $|T_u| - 1 = |T_v| - 2$. This means that there are exactly three components of $T''\setminus v$, namely $T_u \setminus l_1$, $C$, and the third one with a single vertex. Therefore $v$ has a neighbor of degree 1, and this must have been our choice $l_2$.

Now suppose there is a vertex of degree at least 3 in $T_u$. Then there is one in $T_v$ as well. And by the usual argument, $x=y$ and $x+1 = y$ at the same time. A contradiction. Therefore $T_u$ must be a path of length $|T_u|$ and $T_v$ must be a path of length $|T_v| = |T_u| + 1$.

Then, $T$ is a tree with a unique vertex of degree 3, namely $v$, and $T \setminus v$ has three components. One of them is a single vertex, namely $l_2$, and the other two components are paths of length $k$ and $k+1$.

For every $k > 2$, $T$ is not minimal since deleting $l_1$ from $T$ yields a smaller tree $T''$ in AFT. Therefore $k$ must be 2. This proves that $T$ must be isomorphic to $E_7$.

Comment by Ilhee Kim

2013-01-29T18:14:08Z

Thanks a lot! The paper looks very helpful for better understanding of the problem.

Comment by Ilhee Kim

2013-01-29T05:08:11Z

@Gerhard : For $K_4$, I label the vertices by the elements of $Z_2 \times Z_2$, not $Z_4$. If you use $Z_4$, the edge coloring is not well defined.

Comment by Ilhee Kim

2013-01-29T04:41:53Z

I think your edge coloring may not be well-defined. For instance, the difference between two vertices (0,1) and (0,2) is either (0,1) or (0,5) in $Z_2 \times Z_6$? For $Z_{2^k}$, we don't have such a problem since $x-y = y-x = x+y$.

Comment by Ilhee Kim

2013-01-19T01:30:13Z

@ARupinski : I understand. Thanks for the great question. It was really fun to work on it. We are actually thinking about publishing it if our solution is indeed new.

Comment by Ilhee Kim

2013-01-18T23:32:57Z

@ARupinski : Thanks. Please let me know if there is something unclear. By the way, could you tell us some references or motivations of this problem?

Comment by Ilhee Kim

2013-01-16T02:39:47Z

@Todd : Thanks for the tip!

User ilhee kim - MathOverflow

Edge-coloring of the complete graph without any rainbow paths

Answer by Ilhee Kim for Majority vote of total orders

Answer by Ilhee Kim for Does this poset have a unique minimal element?

Comment by Ilhee Kim

Comment by Ilhee Kim

Comment by Ilhee Kim

Comment by Ilhee Kim

Comment by Ilhee Kim

Comment by Ilhee Kim