User ilhee kim - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T00:47:50Z http://mathoverflow.net/feeds/user/30650 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120148/edge-coloring-of-the-complete-graph-without-any-rainbow-paths Edge-coloring of the complete graph without any rainbow paths Ilhee Kim 2013-01-28T21:22:44Z 2013-01-30T00:04:41Z <p>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$.</p> <p>My question is</p> <p>"For each $2k (k \geq 2)$, is there a proper $2k-1$ edge coloring of $K_{2k}$ with no rainbow paths?"</p> <p>It is easy to see that every proper edge-coloring of $K_4$ or $K_6$ does not contain any rainbow paths.</p> <p>For $K_8$, the statement is still true but some proper 7-edge-coloring contains rainbow paths.</p> <p>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$).</p> <p>Here's why the statement is true for $2^k$.</p> <p>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. </p> http://mathoverflow.net/questions/119240/majority-vote-of-total-orders/119903#119903 Answer by Ilhee Kim for Majority vote of total orders Ilhee Kim 2013-01-26T02:02:11Z 2013-01-26T02:02:11Z <p>For $k=3$, the following paper shows an example of a non-3-majority tournament with 8 vertices. </p> <p><a href="http://www2.isye.gatech.edu/~ctovey/publications/papers/voting__19_may_08.pdf" rel="nofollow">http://www2.isye.gatech.edu/~ctovey/publications/papers/voting__19_may_08.pdf</a></p> <p>A few years ago, I checked that every tournament with 7 vertices (even the Paley tournament) is 3-majority by using a computer.</p> http://mathoverflow.net/questions/117151/does-this-poset-have-a-unique-minimal-element/118925#118925 Answer by Ilhee Kim for Does this poset have a unique minimal element? Ilhee Kim 2013-01-14T21:43:48Z 2013-01-16T19:35:52Z <p>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.)</p> <p>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.</p> <p>1) There are at most 2 centers in a tree.</p> <p>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.</p> <p>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$.</p> <p>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.</p> <p>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$.</p> <p>Theorem 1. Let $T$ be a minimal tree in the poset AFT. Then $T$ has exactly two centers.</p> <p>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.</p> <p>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'$.)</p> <p>1) There is another center of $T'$.</p> <p>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).</p> <p>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$$</p> <p>2) $l_1$ is not a neighbor of $u$.</p> <p>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).</p> <p>3) $v$ is not in the component $C_1 \setminus l_1$ of $T' \setminus u$.</p> <p>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).</p> <p>4) $p(l_1)$ is a leaf in $T'$.</p> <p>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).</p> <p>5) $\phi$ switches $u$ and $v$.</p> <p>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).</p> <p>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$.)</p> <p>We now consider $T'' = T \setminus l_2$.</p> <p>6) $u$ is still a center of $T''$, but $v$ is not.</p> <p>$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).</p> <p>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''$.</p> <p>Now consider a non-trivial automorphism $\phi'$ of $T''$.</p> <p>7) $\phi'$ does not fix $v$.</p> <p>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).</p> <p>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|$.</p> <p>8) $|C| = n$ or $n-1$.</p> <p>$|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).</p> <p>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$.</p> <p>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).</p> <p>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$.</p> <p>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.</p> <p>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.</p> <p>Theorem 2. Let $T$ be a minimal tree in the poset AFT. Then $T$ is isomorphic to $E_7$</p> <p>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$.)</p> <p>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$.</p> <p>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.</p> <p>We first look at $T' = T \setminus l_2$.</p> <p>1) $u$ and $v$ are still two centers of $T'$.</p> <p>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'$.</p> <p>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$.</p> <p>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).</p> <p>2) $\phi$ switches $u$ and $v$. And $|T_u| = |T_v| -1$.</p> <p>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).</p> <p>Now we consider $T'' = T \setminus l_1$. Let $\phi'$ be a non-trivial automorphism of $T''$.</p> <p>3) $\phi'$ does not fix $u$. And $v$ is the unique center of $T''$.</p> <p>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''$.</p> <p>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$.</p> <p>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$.</p> <p>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).</p> <p>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$.</p> <p>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$.</p> <p>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$.</p> <p>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$.</p> <p>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$.</p> http://mathoverflow.net/questions/120148/edge-coloring-of-the-complete-graph-without-any-rainbow-paths/120234#120234 Comment by Ilhee Kim Ilhee Kim 2013-01-29T18:14:08Z 2013-01-29T18:14:08Z Thanks a lot! The paper looks very helpful for better understanding of the problem. http://mathoverflow.net/questions/120148/edge-coloring-of-the-complete-graph-without-any-rainbow-paths Comment by Ilhee Kim Ilhee Kim 2013-01-29T05:08:11Z 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. http://mathoverflow.net/questions/120148/edge-coloring-of-the-complete-graph-without-any-rainbow-paths/120174#120174 Comment by Ilhee Kim Ilhee Kim 2013-01-29T04:41:53Z 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$. http://mathoverflow.net/questions/117151/does-this-poset-have-a-unique-minimal-element/118925#118925 Comment by Ilhee Kim Ilhee Kim 2013-01-19T01:30:13Z 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. http://mathoverflow.net/questions/117151/does-this-poset-have-a-unique-minimal-element/118925#118925 Comment by Ilhee Kim Ilhee Kim 2013-01-18T23:32:57Z 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? http://mathoverflow.net/questions/117151/does-this-poset-have-a-unique-minimal-element/118925#118925 Comment by Ilhee Kim Ilhee Kim 2013-01-16T02:39:47Z 2013-01-16T02:39:47Z @Todd : Thanks for the tip!