25.9. 25.9 Reconstruction of the tested sequences

The reconstruction begins with the study of the inner draws. Let us consider the following sequence of length 28: . This is the score sequence of a tournament, consisting of seven weak, 14 medium and 7 strong teams. The weak teams play only draws among themselves, the medium teams win against the weak teams and form a transitive subtournament among themselves, the strong teams win against the weak and medium teams and play only draws among themselves. Here a good management of obligatory draws is necessary for the successful reconstruction.

In general the testing of the realizabilty of the draw sequence of a sport matrix is equivalent with the problem to decide on a given sequence of nonnegative integers whether there exists a simple nondirected graph whose degree sequence is .

Let us consider the following example: . This is the score sequence of a tournament of 4 “week”, 8 “medium” and 4 “strong” teams. The week teams and also the strong teams play only draws among themselves. The medium teams win against the weak ones and the strong teams win against the medium ones. wins again , wins against , wins against , and wins against , and the remaining matches among weak and strong teams end with draw.

In this case the 16 teams play 120 matches, therefore the sum of the scores has to be between 240 and 360. In the given case the sum is 336, therefore the point matrix has to contain 96 wins and 24 draws. So at uniform distribution of draws every team gets exactly one draw pack.

How to reconstruct this sequence? At a uniform distribution of the draw packs we have to guarantee the draws among the weak teams. The original results imply nonuniform distribution of the draws but it seems not an easy task to find a quick and successful method for a nonuniform distribution.

Exercises

25.9-1 How many monoton sequence is possible in a football tournament with 5 teams?

25.9-2 How many sportmatrix is possible in a football tournament with 5 teams?

  PROBLEMS  

25-1 FOOTBALL SCORE SEQUENCES

Design a program generating all football sequences of length 6. Implement your program.

25-2 DRAW SEQUENCES

Design a program which generates all draw sequences of a tournament with teams.

  CHAPTER NOTES  

A nondecreasing sequence of nonnegative integers is a score sequence of a -tournament, if and only if the sum of the elements of equals to and the sum of the first elements of is at least [ 159 ].

is a score sequence of a -tournament, iff the sum of the elements of equals to , and the sum of the first elements of is at least [ 144 ], [ 183 ].

is a score sequence of an -tournament, if and only if (25.17) holds [ 127 ].

In all 3 cases the decision whether is digraphical requires only linear time.

In this paper the results of [ 127 ] are extended proving that for any there exists an optimal minimax realization , that is a tournament having as its outdegree sequence and maximal and minimal in the set of all realization of . There are further papers on imbalances in different graphs [ 140 ], [ 187 ], [ 214 ], [ 215 ], [ 212 ], [ 246 ].

Many efforts was made to enumerate the different types of degree and score sequences and connected with them sequences, e.g. by Ascher [ 11 ], Barnes and Savage [ 18 ], [ 19 ], Hirschhorn and Sellers [ 112 ], Iványi, Lucz and Sótér [ 131 ], [ 130 ], Metropolis [ 176 ], Rodseth, Sellers and Tverberg [ 241 ], Simion [ 254 ], Sloane and Plouffe [ 255 ], [ 256 ], [ 259 ], [ 258 ], [ 257 ].

You can find many references in [ 127 ], [ 128 ], [ 130 ].

Acknowledgement. The author thanks András Frank (Eötvös Loránd University) for valuable advices concerning the application of flow theory, further Péter L. Erdős (Alfréd Rényi Institute of Mathematics of HAS) and Zoltán Kása (Sapientia Hungarian University of Transylvania) for the consultation.

The research of the first author was supported by the European Union and the European Social Fund under the grant agreement no. TÁMOP 4.2.1/B-09/1/KMR-2010-0003.