25.7. 25.7 Supertournaments

In Section 25.1 we defined the -supertournaments.

Now at first we present some results on the special case , that is on the hypertournaments.

25.7.1. 25.7.1 Hypertournaments

Hypergraphs are generalizations of graphs [], []. While edges of a graph are pairs of vertices of the graph, edges of a hypergraph are subsets of the vertex set, consisting of at least two vertices. An edge consisting of vertices is called a -edge. A -hypergraph is a hypergraph all of whose edges are -edges. A -hypertournament is a complete -hypergraph with each -edge endowed with an orientation, that is, a linear arrangement of the vertices contained in the hyperedge. Instead of scores of vertices in a tournament, Zhou et al. [] considered scores and losing scores of vertices in a -hypertournament, and derived a result analogous to Landau's theorem []. The score or of a vertex is the number of arcs containing and in which is not the last element, and the losing score or of a vertex is the number of arcs containing and in which is the last element. The score sequence (losing score sequence) is formed by listing the scores (losing scores) in non-decreasing order.

The following characterizations of score sequences and losing score sequences in -hypertournaments can be found in G. Zhou et al. [].

Theorem 25.22 (Zhou, Yang, Zhang []) Given two non-negative integers and with , a nondecreasing sequence of nonnegative integers is a losing score sequence of some -hypertournament if and only if for each ,

with equality when .

Proof. See [].

Theorem 25.23 (Zhou, Yang, Zhang []) Given two positive integers and with , a nondecreasing sequence of nonnegative integers is a score sequence of some -hypertournament if and only if for each ,

with equality when .

Proof. See [].

Some more results on -hypertournaments can be found in [], [], [], [], []. The analogous results of Theorem 25.22 and Theorem 25.23 for [ ]-bipartite hypertournaments can be found in [] and for -tripartite hypertournaments can be found in [].

Throughout this subsection takes values from 1 to and takes values from 1 to , unless otherwise is stated.

A -partite hypertournament is a generalization of -partite graphs (and -partite tournaments). Given non-negative integers and , with for each , an - -partite hypertournament (or briefly -partite hypertournament) of order consists of vertex sets with for each , together with an arc set , a set of tuples of vertices, with exactly vertices from , called arcs such that any subset of , contains exactly one of the -tuples whose entries belong to .

Let , with for each , , be an arc in and let , we let denote to be the new arc obtained from by interchanging and in . An arc containing vertices from for each , is called an ()-arc.

For a given vertex for each , and , the score (or simply ) is the number of -arcs containing and in which is not the last element. The losing score (or simply ) is the number of -arcs containing and in which is the last element. By arranging the losing scores of each vertex set separately in non-decreasing order, we get lists called losing score lists of and these are denoted by for each , . Similarly, by arranging the score lists of each vertex set separately in non-decreasing order, we get lists called score lists of which are denoted as for each . The following two theorems are the main results of this subsection.

Theorem 25.24 (Pirzada, Zhou, Iványi [][Theorem 3]) Given nonnegative integers and nonnegative integers with for each , the nondecreasing lists of nonnegative integers are the losing score lists of a -partite hypertournament if and only if for each with ,

with equality when for each .

Theorem 25.25 (Pirzada, Zhou, Iványi [][Theorem 4]) Given nonnegative integers and nonnegative integers with for each , the non-decreasing lists of non-negative integers are the score lists of a -partite hypertournament if and only if for each , with

with equality, when for each .

We note that in a -partite hypertournament , there are exactly arcs and in each arc only one vertex is at the last entry. Therefore,

In order to prove the above two theorems, we need the following Lemmas.

Lemma 25.26 (Pirzada, Zhou, Iványi [][Lemma 5]) If is a -partite hypertournament of order with score lists for each , then

Proof. We have for each . If is the losing score of , then

The number of arcs containing for each , , and is

Thus,

Lemma 25.27 (Pirzada, Zhou, Iványi [][Lemma 6]) If are losing score lists of a -partite hypertournament , then there exists some with

so that , () and , (), are losing score lists of some -partite hypertournament, is the largest integer such that .

Proof. Let be losing score lists of a -partite hypertournament with vertex sets so that for each (, ).

Let be the smallest integer such that

and be the largest integer such that

Now, let

, and , , .

Clearly, and are both in non-decreasing order.

Since , there is at least one -arc containing both and with as the last element in , let . Clearly, , and for each , are the losing score lists of .

The next observation follows from Lemma 25.26, and the proof can be easily established.

Lemma 25.28 (Pirzada, Zhou, Iványi [][Lemma 7]) Let , be nondecreasing sequences of nonnegative integers satisfying (25.43). If , then there exist and (), such that , and , (), satisfy (25.43).

Proof of Theorem 25.24. Necessity. Let , be the losing score lists of a -partite hypertournament . For any with , let be the sets of vertices such that for each , . Let be the -partite hypertournament formed by for each .

Then,

Sufficiency. We induct on , keeping fixed. For , the result is obviously true. So, let , and similarly . Now,

We consider the following two cases.

Case 1. .

Then,

By induction hypothesis , are losing score lists of a -partite hypertournament of order . Construct a -partite hypertournament of order as follows. In , let for each , . Adding a new vertex to , for each -tuple containing , arrange on the last entry. Denote to be the set of all these -tuples. Let . Clearly, for each , are the losing score lists of .

Case 2. .

Applying Lemma 25.26 repeatedly on and keeping each , fixed until we get a new non-decreasing list in which now . By Case 1, , are the losing score lists of a -partite hypertournament. Now, apply Lemma 25.26 on , repeatedly until we obtain the initial non-decreasing lists for each . Then by Lemma 25.27, for each are the losing score lists of a -partite hypertournament.

Proof of Theorem 25.25. Let be the score lists of a -partite hypertournament , where with , for each , .

Clearly,

, .

Let , .

Then are the losing score lists of . Conversely, if for each are the losing score lists of , then for each , are the score lists of . Thus, it is enough to show that conditions (25.43) and (25.44) are equivalent provided

for each .

First assume (25.44) holds. Then,

with equality when for each .

Thus (1) holds.

Now, when (25.43) holds, using a similar argument as above, we can show that (25.44) holds. This completes the proof.

25.7.2. 25.7.2 Supertournaments

The majority of the results on hypertournaments can be extended to supertournaments.

The simplest case when all individual tournaments have own input sequence , where . Then we can apply the necessary and sufficient conditions and algorithms of the previous sections.

If all tournaments have a join input sequence , then all the previous necessary conditions remain valid.