30.3. 30.3 Unicity of score sets

-tournaments (multitournaments) are directed graphs in which each pair of vertices is connected with exactly arcs.

Reid formulated the following conjecture in [ 233 ].

Conjecture 30.8 Any set of nonnegative integers is the score set of some 1-tournament T.

Using Landau's theorem this conjecture can be formulated in the following arithmetic form too.

Conjecture 30.9 If , then there exist such positive integers , that

and

In this case we say that the sequence realizes the sequence or is a solution for .

Reid gave a constructive proof of his conjecture for sets containing one, two or three elements [ 233 ].

Later Hager published a constructive proof for sets with four and five elements [ 99 ] and Yao [ 291 ] published the outline of a nonconstructive proof of the general case.

A score set is called k-unique, if there exists exactly 1 score sequence of -tournaments generating the given set. In the talk we investigate the following questions:

  1. characterization of the unique score sets of 1-tournaments;

  2. extension of the Reid's conjecture to 2-tournaments.

30.3.1. 30.3.1 1-unique score sets

At first we formulate a useful necessary condition.

Lemma 30.10 (Iványi and Phong, 2004) If , then for any -tournament holds that the sequence is a solution for , then in the case we have

and in the case we have

and

and

The proof is left an exercise (see Exercise 30.3-1). This lemma implies the exact answer for the case .

Corollary 30.11 (Iványi and Phong, 2004) If , then exactly the sequence is a solution for .

Proof. Lemma 30.10 implies that only this solution is acceptable. One can check that it satisfies the required inequality and equality.

Now we present a useful method of the investigation of the uniqueness. Let . Then according to the Reid-equality we get

implying

But here only the values are permitted where

By substitution from (30.12) we get

Here must be an integer, so transform this formula into

Theorem 30.12 If , then there exist positive integers and satisfying

and

In the following cases there is only one solution:

  • ;

  • ;

  • .

In the following case there are at least two solutions:

  • is odd and .

Proof. a) Existence of a solution. Let and . Then , satisfy all requirements.

b) Uniqueness. If , then , and is integer only if . So we get the unique solution.

If , then only is permitted, implying the unique solution .

If or is odd, then we also can analyse formula (30.15).

This theorem left open the case when the difference is odd and the investigated set is sparse and also the case when the difference is an even number greater then 2.

30.3.2. 30.3.2 2-unique score sets

Now we present a new form of Reid-problem for 2-tournaments.

For a fixed sequence with of positive integers, we shall denote by the set of sequences such that

and

Here we also say that g is a solution for q.

We wish to give necessary and sufficient conditions for to have a solution that is a nonempty .)

Theorem 30.13 For the sequence , we have .

Proof. If , then it is obvious that the solution of is given in the form . Hence we have .

Theorem 30.14 Let be a sequence of positive integers with . Then if and only if either or and there is a prime such that .

Proof. According to the definition of , we need only find positive integers such that and .

Let be integers for which , where . If , then and let and . Hence we have

and

Now assume that and there is a prime such that . In this case and we choose as follows:

It is obvious that

and

Finally, assume that or and is the product of distinct primes. If there are positive integers such that and , then we have and

consequently

This is impossible.

Theorem 30.15 (Iványi, Phong, 2004) Let be the sequence of positive integers with conditions , , and has distinct prime factors. Then

Proof. Since and , the congruence has solutions in positive integers less than . For each solution we set and . One can check that satisfy conditions and .

Exercises

30.3-1 Prove Lemma 30.10.

30.3-2 Find the score sequence of the 1-tournament with a score set [5} and design a schedule for the corresponding tournament.