## 25.8. 25.8 Football tournaments

The football tournaments are special incomplete -tournaments, where the set of the permitted results is .

### 25.8.1. 25.8.1 Testing algorithms

In this section we describe eight properties of football sequences. These properties serve as necessary conditions for a given sequence to be a football sequence.

Definition 25.29 A football tournament is a directed graph (on vertices) in which the elements of every pair of vertices are connected either with 3 arcs directed in identical manner or with 2 arcs directed in different manner. A nondecreasingly ordered sequence of any is called football sequence

The -th vertex will be called -th team and will be denoted by . For the computations we represent a tournament with , what is an sized matrix, in which means the number of points received by in the match against . The elements , that is the elements in the main diagonal of are equal to zero. Let's underline, that the permitted elements are 0, 1 or 3, so .

The vector of the outdegrees of a tournament is called score vector. Usually we suppose that the score vector is nondecreasingly sorted. The sorted score vector is called score sequence and is denoted by . The number of football sequences for teams is denoted by . The values of are known for [].

In this subsection at first we describe six algorithms which require time in worst case, then more complicate algorithms follow.

#### 25.8.1.1.  Linear time testing algorithms

In this subsection we introduce relatively simple algorithms Boundness-Test, Monotonity-Test, Intervallum-Test, Loss-Test, Draw-Loss-test, Victory-Test, Strong-Test , and Sport-Test .

Testing of boundness

Since every team plays matches and receives at least and at most points in each match, therefore in a football sequence it holds for .

Definition 25.30 A sequence of integers will be called -bounded (shortly: bounded), if and only if

Lemma 25.31 (Lucz, Iványi, Sótér []) Every football sequence is a bounded sequence.

Proof. The lemma is a direct consequence of Definition 25.29.

The following algorithm executes the corresponding test. Sorting of the elements of is not necessary. We allow negative numbers in the input since later testing algorithm Decomposition can produce such input for Boundness-Test .

Input. : the number of teams ;

: arbitrary sequence of integer numbers.

Output. : a logical variable. Its value is , if the input vector is bounded, and otherwise.

Working variable. : cycle variable.

Boundness-Test

  1
FOR

TO

2
IF

or    3          4
RETURN

5     6
RETURN



In worst case Boundness-Test runs time, in expected case runs in time. More precisely the algorithm executes comparisons in worst case and asymptotically in average 2 comparisons in best case.

Testing of monotonity

Monotonity is also a natural property of football sequences.

Definition 25.32 A bounded sequence of nonnegative integers will be called -monotone (shortly: monotone), if and only if

Lemma 25.33 (Lucz, Iványi, Sótér []) Every football sequence is a monotone sequence.

Proof. This lemma also is a direct consequence of Definition 25.29.

The following algorithm executes the corresponding test. Sorting of the elements of is not necessary.

Input. : the number of players ;

: a bounded sequence of length .

Output. : a logical variable. Its value is , if the input vector is monotone, and otherwise.

Working variable. : cycle variable.

Monotonity-Test

  1
FOR

TO

2
IF

3          4
RETURN

5     6
RETURN



In worst case Monotonity-Test runs time, in expected case runs in time. More precisely the algorithm executes comparisons in worst case.

The following lemma gives the numbers of bounded and monotone sequences. Let denote the set of -bounded, and the set of -monotone sequences, the size of and the size of .

Lemma 25.34 If , then

and

Proof. (25.56) is implied by the fact that an -bounded sequence contains elements and these elements have different possible values.

To show (25.57) let be a monotone sequence and let , where . Then . The mapping is a bijection and so equals to the number of ways of choosing numbers from , resulting (25.57).

Testing of the intervallum property

The following definition exploits the basic idea of Landau's theorem [].

Definition 25.35 A monotone nonincreasing sequence is called intervallum type (shortly: intervallum), if and only if

Lemma 25.36 Every football sequence is intervallum sequence.

Proof. The left inequality follows from the fact, that the teams play matches and they get together at least two points in each matches.

The right inequality follows from the monotonity of and from the fact, that the teams play matches and get at most 3 points in each match.

The following algorithm Intervallum-Test tests whether a monotone input is intervallum type.

Input. : the number of teams ;

: a bounded sequence of length .

Output. : a logical variable. Its value is , if the input vector is intervallum type, and otherwise.

Working variables. : cycle variable;

: binomial coefficients;

: initial value for the sum of the input data;

: the sum of the smallest input data.

We consider and as global variables, and therefore they are used later without new calculations. The number of -intervallum sequences will be denoted by .

Intervallum-Test

  1     2
FOR

TO

3       4       5
IF

or    6       7
RETURN

8     9
RETURN



In worst case Intervallum-Test runs time. More precisely the algorithm executes comparisons, additions, extractions, multiplications and 2 assignments in worst case. The number of the -intervallum sequences will be denoted by .

Testing of the loss property

The following test is based on Theorem 3 of [][page 86]. The basis idea behind the theorem is the observation that if the sum of the smallest scores is less than , then the teams have lost at least points in the matches among others. Let and .

Definition 25.37 An intervallum satisfying sequence is called loss satisfying, iff

Lemma 25.38 (Lucz, Iványi, Sótér []) A football sequence is loss satisfying.

Proof. See the proof of Theorem 3 in [].

The following algorithm Loss-Test exploits Lemma 25.38.

Input. : the number of teams ;

: a bounded sequence of length .

Output. : a logical variable. Its value is , if the input vector is Landau type, and otherwise.

Working variables. : cycle variable;

: vector of the loss coefficient;

: sums of the input values, global variables;

: binomial coefficients, global variables.

Loss-Test

  1     2
FOR

TO

3       4
IF

5          6
RETURN

7     8
RETURN



In worst case Loss-Test runs in time, in best case in time. We remark that is in the following a global variable. The number of loss satisfying sequences will be denoted by .

Testing of the draw-loss property

In the previous subsection Loss-Test exploited the fact, that small scores signalize draws, allowing the improvement of the upper bound of the sum of the scores.

Let us consider the loss sequence . made a draw, therefore one point is lost and so must hold implying that the sequence is not a football sequence. This example is exploited in the following definition and lemma. Let

Definition 25.39 A loss satisfying sequence is called draw loss satisfying, if and only if

Lemma 25.40 (Lucz, Iványi, Sótér []) A football sequence is draw loss satisfying.

Proof. The assertion follows from the fact that small scores and remainders (mod 3) of the scores both signalize lost points and so decrease the upper bound .

The following algorithm Draw-Loss-Test exploits Lemma 25.38.

Input. : the number of teams ;

: a loss satisfying sequence of length .

Output. : a logical variable. Its value is , if the input vector is Landau type, and otherwise.

Working variables. : cycle variable;

: global variables;

: modified loss coefficients.

Draw-Loss-Test

  1     2
FOR

TO

3       4
IF

5          6
RETURN

7     8
RETURN



In worst case Draw-Loss-Test runs in time, in best case in time.

We remark that is in the following a global variable.

The number of draw loss satisfying sequences will be denoted by .

Testing of the victory property

In any football tournament matches end with victory and end with draw.

Definition 25.41 A loss satisfying (shortly: loss) sequence is called victory satisfying, iff

Lemma 25.42 (Lucz, Iványi, Sótér []) A football sequence is victory satisfying.

Proof. Team could win at most times. The left side of (25.62) is an upper bound for the number of possible wins, therefore it has to be greater or equal then the exact number of wins in the tournament.

The following algorithm Victory-Test exploits Lemma 25.42.

Input. : the number of teams ;

: a loss sequence of length .

Output. : a logical variable. Its value is , if the input vector is Landau type, and otherwise.

Working variables. : cycle variable;

: where is an upper estimation of the number of possible wins of .

: global variables.

Victory-Test

  1     2
FOR

TO

3       4
IF

5       6
RETURN

7     8
RETURN



Victory-Test runs in time in all cases. The number of the victory satisfying sequences is denoted by .

Victory-Test is successful e.g. for the input sequence , but until now we could not find such draw loss sequence, which is not victory sequence. The opposite assertion is also true. Maybe that the sets of victory and draw loss sequences are equivalent?

Testing of the strong draw-loss property

In paragraph “Testing of the draw-loss property” we estimated the loss caused by the draws in a simple way: supposed that every draw implies half point of loss. Especially for short sequences is useful a more precise estimation.

Let us consider the sequence . The sum of the remainders (mod 3) is 2 + 1 = 3, but we have to convert to draws at least three “packs” (3 points), if we wish to pair the necessary draws, and so at least six points are lost, permitting at most .

Exploiting this observation we can sharp a bit Lemma 25.40. There are the following useful cases:

1. one small remainder (1 pont) implies the loss of points;

2. one large remainder (2 points) implies the loss of points;

3. one small and one large remainder imply the loss of points;

4. two large remainders imply the loss of points;

5. one small and two large remainders imply the loss of = 4 points.

According to this remarks let resp. denote the multiplicity of the equality (mod 3) resp. (mod 3).

Definition 25.43 A victory satisfying sequence is called strong, iff

Lemma 25.44 (Lucz, Iványi, Sótér []) Every football sequence is strong.

Proof. The assertion follows from the fact that any point matrix of a football tournament order the draws into pairs.

The following algorithm Strong-Test exploits Lemma 25.44.

Input. : the number of teams ;

: a loss satisfying sequence of length

Output. : a logical variable. Its value is , if the input vector is Landau type, and otherwise.

Working variables. : cycle variable;

: modified loss coefficients, global variables; : sum of the elements of the sequence , global variable;

: strongly modified loss coefficients.

Strong-Test

  1     2
FOR

TO

3
IF

(mod 3)   4       5
IF

(mod 3)   6       7     8
IF

and    9      10
IF

and   11      12
IF

and   13      14
IF

and   15      16
IF

and   17      18
IF

19      20
RETURN
21    22
RETURN



Strong-Test runs in all cases in time.

We remark that is in the following a global variable.

The number of strong sequences will be denoted by .

Testing of the sport property

One of the typical form to represent a football tournament is its point matrix as it was shown in Figure 25.3.

Definition 25.45 A victory satisfying sequence is called sport sequence if it can be transformed into a sport matrix.

Lemma 25.46 (Lucz, Iványi, Sótér []) Every football sequence is a sport sequence.

Proof. This assertion is a consequence of the definition of the football sequences.

If a loss sequence can be realized as a sport matrix, then the following algorithm Sport-Test constructs one of the sport matrices belonging to .

If the team has points, then it has at least draws, wins and losses. These results are called obligatory wins, draws, resp. losses. Sport-test starts its work with the computation of and . Then it tries to distribute the remaining draws.

Input. : the number of players ;

: a victory satisfying sequence of length .

Output. : a logical variable. Its value is , if the input sequence is sport sequence, and otherwise;

Working variables. : cycle variable;

: columns of the sport matrix;

: sum of the numbers of obligatory wins, draws, resp. losses;

: global variables;

: the sum of the elements of the input sequence;

: the exact number of wins, draws, resp. losses.

Sport-Test

  1     2
FOR

TO

3       4       5       6       7       8       9    10
IF

or   11      12
RETURN

13    14    15
FOR

TO

16
WHILE

or  or   17         18         19         20         21         22         23         24
IF

25            26
RETURN

27
IF

or  or   28            29
RETURN
30    31
RETURN



Sport-Test runs in time in all cases. The number of the sport sequences is denoted by .

Concrete examples

Let us consider short input sequences illustrating the power of the linear testing algorithms.

If , then according to Lemma 25.34 we have and . The monotone sequences are , , , , , , , , , . Among the monotone sequences there are 4 interval sequences: , , , and , so . Loss-Test does not help, therefore . Victory-Test excludes , so . Finally Sport-Test can not construct a sport matrix for and so it concludes . After further unsuccessful tests Football reconstructs and , proving .

If , then according to Lemma 25.34 we have and . Among the 84 monotone sequence there are 27 interval sequences, and these sequences at the same time have also the loss property, so . These sequences are the following: , , , , , , , , , , , , , , , , , , , , , , , , , and . From these sequences only , , , , , , are paired sport sequences, so . The following tests are unsuccessful, but Football reconstructs the remained seven sequences, therefore .

If , then according to Lemma 25.34 we have and . The number of paired sport sequences is . We now that , so our linear algorithms evaluate the input sequences correctly up to .

If , then , but our approximating algorithms end with , that is the quality of 5 sequences remains open.

### 25.8.2. 25.8.2 Polynomial testing algorithms of the draw sequences

Earlier we used a greedy approach to check whether the necessary number of draws is allocatable.

Definition 25.47 A sequence is called potential -draw sequence. The number of potential -draw sequences is denoted by .

Lemma 25.48 (Iványi, Lucz, Sótér []) If , then .

Proof. The proof is similar to the proof of Lemma 25.34.

Let us suppose we get a potential draw sequence. In this subsection we describe the testing algorithms Quick-Havel-Hakimi and Linear-Erdős-Gallai .

Quick Havel-Hakimi algorithm

Algorithm Quick-Havel-Hakimi-Test is based on the following classical theorem [], [], [].

Theorem 25.49 (Havel [], Hakimi []) If , then a nonincreasing sequence of positive integers is the outdegree sequence of a simple graph if and only if is the outdegree sequence of some simple graph .

See [], [].

If is for example a complete simple graph, then it contains edges and the direct application of Havel-Hakimi theorem requires time. We make an attempt to decide in linear time the pairability of a sequence of positive integers.

The first simple observation is the necessity of the condition for all . We have not to test this property since all our draw allocation algorithms guarantee its fulfilment. Another interesting condition is

Lemma 25.50 (Iványi, Lucz, Sótér []) If a nonincreasing sequence of positive integers is the outdegree sequence of a simple graph , then

and

Proof. The draw request of the teams must be covered by inner and outer draws. The first sum on the right side gives the exact number of usable outer draws, while the sum of the right side gives the exact number of the reachable inner draws. The minimum on the left side represent an upper bound of the possible inner draws.

If we substitute this upper bound with the precise value, then our formula becomes a sufficient condition, but the computation of this value by Havel-Hakimi theorem is dangerous for the linearity of the method.

Let's take a few example. If , then we have only one potential draw-sequence, which is accepted by Havel-Hakimi algorithm and satisfies (25.64) and (25.65).

If , then there are potential draw sequence: (2,2,2), (2,2,1), (2,1,1) and (1,1,1). From these sequences Havel-Hakimi algorithm and the conditions of Lemma 25.48 both accept only (2,2,2) and (1,1,1).

If , then there are potential draw sequences. Havel-Hakimi algorithm and the conditions of Lemma 25.48 both accept the following 7: (3,3,3,3), (3,3,2,2), (3,2,2,1), (3,1,1,1), (2,2,2), (2,2,1,1), and (1,1,1,1).

If , then there are potential draw sequences. The methods are here also equivalent.

From one side we try to find an example for different decisions or try to find an exact proof of the equivalence of these algorithms.

Linear Erdős-Gallai algorithm

For given nondecreasing sequence of nonnegative integers the first elements of the sequence is called the head of the sequence and last elements are called the tail belonging to the th element of the sequence. The sum of the elements of the head is denoted by , while the sum of the element of the tail is denoted by . The sum is denoted by and is called the capacity of the tail belonging to . If is even, then is called even, otherwise the sequence is called odd sequence.

Another classical theorem on the testing of the potential draw sequences whether they are graphical is the theorem proved by Erdős and Gallai in 1960 [].

Theorem 25.51 (Erdős, Gallai, []) If , the -regular sequence is graphical if and only if

and

Proof. See [], [], [], [].

Recently we could improve this theorem []. The algorithm Erdős-Gallai-Linear exploits, that is monoton. It determines the capacities in constant time. The base of the quick computation is thesequence containing pointers. For given sequence let , where points to the element of having the maximal index among such elements of which are greater or equal with .

Theorem 25.52 (Iványi, Lucz, Sótér []) If , the -regular sequence is graphical if and only if

and if , then

further if , then

Proof. (25.68) is the same as (25.66).

During the testing of the elements of by Erdős-Gallai-Linear there are two cases:

• if , then the contribution of the tail of equals to , since the contribution of the element is only .

• if , then the contribution of the tail of consists of two parts: equal to , while for .

Therefore in the case we have

and in the case

The following program is based on Theorem 25.52. It decides on arbitrary -regular sequence whether it is graphicakl or not.

Input. : number of vertices ;

: -regular sequence.

Output. : logical variable, whose value is , if the input is graphical, and it is , if the input is not graphical.

Work variables. and : cycle variables;

: is the sum of the first elements of the tested ;

: is the maximum of the indices of such elements of , which are not smaller than ; : help variable to compute of the other elenments of the sequence ;

: help variable to compute the elements of the sequence .

Linear-Erdős-Gallai

  1
Line 01: initialization   2
FOR

TO

Lines 02–03: computation of the elements of    3       4
IF

odd       Lines 04–06: test of the parity   5       6
RETURN
7
Line 07: initialization of    8
FOR

DOWNTO

Lines 08–09: setting of some pointers   9      10
FOR

TO

Lines 10–14: calculation of the pointers  11
IF

12
FOR

DOWNTO

13            14      15
FOR

DOWNTO

Lines 15–16: setting of some pointers  16      17
FOR

TO

Lines 17–23: test of   18
IF

and   19         20
RETURN

21
IF

and   22         23
RETURN

24
Lines 24–25: the program ends with  value  25
RETURN



Theorem 25.53 (Iványi, Lucz [], Iványi, Lucz, Sótér []) Algorithm Linear-Erdős-Gallai decides in time, whether an -regular sequence is graphical or not.

Proof. Line 1 requires time, lines 2–3 time, lines 4–6 time, line 07 time, line 08–09 time, lines 10–16 time, lines 17–23 time and lines 24–25 time, therefore the total time requirement of the algorithm is .

Until now the number of good sequences was known only for , see Online Encyclopedia of Integer Sequences []. Using the new and quick algorithms we determined for too [], [], []. Figure 25.6 contains the number of good sequences for , and also for .

Testing of the pairing sport property at cautious allocation of the draws

Sport-Test investigated, whether the scores allow to include draws into the sport matrix.

Let us consider the sport sequence . In a unique way we get the sport matrix

Here has no partners to make two draws, therefore is not a football sequence. Using the Havel-Hakimi algorithm [], [], [] we can try to pair the draws of any sport matrix. If we received the sport matrix in a unique way, and Havel-Hakimi algorithms can not pair the draws, then the investigated sequence is not a football sequence.

Now consider the football sequence , which is the result of a tournament of 7 weak, 14 medium and 7 strong teams. the weak player play draws among themselves and loss against the medium and strong teams. The medium teams form a transitive subtournament and loss against the strong teams. The strong teams play draws among themselves. We perturbate this simple structure: one of the weak teams wins against the best medium team instead of to lost the match. There are 42 draws in the tournament, therefore the sum of the multiplicities of the sport matrix has to be 84. A uniform distribution results for all determining the sport matrix in a unique way.

Let us consider the matches in the subtournament of . This subtournament consists of 21 matches, from which at most can end with draw, therefore at least matches have a winner, resulting at least inner points. But the seven teams have only points signalizing that that the given sport matrix is not a football matrix.

In this case the concept of inner draws offers a solution. Since and , the teams made at least 9 draws among themselves. “Cautious” distribution results a draw sequence , which can be paired easily. Then we can observe that , while , so the teams have to made at least 18 draws. Cautious distribution results a draw sequence . Havel-Hakimi algorithm finishes the pairing with the draw sequence (2,2), so 2 draws remain unpaired. If we assign a further draw pack to this subtournament, then the uniform distribution results the draw sequence consisting of 13 draw packs instead of 12. Since is an odd number, this draw sequence is unpairable—the subtournament needs at least one outer draw.