The idea of comparison-based ranking has been discussed earlier in the chapter Comparison based ranking, where score sequence was introduced as a way of ranking vertices in a tournament. Oriented graphs are generalizations of tournaments. In fact, just like one can think of a tournament as expressing the results of a round-robin competition without ties (with vertices representing players and arrows pointing to the defeated players), one can think of an oriented graph as a round-robin competition with ties allowed (ties are represented by not drawing the corresponding arcs).
Figure 30.1 shows the results of a round-robin competition involving 4 players and , with (a) ties not allowed and (b) ties allowed. In the first instance there is always a winner and a loser whenever two players square off, while in the latter case player ties with player and player ties with player .
In 2009 Antal Iványi studied directed graphs, in which every pair of different vertices is connected with at least and at most arcs. He named them -tournaments or simply -tournament.
If , then the -tournaments are called -tournaments. In this chapter we deal first of all with -tournaments and -tournaments. -tournaments are in some sense equivalent with -tournaments. We use the simple notations 1-tournament , 2-tournament , -tournament . It is worth mentioning that is a classical tournament, while oriented graphs are -tournaments. If we allow loops then every directed graph is some -tournament (see the chapter Comparison Based Ranking of this book).
We discuss two concepts related with -tournaments, namely score sets and kings. A score set is just the set of different scores (out-degrees) of vertices, while a king is a dominant vertex. We shall study both concepts for 1-tournaments first and then extend these to the more general setting of oriented graphs.
Although we present algorithms for finding score sets and kings in -tournaments and -tournaments, much of the focus is on constructing tournaments with special properties such as having a prescribed score set or a fixed number of kings. Since players in a tournament are represented by vertices, we shall use the words player and vertex interchangeably throughout this chapter without affecting the meaning.
We adopt the standard notation to denote a tournament with vertex set and arc set . We denote the number of vertices by , and the out-degree matrix by , and the in-degree matrix by . Furthermore, we use the term -tournament and the notation to represent a tournament with vertices and exactly arcs between the elements of any pair of different vertices. In a similar way and denote a regular, resp. a null graph. When there is no ambiguity we omit one or even both indices and shall refer to the corresponding tournaments as , , and . The score sequences are denoted by , while the score sets as sets by and as sequences by .
In Section 30.1 the score sets of 1-tournaments are discussed, while Section 30.2 deals with the sore sets of oriented graphs. In Section 30.3 the conditions of the unique reconstruction of the score sets are considered at first for -tournaments, then in more details for 1-tournaments and 2-tournaments. In Section 30.4 and Section 30.5 results connected with different kings of tournaments are presented.
Some long and accessible proofs are omitted. In these cases the Reader can find the coordinates of the proof in Chapter notes and Bibliography.
In a round-robin competition with no ties allowed, what are the sets of nonnegative integers that can arise as scores of players? Note that here we are not interested in the scores of individual players (the score sequence), rather we are looking for the sets of nonnegative integers with each integer being the score of at least one player in the tournament. This question motivates the study of score sets of tournaments.
The set of different scores of vertices of a tournament is called the score set of the tournament. In other words, the score set is actually the score sequence of a tournament with repetitions removed. For example the tournament given in Figure 30.2 has score sequence , whereas the score set of this tournament is . Figure 30.3 shows the out-degree matrix of the tournament represented on Figure 30.2.
Figure 30.3. Out-degree matrix of the tournament represented in Figure 30.2.
Determining the score set of a tournament is quite easy. The following algorithm
takes the data of a tournament as input and returns the score set of .
The procedures of this chapter are written using RAM model of computations and pseudocode according to the third edition of the textbook Introduction to Algorithms published by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein in 2009.
FORall vertex 3 4
FORall vertex 5
//is an arc of ? 6 7
//is the found score new? 8 9
Since the scores of the vertices depend on out-degrees, any algorithm determining the score set requires time. Due to the embedded loops in lines 02–08 the running time of
is even in the best case. The precise order of the running time depends among others on the implementation of the
instruction in line 07. E.g., if line 07 is implemented by the sequential comparison of the actual score with the elements of , then the running time is for a score sequence containing different elements and is for a regular tournament.
Out-degree matrix is a useful data structure in the implementation of graph algorithms. The input data of the following algorithm
are and , and the output is the score sequence a as a nonincreasingly ordered sequence and the score set as a decreasingly ordered sequence.
calls the well-known sorting procedure
//score sequence is computed 5 6
//sorting of the score vector 7 8
IF10 11 12
Since the embedded loops in lines 02–05 need time, and the remaining part of the code requires less, the running time of
is in all cases.
Constructing a 1-tournament with a prescribed score set is more difficult than determining the score set of a 1-tournament with prescribed score sequence or with prescriben our-degree matrix. Quite surprisingly, if sufficiently many players participate in a tournament then any finite set of nonnegative integers can arise as a score set. This was conjectured by K. B. Reid in 1978 and turned out to be a relatively challenging problem.
Reid proved the result when , or , or if contains consecutive terms of an arithmetic or geometric progression. That is, Reid showed that any set of one, two or three nonnegative integers is a score set of some tournament and additionally, any set of the form for or for , is a score set of some tournament. Hager settled the cases and in 1986 and finally in 1987, T. Yao gave an existence proof of the general Reid's conjecture based on arithmetic analysis.
Let us try to formulate Reid's conjecture purely as a statement about numbers. Let be an increasing sequence of nonnegative integers. The conjecture means that there exist positive integers such that
is the score sequence of some 1-tournament with vertices. By Landau's theorem, , with , is the score sequence of some -tournament if and only if , for and . Thus it can be readily seen that Reid's conjecture is equivalent to the following statement.
For every nonempty set of nonnegative integers , where , there exist positive integers , such that
It is this equivalent formulation of Reid's conjecture that led to Yao's proof. The proof is not combinatorial in nature, but uses first of all some results of number theory. Commenting on Yao's proof Qiao Li wrote in 2006 in the Annals of New York Academy of Sciences:
Yao's proof is the first proof of the conjecture, but I do not think it is the last one. I hope a shorter and simpler new proof will be coming in the near future.
However, the prophecized constructive proof has not been discovered yet. This is in sharp contrast with Landau's theorem on score sequences, for which several proofs have emerged over the years. Recently, S. Pirzada and T. A. Naikoo gave a constructive combinatorial proof of a new special case of Reid's theorem. Their proof gives an algorithm for constructing a tournament with the prescribed score set, provided the score increments are increasing.
Since any set of nonnegative integers can be written in the form of 30.3, the above theorem is applicable to all sets of nonnegative integers with increasing increments (i.e., .) The importance of Pirzada-Naikoo proof of Theorem 30.2 is augmented by the fact that Yao's original proof is not constructive and is not accessible to a broad audience.
Footnote. Yao's proof originally appeared in Chinese in the journal Kexue Tongbao. Later in 1989, the proof was published in English in the Chinese Science Bulletin. Unfortunately neither are accessible through the world wide web, although the English version is available to subscribers of the Chinese Science Bulletin. In Hungary this journal is accessible in the Library of Technical and Economical University of Budapest.
The following recursive algorithm is based on Pirzada and Naikoo's proof of Theorem 30.2. The algorithm takes the set of increments of the score set as input and returns a tournament whose score set is . Let for . Let denote the regular tournament on vertices and let denote the vertex and arc disjoint union of tournaments and .
IFis odd 2 print
This algorithm calls one of the two following recursive procedures
according to the parity of . The input of both algorithm is some prefix of the sequence of the increments , and the output is a tournament having the score set corresponding to the given increments.
ELSE4 5 6 =
)7 8 such that 9 dominates 10 dominates 11 dominates 12
We can remark that the tournament constructed by the first execution of line 03 of
contains the vertices whose score is , while the tournament constructed in line 04 contains the vertices whose score is in the tournament appearing as output. The vertices having smaller scores appear during the later execution of lines 03 and 04 with exception of the vertices having score since those vertices will be added to the output in line 02.
1 2 3 =
)4 5 such that dominates 6
Since the algorithm is complicated, let's consider an example.
The second step of
is the construction of . Let and be the vertices of this tournament.
The third step of
is the recursive call with parameters and . The fourth action of
is the construction of . Let and be the vertices of this tournament. The fifth step is the construction of . Let be the only vertex of this graph. The sixth action is the call of
with parameters and . Now the number of increments equals to 1, therefore the algorithm constructs in line 02.
The seventh step is the construction of in line 07, then the eighth step is adding new arcs (according to lines 08–11) to the actual constructed in line 07 and consisting from 3 regular tournaments having altogether 5 vertices . The result is shown in Figure 30.7.
Ninth step of
is joining the tournaments and to and the final step is adding of the domination arcs. The out-degree matrix of the output of
is shown in Figure 30.8.
Let be a set of nonnegative integers with .
performs two types of recursions: first if is odd and the second if is even. Assume to be odd. For , the set contains one nonnegative integer and the algorithm returns the regular tournament as output. Note that each vertex of has score , so that score set of is . This shows that the algorithm is correct for .
If , then the set of increments consists of three nonnegative integers with . Now , therefore , so that as . Let be a regular tournament having vertices. Then each vertex of has score .
Again, since , therefore , so that . Let be a regular tournament having vertices. Then each vertex of has score . Also since , let be a regular tournament having vertices. Then each vertex of has score .
outputs a tournament whose vertex set is the disjoint union of vertex sets of , and and whose arc set contains all the arcs of , and such that every vertex of dominates each vertex of , and every vertex of dominates each vertex of and . Thus has vertices with score set
This shows that the algorithm is correct for too. When the set of increments consists of an odd number of nonnegative integers, the algorithm recursively builds the required tournament by using the procedure
. To see this, assume that the algorithm works for all odd numbers upto . That is, if are nonnegative integers with , then the algorithm outputs a tournament having vertices with score set . Let us call this tournament .
We now show how the algorithm constructs a tournament with vertices with score set , where are nonnegative integers with .
Since therefore , , , , so that , that is, .
constructs as a regular tournament having vertices. Each vertex of has score
Again, , therefore , so that as .
constructs as a regular tournament having vertices. Each vertex of has score
sets and adds additional arcs in such a way that every vertex of dominates each vertex of , and every vertex of dominates each vertex of and . Therefore is a tournament having
vertices with score set
Hence by induction, the algorithm is correct for all odd .
To prove the correctness for even case, note that if is odd, then is even. Let be nonnegative integers with . Therefore , where is odd. The procedure
uses the procedure
to generate a tournament having vertices with score set .
Also, since , , the procedure
generates a regular tournament having vertices such that the score for each vertex is .
Finally the algorithm generates the tournament and adds additional arcs so that every vertex of dominates each vertex of . The resulting tournament consists of
vertices and has score set
This shows that the algorithm is correct for even as well.
The running time of
depends on the size of the score set as well as the largest increment . The details are left as an exercise for the Reader (see Exercise 30.1-1).
30.1-1 The out-degree matrix of a tournament is defined as a matrix with entry equal to 1 if player defeats player and 0 otherwise (see (30.16)). A tournament is completely determined by its out-degree matrix. Write an algorithm to generate the out-degree matrix of a regular tournament on vertices, where is any odd positive integer. Hint. Circularly place ones in each row.
30.1-2 Use Exercise 30.1-1 and the discussion in this section to determine the worst-case running time of
30.1-4 Use the tournament obtained in Exercise 30.1-3 to generate the out-degree matrix of a 1-tournament with score set . Write the score sequence of your tournament.