Maths Olympiad Prep

Library / /36 of 37

Combinatorics Difficulty 8.6 Shortlist Find the answer

A tournament is a directed graph for which every (unordered) pair of vertices has a single directed edge from one vertex to the other. Let us define a proper directed-edge-coloring to be an assignment of a color to every (directed) edge, so that for every pair of directed edges uv\overrightarrow{uv} and vw\overrightarrow{vw}, those two edges are in different colors. Note that it is permissible for uv\overrightarrow{uv} and uw\overrightarrow{uw} to be the same color. The directed-edge-chromatic-number of a tournament is defined to be the minimum total number of colors that can be used in order to create a proper directed-edge-coloring. For each nn, determine the minimum directed-edge-chromatic-number over all tournaments on nn vertices.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

A tournament is a directed graph for which every (unordered) pair of vertices has a single directed edge from one vertex to the other. Let us define a proper directed-edge-coloring to be an assignment of a color to every directed edge, so that for every pair of directed edges uv\overrightarrow{uv} and vw\overrightarrow{vw}, those two edges are in different colors. Note that it is permissible for uv\overrightarrow{uv} and uw\overrightarrow{uw} to be the same color. The directed-edge-chromatic-number of a tournament is defined to be the minimum total number of colors that can be used in order to create a proper directed-edge-coloring. For each nn, we aim to determine the minimum directed-edge-chromatic-number over all tournaments on nn vertices.

The answer is log2n\lceil \log_2 n \rceil.

A construction is as follows: Label the vertices {1,2,3,,n}\{1, 2, 3, \ldots, n\} and write each label in binary. Then for any two vertices u,vu, v, let kk be the first position from the right which is different in their binary representations. If the kk-th digit is 00 in uu and 11 in vv, then draw the edge uvu \to v. Clearly, this works.

We now prove the result by induction on nn. It is trivial for n=1n=1. Now say we want to prove the result for nn, and assume without loss of generality that nn is even, say by deleting a vertex if needed. Fix a color, say red, and consider the set SS of all the vertices formed by the tails of these red edges. Consider the partition of the vertices of our graph into SS and VSV \setminus S. At least one of these sets has a size at least n/2n/2, say SS.

Then we claim that there cannot be any red edge "contained" in SS. Indeed, if there is, then its head would lie on some vSv \in S (since it is contained in SS) which already has a red edge going out of it, contradicting the hypothesis.

Hence, SS has n/2n/2 vertices and no edge is red. So
χ1+log2(n/2)=log2(n). \chi \ge 1 + \log_2 (n/2) = \log_2(n).
Thus, the induction is complete.

The answer is: log2n\boxed{\lceil \log_2 n \rceil}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.