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 [ 155 ].

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 [ 168 ]) 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 [ 168 ]) 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 [ 159 ].

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 [ 127 ][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 [ 168 ]) A football sequence is loss satisfying.

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

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 [ 168 ]) 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 [ 168 ]) 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 [ 168 ]) 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 [ 168 ]) 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 [ 130 ]) 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 [ 100 ], [ 109 ], [ 166 ].

Theorem 25.49 (Havel [ 109 ], Hakimi [ 100 ]) 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 [ 100 ], [ 109 ].

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 [ 130 ]) 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 [ 71 ].

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

and

Proof. See [ 52 ], [ 71 ], [ 253 ], [ 275 ].

Recently we could improve this theorem [ 130 ]. 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 [ 130 ]) 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 [ 129 ], Iványi, Lucz, Sótér [ 130 ]) 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 [ 256 ]. Using the new and quick algorithms we determined for too [ 129 ], [ 130 ], [ 131 ]. Figure 25.6 contains the number of good sequences for , and also for .

Figure 25.6.  Number of binomial, head halfing and good sequences, further the ratio of the numbers of good sequences for neighbouring values of Number of binomial, head halfing and good sequences, further the ratio of the numbers of good sequences for neighbouring values of n ..

Number of binomial, head halfing and good sequences, further the ratio of the numbers of good sequences for neighbouring values of n .

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

Figure 25.7.  Sport table belonging to the sequence Sport table belonging to the sequence q=(2,3,3,9) ..

Sport table belonging to the sequence q=(2,3,3,9) .

Here has no partners to make two draws, therefore is not a football sequence. Using the Havel-Hakimi algorithm [ 100 ], [ 109 ], [ 166 ] 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.