\documentclass[dvips,10pt,b5paper]{book}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[dvips]{graphicx}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{multirow}
\usepackage{enumerate}
\usepackage{AlgofInfColor19March2011}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Automata
\usepackage{emlines,emlines2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Compilers
\usepackage[emtex,dvips,all]{xy}
\usepackage{hhline}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Reliable
\usepackage{enumerate}
\usepackage{amsmath,amssymb}
\addtocounter{part}{0}
\addtocounter{chapter}{24}
\setcounter{page}{1250}
\setcounter{tocdepth}{2}
\topmargin -10mm
\oddsidemargin 0.0in
\evensidemargin 0.0in
\makeindex
\sloppy
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\Zset{\mathbb{Z}}
\begin{document}
\tableofcontents
\chapter{ Comparison Based Ranking\label{chapterComparison}}
\noindent In practice often appears the problem, how to rank different objects.
Researchers of these problems frequently mention different applications, e.g. in biology
Landau\nevindex{Landau, H. G.} \cite{Landau1953}, in chemistry Hakimi\nevindex{Hakimi, S. Louis}
\cite{Hakimi1962}, in networks Kim,\nevindex{Kim, Hyunje} Toroczkai,\nevindex{Toroczkai, Zoltán}
Miklós,\nevindex{Miklós, István} Erdős,\nevindex{Erdős, Péter László} and Székely\nevindex{Székely, László Aladár}
\cite{KimTMESz2009}, Newman and Barabási \cite{NewmanB2006},
in comparison based decision making Bozóki,\nevindex{Bozóki, Sándor} Fülöp,\nevindex{Fülöp, János}
Kéri,\nevindex{Kéri, Gerzson} Poesz,\nevindex{Poesz, Attila} Rónyai\nevindex{Rónyai, Lajos} and
Kéri\nevindex{Kéri, Gerzson} \cite{BozokiFP2011,BozokiFR2010,Keri2005},
in sports Iványi,\nevindex{Iványi, Antal Miklós}
Pirzada,\nevindex{Pirzada, Shariefuddin} and Zhou\nevindex{Zhou, Guofei} \cite{Ivanyi2009,Ivanyi2010,
IvanyiLS2011AML,IvanyiLS2011Acta,PirzadaIK2011,PirzadaZI2010}.
\nevindex{Lucz, Loránd}\nevindex{Sótér, Péter}
A popular method is the comparison of two---and sometimes more---objects in all possible manner and
distribution some amount of points among the compared objects.
In this chapter we introduce a general model for such ranking and study some connected problems.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction to supertournaments\label{secIntroductiontosuper}}
Let $n$, $m$ be positive integers, $\mathbf{a} = (a_1,a_2,\ldots,a_m)$, $\mathbf{b} = (b_1,b_2,\ldots,b_m)$ and
$\mathbf{k} = (k_1,k_2,\ldots,k_m)$ vectors of nonnegative integers with $a_i \leq b_i \ (i = 1, 2, \ldots, m)$
and $0 < k_1 < k_2 < \cdots < k_m.$
An \ki{$(\mathbf{a,b,k},m,n)$-supertournament}\inddef{abkmnsupertournament@$(\mathbf{a,b,k},m,n)$-supertournament}
is an $x \times n$ sized matrix $\mathcal{M}$, whose columns correspond
to the players of the tournament (they represent the rankable objects)
and the rows correspond to the comparisons of the objects. The permitted elements of $\mathcal{M}$
belong to the set $\{0,1,2,\ldots,b_{max}\} \cup \{ * \}$, where $m_{ij} = *$ means, that the player $P_j$ is
not a participants of the match corresponding to the $i$-th line, $m_{ij} = k$ means, that $P_j$
received $k$ points in the match corresponding to the $i$-th line, and $b_{max} = \max_{1\leq i\leq n} b_i$.
The sum (dots are taken in the count as zeros) of the elements of the $i$-th column of $\mathcal{M}$ is denoted
by $d_i$ and is called
\ki{the score}\inddef{score} of the $i$th player P$_i:$
\begin{equation}
d_i = \sum _{j=1}^x m_{ij} \quad (i = 1, \ldots, x).
\end{equation}
The sequence $\mathbf{d} = (d_1,\ldots,d_n)$ is called the \ki{score vector}\inddef{score vector} of the tournament.
The increasingly ordered sequence of the scores is called the
\ki{score sequence}\inddef{the score sequence} of the tournament and is denoted by $\mathbf{s} = (s_1,\ldots,s_n).$
Using the terminology of the sports a supertournament can combine the matches of different sports.
For example in Hungary there are popular chess-bridge,\index{chess-bridge tournament}
chess-tennis\index{chess-tennis tournament} and tennis-bridge tournaments.\index{tennis-bridge tournament}
A sport is characterized by the set of the permitted results. For example in tennis the set of permitted results
is $S_{\textrm{tennis}} = \{0:1\}$, for chess is the set $S_{\textrm{chess}} = \{0:2,1:1\}$, for football is the set
$S_{\textrm{football}} = \{0:3,1:1\}$ and in the Hungarian card game last trick is
$S_{\textrm{last trick}} = \{(0,1,1),(0,0,2)$. There are different possible rules for an individual
bridge tournament, e.g. $S_{\rm{bridge}} = \{(0,2,2,2),(1,1,1,3)\}$.
The number of participants of a match of a given sport $S_i$
is denoted by $k_i$, the minimal number of the distributed points in a match is denoted by $a_i$,
and the maximal number of points is denoted by $b_i$.
If a supertournament consists of only the matches of one sport, then we use $a, \ b$ and $k$ instead of
vectors $\mathbf{a}, \ \mathbf{b},$ and $\mathbf{k}$ and omit the parameter $m$.
When the number of the players is not important, then the parameter $n$ is also omitted.
If the points can be divided into arbitrary integer partitions, then the given sport is called
\ki{complete},\inddef{complete sport} otherwise it is called \ki{incomplete}.\inddef{incomplete sport}
According to this definitions chess is a complete (2,2)-sport, while football is an incomplete (2,3)-sport.
Since a set containing $n$ elements has $\textbinom{n}{k}$ $k$-element subsets, an $(a,b,k)$-tournament consists of
$\textbinom{n}{k}$ matches. If all matches are played, then the tournament is
\ki{finished,}\inddef{finished tournament} otherwise it is \ki{partial}.\inddef{partial tournament}
In this chapter we deal only with finished tournaments and mostly with complete tournaments (exception is only the section on football).)
Figure \ref{fig30-example} contains the results of a full and complete chess+last trick+bridge supertournament.
In this example $n = 4,$ $\mathbf{a} = \mathbf{b} = (2,2,6), \mathbf{k} = (2,3,4),$
and $x = \textbinom{4}{2} + \textbinom{4}{3} + \textbinom{4}{4} = 11.$ In this example the score vector
of the given supertournament is $(7,3,8,10)$, and its score sequence is $(3,7,8,10)$.
\begin{figure}[!t]
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
match/player & P$_1$ & P$_2$ & P$_3$ & P$_4 $ \\ \hline
P$_1$-P$_2$ & $1$ & $1$ & * & * \\ \hline
P$_1$-P$_3$ & $0$ & * & $2$ & * \\ \hline
P$_1$-P$_4$ & $0$ & * & * & $2$ \\ \hline
P$_2$-P$_3$ & * & $0$ & $2$ & * \\ \hline
P$_2$-P$_4$ & * & $0$ & * & $2$ \\ \hline
P$_3$-P$_4$ & $*$ & * & $1$ & $1$ \\ \hline \hline
P$_1$-P$_2$-P$_3$ & $1$ & $1$ & $0$ & * \\ \hline
P$_1$-P$_2$-P$_4$ & $1$ & $0$ & * & $2$ \\ \hline
P$_1$-P$_3$-P$_4$ & $1$ & * & $1$ & $0$ \\ \hline
P$_2$-P$_3$-P$_4$ & * & $0$ & $0$ & $2$ \\ \hline \hline
P$_1$-P$_2$-P$_3$-P$_4$& $3$ & $1$ & $1$ & $1$ \\ \hline \hline
Total score & $7$ & $3$ & $8$ & $10$ \\ \hline \hline
\end{tabular} \\
\caption{Point matrix of a chess+last trick-bridge tournament with $n = 4$ players.\label{fig30-example}}
\end{center}
\vspace{-2mm}
\end{figure}
In this chapter we investigate the problems connected with the existence and construction of different types
of supertournaments having prescribed score sequences.
At first we give an introduction to $(a,b)$-tournaments (Section \ref{sec25-2}),
then summarize the results on (1,1)-tournaments (Section \ref{sec25-3}), then
for $(a,a)$-tournaments (Section \ref{sec25-4}) and for general $(a,b)$-tournaments (Sections \ref{sec25-5}.
In Section \ref{sec25-6} we deal with imbalance sequences,\index{imbalance sequence} and in Section
\ref{sec25-7} with supertournaments.\index{supertournament} Finally in Section \ref{sec25-8}
we investigate special incomplete tournaments (football tournaments).\index{football tournament}
\begin{gyak}
\ujgyak Describe known and possible multitournaments.
\ujgyak Estimate the number of given types of multitournaments.
\end{gyak}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction to $(a,b)$-tournaments\label{sec25-2}}
Let $a, \ b \ (b \geq a)$ and $n \ (n \geq 2)$ be nonnegative integers and let $\mathcal{T}(a,b,n)$
be the set of such generalised
tournaments, in which every pair of distinct players is connected at most with $b$, and
at least with $a$ arcs. The elements of
$\mathcal{T}(a,b,n)$ are called \ki{$(a,b,n)$-tournaments.}\inddef{abn-tournament@$(a,b,n)$-tournament}
The vector $D = (d_1, d_2, \ldots, d_n)$ of the outdegrees of
$T \in \mathcal{T}(a,b,n)$ is called \ki{the score vector}\inddef{score vector} of $T$.
If the elements of $D$ are in nondecreasing order,
then $D$ is called the \ki{score sequence}\inddef{score set} of $T$.
An arbitrary vector $\mathbf{d} = (d_1, d_2, \ldots, d_n)$ of nonnegative integers is called
\ki{graphical vector,}\inddef{graphical vector} iff there exists a
loopless multigraph whose degree vector is $\mathbf{d}$, and $\mathbf{d}$ is called
\ki{digraphical vector}\inddef{digraphical vector} (or \textit{score vector}) iff there
exists a loopless directed multigraph whose outdegree vector is $\mathbf{d}.$
A nondecreasingly ordered graphical vector is called \ki{graphical sequence,}\inddef{graphical sequence}
and a nondecreasingly ordered digraphical vector is called \ki{digraphical sequence}\inddef{digraphical sequence}
(or \textit{score sequence}).
The number of arcs of $T$ going from player P$_i$ to player P$_j$ is denoted by $m_{ij} \ (1 \leq i,j \leq n)$, and
the matrix $\mathcal{M} = [1. \ .n,1 . \ .n]$ is called the \ki{point matrix}\inddef{point matrix} or
\textit{tournament matrix} of $T$.
In the last sixty years many efforts were devoted to the study of both types of vectors, resp. sequences.
E.g. in the papers \cite{Berge1976,ErdosG1960,FrankGy1978,Griggs2004,Hakimi1962,Hakimi1965,Hakimi1974,Havel1955,
Katona1966,Patrinos1976,Senior1951,Sierksma1991,Szekely1992,
TripathiV2003,WangZ2008} the graphical sequences,
while in the papers \cite{AcostaB2011,Avery1991,BangS1979,Berge1976,BrualdiS2001,
FordF1962,Gervacio1988,Gervacio1993,GriggsR1999,Guiduli1998,Hakimi1965,Hemasinha2003,Kleitman1973,Kleitman1981,
Landau1953,Mahmoodian1978,Moon1962,Moon1963,Moon1968,Narayana1964,Narayana1971,Ore1956I,Ore1956II,Ore1958,
Pecsy2000,Reid1996,Reid1998,Ruskey1994,vandenBrink2003,WangK1973,Winston1983}
the score sequences were discussed.
Even in the last two years many authors investigated the conditions, when $D$ is graphical (e.g.
\cite{BarrusKH2008,BoeschH1976,BrualdiK2009,ChungG2008,Frank2008Mat1,Frank2008Mat2,FrankLSz2008,
Frank2009,Hu2009,HulettWW2008,Jordon2009,KimTMESz2009,
Klivans2008,Klivans2009,MeierlingV2009,MiklosES2011,Pirzada2009,PirzadaCN2009,RodsethST2009,TripathiT2008,
vandenBrink2009,Volkmann2009,Weisstein2011DS,Weisstein2011GS,Yin2008})
or digraphical (e.g. \cite{BeasleyBR2009,HarborthK1962,Ivanyi2009,KemnitzD1997,Knuth2011,Lovasz2007,
NabiyevP2008,Palvolgyi2009,PirzadaSS20082di,PirzadaSS2008Ineq,PirzadaSS2008orient,
PirzadaZ2008,Ryser1964,SameeMPN2007,Thomassen1981,ZhouP2008}).
It is worth to mention another interesting direction of the study of different kinds of tournament,
the score sets\index{score set} \cite{PirzadaIK2011}
In this chapter we deal first of all with directed graphs and usually follow the terminology used by
K. B. Reid \cite{Reid2004,Reid1998}.
If in the given context $a, \ b$ and $n$ are fixed or non important, then we speak simply on
\textit{tournaments} instead of generalized or $(a,b,n)$-tournaments.
The first question: how one can characterise the set of the score sequences of the $(a,b,n)$-tournaments.
Or, with another words, for which sequences $\mathbf{q}$ of nonnegative integers does exist an $(a,b,n)$-tournament
whose outdegree sequence is $\mathbf{q}.$ The answer is given in Section \ref{sec-25-5}.
If $T$ is an $(a,b,n)$-tournament with point matrix $\mathcal{M} = [1. \ .n,1 . \ .n]$,
then let $E(T), \ F(T)$ and $G(T)$ be defined as follows: $E(T) = \max_{1\leq i,j\leq n} m_{ij}$,
$F(T) = \max_{1\leq i < j\leq n} (m_{ij} + m_{ji})$, and $g(T) = \min_{1\leq i < j\leq n} (m_{ij} + m_{ji})$.
Let $\Delta(D)$ denote the set of all tournaments having $D$ as
outdegree sequence, and let $e(D), \ f(D)$ and $g(D)$ be defined as follows:
$e(D) = \{\min \ E(T) \ | \ T \in \Delta(D)\}$, $f(D) = \{\min \ F(T) \ | \ T \in \Delta(D)\}$, and
$g(D) = \{\max \ G(T) \ | \ T \in \Delta(D)\}$. In the sequel we use the short notations
$E, \ F, \ G, \ e, \ f, \ g,$ and $\Delta$.
Hulett,\nevindex{Hulett, H.} Will,\nevindex{Will, T. G.} and
Woeginger\nevindex{Woeginger, Gerhard J.} \cite{HulettWW2008,Will2004}, Kapoor,\nevindex{Kapoor, S. F.}
Polimeni,\nevindex{Polimeni, A. D.} and Wall\nevindex{Wall, C. E.} \cite{KapoorPW1977}, and Tripathi et al.
\cite{TripathiV2006,TripathiT2008} investigated the construction problem of a minimal size graph having a
prescribed degree set \cite{Reid1978,Yao1989}.
In a similar way we follow a mini-max approach formulating the following questions:
given a sequence $\mathbf{q}$ of nonnegative integers,
\begin{itemize}
\item How to compute $e$ and how to construct a tournament $T \in \Delta$ characterised by $e$? In Subsection
\ref{subsec-25-53} a formula to compute $e,$ and an algorithm to construct a corresponding tournament are presented.
\item How to compute $f$ and $g$? In Subsection \ref{subsec-25-55} an algorithm to compute $f$ and $g$ is described.
\item How to construct a tournament $T \in \Delta$ characterised by $f$ and $g$? In Section \ref{subsec-25-59}
an algorithm to construct a corresponding tournament is presented and analysed.
\end{itemize}
We describe the proposed algorithms in words, by examples and by the pseudocode used in \cite{CormenLRS2009}.
2
In the following sections we characterize the score sequences of $(1,1)$-tournaments in Section \ref{sec25-3},
then the score sequences of $(a,a)$-tournaments in Section \ref{sec25-4}. In Section \ref{sec25-5} we show that
for arbitrary increasingly ordered sequence of integers$\mathbf{q}$ we can choose suitable $a$ and $b$ such, that
there exists an $(a,b)$-tournament whose score sequence is $\mathbf{q}$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Existence of $(1,1,n)$-tournaments with prescribed score sequence\label{sec25-3}}
The simplest supertournament is the classical tournament, in our notation the $(1,1,n)$-tournament.
Now, we give the characterization of score sequences of tournaments which is due to
Landau\nevindex{Landau, H. G.} \cite{Landau1953}. This result has attracted quite a bit of attention
as nearly a dozen different proofs appear in the literature.
Early proofs tested the readers patience with special choices of subscripts, but eventually such gymnastics
were replaced by more elegant arguments. Many of the existing proofs are discussed in a survey written
by K. Brooks Reid\nevindex{Reid, K. Brooks} \cite{Reid1996}. The proof we give here is due to
Thomassen\nevindex{Thomassen, Carsten}
\cite{Thomassen1981}. Further, two new proofs can be found in in the paper due to
Griggs\nevindex{Griggs, J.} and Reid \cite{GriggsR1999}.
\begin{tetel} \emph{(Landau \cite{Landau1953})} A\label{theorem-Landau} sequence of nonnegative integers
$q = (q_1,\ldots,q_n)$ is the score vector of a $(1,1,n)$-tournament
if and only if for each subset $I \in \{1,\ldots,n \}$
\begin{equation}
\sum _{i \subseteqq I} q_i \geq \binom {|I|}{2},\label{eq-Landauvec}
\end{equation}
with equality when $|I| = n$.
\end{tetel}
This theorem, called Landau theorem is a nice necessary and sufficient condition, but its direct
application can require the test of exponential number of subsets.
If instead of the nonordered vector we consider a nondecreasingly ordered sequence $q = (q_1,\ldots,q_n),$
then due to the monotonity $q_1 \leq \cdots q_n$ the inequalities (\ref{eq-Landauvec})
called Landau inequalities, we get its following consequence.
\begin{kov} A nondecreasing sequence of nonnegative integers $\mathbf{q} = (q_1,$ \linebreak
\noindent $\ldots, q_n)$ is the score sequence of some $(1,1,n)$-tournament, iff
\begin{equation}
\sum_{i=1}^k q_i \geq \binom{k}{2}\label{eq-Landausec}
\end{equation}
for $i = 1, \ \ldots, \ n$ with equality for $k = n.$
\end{kov}
\begin{biz}
\textbf{Necessity} If a nondecreasing sequence of nonnegative integers $\mathbf{q}$ is the score sequence of
an $(1,1,n)$-tournament $T,$, then the sum of the first $k$ scores in the sequence counts exactly
once each arc in the subtournament $W$ induced by $\{v_1,\ldots,v_k\}$
plus each arc from $W$ to $T - W.$ Therefore the sum is at least $\frac{k(k - 1)}{2}$,
the number of arcs in $W$. Also, since the sum of the scores of the vertices counts each arc
of the tournament exactly once, the sum of the scores is the total number of arcs, that is,
$\frac{n(n-1)}{2}$.
\textbf{Sufficiency} (Thomassen \cite{Thomassen1981}) Let $n$ be the smallest integer for which there is
a nondecreasing sequence $\mathbf{s}$ of nonnegative integers satisfying Landau's conditions (\ref{eq-Landau-sec}),
but for which there is no $(1,1,n)$-tournament with score sequence $\mathbf{s}$. Among all such $\mathbf{s}$,
pick one for which $\mathbf{s}$ is as lexicografically small as possible.
First consider the case where for some $k < n$,
\begin{equation}
\sum_{i=1}^k s_i = \binom{k}{2}.
\end{equation}
By the minimality of $n$, the sequence $\mathbf{S}_1 = [s_1,\ldots,s_k]$ is the score sequence of some tournament
$T_1.$ Further,
\begin{equation}
\sum _{i=1}^m (s_{k+i}-k) = \sum _{i=1}^{m+k} s_i - mk \geq \binom{m+k}{2} - \binom{k}{2} - mk = \binom{m}{2},
\end{equation}
for each $m, \ 1 \leq m \leq n - k,$ with the equality when $m = n - k.$ Therefore, by the minimality of
$n,$ the sequence $\mathbf{S}_2 = [s_{k+1} - k, s_{k+2 -k}, \ldots, s_n - k]$ is the score sequence
of some tournament $T_2$. By forming the disjoint union of $T_1$ and $T_2$ and adding all arcs from $T_2$
to $T_1,$ we obtain a tournament with score sequence $\mathbf{s}.$
Now, consider the case where each inequality in (\ref{eq-Landausec}) is strict when $k < n$ (in particular
$q_1 > 0)$. Then the sequence $\mathbf{S}_3 = [q_1 - 1, \ldots, q_{n-1},q_n + 1]$
satisfies (\ref{eq-Landausec} and by the minimality of $q_1$, $\mathbf{S}_3$ is the score sequence of some tournament
$T_3$. Let $u$ and $v$ be the vertices with scores $q_n +1$ and $q_1 - 1$ respectively. Since the score
of $u$ is larger than that of $v,$ then according to Lemma \ref{lemma-Thomassen} $T_3$ has a path
$P$ from $u$ to $v$ of length $\leq 2$.
By reversing the arcs of $P,$ we obtain a tournament with score sequence $\mathbf{s},$ a contradiction.
\end{biz}
Landau's theorem is the tournament analog of the Erdős-Gallai theorem for graphical sequences
\cite{ErdosG1960}. A tournament analog of the Havel-Hakimi theorem \cite{Havel1955,Hakimi1963}
for graphical sequences is the following result, the proof of which can be found in
the paper of Reid and Beineke \cite{ReidB1979}.\nevindex{Reid, K. Brooks},\nevindex{Beineke, L. W.}
\begin{tetel} \emph{(Reid, Beineke, \cite{ReidB1979})} A nondecreasing sequence $[q_1,\ldots,q_n]$
of nonnegative integers, $n \geq 2$, is the score sequence of an $(1,1,n)$-tournament if and only if
the new sequence
\begin{equation}
(q_1,\ldots,q_{q_n},q_{q_n + 1}-1, \ldots, q_{n-1} - 1),
\end{equation}
when arranged in nondecreasing order, is the score sequence of some $(1,1,n-1)$-tournament.
\end{tetel}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Existence of an $(a,a)$-tournament with prescribed score sequence\label{sec25-4}}
For the $(a,a)$-tournament Moon \cite{Moon1963} proved the following extension of Landau's theorem.
\begin{tetel} \emph{(Moon \cite{Moon1963}, Kemnitz, Dulff \cite{KemnitzD1997}} A\label{theorem-Kemnitz}
nondecreasing sequence of nonnegative integers $q = (q_1,\ldots,q_n)$
is the score sequence of an $(a,a,n)$-tournament if and only if
\begin{equation}
\sum_{i=1}^k q_i \geq a \binom{k}{2},\label{eq-Kemnitz}
\end{equation}
for $i = 1, \ \ldots, \ n$ with equality for $k = n.$
\end{tetel}
\begin{biz} See \cite{KemnitzD1997,Moon1963}.
\end{biz}
Later Kemnitz and Dulff \cite{KemnitzD1997} reproved this theorem.
The proof ot Kemnitz and Dulff is based on the following lemma, which is an extension of a lemma
due to Thomassen \cite{Thomassen1981}.
\begin{lemma} Let\label{lemma-Thomassen} $u$ be a vertex of maximum score in an $(a,a,n)$-tournament $T.$
If $v$ is a vertex of $T$ different from $u,$ then there is a directed path $P$ from $u$ to $v$ of lenth at most 2.
\end{lemma}
\begin{biz} Let $v_1,\ldots,v_l$ be all vertices of $T$ such that $(u,v_i) \in E(T), \ i = 1,\ldots,l.$ If
$v \in \{v_1,\ldots,v_l\}$ then $|P| = 1$ for the length $|P|$ of path $P.$ Otherwise if there exists a vertex
$v_i, \ 1 \leq i \leq l,$ such that $(v_i,v) \in E(T)$ then $|P| = 2.$ If for all
$i, \ 1 \leq i \leq l$ $(v_i,v) \notin E(T)$ then there are $k$ arcs $(v,v_i) \in T$ which implies
$d^+(v) \geq kl + k > kl \geq d^+ u,$ a contradiction to the assumption that $u$ has maximum score.
\end{biz}
\textcolor{magenta}{\textbf{Proof}} \textbf{of Theorem \ref{theorem-Kemnitz}.} The necessity of condition
(\ref{eq-Kemnitz}) is obvious since there are $a\textbinom{k}{2}$ arcs among any $k$ vertices and
there are $a\textbinom{k}{2}$ arcs among all $n$ vertices.
To prove the sufficiency of (\ref{eq-Kemnitz}) we assume that the sequence $S_n = (s_1,\ldots,s_n)$ is a
counterexample to the theorem with minimum $n$ and smallest $s_1$ with that choice of $n.$
Suppose first that there exists an integer $m, \ 1 \leq m < n,$ such that
\begin{equation}
\sum _{i = 1}^m s_i = k \binom{k}{2}. \label{eq-Kemnitz1}
\end{equation}
Because the minimality of $n,$ the sequence $(s-1,\ldots,s_n)$ is the score sequence of some $(1,1,n)$-tournament
$T_1.$
Consider the sequence $R_{n-m} = (r-1,r_2,\ldots,r_{n-m})$ defined by $r_i = s_{m+1} - km,$ $i =1,\ldots,n-m.$
because of $\sum _{i=1}^{m+1} s_i \geq k \textbinom{m+1}{2}$ by assumption it follows that
$$
s_{m + 1} = \sum _{i=1} ^{m + 1} s_i - \sum _{i=1} ^m s_i \geq k\binom{m + 1}{2}
- k\binom{m}{2} - km\label{eq-Kemnitz2}
$$
which implies $r_i \geq 0.$ Since $S_n$ is nondecreasing also $R_{n-m}$ is a nondecreasing sequence of
nonnegative integers.
For each $l$ with $1 \leq l \leq n - m$ it holds that
\begin{equation}
\sum _{i=1}^l r_i = \sum _{i=1}^l (s_{m+1} - km) = \sum _{i=1}^{l +m} s_i - \sum _{i=1}^m s_i - lam \geq
k\binom{l + m}{2} - k\binom{m}{2} - lam = k\binom{l}{2}\label{eq-Kemnitz3}
\end{equation}
with equality for $l = n - m$ since by assumption
\begin{equation}
\sum _{i=1}^{l+m} s_i \geq a\binom{l + m}{2}, \quad \sum _{i=1}^m s_i = a \binom{m}{2}.\label{eq-Kemnitz4}
\end{equation}
Therefore the sequence $R_{n - m}$ fulfils condition (\ref{eq-Kemnitz1}), by the minimality of $n,$ $R_{n - m}$
is the score sequence of some $(a,a,n-m)$-tournament $T_2.$ By forming the disjoint union of $T_1$ and
$T_2$ we obtain a $(a,a,n)$-tournament $T$ with score sequence $S_n$ in contradiction to the assumption that $S_n$
is counterexample.
Now we consider the case that the inequality in condition (\ref{eq-Kemnitz1}) is strict
for each $m,$ $1 \leq m < n.$ This implies in particular $s_1 > 0.$
The sequence $\overline{S}_n = (s-1,s_2,s_3,\ldots,s_{n-1},s_n)$ is a nondecreasing sequence of
nonnegative integers which fulfils condition (\ref{eq-Kemnitz1}). Brecause of the minimality of $S_n,$
$\overline{S}_n$ is the score sequence of some $(a,a,n)$-tournament $T_3.$ Let $u$denote a vertex of
$T_3$ with score $s_n + 1$ and $v$ a vertex of $T_3$ with score $S_1 - 1.$ Since $u$ has maximum score
in $T_3$ there is a directed path $P$ from $u$ to $v$ of length at most 2 according to Lemma
\ref{lemma-Thomassen}. By reversing the arcs of the path $P$ we obtain a $(a,a,n)$-tournament $T$
with score sequence $S_n.$ This contradiction completes the proof. \fkocka
\lineskip=6pt
\noindent\ignorespaces
\vspace{0mm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Existence of an $(a,b)$-tournament with prescribed score sequence\label{sec25-5}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Existence of a tournament with arbitrary degree sequence\label{sec25-51}}
Since the numbers of points $m_{ij}$ are not limited, it is easy to construct a
$(0,d_n,n)$-tournament for any $D$.
\begin{lemma} If $n \geq 2$, then for any\label{lemma-exist} vector of nonnegative integers
$D = (d_1,$ $d_2, \ldots, d_n)$ there exists a loopless directed multigraph $T$ with outdegree vector
$D$ so, that $E \leq d_n$.
\end{lemma}
\begin{biz} Let $m_{n1} = d_n$ and $m_{i,i+1} = d_i$ for $i = 1, 2, \ldots, n - 1$, and let
the remaining $m_{ij}$ values be equal to zero.
\end{biz}
Using weighted graphs it would be easy to extend the definition of the $(a,b,n)$-tournaments
to allow \textit{arbitrary real values} of $a$, $b$, and $D$. The following algorithm
\textsc{Naive-Construct} works without changes also for input consisting of real numbers.
We remark that Ore in 1956 \cite{Ore1956I,Ore1956II,Ore1958} gave the necessary and sufficient conditions
of the existence of a tournament with prescribed indegree and outdegree vectors.
Further Ford and Fulkerson \cite[Theorem11.1]{FordF1962}
published in 1962 necessary and sufficient conditions of the existence of a tournament
having prescribed lower and upper bounds for the indegree and outdegree of the vertices. They results
also can serve as basis of the existence of a tournament having arbitrary outdegree sequence.
\subsection{Definition of a naive reconstructing algorithm\label{subsec-25-52}}
Sorting of the elements of $D$ is not necessary.
\textit{Input}. $n $: the number of players $(n \geq 2)$; \\
$D = (d_1, d_2, \ldots, d_n)$: arbitrary sequence of nonnegative integer numbers.
\textit{Output}. $\mathcal{M} = [1. \ .n,1. \ . n]$: the point matrix of the reconstructed tournament.
\textit{Working variables}. $i, \ j$: cycle variables.
\medskip
\noindent \textsc{Naive-Construct}$(n,D)$\inddef{\textsc{Naive-Construct}}
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
\hspace{-7mm}02 \> \textbf{for} \= $j = 1$ \textbf{to} $n$ \\
\hspace{-7mm}03 \> \> $d_{ij} = 0$ \\
\hspace{-7mm}04 $d_{n1} = d_n$ \\
\hspace{-7mm}05 \textbf{for} \= $i = 1$ \textbf{to} $n - 1$ \\
\hspace{-7mm}06 \> $d_{i,i+1} = d_i$ \\
\hspace{-7mm}07 \textbf{return} $\mathcal{M}$
\end{tabbing}
The running time of this algorithm is $\Theta(n^2)$ in worst case (in best case too). Since the point
matrix $\mathcal{M}$ has $n^2$ elements, this algorithm is asymptotically optimal.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Computation of $e$\label{subsec25-53}}
This is also an easy question. From here we suppose that $D$ is a nondecreasing sequence
of nonnegative integers, that is $0 \leq d_1$ $\leq d_2 \leq \ldots \leq d_n$.
Let $h = \lceil d_n/(n - 1) \rceil $.
Since $\Delta(D)$ is a finite set for any finite score vector $D$,
$e(D) = \min\{E(T) | T \in \Delta(D)\}$ exists.
\medskip
\begin{lemma} \emph{(Iványi \cite{Ivanyi2009})} If $n \geq 2$, then for\label{lemma-e} any sequence
$D = (d_1, d_2,\ldots,d_n)$ there exists a $(0,b,n)$-tournament $T$ such that
\begin{equation}
E \leq h \qquad \hbox{and} \quad b \leq 2h,\label{equation-e}
\end{equation}
and $h$ is the smallest upper bound for $e$, and $2h$ is the smallest possible upper bound for $b$.
\end{lemma}
\begin{biz}
If all players gather their points in a uniform as possible manner, that is
\begin{equation}
\max_{1 \leq j \leq n} m_{ij} - \min _{1 \leq j \leq n, \ i \neq j} m_{ij} \leq 1 \quad
\hbox{ for } i = 1, \ 2, \ \ldots, \ n, \label{equation-uniform}
\end{equation}
then we get $E \leq h$, that is the bound is valid. Since player P$_n$ has
to gather $d_n$ points, the pigeonhole
principle \cite{Bege2007,BegeK2006,DosseyOSV1987} implies $E \geq h$, that is the bound is not improvable.
$E \leq h$ implies $\max_{1 \leq i < j \leq n} m_{ij} + m_{ji} \leq 2h$.
The score sequence $D = (d_1,d_2,\ldots,d_n) = (2n(n -1),2n(n - 1), \ldots,
2n(n - 1))$ shows, that the upper bound $b \leq 2h$ is not improvable.
\end{biz}
\begin{kov} \emph{(Iványi \cite{Ivanyi2010})} If $n \geq 2$, then for\label{corollary-e} any sequence
$D = (d_1, d_2, \ldots ,d_n)$ holds $e(D) = \lceil d_n/(n - 1) \rceil$.
\end{kov}
\begin{biz} According to Lemma \ref{lemma-e} $h = \lceil d_n/(n - 1) \rceil$
is the smallest upper bound for $e$.
\end{biz}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Definition of a construction algorithm\label{subsec-25-54}}
The following algorithm constructs a $(0,2h,n)$-tournament $T$ having $E \leq h$ \ for any $D$.
\textit{Input}. $n $: the number of players $(n \geq 2)$; \\
$D = (d_1, d_2, \ldots, d_n)$: arbitrary sequence of nonnegative integer numbers.
\textit{Output}. $\mathcal{M} = [1. \ .n,1. \ . n]$: the point matrix of the tournament.
\textit{Working variables}. $i, \ j, \ l$: cycle variables; \newline
$k$: the number of the ''larger part`` in the uniform distribution of the points.
\medskip
\noindent \textsc{Pigeonhole-Construct}$(n,D)$\inddef{\textsc{Pigeonhole-Construct}}
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
\hspace{-7mm}02 \> \= $m_{ii} = 0$ \\
\hspace{-7mm}03 \> \> $k = d_i - (n - 1)\lfloor d_i/(n - 1) \rfloor$ \\
\hspace{-7mm}04 \> \textbf{for} \= $j = 1$ \textbf{to} $k$ \\
\hspace{-7mm}05 \> \> $l = i + j \ (\hbox{mod} \ n)$ \\
\hspace{-7mm}06 \> \> $m_{il} = \lceil d_n/(n - 1) \rceil$ \\
\hspace{-7mm}07 \> \textbf{for} \= $j = k + 1$ \textbf{to} $n - 1$ \\
\hspace{-7mm}08 \> \> $l = i + j \ (\hbox{mod} \ n)$ \\
\hspace{-7mm}09 \> \> $m_{il} = \lfloor d_n/(n - 1) \rfloor$ \\
\hspace{-7mm}10 \textbf{return} $\mathcal{M}$
\end{tabbing}
The running time of \textsc{Pigeonhole-Construct} is $\Theta(n^2)$ in worst case (in best case too).
Since the point matrix $\mathcal{M}$ has $n^2$ elements, this algorithm is asymptotically optimal.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Computation of $f$ and $g$\label{subsec-25-55}}
Let $S_i \ (i = 1, \ 2, \ \ldots, \ n)$ be the sum of the first $i$ elements of $D$,
$B_i \ (i = 1, \ 2, \ \ldots, \ n)$ be the binomial coefficient $n(n - 1)/2$.
Then the players together can have $S_n$ points only if $fB_n \geq S_n$.
Since the score of player P$_n$ is $d_n$,
the pigeonhole principle implies $f \geq \lceil d_n/(n - 1) \rceil$.
These observations result the following lower bound for $f$:
\begin{equation}
f \geq \max \left (\left \lceil \frac{S_n}{B_n} \right \rceil, \left \lceil \frac{d_n}{n - 1}
\right \rceil \right)\koz.\label{equation-flowerbound}
\end{equation}
If every player gathers his points in a uniform as possible manner then
\begin{equation}
f \leq 2 \left \lceil \frac{d_n}{n - 1} \right \rceil.\label{equation-fupperbound}
\end{equation}
These observations imply a useful characterisation of $f$.
\begin{lemma} \emph{(Ivanyi2009)}If $n \geq 2,$ then for\label{lemma-fgbounds} arbitrary sequence
$\textbf{d} = (d_1, d_2, \ldots, d_n)$ there exists
a $(g,f,n)$-tournament having $D$ as its outdegree sequence and the following bounds for $f$ and $g$:
\begin{equation}
\max \left ( \left \lceil \frac{S}{B_n} \right \rceil, \left \lceil \frac{d_n}{n - 1} \right
\rceil \right) \leq f \leq 2 \left \lceil \frac{d_n}{n - 1} \right \rceil,\label{equation-flemma}
\end{equation}
\begin{equation}
0 \leq g \leq f.\label{equation-glemma}
\end{equation}
\end{lemma}
\begin{biz}
(\ref{equation-flemma}) follows from (\ref{equation-flowerbound}) and (\ref{equation-fupperbound}), (\ref{equation-glemma})
follows from the definition of $f$.
\end{biz}
It is worth to remark, that if $d_n/(n - 1)$ is integer and the scores are identical, then the lower and upper bounds in
(\ref{equation-flemma}) coincide and so Lemma \ref{lemma-fgbounds} gives the exact value of $F$.
In connection with this lemma we consider three examples.
If $d_i = d_n = 2c(n - 1) \ (c > 0, \ i = 1, \ 2, \ \ldots, \ n - 1)$, then
$d_n/(n - 1) = 2c$ and $S_n/B_n = c$, that is $S_n/B_n$ is twice larger than $d_n/(n - 1)$. In the other extremal case, when
$d_i = 0 \ (i = 1, \ 2, \ \ldots, n - 1)$ and $d_n = cn(n - 1) > 0$, then $d_n/(n - 1) = cn$, $S_n/B_n = 2c$, so $d_n/(n - 1)$ is
$n/2$ times larger, than $S_n/B_n$.
If $D = (0, 0, 0, 40, 40,40)$, then Lemma \ref{lemma-fgbounds} gives the bounds $8 \leq f \leq 16$.
Elementary calculations show that Figure \ref{figure-1} contains the solution with minimal $f$, where $f = 10$.
\begin{figure}[!h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline
Player/Player & P$_1$ & P$_2$ & P$_3$ & P$_4 $ & P$_5$ & P$_5$ & Score \\ \hline
P$_1$ & --- & $0$ & $0$ & $0$ & $0$ & $0$ & $0$ \\ \hline
P$_2$ & $0$ & --- & $0$ & $0$ & $0$ & $0$ & $0$ \\ \hline
P$_3$ & $0$ & $0$ & --- & $0$ & $0$ & $0$ & $0$ \\ \hline
P$_4$ &$10$ & $10$ & $10$ & --- & $5$ & $5$ & $40$\\ \hline
P$_5$ &$10$ & $10$ & $10$ & $5$ & --- & $5$ & $40$ \\ \hline
P$_6$ &$10$ & $10$ & $10$ & $5$ & $5$ & --- & $40$ \\ \hline
\end{tabular} \\
\caption{Point matrix of a $(0,10,6)$-tournament with $f = 10$ for $D = (0,0,0,40,40,40)$.\label{figure-1}}
\end{center}
\vspace{-2mm}
\end{figure}
In \cite{Ivanyi2009} we proved the following assertion.
\begin{tetel} \emph{(Ivanyi2009)} For $n \geq 2$ a\label{theorem-interval} nondecreasing sequence
$D = (d_1, d_2, \ldots, d_n)$ of nonnegative
integers is the score sequence of some $(a,b,n)$-tournament if and only if
\begin{equation}
aB_k \leq \sum_{i = 1}^k d_i \leq bB_n - L_k - (n - k)d_k \quad (1 \leq k \leq n),\label{equation-interval}
\end{equation}
where
\begin{equation}
L_0 = 0, \hbox{ and } L_k = \max \left( L_{k - 1}, \ bB_k - \sum_{i = 1}^{k}
d_i \right ) \quad (1 \leq k \leq n).\label{equation-loss}
\end{equation}
\end{tetel}
The theorem proved by Moon \cite{Moon1963}, and later by Kemnitz and Dolff \cite{KemnitzD1997}
for $(a,a,n)$-tournaments is the special case $a = b$ of Theorem \ref{theorem-interval}.
Theorem 3.1.4 of \cite{IvanyiP2004} is the special case $a = b = 2$. The theorem of
Landau \cite{Landau1953} is the special case $a = b = 1$ of Theorem \ref{theorem-interval}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Definition of a testing algorithm\label{subsec-25-56}}
The following algorithm \textsc{Interval-Test} decides whether a given $D$ is a
score sequence of an $(a,b,n)$-tournament or not. This algorithm is based on Theorem
\ref{theorem-interval} and returns $W = \textsc{True}$ if $D$ is a score sequence, and
returns $W = \textsc{False}$ otherwise.
\medskip
\textit{Input}. $a$: minimal number of points divided after each match; \\
$b$: maximal number of points divided after each match.
\textit{Output}. $W$: logical variable $(W = \textsc{True}$ shows that $D$ is an
$(a,b,n)$-tournament.
\textit{Local working variable}. $i$: cycle variable; \\
$L = (L_0,L_1,\ldots,L_n)$: the sequence of the values of the loss function.
\textit{Global working variables}. $n$: the number of players $(n \geq 2)$; \\
$D = (d_1, d_2, \ldots, d_n)$: a nondecreasing sequence of nonnegative integers; \\
$B = (B_0,B_1,\ldots,B_n)$: the sequence of the binomial coefficients; \\
$S = (S_0,S_1,\ldots,S_n)$: the sequence of the sums of the $i$ smallest scores.
\medskip
\noindent \textsc{Interval-Test}$(a,b)$\inddef{\textsc{Interval-Test}}
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
\hspace{-7mm}02 \> $L_i = \max(L_{i - 1}, \ bB_n - S_i - (n - i)d_i)$ \\
\hspace{-7mm}03 \> \textbf{if} \= $S_i < aB_i$ \\
\hspace{-7mm}04 \> \> $W = \textsc{False}$ \\
\hspace{-7mm}05 \> \> \textbf{return} $W$ \\
\hspace{-7mm}06 \> \> \textbf{if} \= $S_i > bB_n - L_i - (n - i)d_i$ \\
\hspace{-7mm}07 \> \> \> $W \leftarrow \textsc{False}$ \\
\hspace{-7mm}08 \> \> \> \textbf{return} $W$ \\
\hspace{-7mm}09 \textbf{return} $W$
\end{tabbing}
In worst case \textsc{Interval-Test} runs in $\Theta(n)$ time even in the general case $0 < a < b$ (n the best case
the running time of \textsc{Interval-Test} is $\Theta(n)$). It is worth to mention, that the often referenced
Havel--Hakimi algorithm \cite{Hakimi1962,Havel1955} even in the special case $a = b = 1$
decides in $\Theta({n^2})$ time
whether a sequence $D$ is digraphical or not.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Definition of an algorithm computing $f$ and $g$\label{subsec-25-57}}
The following algorithm is based on the bounds of $f$ and $g$ given
by Lemma \ref{lemma-fgbounds} and the logarithmic search
algorithm described by D. E. Knuth \cite[page 410]{Knuth2011}.
\medskip
\textit{Input}. No special input (global working variables serve as input).
\textit{Output}. $b$: $f$ (the minimal $F$); \\
$a$: $g$ (the maximal $G$).
\textit{Local working variables}. $i$: cycle variable; \\
$l$: lower bound of the interval of the possible values of $F$; \\
$u$: upper bound of the interval of the possible values of $F$.
\textit{Global working variables}. $n$: the number of players $(n \geq 2)$; \\
$D = (d_1, d_2, \ldots, d_n)$: a nondecreasing sequence of nonnegative integers; \\
$B = (B_0,B_1,\ldots,B_n)$: the sequence of the binomial coefficients; \\
$S = (S_0,S_1,\ldots,S_n)$: the sequence of the sums of the $i$ smallest scores; \\
$W$: logical variable (its value is \textsc{True}, when the investigated $D$ is a score sequence).
\medskip
\noindent \textsc{MinF-MaxG}\inddef{\textsc{MinF-MaxG}}
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $B_0 = S_0 = L_0 = 0$ \hspace{2.8cm} $\rhd$ Initialization \\
\hspace{-7mm}02 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
\hspace{-7mm}03 \> $B_i = B_{i - 1} + i - 1$ \\
\hspace{-7mm}04 \> $S_i = S_{i - 1} + d_i$ \\
\hspace{-7mm}05 $l = \max (\lceil S_n/B_n \rceil,\lceil d_n/(n - 1) \rceil$) \\
\hspace{-7mm}06 $u = 2 \left \lceil d_n/(n - 1) \right \rceil$ \\
\hspace{-7mm}07 $W = \textsc{True}$ \hspace{3.9cm} $\rhd$ Computation of $f$ \\
\hspace{-7mm}08 \textsc{Interval-Test}$(0,l)$ \\
\hspace{-7mm}09 \textbf{if} \= $W == \textsc{True}$ \\
\hspace{-7mm}10 \> $b = l$ \\
\hspace{-7mm}11 \> \textbf{go to} 21 \\
\hspace{-7mm}12 $b = \lceil (l + u)/2 \rceil $ \\
\hspace{-7mm}13 \textsc{Interval-Test}$(0,f)$ \\
\hspace{-7mm}14 \textbf{if} \= $W == \textsc{True}$ \\
\hspace{-7mm}15 \> \textbf{go to} 17 \\
\hspace{-7mm}16 $l = b$ \\
\hspace{-7mm}17 \textbf{if} \= $u == l + 1$ \\
\hspace{-7mm}18 \> $b = u$ \\
\hspace{-7mm}19 \> \textbf{go to} 37 \\
\hspace{-7mm}20 \textbf{go to} 14 \\
\hspace{-7mm}21 $l = 0$ \hspace{5cm} $\rhd$ Computation of $g$ \\
\hspace{-7mm}22 $u = f$ \\
\hspace{-7mm}23 \textsc{Interval-Test}$(b,b)$ \\
\hspace{-7mm}24 \textbf{if} \= $W == \textsc{True}$ \\
\hspace{-7mm}25 \> $a \leftarrow f$ \\
\hspace{-7mm}26 \> \textbf{go to} 37 \\
\hspace{-7mm}27 $a = \lceil (l + u)/2 \rceil$ \\
\hspace{-7mm}28 \textsc{Interval-Test}$(0,a)$ \\
\hspace{-7mm}29 \textbf{if} \= $W == \textsc{True}$ \\
\hspace{-7mm}30 \> $l \leftarrow a$ \\
\hspace{-7mm}31 \> \textbf{go to} 33 \\
\hspace{-7mm}32 $u = a$ \\
\hspace{-7mm}33 \textbf{if} \= $u == l + 1$ \\
\hspace{-7mm}34 \> $a = l$ \\
\hspace{-7mm}35 \> \textbf{go to} 37 \\
\hspace{-7mm}36 \textbf{go to} 27 \\
\hspace{-7mm}39 \textbf{return} $a,b$
\end{tabbing}
\textsc{MinF-MaxG} determines $f$ and $g$.
\begin{lemma} \emph{(Ivanyi2010)} Algorithm\label{lemma-fg} \textsc{MinG}-\textsc{MaxG}
computes the values $f$ and $g$ for arbitrary sequence
$D = (d_1, d_2,\ldots,d_n)$ in $O(n \log(d_n/(n))$ time.
\end{lemma}
\begin{biz} According to Lemma \ref{lemma-fgbounds} $F$ is an element of the interval
$[\lceil d_n/(n - 1)\rceil, \lceil 2d_n/(n - 1)\rceil]$ and $g$ is an element of the interval $[0,f]$.
Using Theorem B of \cite[page 412]{Knuth2011} we get that $O(\log (d_n/n))$ calls of \textsc{Interval-Test}
is sufficient, so the $O(n)$ run time of \textsc{Interval-Test} implies the required
running time of \textsc{MinF}-\textsc{MaxG}.
\end{biz}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Computing of $f$ and $g$ in linear time\label{subsec-25-58}}
Analysing Theorem \ref{theorem-interval} and the work of algorithm \textsc{MinF-MaxG} one can observe that
the maximal value of $G$ and the minimal value of $F$ can be computed independently by \textsc{Linear-MinF-MaxG}.
\medskip
\textit{Input}. No special input (global working variables serve as input).
\textit{Output}. $b$: $f$ (the minimal $F$). \\
$a$: $g$ (the maximal $G$).
\textit{Local working variables}. $i$: cycle variable.
\textit{Global working variables}. $n$: the number of players $(n \geq 2)$; \\
$D = (d_1, d_2, \ldots, d_n)$: a nondecreasing sequence of nonnegative integers; \\
$B = (B_0,B_1,\ldots,B_n)$: the sequence of the binomial coefficients; \\
$S = (S_0,S_1,\ldots,S_n)$: the sequence of the sums of the $i$ smallest scores.
\medskip
\noindent \textsc{Linear-MinF-MaxG}\inddef{\textsc{Linear-MinF-MaxG}}
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $B_0 = S_0 = L_0 = 0 $ \hspace{2.3 cm} $\rhd$ Initialization \\
\hspace{-7mm}02 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
\hspace{-7mm}03 \> $B_i = B_{i - 1} + i - 1$ \\
\hspace{-7mm}04 \> $S_i = S_{i - 1} + d_i$ \\
\hspace{-7mm}05 $a = 0$) \\
\hspace{-7mm}06 $b = \min 2 \left \lceil d_n/(n - 1) \right \rceil$ \\
\hspace{-7mm}07 \textbf{for} \= $i = 1$ \textbf{to} $n$ \hspace{3.2cm} $\rhd$ Computation of $g$ \\
\hspace{-7mm}08 \> $a_i = \left \lceil (2S_i/(n^2 - n) \right \rceil) < a$ \\
\hspace{-7mm}09 \> \textbf{if} \= $a_i > a$ \\
\hspace{-7mm}10 \> $a = a_i$ \\
\hspace{-7mm}11 \textbf{for} \= $i = 1 \textbf{ to } n$ \hspace{3.5cm} $\rhd$ Computation of $f$ \\
\hspace{-7mm}12 \> $L_i = \max(L_{i - 1},bB_n - S_i - (n - i)d_i$ \\
\hspace{-7mm}13 \> $b_i = (S_i + (n - i)d_i + L_i)/B_i$ \\
\hspace{-7mm}14 \> \textbf{if} \= $b_i < b$ \\
\hspace{-7mm}15 \>$b = b_i$ \\
\hspace{-7mm}16 \textbf{return} $a,b$
\end{tabbing}
\begin{lemma} Algorithm\label{lemma-linfg} \textsc{Linear-MinG-MaxG} computes the values $f$ and $g$
for arbitrary sequence $D = (d_1, d_2,\ldots,d_n)$ in $\Theta(n)$ time.
\end{lemma}
\begin{biz} Lines 01--03, 07, and 18 require only constant time, lines 04--06, 09--12, and 13--17
require $\Theta(n)$ time, so the total running time is $\Theta(n)$.
\end{biz}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Tournament with $f$ and $g$\label{sec25-7}}
The following reconstruction algorithm \textsc{Score-Slicing2} is based on balancing between
additional points (they are similar to ``excess'',
introduced by Brauer et al. \cite{Brauer1968}) and missing points introduced
in \cite{Ivanyi2009}. The greediness of
the algorithm Havel--Hakimi \cite{Hakimi1962,Havel1955} also characterises this algorithm.
This algorithm is an extended version of the algorithm \textsc{Score-Slicing} proposed in \cite{Ivanyi2009}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Definition of the minimax reconstruction algorithm\label{subsec-25-71}}
The work of the slicing program is managed by the following program \textsc{Mini-Max}.
\textit{Input.} $n$: the number of players $(n \geq 2)$; \\
$D = (d_1, d_2, \ldots, d_n)$: a nondecreasing sequence of integers satisfying (\ref{equation-interval}).
\textit{Output}. $\mathcal{M} = [1 \ . \ . \ n,1 \ . \ . \ n]$: the point matrix of the reconstructed tournament.
\textit{Local working variables.} $i, \ j$: cycle variables.
\textit{Global working variables.} $p = (p_0, p_1, \ldots, p_n)$: provisional score sequence; \\
$P = (P_0,P_1,\ldots,P_n)$: the partial sums of the provisional scores; \\
$\mathcal{M}[1 \ . \ . \ n,1 \ . \ . \ n]$: matrix of the provisional points. \\
\medskip
\noindent \textsc{Mini-Max}$(n,D)$\inddef{ \textsc{Mini-Max}}
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 \textsc{MinF}-\textsc{MaxG}$(n,D)$ \hspace{2.5 cm} $\rhd$ Initialization \\
\hspace{-7mm}02 $p_0 = 0$ \\
\hspace{-7mm}03 $P_0 = 0$ \\
\hspace{-7mm}04 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
\hspace{-7mm}05 \> \textbf{for} \= $j = 1$ \textbf{to} $i - 1$ \\
\hspace{-7mm}06 \> \> $\mathcal{M}[i,j] = b$ \\
\hspace{-7mm}07 \> \> \textbf{for} \= $j = i$ \textbf{to} $n$ \\
\hspace{-7mm}08 \> \> \> $\mathcal{M}[i,j] = 0$ \\
\hspace{-7mm}09 \> $p_i = d_i$ \\
\hspace{-7mm}10 \textbf{if} \= $n \geq 3$ \hspace{5.1cm} $\rhd$ Score slicing for $n \geq 3$ players \\
\hspace{-7mm}11 \> \textbf{for} \= $k = n$ \textbf{downto} $3$ \\
\hspace{-7mm}12 \> \> \textsc{Score-Slicing2}$(k)$\\
\hspace{-7mm}13 \textbf{if} \= $n == 2$ \hspace{5.1 cm} $\rhd$ Score slicing for 2 players \\
\hspace{-7mm}14 \> $m_{1,2} = p_1$ \\
\hspace{-7mm}15 \> $m_{2,1} = p_2$ \\
\hspace{-7mm}16 \textbf{return} $\mathcal{M}$
\end{tabbing}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Definition of the score slicing algorithm\label{subsec-25-72}}
The key part of the reconstruction is the following algorithm \textsc{Score-Slicing2} \cite{Ivanyi2009}.
During the reconstruction process we have to take into account the following bounds:
\begin{equation}
a \leq m_{i,j} + m_{j,i} \leq b \quad (1 \leq i < j \leq n);\label{equation-8}
\end{equation}
\begin{equation}
\mbox{modified scores have to satisfy (\ref{equation-interval});}\label{equation-9}
\end{equation}
\begin{equation}
m_{i,j} \leq p_i \ (1 \leq i, \ j \leq n, i \neq j);\label{equation-10}
\end{equation}
\begin{equation}
\mbox{the monotonicity } p_1 \leq p_2 \leq \ldots \leq p_k \mbox{ has to be saved } \ (1 \leq k \leq n)\label{equation-11}
\end{equation}
\begin{equation}
m_{ii} = 0 \quad (1 \leq i \leq n).
\end{equation}
\textit{Input.} $k$: the number of the actually investigated players $(k > 2)$; \\
$p_k = (p_0,p_1,p_2,\ldots,p_k) \ (k = 3, \ 4, \ \cdots, \ n)$: prefix of the provisional score sequence $p$; \\
$\mathcal{M}[1 \ . \ . \ n,1 \ . \ . \ n]$: matrix of provisional points; \\
\textit{Output.}
\textit{Local working variables.} $A = (A_1,A_2,\ldots,A_n)$ the number of the additional points; \\
$M$: missing points: the difference of the number of actual points and the number of maximal possible points of P$_k$;\\
$d$: difference of the maximal decreasable score and the following largest score; \\
$y$: number of sliced points per player; \\
$f$: frequency of the number of maximal values among the scores $p_1, \ p_2,$ \linebreak
\noindent $\ldots, \ p_{k-1}$;\\
$i, \ j$: cycle variables;\\
$m$: maximal amount of sliceable points; \\
$P = (P_0,P_1,\ldots,P_n)$: the sums of the provisional scores; \\
$x$: the maximal index $i$ with $i < k$ and $m_{i,k} < b$.
\textit{Global working variables}: $n$: the number of players $(n \geq 2)$; \\
$B$ = $(B_0,B_1,B_2,\ldots,B_n)$: the sequence of the binomial coefficients; \\
$a$: minimal number of points divided after each match; \\
$b$: maximal number of points divided after each match.
\medskip
\noindent \textsc{Score-Slicing2}$(k)$\inddef{\textsc{Score-Slicing2}}
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 \textbf{for} \= $i = 1$ \textbf{to} $k - 1$ \hspace{1.85 cm} $\rhd$ Initialization \\
\hspace{-7mm}02 \> $P_i = P_{i-1} + p_i$\\
\hspace{-7mm}03 \> $A_i = P_i - aB_i$ \\
\hspace{-7mm}04 $M = (k - 1)b - p_k$\\
\hspace{-7mm}05 \textbf{while} \= $M > 0$ \textbf{and} $A_{k - 1} > 0$ \hspace{0.2 cm} $\rhd$ There are missing and additional points\\
\hspace{-7mm}06 \> $x = k-1$\\
\hspace{-7mm}07 \> \textbf{while} \= $r_{x,k} = b$ \\
\hspace{-7mm}08 \> \> $x = x-1$\\
\hspace{-7mm}09 \> $f = 1$ \\
\hspace{-7mm}10 \> \textbf{while} \= $p_{x-f +1}=p_{x-f}$\\
\hspace{-7mm}11 \> \> $f = f + 1$\\
\hspace{-7mm}12 \> $d = p_{x- f + 1}-p_{x- f}$\\
\hspace{-7mm}13 \> $m = \min(b,d,\lceil A_x/b \rceil,\lceil M/b \rceil)$\\
\hspace{-7mm}14 \> \textbf{for} \= $i = f$ \textbf{downto} $1$\\
\hspace{-7mm}15 \> \> $y = \min(b-r_{x+1-i,k},m,M,A_{x+1-i},p_{x+1-i})$\\
\hspace{-7mm}16 \> \> $r_{x+1-i,k} = r_{x+1-i,k} + y$\\
\hspace{-7mm}17 \> \> $p_{x+1-i} = p_{x+1-i}-y$\\
\hspace{-7mm}18 \> \> $r_{k,x+1-i} = b - r_{x+1-i,k}$\\
\hspace{-7mm}19 \> \> \> $M = M - y$\\
\hspace{-7mm}20 \> \> \textbf{for} \= $j = i$ \textbf{downto} $1$\\
\hspace{-7mm}21 \> \> \> $A_{x+1-i} = A_{x+1-i} - y$\\
\hspace{-7mm}22 \textbf{while} \= $M > 0$ \hspace{2.8 cm} $\rhd$ No missing points \\
\hspace{-7mm}23 \> $i = k - 1$ \\
\hspace{-7mm}24 \> $y = \max(m_{ki} + m_{ik} - a, m_{ki},M)$ \\
\hspace{-7mm}25 \> $r_{ki} = r_{ki} -y$ \\
\hspace{-7mm}26 \> $M = M - y$ \\
\hspace{-7mm}27 \> $i = i - 1$ \\
\hspace{-7mm}28 \textbf{return} $\pi _k,M$
\end{tabbing}
Let's consider an example. Figure \ref{figure-2} shows the point table of a
$(2,10,6)$-tournament $T$.
\begin{figure}[!h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline
Player/Player & P$_1$ & P$_2$ & P$_3$ & P$_4$ & P$_5$ & P$_6 $ & Score \\ \hline
P$_1 $ & --- & 1 & 5 & 1 & 1 & 1 & 09 \\ \hline
P$_2$ & 1 & --- & 4 & 2 & 0 & 2 & 09 \\ \hline
P$_3$ & 3 & 3 & --- & 5 & 4 & 4 & 19 \\ \hline
P$_4$ & 8 & 2 & 5 & --- & 2 & 3 & 20 \\ \hline
P$_5$ & 9 & 9 & 5 & 7 & --- & 2 & 32 \\ \hline
P$_6$ & 8 & 7 & 5 & 6 & 8 & --- & 34 \\ \hline
\end{tabular} \\
\caption{The point table of a $(2,10,6)$-tournament $T$.\label{figure-2}}
\end{center}
\vspace{-2mm}
\end{figure}
The score sequence of $T$ is $D$ = (9,9,19,20,32,34).
In \cite{Ivanyi2009} the algorithm \textsc{Score-Slicing2} resulted the
point table represented in Figure \ref{figure-3}.
\begin{figure}[h]
\begin{center}
\vspace{2mm}
\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline
Player/Player & P$_1$ & P$_2$ & P$_3 $ & P$_4 $ & P$_5$ & P$_6$ & Score \\ \hline
P$_1$ & --- & 1 & 1 & 6 & 1 & 0 & 9 \\ \hline
P$_2$ & 1 & --- & 1 & 6 & 1 & 0 & 9 \\ \hline
P$_3$ & 1 & 1 & --- & 6 & 8 & 3 & 19 \\ \hline
P$_4$ & 3 & 3 & 3 & --- & 8 & 3 & 20 \\ \hline
P$_5$ & 9 & 9 & 2 & 2 & --- & 10 & 32 \\ \hline
P$_6$ & 10 & 10 & 7 & 7 & 0 & --- & 34 \\ \hline
\end{tabular} \\
\vspace{2 mm}
\caption{The point table of $T$ reconstructed by \textsc{Score-Slicing2}.\label{figure-3}}
\end{center}
\vspace{-2mm}
\end{figure}
The algorithm \textsc{Mini-Max} starts with the computation of $f$. \textsc{MinF-MaxG} called in line 01 begins with initialization,
including provisional setting of the elements of $\mathcal{M}$ so, that $m_{ij} = b$, if $i > j$, and $m_{ij} = 0$ otherwise.
Then \textsc{MinF-MaxG} sets the lower bound
$l = \max(9,7) = 9$ of $f$ in line 07 and tests it in line 10
\textsc{Interval-Test}. The test shows that $l = 9$ is large enough so \textsc{Mini-Max} sets $b = 9$ in line 12 and jumps to
line 23 and begins to compute $g$. \textsc{Interval-Test} called in line 25 shows that $a = 9$ is too large, therefore
\textsc{MinF-MaxG} continues with the test of $a = 5$ in line 30. The result is positive, therefore comes the test of $a = 7$,
then the test of $a = 8$. Now $u = l + 1$ in line 35, so $a = 8$ is fixed, and the control returns to line 02 of \textsc{Mini-Max}.
Lines 02--09 contain initialization, and \textsc{Mini-Max} begins the reconstruction of a $(8,9,6)$-tournament in line 10.
The basic idea is that \textsc{Mini-Max} successively determines the won and lost points of P$_6$, P$_5$, P$_4$ and P$_3$ by
repeated calls of \textsc{Score-Slicing2} in line 12, and finally it computes directly the result of the match between P$_2$ and P$_1$.
At first \textsc{Mini-Max} computes the results of P$_6$ calling calling \textsc{Score-Slicing2} with parameter $k = 6$.
The number of additional points of the first five players is
$A_5 = 89 - 8 \cdot 10 = 9$ according to line 03, the number of missing points of P$_6$ is $M = 5 \cdot 9 - 34 = 11$
according to line 04. Then \textsc{Score-Slicing2} determines
the number of maximal numbers among the provisional scores $p_1, \ p_2, \ \ldots, \ p_5$ ($f = 1$ according to lines 09--14) and
computes the difference between $p_5$ and $p_4$ ($d = 12$ according to line 12). In line 13 we get, that $m = 9$ points are
sliceable, and P$_5$ gets these points in the match with P$_6$ in line 16, so the number of missing points of P$_6$
decreases to $M = 11 - 9 = 2$ (line 19) and the number of additional point decreases to $A = 9 - 9 = 0$.
Therefore the computation continues in lines 22--27 and $m_{64}$ and $m_{63}$ will be decreased by 1 resulting $m_{64} = 8$
and $m_{63} = 8$ as the seventh line and seventh column of Figure \ref{figure-4} show.
The returned score sequence is $p = (9,9,19,20,23)$.
\begin{figure}[!h]
\begin{center}
\vspace{2mm}
\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline
Player/Player & P$_1$ & P$_2$ & P$_3 $ & P$_4$ & P$_5$ & P$_6 $ & Score \\ \hline
P$_1$ & --- & 4 & 4 & 0 & 0 & 0 & 9 \\ \hline
P$_2$ & 4 & --- & 4 & 1 & 0 & 0 & 9 \\ \hline
P$_3$ & 4 & 4 & --- & 7 & 4 & 0 & 19 \\ \hline
P$_4$ & 7 & 7 & 1 & --- & 5 & 0 & 20 \\ \hline
P$_5$ & 8 & 8 & 4 & 3 & --- & 9 & 32 \\ \hline
P$_6$ & 9 & 9 & 8 & 8 & 0 & --- & 34 \\ \hline
\end{tabular} \\
\vspace{2 mm}
\caption{The point table of $T$ reconstructed by \textsc{Mini-Max}.\label{figure-4}}
\end{center}
\vspace{-2mm}
\end{figure}
Second time \textsc{Mini-Max} calls \textsc{Score-Slicing2} with parameter $k = 5$, and get $A_4 = 9$ and $M = 13$. At first $A_4$
gets $1$ point, then $A_3$ and $A_4$ get both 4 points, reducing $M$ to $4$ and $A_4$ to $0$. The computation continues
in line 22 and results the further decrease of $m_{54}$, $m_{53}$, $m_{52}$, and $m_{51}$ by 1, resulting $m_{54} = 3$,
$m_{53} = 4$, $m_{52} = 8$, and $m_{51} = 8$ as the sixth row of Figure \ref{figure-4} shows.
Third time \textsc{Mini-Max} calls \textsc{Score-Slicing2} with parameter $k = 4$, and get $A_3 = 11$ and $M = 11$. At first
P$_3$ gets $6$ points, then P$_3$ further 1 point, and P$_2$ and P$_1$ also both get 1 point, resulting $m_{34} = 7$, $m_{43} = 2$,
$m_{42} = 8$, $m_{24} = 1$, $m_{14} = 1$ and $m_{14} = 8$, further $A_3 = 0$ and $M = 2$. The computation continues in lines
22--27 and results a decrease of $m_{43}$ by 1 point resulting $m_{43} = 1$, $m_{42 = 8}$, and $m_{41} = 8$, as the fifth row
and fifth column of Figure \ref{figure-4} show. The returned score sequence is $p = (9,9,15)$.
Fourth time \textsc{Mini-Max} calls \textsc{Score-Slicing2} with parameter $k = 3$, and gets $A_2 = 10$ and $M = 9$. At first
P$_2$ gets $6$ points, then ... The returned point vector is $p = (4,4)$.
Finally \textsc{Mini-Max} sets $m_{12} = 4$ and $m_{21} = 4$ in lines 14--15 and returns the point matrix
represented in Figure \ref{figure-4}.
The comparison of Figures \ref{figure-3} and \ref{figure-4} shows a large difference
between the simple reconstruction of
\textsc{Score-Slicing2} and the minimax reconstruction
of \textsc{Mini-Max}: while in the first case the maximal value of
$m_{ij} + m_{ji}$ is $10$ and the minimal value is $2$, in the second case
the maximum equals to $9$ and the minimum equals
to $8$, that is the result is more balanced (the given $D$ does
not allow to build a perfectly balanced $(k,k,n)$-tournament).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Analysis of the minimax reconstruction algorithm\label{subsec25-73}}
The main result of this paper is the following assertion.
\begin{tetel} \emph{(Iványi \cite{Ivanyi2010})} If $n \geq 2$ is a positive integer
and $\mathbf{q} = (q_1, q_2, \ldots, q_n)$
is a nondecreasing sequence of nonnegative integers, then there exist positive integers $f$ and $g$,
and a $(g,f,n)$-tournament $T$ with point matrix $\mathcal{M}$ such, that
\begin{equation}
f = \min(m_{ij} + m_{ji}) \leq b,
\end{equation}
\vspace{-4mm}
\begin{equation}
g = \max m_{ij} + m_{ji} \geq a
\end{equation}
for any $(a,b,n)$-tournament, and algorithm \textsc{Linear-MinF-MaxG} computes $f$ and $g$ in $\Theta(n)$ time,
and algorithm \textsc{Mini-Max} generates a suitable $T$ in $O(q_n n^2)$ time.
\end{tetel}
\begin{biz} The correctness of the algorithms \textsc{Score-Slicing2}, \textsc{Min}$F$-\textsc{Max}$G$ implies the
correctness of \textsc{Mini-Max}.
Lines 1--46 of \textsc{Mini-Max} require $O(\log (d_n/n))$ uses of \textsc{MinG-MaxF},
and one search needs $O(n)$ steps
for the testing, so the computation of $f$ and $g$ can be executed in
$O(n \log (q_n/n))$ times.
The reconstruction part (lines 47--55) uses algorithm \textsc{Score-Slicing2}, which runs in $O(b n^3)$
time \cite{Ivanyi2009}. \textsc{Mini-Max} calls \textsc{Score-Slicing2} $n - 2$ times with
$f \leq 2\lceil d_n/n \rceil$, so $n^3 q_n/n = q_n n^2$ finishes the proof.
\end{biz}
The property of the tournament reconstruction problem that the extremal values of $f$ and $g$
can be determined independently and so there exists a tournament $T$ having both extremal features is
called linking property.\inddef{linking property} One of the earliest occurrences appeared
in a paper Mendelsohn\nevindex{Mendelsohn, Nathan S.}
and Dulmage\nevindex{Dulmage, A. L.} \cite{MendelsohnD1958}. It was formulated by Ford\nevindex{Ford, L. R.} and
Fulkerson\nevindex{Fulkerson, D. R.} \cite[page 49]{FordF1962} in a theorem on the existence of integral matrices
for which the row-sums and the column-sums lie between specified bounds. The concept was investigated in detail in
the book written by Mirsky\nevindex{Mirsky, Leonid} \cite{Mirsky1971}. A. Frank\nevindex{Frank, András} used this
property in the analysis of different different problems of combinatorial optimization
\cite{Frank1980,Frank2011}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Imbalances in $(0,b,n)$-tournaments\label{sec25-8}}
A $(0,b,n)$-tournament is a digraph in which multiarcs multiarcs are permitted, and
which has no loops \cite{GrossY2004}.
At first we consider the special case $b = 0,$ then the $(0,b,n)$-tournaments.
\subsection{Imbalances in $(0,1,n)$-tournaments.}
A $(0,1,n)$-tournament is a directed graph (shortly digraph) without loops and without multiple arcs is
also called \ki{a simple digraph}\inddef{simple digraph}
\cite{GrossY2004}. The \ki{imbalance}\inddef{imbalance} of a vertex
$v_i$ in a digraph as $b_{v_{i}}$ (or simply $b_{i})= d_{v_{i}}^{+}-d_{v_{i}}^{-}$, where $d_{v_{i}}^{+}$ and
$d_{v_{i}}^{-}$ are respectively the outdegree\index{outdegree} and indegree\index{indegree} of $v_i$.
The \ki{imbalance sequence}\inddef{imbalance sequence} of a simple digraph is formed by listing
the vertex imbalances in nonincreasing order. A sequence of integers $F=[f_{1},f_{2},\ldots,f_{n}]$
with $f_{1}\geq f_{2}\geq\ldots\geq
f_{n}$ is \ki{feasible}\inddef{feasible} if the sum of its elements is zero, and satisfies
$\displaystyle\sum_{i=1}^{k}f_{i}\leq k(n-k),$
for $1\leq k< n$.\\
The following result provides a necessary and sufficient
condition for a sequence of integers to be the imbalance sequence of a simple digraph.\\
\begin{tetel} \emph{Mubayi, Will, West \cite{MubayiWW2001}}
A sequence is realizable as an imbalance sequence of a $(0,1,n)$-tournament if and only if it is feasible.
\end{tetel}
The above result is equivalent to saying that a sequence of integers $B=[b_{1},\ldots,b_{n}]$ with $b_{1}\geq
b_{2}\geq\ldots\geq b_{n}$ is an imbalance sequence of a $(0,1,n)$-tournament if and only if
\begin{equation}
\sum -{i=1}^{k} b_i \leq k(n-k),
\end{equation}
for $1 \leq k< n,$ with equality when $k=n.$
On arranging the imbalance sequence in non-decreasing order, we have the following observation.
\begin{kov}
A sequence of integers $B=[b_{1},\ldots,b_{n}]$ with $b_{1}\leq b_{2}\leq\ldots\leq b_{n}$
is an imbalance sequence of a $(0,1,n)$-tournament if and only if
\begin{equation*}
\sum _{i=1}^k b_i\geq k(k-n),
\end{equation*}
for $1\leq k< n$ with equality when $k = n.$
\end{kov}
Various results for imbalances in different tournaments can be found
in \cite{Ivanyi2009,Ivanyi2010,PirzadaNS2010,PirzadaNSI2010}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Imbalances in $(0,2,n)$-tournaments}
A $(0,b,n)$-tournament is a a digraph in which multiarcss are permitted, and
which has no loops \cite{GrossY2004}. If $b \geq 2$ then a $(0,b,n)$-tournament
is an orientation of a multigraph that is without loops and contains at most $b$
edges between the elements of any pair of distinct vertices.
Let $T$ be a $(0,b,n)$-tournament with vertex set $V=\{v_1,\ldots,v_n\},$ and let
$d_{v}^{+}$ and $d_{v}^{-}$ respectively denote the outdegree and indegree of vertex $v$.
Define $b_{v_{i}}$ (or simply $b_{i}$) $=d_{v_{i}}^{+}-d_{u_{i}}^{-}$ as
imbalance of $v_{i}$. Clearly, $-r(n-1)\leq b_{v_{i}}\leq r(n-1)$.
The imbalance sequence of $D$ is formed by listing the vertex imbalances in
nondecreasing order.
We remark that $(0,b,n)$-digraphs are special cases of $(a,b)$-digraphs containing at least $a$
and at most $b$ edges between the elements of any pair of vertices. Degree sequences of $(0,b,n)$-tournaments
were studied by Mubayi, West, Will \cite{MubayiWW2001} and Pirzada, Naikoo and Shah \cite{PirzadaNS2010}.
Let $u$ and $v$ be distinct vertices in $T.$ If there are $f$ arcs directed from $u$ to $v$ and $g$ arcs
directed from $v$ to $u,$ we denote this by $u(f-g)v$, where $0\leq f,g, f+g \leq r.$
A double in $T$ is an induced directed subgraph with two vertices $u,$ and $v$ having the form
$u(f_1 - f_2)v$, where $1 \leq f_1$, $ f_2 \leq r,$ and $1 \leq f_1 + f_2 \leq r,$ and $f_1$ is
the number of arcs directed from $u$ to $v,$ and $f_2$ is the number of arcs directed from $v$ to $u$.
A triple in $D$ is an induced subgraph with tree vertices $u$, $v$, and $w$ having the form
$u(f_1 - f_2)v(g_1 - g_2)w(h_1 - h_2)u$, where $1 \leq f_1$, $f_2$, $g_1$, $g_2$, $h_1$,
$h_2 \leq r,$ and $1 \leq f_1 + f_2$, $g_1 + g_2 $, $ h_1 + h_2 \leq b,$ and the meaning of
$f_1$, $f_2$, $ g_1$, $ g_2$, $ h_1$, $ h_2$ is similar to the meaning in the definition of doubles.
An oriented triple in $D$ is an induced subdigraph with three vertices. An oriented triple is said
to be transitive if it is of the form $u(1-0)v(1-0)w(0-1)u$, or
$u(1-0)v(0-1)w(0-0)u$, or $u(1-0)v(0-0)w(0-1)u$, or $u(1-0)v(0-0)w(0-0)u$, or $u(0-0)v(0-0)w(0-0)u$,
otherwise it is intransitive. An $r$-graph is said to be transitive if all its oriented triples
are transitive. In particular, a triple $C$ in an $r$-graph is transitive if every oriented triple
of $C$ is transitive.
The following observation can be easily established and is analogues to Theorem 2.2 of Avery \cite{Avery1991}.\\
\begin{lemma} \emph{(Avery1991)} If\label{lemma-Avery} $\,T_1$ and $T_2$ are two $(0,b,n)$-tournaments with
same imbalance sequence, then $T_1$ can be transformed to $T_2$ by successively transforming
(i) appropriate oriented triples in one of the following ways,
either (a) by changing the intransitive oriented triple $u(1-0)v(1-0)w(1-0)u$ to a transitive oriented triple
$u(0-0)v(0-0)w(0-0)u$, which has the same imbalance sequence or vice versa, or (b) by changing the
intransitive oriented triple $u(1-0)v(1-0)w(0-0)u$ to a transitive oriented triple $u(0-0)v(0-0)w(0-1)u$,
which has the same imbalance sequence or vice versa; or (ii) by changing a double $u(1-1)v$ to a double $u(0-0)v$,
which has the same imbalance sequence or vice versa.
\end{lemma}
The above observations lead to the following result.
\begin{tetel} Among all $(0,b,n)$-tournaments with given imbalance sequence, those with the fewest arcs
are transitive.
\end{tetel}
\begin{biz} Let $\mathbf{b}$ be an imbalance sequence and let $T$ be a realization of $\mathbf{b}$ that
is not transitive. Then $T$ contains an intransitive oriented triple. If it is of the form $u(1-0)v(1-0)w(1-0)u,$
it can be transformed by operation \emph{i(a)} of Lemma \ref{lemma-Avery} to a transitive oriented
triple $u(0-0)v(0-0)w(0-0)u$ with the same imbalance sequence and three arcs fewer. If $T$ contains an intransitive
oriented triple of the form $u(1-0)v(1-0)w(0-0)u$, it can be transformed by operation \emph{i(b)} of
Lemma \ref{lemma-Avery} to a transitive oriented triple $u(0-0)v(0-0)w(0-1)u$ same imbalance sequence
but one arc fewer. In case $T$ contains both types of intransitive
oriented triples, they can be transformed to transitive ones with certainly lesser arcs. If in $T$ there is
a double $u(1-1)v,$ by operation \emph{(ii)} of Lemma \ref{lemma-Avery}, it can be transformed to
$u(0-0)v$, with same imbalance sequence but two arcs fewer.
\end{biz}
The next result gives necessary and sufficient conditions for a sequence of integers to be the imbalance
sequence of some $(0,b,n)$-tournament.
\begin{tetel}\label{tetel-PNSI3} \emph{(Pirzada, Naiko, Samee, Iványi \cite{PirzadaNSI2010}Ivanyi)}
A nondecreasing sequence $\mathbf{b} = [b_{1},\ldots,b_{n}]$ of integers is an imbalance sequence
of a $(0,b,n)$-tournament if and only if
\begin{equation}
\sum _{i=1}^k b_i \geq bk(k-n),\label{eq-PNSI}
\end{equation}
with equality when $k = n.$
\end{tetel}
\begin{biz}
{\bf Necessity.} A subtournament induced by $k$ vertices has a sum of imbalances at least $bk(k-n).$\\
{\bf Sufficiency.} Assume that $\mathbf{b}=[b_{1},\ldots,b_{n}]$ is a nonincreasing sequence of integers
satisfying conditions (\ref{eq-PNSI}) but is not the imbalance sequence of any $(0,b,n)$-tournament.
Let this sequence be chosen in such a way that $n$ is the smallest possible and
$b_1$ is the least with that choice of $n.$ We consider the following two cases.
{\bf Case (i).} Suppose equality in (\ref{eq-PNSI}) holds for some $ k \leq n,$ so that
\begin{equation}
\sum_{i=1}^{k} b_i = bk(k-n),
\end{equation}
for $1 \leq k < n.$
By minimality of $n,$ $B_{1} = (b_{1},\ldots, b_{k})$ is the imbalance sequence of some $(0,b,n)$-tournament
$T_1$ with vertex set, say $V_{1}.$ Let $\mathbf{b}_2 = (b_{k+1},b_{k+2},\ldots,b_n).$\\
Consider,\\
\begin{equation}
\begin{split}
\sum_{i=1}^{f}b_{k+i} & =\sum _{i=1} ^{k+f} b_i- \sum _{i=1}^k b_i \\&\geq
b(k+f)[(k+f)-n]- bk(k - n) \\ & = b(k_2 + kf - kn + fk + f_2 - fn- k_2 + kn)\\&\geq
r(f_2 -fn) \\ & = rf(f-n),
\end{split}
\end{equation}
for $1 \leq f \leq n-k,$ with equality when $f=n-k.$ Therefore, by the minimality for $n,$
the sequence $\mathbf{b}_2$ forms the imbalance sequence
of some $(0,b,n)$-tournament $T_{2}$ with vertex set, say $V_{2}.$ Construct a new $(0,b,n)$-tournament $T$
with vertex set as follows.\\
\indent Let $V = V_1 \cup V_2$ with, $V_1 \cap V_2 = \phi$ and the arc set containing those arcs which are in
$T_1$ and $T_2.$ Then we obtain the $(0,b,n)$-tournament $T$ with the imbalance sequence $\mathbf{b},$
which is a contradiction.\\
{\bf Case (ii).} Suppose that the strict inequality holds in (\ref{eq-PNSI}) for some $k < n,$ so that\\
\begin{equation}
\sum _{i=1}^k q_i > bk(k-n),
\end{equation}
for $1\leq k b_{v_1} +1,$
there exists a vertex $v_p\in V_1$ such that $v_{n}(0-0)v_{p}(1-0)v_1$, or
$v_{n}(1-0)v_{p}(0-0)v_1$, or $v_{n}(1-0)v_{p}(1-0)v_1$, or $v_{n}(0-0)v_{p}(0-0)v_1$, and if these are
changed to $v_{n}(0-1)v_{p}(0-0)v_1$, or
$v_{n}(0-0)v_{p}(0-1)v_1$, or $v_{n}(0-0)v_{p}(0-0)v_1$, or $v_{n}(0-1)v_{p}(0-1)v_1$ respectively,
the result is a $(0,b,n)$-tournament with imbalances sequence $\mathbf{b},$ which is again a contradiction.
This proves the result.
\end{biz}
Arranging the imbalance sequence in nonincreasing order, we have the following observation.
\begin{kov}
A nondecreasing sequence $\mathbf{q} = (q_{1},\ldots,q_{n})$ of integers is an
imbalance sequence of a $(0,b,n)$-tournament if and only if
\begin{equation*}
\sum_{i=1}^{k} q_{i}\leq bk(n-k),
\end{equation*}
for $1 \leq k \leq n,$ with equality when $k=n$.
\end{kov}
The \ki{converse of a $(0,b,n)$-tournament}\inddef{the converse of a $0,b,n$-tournament} $T$ is a
$(0,b,n)$-graph $T^\prime,$ obtained by reversing orientations of all arcs of $T$. If
$\mathbf{q}=(q_{1},\ldots,q_{n}]$ with $q_1\leq 2_\leq \ldots \leq b_n$ is the imbalance sequence of a
$(0,b,n)$-tournament $T,$ then $\mathbf{q}^{\prime}=(-q_n,-q_{n-1},\ldots,-q_{1}]$ is the imbalance sequence of $T'$.
The next result gives lower and upper bounds for the imbalance $b_{i}$ of a vertex $v_{i}$ in
a $(0,b,n)$-tournament $T.$
\begin{tetel}
If\label{tetel-bounds} $\mathbf{q} = (q_1,\ldots,b_n)$ is an imbalance sequence of a $(0,b,n)$-tournament $T,$ then for each $i$
\begin{equation}
b(i-n)\leq q_i \leq b(i-1).
\end{equation}
\end{tetel}
\begin{biz}
Assume to the contrary that $q_{i} < b(i-n),$ so that for $k* 1,$ a nondecreasing sequence $\mathbf{q}=[q_{1},\ldots, q_{n}]$
of nonnegative integers is a losing score sequence of some $k$-hypertournament if and only if for each $j,$
\begin{equation} \sum _{i=1}^j q_{i}\geq {\binom{j}{k}},
\end{equation}
with equality when $j=n$.
\end{tetel}
\begin{biz}
See \cite{ZhouYZ2000}.
\end{biz}
\begin{tetel} \emph{Zhou , Zhao, Yang \cite{ZhouYZ2000}}\label{theorem11} Given two positive integers
$n$ and $k$ with $n \geq k > 1,$ a nondecreasing sequence $\mathbf{q}=(q_{1},\ldots, q_{n})$
of nonnegative integers is a score sequence of some $(0,\infty,k,n)k$-hypertournament if and only if for each $j,$
\begin{equation} \sum _{i=1}^j q_i \geq j\binom{n - 1}{k - 1} + \binom{n - j}{k} - \binom{n}{k},
\end{equation}
with equality when $j=n$.
\end{tetel}
\begin{biz} See \cite{ZhouYZ2000}.
\end{biz}
Some more results on $k$-hypertournaments can be found in
\cite{BrcanovP2010,KohR2003,Pirzada2008,PirzadaCN2009,ZhouP2008}. The analogous results of
Theorem \ref{theorem-ZhouZY200-1} and Theorem \ref{theorem-ZhouZY-2} for [$h,k$]-bipartite
hypertournaments can be found in \cite{Pirzada2009} and for $[\alpha,\beta,\gamma]$-tripartite hypertournaments
can be found in \cite{PirzadaNZ2007}.
Throughout this subsection $i$ takes values from 1 to $k$ and $j_i$ takes values from 1 to $n_i,$
unless otherwise stated.
A \ki{$k$-partite hypertournament}\inddef{kpartitehypertournament@$k$-partite hypertournament}
is a generalization of $k$-partite graphs (and $k$-partite tournaments).
Given non-negative integers $n_{i}$ and $\alpha _{i}$, $(i=1, 2,\ldots, k)$ with $n_{i}\geq \alpha _{i}\geq 1$
for each $i$, an $[\alpha _{1},\alpha _{2},\ldots,\alpha _{k}]$-$k$-partite hypertournament
(or briefly $k$-partite hypertournament) $M$ of order $\sum _{1}^{k}n_{i}$ consists of $k$ vertex
sets $U_{i}$ with $\left|U_{i}\right|=n_{i}$ for each $i,$
$(1\leq i\leq k)$ together with an arc set $E,$ a set of $\sum _{1}^{k}\alpha _{i}$ tuples of vertices,
with exactly $\alpha _{i}$ vertices from $U_{i}$, called arcs such that any $\sum _{1}^{k}\alpha _{i}$ subset
$\cup_{1}^{k}U_{i}^{\prime}$ of $\cup _{1}^{k}U_{i}$, $E$ contains exactly one
of the $\left(\sum _{1}^{k}\alpha _{i}\right)$
$\sum _{1}^{k}\alpha _{i}$-tuples whose $\alpha _{i}$ entries belong to $U_{i}^{\prime}$.
Let $e=(u_{11}, u_{12},\ldots, u_{1\alpha _{1}}, u_{21}, u_{22},\ldots,u_{2\alpha _{2}},\ldots, u_{k1}, u_{k2},\ldots,
u_{k\alpha _{k}})$, with $u_{ij_{i}}\in U_{i}$ for each $i$,
$(1\leq i\leq k, 1\leq j_{i}\leq \alpha _{i})$, be an arc in
$M$ and let $h\alpha _{1}$, and similarly $n_{2}>\alpha _{2},\ldots,n_{k}>\alpha _{k}$. Now,
\begin{equation}
\begin{split}
r_{1n_{1}}&=\sum _{i=1}^{k}\sum _{j_{i}=1}^{n_{i}}r_{ij_{i}
}-\left( \sum _{j_{1}=1}^{n_{1}-1}r_{1j_{1}}+\sum _{i=2}^{k}\sum _{j_{i}
=1}^{n_{i}}r_{ij_{i}}\right)\\&\leq\prod _{1}^{k}\left(\begin{array}[c]{c}n_{t}\\
\alpha _{t}\end{array}\right)-\left(\begin{array}[c]{c}n_{1}-1\\
\alpha _{1}\end{array}\right)\prod _{2}^{k}\left(\begin{array}[c]{c}
n_{t}\\
\alpha _{t}\end{array}\right)\\&=\left[\left(\begin{array}[c]{c}n_{1}\\
\alpha _{1}\end{array}\right)-\ \left(\begin{array}[c]{c}n_{1}-1\\
\alpha _{1}\end{array}\right)\right]\prod _{2}^{k}\left(\begin{array}
[c]{c}n_{t}\\
\alpha _{t}\end{array}\right)\\& =\left(\begin{array}[c]{c}n_{1}-1\\
\alpha _{1}-1\end{array}\right)\prod _{2}^{k}\left(\begin{array}[c]{c}
n_{t}\\
\alpha _{t}\end{array}\right).
\end{split}
\end{equation}
We consider the following two cases.\\
{\bf Case 1.} $r_{1n_{1}}=\left(\begin{array}[c]{c}n_{1}-1\\
\alpha _{1}-1\end{array}\right) \prod _{2}^{k}\left(\begin{array}[c]{c}n_{t}\\
\alpha _{t}\end{array}\right)$.
\indent Then,
\begin{equation}
\begin{split}
\sum _{j_{1}=1}^{n_{1}-1}r_{1j_{1}}+ \sum _{i=2}^{k}\sum _{j_{i}
=1}^{n_{i}}r_{ij_{i}}&=\sum _{i=1}^{k}\sum _{j_{i}=1}^{n_{i}}r_{ij_{i}}
-r_{1n_{1}}\\&=\prod _{1}^{k}\left(\begin{array}[c]{c}n_{t}\\
\alpha _{t}\end{array}\right) -\left(\begin{array}[c]{c}n_{1}-1\\
\alpha _{1}-1\end{array}\right)\prod _{2}^{k}\left(\begin{array}[c]{c}
n_{t}\\
\alpha _{t}\end{array}\right)\\&=\left[\left(\begin{array}[c]{c}n_{1}\\
\alpha _{1}\end{array}\right) -\ \left(\begin{array}[c]{c}n_{1}-1\\
\alpha _{1}-1\end{array}\right)\right]\prod _{2}^{k}\left(\begin{array}
[c]{c}n_{t}\\
\alpha _{t}\end{array}\right)\\& =\left(\begin{array}[c]{c}n_{1}-1\\
\alpha _{1}\end{array}\right)\prod _{2}^{k}\left(\begin{array}[c]{c}
n_{t}\\
\alpha _{t}\end{array}\right).
\end{split}
\end{equation}
\indent By induction hypothesis $[r_{11}, r_{12},\ldots, r_{1(n_{1}-1)}],$ $R_{2}, \ldots, R_{k}$
are losing score lists of a $k$-partite hypertournament
$M^{\prime}(U_{1}^{\prime},U_{2},\ldots,U_{k})$ of order $\left(\sum _{i=1}^{k}
n_{i}\right)-1$. Construct a $k$-partite hypertournament $M$ of order
$\sum _{i=1}^{k}n_{i}$ as follows. In $M^{\prime}$, let $U_{1}^{\prime}=\{u_{11},
u_{12},\ldots, u_{1(n_{1}-1)}\}, U_{i}=\{u_{ij_{i}}\}_{j_{i}=1}^{n_{i}}$ for each $i$, $(2\leq i\leq k)$.
Adding a new vertex $u_{1n_{1}}$ to
$U_{1}^{\prime}$, for each $\left(\sum _{i=1}^{k}\alpha _{i}\right)$-tuple
containing $u_{1n_{1}}$, arrange $u_{1n_{1}}$ on the last entry. Denote $E_{1}$
to be the set of all these $\left(\begin{array}
[c]{c}n_{1}-1\\
\alpha _{1}-1\end{array}\right)\prod _{2}^{k}\left(\begin{array}[c]{c}
n_{t}\\
\alpha _{t}\end{array}\right)$ $\left(\sum _{i=1}^{k}\alpha _{i}\right)$-tuples. Let $E(M)=E(M^{\prime})\cup E_{1}$.
Clearly, $R_{i}$ for each $i$, $(1\leq i\leq k)$ are
the $k$ losing score lists of $M$.\\
\textbf{Case 2.} $r_{1n_{1}}<\left(\begin{array}[c]{c}n_{1}-1\\
\alpha _{1}-1\end{array}\right)\prod _{2}^{k}\left(\begin{array}[c]{c}
n_{t}\\
\alpha _{t}\end{array}\right)$.\\
\indent Applying Lemma \ref{lemma-PirzadaZI-3} repeatedly on $R_{1}$ and keeping
each $R_{i}$, $(2\leq i\leq k)$ fixed until
we get a new non-decreasing list
$R_{1}^{\prime}=[r_{11}^{\prime}, r_{12}^{\prime},\ldots, r_{1n_{1}}^{\prime}]$ in which
now $_{1n_{1}}^{\prime}=\left(\begin{array}[c]{c}n_{1}-1\\
\alpha _{1}-1\end{array}\right)\prod _{2}^{k}\left(\begin{array}[c]{c} n_{t}\\
\alpha _{t}\end{array}\right)$. By Case 1, $R_{1}^{\prime}$, $R_{i}$ $(2\leq i\leq k)$ are the losing
score lists of a $k$-partite hypertournament. Now, apply Lemma \ref{lemma-PirzadaZI-2} on
$R_{1}^{\prime}$, $R_{i}$ $(2\leq i\leq k)$ repeatedly until we obtain the initial
non-decreasing lists $R_{i}$ for each $i$ $(1\leq i\leq k)$. Then by Lemma \ref{lemma-PirzadaZI-2}, $R_{i}$ for each $i$
$(1 \leq i \leq k)$ are the losing score lists of a $k$-partite hypertournament. \hfill $\blacksquare$ \\
\textcolor{magenta}{\textbf{Proof}} \textbf{of Theorem \ref{theorem22}.}
Let $S_{i}=[s_{ij_{i}}]_{j_{i}=1}^{n_{i}}(1 \leq i\leq k)$ be the $k$
score lists of a $k$-partite hypertournament $M(U_{i},1\leq i\leq k)$, where $U_{i}=\{u_{ij_{i}}\}_{j_{i}=1}^{n_{i}}$
with $d_{M}^{+}(u_{ij_{i}})=s_{ij_{i}}$, for each $i$, $(1\leq i\leq k)$.
\indent Clearly,\\ $d^{+}(u_{ij_{i}})+d^{-}(u_{ij_{i}})=\frac{\alpha _{i}}{n_{i}
}\prod _{1}^{k}\left(\begin{array}[c]{c}n_{t}\\
\alpha _{t}\end{array}\right)$, $(1\leq i\leq k,1\leq j_{i}\leq n_{i})$.
Let $r_{i(n_{i}+1-j_{i})}=\ $d$^{-}(u_{ij_{i}})$, $(1\leq i\leq k,1\leq j_{i}\leq n_{i})$.
Then $R_{i}=[r_{ij_{i}}]_{j_{i}=1}^{n_{i}}(i=1,2,\ldots,k)$ are the $k$ losing score
lists of $M$. Conversely, if $R_{i}$ for each $i$ $(1\leq i\leq k)$ are the losing
score lists of $M$, then $S_{i}$ for each $i$, $(1\leq i\leq k)$ are the score lists of $M$.
Thus, it is enough to show that conditions (\ref{eq-PirzadaNSI2010-1})
and (\ref{eq-PirzadaNSI2010-1}) are equivalent provided
$s_{ij_{i}}+ r_{i(n_{i}+1-j_{i})}=\left(\frac{\alpha _{i}}{n_{i}}\right)\prod _{1}^{k}\left(\begin{array}[c]{c}n_{t}\\
\alpha _{t}\end{array}\right)$, for each $i$ $(1\leq i\leq k \hbox{ and } 1\leq j_{i} \leq n_{i})$.
First assume (\ref{eq-PirzadaZI2010-2}) holds. Then,
\begin{equation*}
\begin{split}
\sum _{i=1}^{k}\sum _{j_{i}=1}^{p_{i}}r_{ij_{i}}&=\sum _{i=1}^{k}\sum _{j_{i}=1}^{p_{i}}
\left( \frac{\alpha _{i}}{n_{i}}\right)\left( \prod _{1}^{k}\left(\begin{array}[c]{c}n_{t}\\
\alpha _{t}\end{array}\right)\right)-\sum _{i=1}^{k}\sum _{j_{i}=1}^{p_{i}}s_{i(n_{i}+1-j_{i})}\\&=\sum _{i=1}^{k}
\sum _{j_{i}=1}^{p_{i}}\left( \frac{\alpha _{i}}{n_{i}
}\right)\left(\prod _{1}^{k}\left(\begin{array}[c]{c}n_{t}\\
\alpha _{t}\end{array}\right)\right)-\left[\sum _{i=1}^{k}\sum _{j_{i}=1}^{n_{i}}r_{ij_{i}}-\sum _{i=1}^{k}
\sum _{j_{i}=1}^{n_{i}-p_{i}}s_{ij_{i}}\right]\\&\geq\left[\sum _{i=1}^{k}\sum _{j_{i}=1}^{p_{i}}
\left(\frac{\alpha _{i}}{n_{i}}\right)\left(\prod _{1}^{k}\left(\begin{array}
[c]{c}n_{t}\\
\alpha _{t}\end{array}\right)\right)\right]\\
&-\left[\left(\left(\sum _{1}^{k}\alpha _{i}\right)-1\right)
\prod _{1}^{k}\left(\begin{array}[c]{c} n_{i}\\
\alpha _{i}\end{array}\right)\right]\\&+\sum _{i=1}^{k}(n_{i}-p_{i})\left(\frac{\alpha _{i}}{n_{i}
}\right)\prod _{1}^{k}\left(\begin{array}[c]{c}n_{t}\\
\alpha _{t}\end{array}\right)\\
&+\prod _{1}^{k}\left(\begin{array}[c]{c} n_{i}-(n_{i}-p_{i})\\
\alpha _{i}\end{array}\right)-\prod _{1}^{k}\left(\begin{array}[c]{c} n_{i}\\
\alpha _{i}\end{array}\right)\\&=\prod _{1}^{k}\left(\begin{array}[c]{c}n_{i}\\
\alpha _{i}\end{array}\right),
\end{split}
\end{equation*}
with equality when $p_{i}=n_{i}$ for each $i$ $(1\leq i\leq k)$. \indent Thus (1) holds.
Now, when (\ref{eq-PirzadaNSI2010}) holds, using a similar argument as above, we can show
that (\ref{eq-PirzadaNSI2010-2}) holds. This completes the proof. \hfill $\blacksquare$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Supertournaments\label{subsec-25-92}}
The majority of the results on hypertournaments can be extended to supertournaments.
The simplest case when all $m$ individual tournaments have own input sequence
$\mathbf{q_i} = q_{i,1},\ldots,q_{i,n_i},$ where $n_i = \binom{n}{k_i}.$
Then we can apply the necessary and sufficient conditions and algorithms of the previous sections.
If all $m$ tournaments have a join input sequence $\mathbf{q_1,\ldots,q_n},$ then all the previous necessary conditions
remain valid.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Football tournaments\label{sec-25-10}}
The football tournamentsqindex{football tournament} are special incomplete $(2,3,n)$-tournaments,
where the set of the permitted results is $S_{\rm{football} = \{0:3, 1:1}.$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Testing algorithms\label{subsec-25-10-1}}
In this section we describe ten properties of football sequences. These properties serve as necessary conditions
for a given sequence to be a football sequence.
\begin{defi} A\label{def-football} \textbf{football tournament} $F$ is a directed graph (on $n \geq 2$ 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 $F$ is called \textbf{football sequence}
\end{defi}
The $i$-th vertex will be called $i$-th team and will be denoted by T$_i$. For the computations we represent a tournament with
$M$, what is an $n \times n$ sized matrix, in which $m_{ij}$ means the number of points received by T$_i$ in the match
against T$_j$. The elements $m_{ii}$, that is the elements in the main diagonal of $M$ are equal to zero. Let's underline, that
the permitted elements are 0, 1 or 3, so $| \mathcal{F} | = 3^{n(n - 1)/2}$.
The vector of the outdegrees $d = (d_1, d_2, \ldots, d_n)$ of a tournament $F$ 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
$f = (f_1, f_2, \ldots, f_n)$.
In this section at first we describe 6 algorithms which require $\Theta(n)$ time in worst case, then more complicate
algorithms follow.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Linear time testing algorithms\label{subsubsec-25-10-2}}
In this subsection we introduce relatively simple algorithms \textsc{Boundness-Test, Mono-}
\textsc{tonity-Test, Intervallum-Test,
Loss-Test, Draw-Loss-test, Victory-Test}, \textsc{Strong-Test}, and \textsc{Sport-Test}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Testing of boundness}
Since every team T$_i$ plays $n - 1$ matches and receives at least $0$ and at most $3$
points in each match, therefore in a
football sequence it holds $0 \leq f_i \leq 3(n - 1)$ for $i = 1, \ 2, \ \ldots, \ n$.
\begin{defi} A\label{def-bounded} sequence $(q_1,q_2,\ldots,q_n)$ of integers will be called
\textbf{$n$-bounded} (shortly: bounded), iff
\begin{equation}
0 \leq q_i \leq 3(n - 1) \quad \emph{for \ } i = 1, \ 2, \ \ldots, \ n.
\end{equation}
\end{defi}
\begin{lemma}\label{lemma-footbal-is-bounded} Every football sequence is a bounded sequence.
\end{lemma}
\begin{biz} The lemma is a direct consequence of Definition \ref{def-football}.
\end{biz}
The following algorithm executes the corresponding test. Sorting of the elements of $q$ is not necessary.
We allow negative numbers in the input since later testing algorithm \textsc{Decomposition}
can produce such input for \textsc{Bounded}.
\textit{Input}. $n$: the number of teams $(n \geq 2)$; \\
$q = (q_1, q_2, \ldots, q_n)$: arbitrary sequence of integer numbers.
\textit{Output}. $W$: a logical variable. Its value is \textsc{True}, if the input vector is bounded, and
$\textsc{False}$ otherwise.
\textit{Working variable}. $i$: cycle variable.
\bigskip
\noindent \textsc{Boundness-Test}$(n,q,W)$\inddef{\textsc{Boundness-Test}} \\
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
\hspace{-7mm}02 \> \textbf{if} \= $q_i < 0$ or $q_{i} > 3(n - 1)$ \\
\hspace{-7mm}03 \> \> $W = \textsc{False}$ \\
\hspace{-7mm}04 \> \> \textbf{return} $W$\\
\hspace{-7mm}05 $W = \textsc{True}$ \\
\hspace{-7mm}06 \textbf{return} $W$
\end{tabbing}
In worst case \textsc{Boundness-Test} runs $\Theta(n)$ time, in expected case runs in $\Theta(1)$ time. More precisely
the algorithm executes $n$ comparisons in worst case and asymptotically in average 2 comparisons in best case.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Testing of monotonity\label{subsec-monotonity}}
Monotonity is also a natural property of football sequences.
\begin{defi} A\label{def-monotonity} bounded sequence of nonnegative integers $q = (q_1,q_2,\ldots,q_n)$
will be called \textbf{$n$-monotone} (shortly: monotone), iff
\begin{equation}
q_1 \leq q_2 \leq \cdots \leq q_n.
\end{equation}
\end{defi}
\begin{lemma} Every\label{lemma-monotonity} football sequence is a monotone sequence.
\end{lemma}
\begin{biz} This lemma also is a direct consequence of Definition \ref{def-football}.
\end{biz}
The following algorithm executes the corresponding test. Sorting of the elements of $q$ is not necessary.
\textit{Input}. $n$: the number of players $(n \geq 2)$; \\
$q = (q_1, q_2, \ldots, q_n)$: a bounded sequence of length $n$.
\textit{Output}. $W$: a logical variable. Its value is \textsc{True}, if the input vector is monotone, and
$\textsc{False}$ otherwise.
\textit{Working variable}. $i$: cycle variable.
\bigskip
\noindent \textsc{Monotonity-Test}$(n,q,W)$\inddef{\textsc{Monotonity-Test}} \\
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 \textbf{for} \= $i = 1$ \textbf{to} $n -1$ \\
\hspace{-7mm}02 \> \textbf{if} \= $q_{i} < q_{i - 1}$ \\
\hspace{-7mm}03 \> \> $W = \textsc{False}$ \\
\hspace{-7mm}04 \> \> \textbf{return} $W$\\
\hspace{-7mm}05 $W = \textsc{True}$ \\
\hspace{-7mm}06 \textbf{return} $W$
\end{tabbing}
In worst case \textsc{Monotonity-Test} runs $\Theta(n)$ time, in expected case runs in $\Theta(1)$ time. More precisely
the algorithm executes $n$ comparisons in worst case.
The following lemma gives the numbers of bounded and monotone sequences. Let $\mathcal{B}(n)$ denote the set of
$n$-bounded, and $\mathcal{M}(n)$ the set of $n$-monotone sequences, $\beta(n)$ the size of $\mathcal{B}(n)$ and
$\mu(n)$ the size of $\mathcal{M}(n)$.
\begin{lemma} If\label{lemma-cardinality} $n \geq 2$, then
\begin{equation}
\beta(n) = (3n - 2)^n \label{eq-numberofbounded}
\end{equation}
and
\begin{equation}
\mu(n) = \binom{4n - 3}{n}.\label{eq-numberofmonotone}
\end{equation}
\end{lemma}
\begin{biz}
(\ref{eq-numberofbounded}) is implied by the fact that an $n$-bounded sequence contains $n$ elements and
these elements have $3n - 2$ different possible values.
To show (\ref{eq-numberofmonotone}) let $m = (m_1,m_2,\ldots,m_n)$ be a monotone sequence and let
$m' = (m_1',m_2',\ldots,m_n')$, where $m_i' = m_i + i - 1$. Then $0 \leq m_1' < m_2' < \cdots < m_n' < 4n - 4.$
The mapping $m \rightarrow m'$ is a bijection and so $\mu(n)$ equals to the number of ways of choosing $n$ numbers
from $4n - 3$, resulting (\ref{eq-numberofmonotone}).
\end{biz}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Testing of the intervallum property\label{subseq-Landau}}
The following definition exploits the basic idea of Landau's theorem \cite{Landau1953}.
\begin{defi} A monotone sequence $q = (q_1,q_2,\ldots,q_n)$ is called \textbf{intervallum type} (shortly: intervallum), iff
\begin{equation}
2 \binom{k}{2} \leq \sum_{i=1}^k q_i \leq 3 \binom{n}{2} - (n - i)q_i \quad (k = 1, 2, \ldots, n).
\end{equation}
\end{defi}
\begin{lemma} Every football sequence is intervallum sequence.
\end{lemma}
\begin{biz}
The left inequality follows from the fact, that the teams T${_1}$, T${_2}$, \ldots T${_k}$
play $\textbinom{k}{2}$ matches and they get together at least two points in each matches.
The right inequality follows from the monotonity of $m$ and from the fact, that the teams play
$\textbinom{n}{2}$ matches and get at most 3 points in each match.
\end{biz}
The following algorithm \textsc{Intervallum-Test} tests whether a monotone input is intervallum type.
\textit{Input}. $n$: the number of teams $(n \geq 2)$; \\
$q = (q_1, q_2, \ldots, q_n)$: a bounded sequence of length $n$.
\textit{Output}. $W$: a logical variable. Its value is \textsc{True}, if the input vector is intervallum type, and
$\textsc{False}$ otherwise.
\textit{Working variables}. $i$: cycle variable;
$B_k = \textbinom{n}{k} (k = 0, \ 1, \ 2, \ \ldots, \ n)$: binomial coefficients;
$S_0 = 0$: initial value for the sum of the input data;
$S_k = \sum_{i=1}^k q_i \ (k = 1, \ 2, \ \ldots, \ n)$: the sum of the smallest $k$ input data.
We consider $B = (B_0, B_1, \ldots, B_n)$ and $S = (S_0, S_1, \ldots, S_n)$ as global variables, and therefore
they are used later without new calculations. The number of $n$-intervallum sequences will be denoted by $\gamma(n)$.
\bigskip
\noindent \textsc{Intervallum-Test}$(n,q,W)$\inddef{\textsc{Monotonity-Test}} \\
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $B_0 = S_0 = 0$ \\
\hspace{-7mm}02 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
\hspace{-7mm}02 \> $B_{i} = B_{i-1} + i - 1$ \\
\hspace{-7mm}04 \> $S_i = S_{i-1} + q_i$ \\
\hspace{-7mm}05 \> \textbf{if} $2B_i > S_i$ or $S_i > 3B_n - (n - i)q_i$ \\
\hspace{-7mm}06 \> $W = \textsc{False}$ \\
\hspace{-7mm}07 \> \> \textbf{return} $W$\\
\hspace{-7mm}08 $W = \textsc{True}$ \\
\hspace{-7mm}09 \textbf{return} $W$
\end{tabbing}
In worst case \textsc{Intervallum-Test} runs $\Theta(n)$ time. More precisely
the algorithm executes $2n$ comparisons, $2n$ additions, $2n$ extractions, $n$ multiplications and 2 assignments
in worst case. The number of the $n$-intervallum sequences will be denoted by $\gamma(n)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Testing of the loss property}
The following test is based on Theorem 3 of \cite[page 86]{Ivanyi2009}. The basis idea behind the theorem
is the observation that if the sum of the $k$ smallest scores is less than $3 \textbinom{k}{2}$,
then the teams T$_1$, \ T$_2$, \ \ldots, \ T$_k$ have lost at least $3 \textbinom{k}{2} - S_k$ points in the matches among others.
Let $L_0 = 0$ and $L_k = \max(L_{k-1},3\textbinom{n}{2} - S_k) \ (k = 1, \ 2, \ \ldots, \ n)$.
\begin{defi} An intervallum satisfying sequence $q = (q_1,q_2,\ldots,q_n)$ is called \textbf{loss satisfying}, iff
\begin{equation}
\sum_{i=1}^k q_i + (n - k)q_k \leq 3 B_n - L_k \quad (k = 1, 2, \ldots, n).
\end{equation}
\end{defi}
\begin{lemma} A\label{lemma-loss} football sequence is loss satisfying.
\end{lemma}
\begin{biz} See the proof of Theorem 3 in \cite{Ivanyi2009}.
\end{biz}
The following algorithm \textsc{Loss-Test} exploits Lemma \ref{lemma-loss}.
\textit{Input}. $n$: the number of teams $(n \geq 2)$; \\
$q = (q_1, q_2, \ldots, q_n)$: a bounded sequence of length $n$.
\textit{Output}. $W$: a logical variable. Its value is \textsc{True}, if the input vector is Landau type, and
$\textsc{False}$ otherwise.
\textit{Working variables}. $i$: cycle variable;
$L = (L_0, L_1, \ldots, L_n)$: vector of the loss coefficient;
$S = (S_0, S_1, \ldots, S_n)$: sums of the input values, global variables;
$B = (B_0, B_1, \ldots, B_n)$: binomial coefficients, global variables.
\bigskip
\noindent \textsc{Loss-Test}$(n,q,W)$\inddef{\textsc{Loss-Test}} \\
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $L_0 = 0$ \\
\hspace{-7mm}02 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
\hspace{-7mm}03 \> $L_i = \max(L_{i-1},3B_i - S_i)$ \\
\hspace{-7mm}04 \> \textbf{if} $S_i + (n - i)q_i > 3B_n - L_i$ \\
\hspace{-7mm}05 \> \> $W = \textsc{False}$ \\
\hspace{-7mm}06 \> \> \textbf{return} $W$\\
\hspace{-7mm}07 $W = \textsc{True}$ \\
\hspace{-7mm}08 \textbf{return} $W$
\end{tabbing}
In worst case \textsc{Loss-Test} runs in $\Theta(n)$ time, in best case in $\Theta(1)$ time.
We remark that $L = (L_0,L_1,\ldots,L_n)$ is in the following a global variable.
The number of loss satisfying sequences will be denoted by $\lambda(n)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Testing of the draw-loss property}
In the previous subsection \textsc{Loss-Test} exploited the fact, that small scores signalize draws,
allowing the improvement
of the upper bound $3B_n$ of the sum of the scores.
Let's consider the loss sequence $(1,2)$. T$_1$ made a draw, therefore one point is lost and so
$S_2 \leq 2B_2 - 1 = 1$ must hold implying that the sequence $(1,2)$ is not a football sequence.
This example is exploited in the following definition and lemma. Let
\begin{equation}
L'(0) =0 \quad \mathrm{and} \quad L_k' = \max \left ( L_{i-1}', 3B_k - S_k, \left \lceil
\frac{\sum_{i=1}^k (q_i - 3\lfloor q_i/3 \rfloor)}{2} \right \rceil \right ).
\end{equation}
\begin{defi} A loss satisfying sequence $q = (q_1,q_2,\ldots,q_n)$ is called \textbf{draw loss satisfying,} iff
\begin{equation}
\sum_{i=1}^k q_k + (n - k)q_k \leq 3B_n - L_k' \quad (k = 1, 2, \ldots, n).
\end{equation}
\end{defi}
\begin{lemma} A\label{lemma-drawloss} football sequence is draw loss satisfying.
\end{lemma}
\begin{biz} 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 $3B_n$.
\end{biz}
The following algorithm \textsc{Draw-Loss-Test} exploits Lemma \ref{lemma-loss}.
\textit{Input}. $n$: the number of teams $(n \geq 2)$; \\
$q = (q_1, q_2, \ldots, q_n)$: a loss satisfying sequence of length $n$.
\textit{Output}. $W$: a logical variable. Its value is \textsc{True}, if the input vector is Landau type, and
$\textsc{False}$ otherwise.
\textit{Working variables}. $i$: cycle variable;
$L, \ S$ global variables;
$L' = (L_0',L_1',\ldots,L_n')$: modified loss coefficients.
\bigskip
\noindent \textsc{Draw-Loss-Test}$(n,q,W)$\inddef{\textsc{Draw-Loss-Test}} \\
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $L_0' = 0$ \\
\hspace{-7mm}02 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
\hspace{-7mm}03 \> $L_i' = \max(L_i),\left \lceil \frac{\sum_{i=1}^k (q_i -3\lfloor q_i/3 \rfloor)}{2} \right \rceil$ \\
\hspace{-7mm}04 \> \textbf{if} $S_i + (n - i)q_i > 3B_n - L_i'$ \\
\hspace{-7mm}05 \> \> $W = \textsc{False}$ \\
\hspace{-7mm}06 \> \> \textbf{return} $W$\\
\hspace{-7mm}07 $W = \textsc{True}$ \\
\hspace{-7mm}08 \textbf{return} $W$
\end{tabbing}
In worst case \textsc{Draw-Loss-Test} runs in $\Theta(n)$ time, in best case in $\Theta(1)$ time.
We remark that $L'$ is in the following a global variable.
The number of draw loss satisfying sequences will be denoted by $\delta(n)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Testing of the victory property}
In any football tournament $S_n - 2 \textbinom{n}{2}$ matches end with victory and $3\textbinom{n}{2} - S_n$
end with draw.
\begin{defi} A loss satisfying (shortly: loss) sequence $q = (q_1,q_2,\ldots,q_n)$ is called
\textbf{victory satisfying}, iff
\begin{equation}
\sum_{i = 1}^n \left \lfloor \frac{q_i}{3} \right \rfloor \geq S_n - 2 \binom{n}{2}
\quad (k = 1, 2, \ldots, n).\label{eq-victory}
\end{equation}
\end{defi}
\begin{lemma} A\label{lemma-victory} football sequence is victory satisfying.
\end{lemma}
\begin{biz} Team T$_i$ could win at most $\lfloor q_i/3 \rfloor$ times. The left side of
(\ref{eq-victory}) 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.
\end{biz}
The following algorithm \textsc{Victory-Test} exploits Lemma \ref{lemma-victory}.
\textit{Input}. $n$: the number of teams $(n \geq 2)$; \\
$q = (q_1, q_2, \ldots, q_n)$: a loss sequence of length $n$.
\textit{Output}. $W$: a logical variable. Its value is \textsc{True}, if the input vector is Landau type, and
$\textsc{False}$ otherwise.
\textit{Working variables}. $i$: cycle variable;
$V = (V_0, V_1, V_2, \ldots, V_n)$: where $V_i$ is an upper estimation of the number of possible wins of T$_1$, T$_2$, \ldots, T$_i$.
$S_n, \ B_n$: global variables.
\bigskip
\noindent \textsc{Victory-Test}$(n,q,W)$\inddef{\textsc{Victory-Test}} \\
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $V_0 = 0$ \\
\hspace{-7mm}02 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
\hspace{-7mm}03 \> $V_{i} = V_{i-1} + \lfloor q_i/3 \rfloor$ \\
\hspace{-7mm}04 \textbf{if} \= $V_n < S_n - 2 B_n$ \\
\hspace{-7mm}05 \> $W = \textsc{False}$ \\
\hspace{-7mm}06 \> \textbf{return} $W$\\
\hspace{-7mm}07 $W = \textsc{True}$ \\
\hspace{-7mm}08 \textbf{return} $W$
\end{tabbing}
\textsc{Victory-Test} runs in $\Theta(n)$ time in all cases. The number of the victory satisfying
sequences is denoted by $\nu(n)$.
\textsc{Victory-Test} is successful e.g. for the input sequence $(1,2)$,
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?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{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's consider the sequence $(2,3,3,7)$. 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 $S_n = 12$.
Exploiting this observation we can sharp a bit Lemma \ref{lemma-drawloss}. There are the following useful cases:
\begin{enumerate}
\item one small remainder (1 pont) implies the loss of $(1 + 5 \times 3)/2 = 8$ points;
\item one large remainder (2 points) implies the loss of $(2 + 4 \times 3)/2 = 5$ points;
\item one small and one large remainder imply the loss of $(1 + 2 + 3 \times 3)/2 = 6$ points;
\item two large remainders imply the loss of $(2 + 2 + 2 \times 3)/2 = 5$ points;
\item one small and two large remainders imply the loss of $(2 + 2 + 1 + 3)/2$ = 4 points.
\end{enumerate}
According to this remarks let $m_1$ resp. $m_2$ denote the multiplicity of the equality $q_k = 1$ (mod 3) resp.
$q_k = 2 (\mod \ 3)$.
\begin{defi} A victory satisfying sequence $q = (q_1,q_2,\ldots,q_n)$ is called \textbf{strong}, iff
\begin{equation}
\sum_{i=1}^k q_k + (n - k)q_k \leq 3B_n - L_k'' \quad (k = 1, 2, \ldots, n).
\end{equation}
\end{defi}
\begin{lemma} Every football sequence is strong.
\end{lemma}
\begin{biz} The\label{lemma-strong} assertion follows from the fact that any point matrix
of a football tournament order the draws into pairs.
\end{biz}
The following algorithm \textsc{Strong-Test} exploits Lemma \ref{lemma-strong}.
\textit{Input}. $n$: the number of teams $(n \geq 2)$; \\
$q = (q_1, q_2, \ldots, q_n)$: a loss satisfying sequence of length $n$
\textit{Output}. $W$: a logical variable. Its value is \textsc{True}, if the input vector is Landau type, and
$\textsc{False}$ otherwise.
\textit{Working variables}. $i$: cycle variable;
$L' = (L_0', L_1', \ldots,L_n)$: modified loss coefficients, global variables;
$S_n$: sum of the elements of the sequence $q$, global variable;
$L'' = (L_0'', L_1'', \ldots, L_n'')$: strongly modified loss coefficients.
\bigskip
\noindent \textsc{Strong-Test}$(n,q,W)$\inddef{\textsc{Strong-Test}} \\
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $m_1 = m_2 = 0$ \\
\hspace{-7mm}02 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
\hspace{-7mm}03 \> \textbf{if} \= $q_i = 1$ (mod 3) \\
\hspace{-7mm}04 \> $m_1 = m_1 + 1$ \\
\hspace{-7mm}05 \> \textbf{if} \= $q_i == 2$ (mod 3) \\
\hspace{-7mm}06 \> $m_2 = m_2 + 1$ \\
\hspace{-7mm}07 $L'' = L'$ \\
\hspace{-7mm}08 \textbf{if} \= $m_1 == 1$ and $m_2 = 0$ \\
\hspace{-7mm}09 \> $L'' = \max(L', 8)$ \\
\hspace{-7mm}10 \textbf{if} \= $m_1 == 0$ and $m_2 = 1$ \\
\hspace{-7mm}11 \> $L'' = \max(L',5)$ \\
\hspace{-7mm}12 \textbf{if} \= $m_1 == 1$ and $m_2 = 1$ \\
\hspace{-7mm}13 \> $L'' = \max(L',6)$ \\
\hspace{-7mm}14 \textbf{if} \= $m_1 == 0$ and $m_2 = 2$ \\
\hspace{-7mm}15 \> $L'' = \max(L',5)$ \\
\hspace{-7mm}16 \textbf{if} \= $m_1 == 1$ and $m_2 = 2$ \\
\hspace{-7mm}17 \> $L'' = \max(L',4)$ \\
\hspace{-7mm}18 \textbf{if} \= $S_n < 3B_n - L''$ \\
\hspace{-7mm}19 \> $W = \textsc{False}$ \\
\hspace{-7mm}20 \> \textbf{return} \\
\hspace{-7mm}21 $W = \textsc{True}$ \\
\hspace{-7mm}22 \textbf{return} $W$
\end{tabbing}
\textsc{Strong-Test} runs in all cases in $\Theta(n)$ time.
We remark that $L''$ is in the following a global variable.
The number of strong sequences will be denoted by $\tau(n)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{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 \ref{fig-points}.
\begin{defi} A victory satisfying sequence $q = (q_1,q_2,\ldots,q_n)$ is called sport sequence
iff it can be transformed into a sport matrix.
\end{defi}
\begin{lemma} Every football sequence is a sport sequence.
\end{lemma}
\begin{biz} This assertion is a consequence of the definition of the football sequences.
\end{biz}
If a loss sequence $q$ can be realized as a sport matrix, then the following algorithm
\textsc{Sport-Test} constructs one of the
sport matrices belonging to $q$.
If the team T$_i$ has $q_i$ points, then it has at least $d_i = q_i \ (\mathrm{mod} \ 3)$ draws,
$v_i = \max(0,q_i - n + 1)$ wins
and $l_i = \max(0, n - 1 - q_i)$ losses. These results are called
\textit{obligatory wins, draws}, resp. \textit{losses}.
\textsc{Sport-test} starts its work with the computation of $v_i, \ d_i$ and $l_i$.
Then it tries to distribute the remaining
draws.
\textit{Input}. $n$: the number of players $(n \geq 2)$; \\
$q = (q_1, q_2, \ldots, q_n)$: a victory satisfying sequence of length $n$.
\textit{Output}. $W$: a logical variable. Its value is \textsc{True}, if the input sequence is sport sequence, and
$\textsc{False}$ otherwise;
\textit{Working variables}. $i$: cycle variable;
$v, \ d, \ l$: columns of the sport matrix;
$V, \ D, \ L:$ sum of the numbers of obligatory wins, draws, resp. losses;
$B_n, \ S_n$: global variables;
$S_n = \sum_{i=1}^n q_i$: the sum of the elements of the input sequence;
$VF, \ DF, \ LF$: the exact number of wins, draws, resp. losses.
\bigskip
\noindent \textsc{Sport-Test}$(n,q,W)$\inddef{\textsc{Sport-Test}} \\
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $V = D = L = 0 $ \\
\hspace{-7mm}02 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
\hspace{-7mm}03 \> $v_i = \max(0,q_i - n + 1)$ \\
\hspace{-7mm}04 \> $V = V + v_i$ \\
\hspace{-7mm}05 \> $d_i = q_i \ (\mathrm{mod} \ 3)$ \\
\hspace{-7mm}06 \> $D = D + d_i$ \\
\hspace{-7mm}07 \> $l_i = \max(0, n - 1 - q_i)$ \\
\hspace{-7mm}08 \> $L = L + l_i$ \\
\hspace{-7mm}09 $DF = 3B_n - S_n$ \\
\hspace{-7mm}10 \textbf{if} \= $D > DF$ or $2DF - D \neq 0 \ (\mathrm{mod} \ 3)$ \\
\hspace{-7mm}11 \> $W = \textsc{False}$ \\
\hspace{-7mm}12 \> \textbf{return} $W$\\
\hspace{-7mm}13 $VF = S_n - 2B_n$ \\
\hspace{-7mm}14 $LF = VF$ \\
\hspace{-7mm}15 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
\hspace{-7mm}16 \> \textbf{while} \= $DF > 0$ or $VF > 0$ or $LF > 0$ \\
\hspace{-7mm}17 \> \> $x = \min(\frac{q_i - d_i - 3v_i}{3},
\lfloor \frac{3(n - 1) - q_i - d_i}{6} \rfloor)$ \\
\hspace{-7mm}18 \> \> $d_i = d_i + 3x$ \\
\hspace{-7mm}19 \> \> $DF = DF - 3x$ \\
\hspace{-7mm}20 \> \> $v_i = \frac{q_i - d_i}{3}$ \\
\hspace{-7mm}21 \> \> $VF = VF - v_i$ \\
\hspace{-7mm}22 \> \> $l_i = n - 1 - d_i - v_i$ \\
\hspace{-7mm}23 \> \> $LF = LF - l_i$ \\
\hspace{-7mm}25 \> \> \textbf{if} \= $l_i \neq v_i$ \\
\hspace{-7mm}26 \> \> \> $W = \textsc{False}$ \\
\hspace{-7mm}27 \> \> \> \textbf{return} $W$ \\
\hspace{-7mm}28 \> \> \textbf{if} \> $DF \neq 0$ or $VF \neq 0$ or $LF \neq 0$ \\
\hspace{-7mm}29 \> \> \> $W = \textsc{False}$ \\
\hspace{-7mm}30 \> \> \> \textbf{return} \\
\hspace{-7mm}28 $W = \textsc{True}$ \\
\hspace{-7mm}29 \textbf{return} $W$
\end{tabbing}
\textsc{Sport-Test} runs in $\Theta(n)$ time in all cases. The number of the sport
sequences is denoted by $\sigma (n)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Concrete examples}
Let's consider short input sequences illustrating the power of the linear testing algorithms.
If $n = 2$, then according to Lemma \ref{lemma-cardinality} we have $\beta(2) = 4^4 =16$ and $\mu(2) = \textbinom{5}{2} = 10.$
The monotone sequences are $(0,0)$, $0,1$, $(0,2)$, $(0,3)$, $(1,1)$, $)1,2$, $(1,3)$, $(2,2)$, $(2,3)$, $(3,3)$.
Among the monotone sequences there are 4 complete sequences: $(0,2)$, $(0,3)$, $1,1$, and $(1,2)$, so $\gamma(2) = 4$.
\textsc{Loss-Test} does not help, therefore $\lambda(2) = 4.$ \textsc{Victory-Test} excludes $(1,2)$, so $v(2) = 3.$
Finally \textsc{Sport-Test} can not construct a sport matrix and so it concludes $\sigma(2) = 2$. After further
unsuccessful tests \textsc{Football} reconstructs $(0:3)$ and $(1,1)$, proving $\varphi(2) = 2$.
If $n = 3$, then according to Lemma \ref{lemma-cardinality} we have $\beta(3) = 7^3 = 343$ and $\mu(3) = \textbinom{9}{3} = 84.$
Among the 84 monotone sequence there are 27 complete sequences, and these sequences at the same time have also
the loss property, so $\gamma(3) = \lambda(3) = 27$. These sequences are the following: $(0,2,4), (0,2,5), (0,2,6),
(0,3,3), (0,3,4), (0,3,5), (0,3,6),$ $(0, 4, 4), (0, 4, 5), (1,1,4), (1,1,5),(1, 1, 6), (1, 2, 3), (1, 2, 4), (1, 2, 5),
(1, 2, 6), (1, 3, 3),(1, 3,$ $4), (1, 3, 5), (1, 4, 4), (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 2, 5), (2, 3, 3), (2, 3, 4)$
and $(3, 3, 3)$. From these sequences $(0,2,4),...$ are not sport sequences, therefore $\sigma(3) = ??$, and $()...$
are not paired sport sequences, so $\pi(3) = 7.$ The following tests are unsuccessful, but \textsc{Football} reconstructs
the remained seven sequences, therefore $\varphi(3) = 7.$
If $n = 4$, then according to Lemma \ref{lemma-cardinality} we have $\beta(4) = 10^4 =$ 10\,000 and
$\mu(4) = \textbinom{13}{4} = 715$. The number of complete sequences is $\gamma(4) = ???$ and the number of sequences having
the loss property is $\lambda(4) = 57$ and $\sigma(4) = ??$, further $\pi(4) = 40.$ We now that $\varphi(4) = 40$,
so our simple algorithms evaluate the input sequences no longer then 4.
If $n = 5$, then according to Lemma \ref{lemma-cardinality} we have $\beta(5) = 16^5 =$ 1\,048\,576 and
$\mu(5) = \textbinom{17}{5} = 6188$. ????
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Further polynomial testing algorithms\label{subsec-25-92}}
In this subsection we describe the testing algorithms \textsc{Quick-HH}, \textsc{Draw-Pairing-Test}, \textsc{Decomposition-Test}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Quick Havel-Hakimi algorithm\label{subsec-QuickHH}}
In Subsection \ref{subsec-drawloss} we used a greedy approach to check whether the necessary number of draws is allocatable.
A more efficient approach is to try to pair the allocated draws. A known method of this test to use the the following
Havel-Hakimi theorem \cite{Hakimi1962,Havel1955,Lovasz2007} offering a recursive algorithm.
\begin{tetel} \emph{(Havel \cite{Havel1955}, Hakimi \cite{Hakimi1962})}. If $n \geq 3$, then a nonincreasing sequence
$d = (d_1,d_2,\ldots,d_n)$ of positive integers is the outdegree sequence
of a simple graph $G$ iff $d' = (d_2 - 1, d_3 - 1, \ldots, d_{d_1} - 1, d_{d_1 + 1} - 1, d_{d_1 + 2},
\ldots, d_{d_n})$ is the outdegree sequence of some simple graph $G'$.
\end{tetel}
If $G$ is for example a complete simple graph, then it contains $\Theta(n^2)$ edges and the direct application
of Havel-Hakimi theorem requires $\Theta(n^2)$ 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 $d_i \leq n - 1$ for all $i = 1, \ 2, \ldots, \ n$.
We have not to test this property since all our draw allocation algorithms guarantee its fulfilment.
A more interesting condition is
\begin{lemma} If a nonincreasing sequence $d = (d_1,d_2,\ldots,d_n)$ of positive integers is the outdegree sequence
of a simple graph $G$, then
\begin{equation}
\sum_{i = 1}^n d_i \quad \mathrm{is \ even.}\label{eq-QHH1}
\end{equation}
and
\begin{equation}
\sum_{i = 1}^{k} d_i - \min \left (2 \binom{k}{2}, \sum_{i=1}^k d_i \right ) \leq \sum_{i = k + 1}^n d_i
\quad (k = 1, \ 2, \ldots, \ n).\label{eq-QHH2}
\end{equation}
\end{lemma}
\begin{biz}
The draw request of the teams T$_1$, T$_2$, \ldots, T$_k$ 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.
\end{biz}
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\index{Havel-Hakimi theorem}
is dangerous for the linearity of the method.
\begin{defi} A sequence $1 \leq d_1 \leq d_2 \leq \cdots \leq d_n \leq n -1$ is called \textbf{potential} $n$\textbf{-draw sequence}.
The number of potential $n$-draw sequences is denoted by $\pi(n)$.
\end{defi}
\begin{lemma} If\label{lemma-QHH} $n \geq 1$, then $\pi(n) = \binom{2n -2}{n}$.
\end{lemma}
\begin{biz} The proof is similar to the proof of Lemma \ref{lemma-cardinality}.
\end{biz}
Let's take a few example. If $n = 2$, then we have only one potential draw-sequence, which is accepted
by Havel-Hakimi algorithm and satisfies (\ref{eq-QHH1}) and (\ref{eq-QHH2}).
If $n = 3$, then there are $\textbinom{4}{3} = 4$ 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 \ref{lemma-QHH} both accept only (2,2,2) and (1,1,1).
If $n = 4,$ then there are $\textbinom{6}{4} = 15$ potential draw sequences. Havel-Hakimi
algorithm and the conditions of Lemma
\ref{lemma-QHH} 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 $n = 5$, then there are $\textbinom{8}{5} = 56$ 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.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Testing of the pairing sport property at cautious allocation of the draws\label{subsec-pairingtest}}
\textsc{Sport-Test} investigated, whether the scores allow to include $S_n - 2$ $\textbinom{n}{2}$ draws into the sport matrix.
Let's consider the sport sequence $(2,3,3,9)$. In a unique way we get the sport matrix
\begin{table}[!ht]
\vspace{8mm}
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
Team & Wins & Draws & Losses & Points \\ \hline
$T_1$ & 3 & 0 & 0 & 9 \\ \hline
$T_2$ & 1 & 0 & 2 & 3 \\ \hline
$T_3$ & 1 & 0 & 2 & 3 \\ \hline
$T_4$ & 0 & 2 & 1 & 2 \\ \hline
\end{tabular}
\end{center}
\vspace{-4mm}
\caption{Sport table belonging to the sequence $q = (2,3,3,9)$\label{fig-fourteams}}
\end{table}
Here T$_4$ has no partners to make two draws, therefore $q$ is not a football sequence.
Using the Havel-Hakimi algorithm
\cite{Hakimi1962,Havel1955,Lovasz2007} 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.
We can increase the chance to get such negative result thinking on the method of allocation of the draws.
\textsc{Sport-Test} allocated the draws in a greedy way. The following lemma shows that the uniform as possible allocation
strategy is increases the percent of sequences refused by a testing algorithm.
\begin{lemma} If
\end{lemma}
\begin{biz}
\end{biz}
Now consider the football sequence $f = (6^6,9,21,24,27,\ldots,54,57,57,69^7)$, 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 $v_i$ multiplicities of the sport
matrix has to be 84. A uniform distribution results $v_i = 3$ for all $i$ determining the sport matrix in a unique way.
Let's consider the matches in the subtournament of T$_1$, T$_2$, \ldots, T$_7$. This subtournament consists of 21 matches,
from which at most $\lfloor \frac{7\cdot 3}{2} \lfloor = 10$ can end with draw, therefore at least $11$ matches
have a winner, resulting at least $2 \cdot 10 + 3 \cdot 11 = 53$ inner points. But the seven teams have only
$6 \times 6 + 9 = 45$ 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 $f_1 + f_2 + \ldots + f_6 = 36$ and $3 \textbinom{6}{2} = 45$,
the teams T$_1$, T$_2$, \ldots, T$_6$ made at least 9 draws among themselves. "Cautious" distribution results
a draw sequence $(3^6)$, which can be paired easily. Then we can observe that $f_1 + f_2 + \ldots + f_6 + f_7 = 45$, while
$3 \cdot \textbinom{7}{2} = 63$, so the teams T$_1$, T$_2$, \ldots, T$_7$ have to made at least 18 draws.
Cautious distribution results a draw sequence $(6^5,3,3)$. 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 $(6^6,3)$ consisting of
13 draw packs instead of 12. Since $3 \cdot 13 = 39$
is an odd number, this draw sequence is unpairable---the subtournament needs at least one outer draw. ???
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Reconstruction of the tested sequences\label{sec-25-11}}
The reconstruction begins with the study of the inner draws. Let's consider the following sequence of length 28:
$q = (6^6,9,21,24,27,30,\ldots,54,57,57,69^7)$. 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\index{realizability} of the draw sequence
of a sport matrix is equivalent with the problem to decide on a given sequence $d$ of nonnegative integers
whether there exists a simple nondirected graph whose degree sequence is $d.$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Concrete examples\label{sec-25-12}}
Let's consider the following example: $q = (6^4,12,15,18,21,24,27,30^5,33)$. 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. T$_25$ wins again T$_1,$ T$_{26}$ wins against T$_2,$ T$_{27}$ wins against T$3,$ and
T$_{28}$ wins against T$_4,$ 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.
\begin{gyak}
\ujgyak \label{ex-255}
How many
\end{gyak}
\begin{fld}
\ujfld{Football score sequences}
{Let}
\end{fld}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{fejmegj}
A nondecreasing sequence of nonnegative integers $D = (d_1, d_2, \ldots,d_n)$
is a score sequence of a $(1,1,1)$-tournament, iff
the sum of the elements of $D$ equals to $B_n$ and the sum of the first
$i \ (i = 1, \ 2, \ \ldots, \ n - 1)$ elements of
$D$ is at least $B_i$ \cite{Landau1953}.
$D$ is a score sequence of a $(k,k,n)$-tournament, iff the sum of the elements of $D$ equals to $kB_n,$
and the sum of the first $i$ elements of $D$ is at least $kB_i$ \cite{KemnitzD1997,Moon1962}.
$D$ is a score sequence of an $(a,b,n)$-tournament, iff (\ref{equation-interval}) holds \cite{Ivanyi2009}.
In all 3 cases the decision whether $D$ is digraphical requires only linear time.
In this paper the results of \cite{Ivanyi2009} are extended proving that for any $D$ there exists an optimal
minimax realization $T$, that is a tournament having $D$ as its outdegree sequence and maximal $G$ and minimal $F$
in the set of all realization of $D$.
In a continuation \cite{Ivanyi2010} of this chapter we construct balanced as possible tournaments
in a similar way if not only the outdegree sequence but the indegree sequence is also given.
\cite{Avery1991}\nevindex{Avery, Peter} \cite{BangS1979} \cite{BarrusKH2008} \cite{BeasleyBR2009} \cite{BoeschH1976}
\cite{Brauer1968}
\cite{BrualdiS2001}\nevindex{Brualdi, A. Richard} \cite{BrualdiK2009} \cite{GrossY2004}
\cite{Hakimi1962}\nevindex{Hakimi, S. Louis} \cite{Havel1955}\nevindex{Havel, Vaclav}
\cite{Ivanyi2009} \cite{Ivanyi2010} \cite{Ivanyi2010Kom} \cite{Ivanyi2011Kyoto} \cite{Ivanyi2011Opkut}
\nevindex{Iványi, Antal Miklós}
\cite{Knuth2011}\nevindex{Knuth, Donald Ervin}
\cite{Landau1953} \cite{Moon1962} \cite{Moon1963} \cite{MubayiWW2001}
\cite{Pirzada2008}\nevindex{Pirzada, Shariefuddin} \cite{Pirzada2009}
There are further papers on imbalances\index{imbalance} in different graphs
\cite{KayibiKP2011,MubayiWW2001,Pirzada2008,SameeC2010}.
\nevindex{Kahn, Mohammad Ali}\nevindex{Chishti, T. A.}\nevindex{Samee, Uma Tool}\nevindex{Kayibi, Koko K.}
\nevindex{Mubayi, D.}\nevindex{West, D. B.}
\nevindex{Iványi, Antal Miklós}
Many efforts was made to enumerate the different types of degree and score sequences and connected
with them sequences, e.g. by Ascher \cite{Ascher1987}, Barnes and Savage \cite{BarnesS1995,BarnesS1997},
Hirschhorn and Sellers \cite{HirschhornS2008},
Iványi, Lucz and Sótér \cite{IvanyiLS2011AML,IvanyiLS2011Acta}, Metropolis \cite{Metropolis1980}, R{\o}dseth,
Sellers and Tverberg \cite{RodsethST2009}, Simion \cite{Simion1996}, Sloane and Plouffe
\cite{SloaneP1995,Sloane2011,Sloane2011A001700,Sloane2011A004251,Sloane2011A005654}.
\nevindex{Ascher, Marcia}\nevindex{Iványi, Antal Miklós}\nevindex{Lucz, Loránd}\nevindex{Sótér, Péter}
\nevindex{Barnes, Tiffany M.}\nevindex{Savage, Carla D.}\nevindex{Metropolis, N.}\nevindex{Stein, P. R.}
\nevindex{Sloane, Neil A. J.}\nevindex{Plouffe, Simon}\nevindex{Simion, Rodica}
\vspace{4mm}
\textbf{Acknowledgement.} The author thanks András Frank\nevindex{Frank, András} (Eötvös Loránd University)
for valuable advices concerning the application of flow theory and Péter L. Erdős\nevindex{Erdős, Péter László}
(Alfréd Rényi\nevindex{Rényi, Alfréd (1921--1970)} Institute of Mathematics of HAS) for the consultation.
The research of the third 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.
\end{fejmegj}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliography{AlgofInf3-6Aug}
\bibliographystyle{algofinf}
\begin{printindex}
\end{printindex}
\begin{printnevindex}
\end{printnevindex}
\end{document}
*