Solution of a covering problem related to labelled tournaments

✍ Scribed by Sgall, Ji?�

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 462 KB
• Volume: 23
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199610)23:2<111::aid-jgt2>3.0.co;2-w

✦ Synopsis

Suppose we have a tournament with edges labelled so that the edges incident with any vertex have at most k distinct labels (and no vertex has outdegree 0). Let m be the minimal size of a subset of labels such that for any vertex there exists an outgoing edge labelled by one of the labels in the subset. It was known that m 5 (k$l) for any tournament. We show that this bound is almost best possible, by a probabilistic construction of tournaments with m = s2(k2/ log k ) . We give explicit tournaments with m = k2-"('). If the number of vertices is bounded by N < 2k, we have a better upper bound of m = O(k log N ) , which is again almost optimal. We also consider a relaxation of this problem in which instead of the size of a subset of labels we minimize the total weight of a fractional set with analogous properties. In that case the optimal bound is 2k -1.