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 and , those two edges are in different colors. Note that it is permissible for and 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 , determine the minimum directed-edge-chromatic-number over all tournaments on vertices.
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 and , those two edges are in different colors. Note that it is permissible for and 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 , we aim to determine the minimum directed-edge-chromatic-number over all tournaments on vertices.
The answer is .
A construction is as follows: Label the vertices and write each label in binary. Then for any two vertices , let be the first position from the right which is different in their binary representations. If the -th digit is in and in , then draw the edge . Clearly, this works.
We now prove the result by induction on . It is trivial for . Now say we want to prove the result for , and assume without loss of generality that is even, say by deleting a vertex if needed. Fix a color, say red, and consider the set of all the vertices formed by the tails of these red edges. Consider the partition of the vertices of our graph into and . At least one of these sets has a size at least , say .
Then we claim that there cannot be any red edge "contained" in . Indeed, if there is, then its head would lie on some (since it is contained in ) which already has a red edge going out of it, contradicting the hypothesis.
Hence, has vertices and no edge is red. So
Thus, the induction is complete.
The answer is: .