\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   \cite{BozokiFP2011,BozokiFR2010,Keri2005}, 
in sports Iványi,\nevindex{Iványi, Antal Miklós} Lucz,\nevindex{Lucz, Loránd} Pirzada,\nevindex{Pirzada, Shariefuddin} 
Sótér\nevindex{Sótér, Péter} and Zhou\nevindex{Zhou, Guofei} \cite{Ivanyi2009,Ivanyi2010,
IvanyiLS2011AML,IvanyiL2011Comb,IvanyiLS2011Acta,LuczIS2012,PirzadaIK2011,PirzadaZI2010, SoterIL2012}.

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{sec25-1}}\index{supertournament|(}
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, while $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 in 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,n)$-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 (Section \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} In Section \ref{sec25-8} 
we investigate special incomplete tournaments (football tournaments)\index{football tournament}
 and finally in Section \ref{sec25-9} we consider examples of the reconstruction of football tournaments.
\begin{gyak}
\ujgyak Describe known and possible multitournaments. 
\ujgyak Estimate the number of given types of multitournaments.
\end{gyak}\index{supertournament|)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction to $(a,b)$-tournaments\label{sec25-2}}
Let $a, \ b \ (a \leq b)$ and $n \ (2 \leq n)$ be nonnegative integers and let $\mathcal{T}(a,b,n)$ 
be the set of such generalized 
tournaments, in which every pair of distinct players is connected by at least $a$, and 
at most $b$ 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 $\mathbf{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 $\mathbf{d}$ are in nondecreasing order, 
then $\mathbf{d}$ is called the \ki{score sequence}\inddef{score set} of $T.$   

An arbitrary vector $\mathbf{q} = (q_1, \ldots, q_n)$ of nonnegative integers is called 
\ki{multigraphic vector,}\inddef{multigraphic vector} (or degree vector) if there exists a 
loopless multigraph whose degree vector is $\mathbf{q},$ and $\mathbf{d}$ is called 
\ki{dimultigraphic vector}\inddef{dimultigraphic vector} (or \textit{score vector}) iff there 
exists a loopless directed multigraph whose outdegree vector is $\mathbf{d}.$

A nondecreasingly ordered multigraphic vector is called \ki{multigraphic sequence,}\inddef{multigraphic sequence} 
and a nondecreasingly ordered dimultigraphic vector is called 
\ki{dimultigraphic sequence}\inddef{dimultigraphic sequence} 
(or \textit{score sequence}).

In there exists a simple graph, resp. a simple digraph with degree/out-degree sequence $\mathbf{d},$ then 
$\mathbf{d}$ is called simply \ki{graphic,} resp. \ki{digraphic.}\inddef{graphic sequence}\inddef{digrahic 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} of the $T.$ 

In the last sixty years many efforts have been 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,
IvanyiLS2011Acta,IvanyiLS2011AML,IvanyiL2011Comb,Katona1966,Patrinos1976,Senior1951,SierksmaH1991,SoterIL2012,
Szekely1992,TripathiV2003,WangZ2008} the multigraphic 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 dimultigraphic sequences 
have been discussed.\nevindex{Sótér, Péter}\nevindex{Lucz, Loránd}\nevindex{Pécsy, Gábor}\nevindex{Szûcs, László}

Even in the last two years many authors investigated the conditions when $\mathbf{q}$ is multigraphical  (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 dimultigraphical (e.g. \cite{BeasleyBR2009,HarborthK1962,Ivanyi2009,KemnitzD1997,Knuth2011,Lovasz2007,
NabiyevP2008,Palvolgyi2009,PirzadaSS20082di,PirzadaSS2008Ineq,PirzadaSS2008orient, 
PirzadaZ2008,Ryser1964,SameeMPN2007,Thomassen1981,ZhouP2008}).\nevindex{Iványi, Antal Miklós}\nevindex{Pirzada, Shariefuddin}
\nevindex{Thomassen, Carsten}\nevindex{Volkmann, Lutz}\nevindex{Frank, András}\nevindex{Székely, László Aladár}

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}.\nevindex{Reid, K. Brooks}
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 is: how one can characterize the set of the score sequences of the $(a,b)$-tournaments? 
Or, with other words, for which sequences $\mathbf{q}$ of nonnegative integers does exist an $(a,b)$-tournament 
whose outdegree sequence is $\mathbf{q}.$ The answer is given in Section \ref{sec25-5}.

If $T$ is an $(a,b)$-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(\mathbf{q})$ denote the set of all tournaments having $\mathbf{q}$ as 
outdegree sequence, and let $e(D), \ f(D)$ and $g(D)$ be defined as follows: 
$e(D) = \{\min \ E(T) \ | \ T \in \Delta(\mathbf{q})\}$, $f(\mathbf{q}) 
= \{\min \ F(T) \ | \ T \in \Delta(\mathbf{q})\},$ and 
$g(D) = \{\max \ G(T) \ | \ T \in \Delta(\mathbf{q})\}$. 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$ characterized by $e$? In Subsection 
\ref{subsec25-53} a formula to compute $e,$ and an in \ref{subsec25-54} an algorithm 
to construct a corresponding tournament is presented.

\item How to compute $f$ and $g$? In Subsection \ref{subsec25-54} we characterize $f$ and $g,$ and 
in Subsection \ref{subsec25-55} an algorithm to compute $f$ and $g$ is described, while in Subsection 
\ref{subsec25-58} we compute $f$ and $g$ in linear time.

\item How to construct a tournament $T \in \Delta$ characterized by $f$ and $g$? In Subsection \ref{subsec25-510} 
an algorithm to construct a corresponding tournament is presented and analyzed.
\end{itemize}

We describe the proposed algorithms in words, by examples and by the pseudocode used in \cite{CormenLRS2009}. 

 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Existence of $(1,1)$-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 the paper due to 
Griggs\nevindex{Griggs, Jerrold L.} 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 \subseteq \{1,\ldots,n \}$ 
\begin{equation}
\sum _{i \in 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 \leq q_n$ the inequalities (\ref{eq-Landauvec}), 
called Landau inequalities, we get the following consequence.

\begin{kov} \emph{(Landau \cite{Landau1953})} A nondecreasing sequence of nonnegative integers 
$\mathbf{q} = (q_1, \ldots, q_n)$ is the score sequence of some $(1,1,n)$-tournament, if and only if  
\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-Landausec}), 
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 = [s_1 - 1, \ldots, s_{n-1},s_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 $s_n +1$ and $s_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{Hakimi1963,Havel1955} 
for graphical sequences is the following result.\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}
arranged in nondecreasing order, is the score sequence of some $(1,1,n-1)$-tournament.
\end{tetel}
\begin{biz} See \cite{ReidB1979}.
\end{biz}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 of Kemnitz and Dulff is based on the following lemma, which is an extension of a lemma 
due to Thomassen \cite{Thomassen1981}.

\begin{lemma} \emph{(Thomassen \cite{Thomassen1981})} 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 length at most 2. 
\end{lemma}
\begin{biz} (\cite{KemnitzD1997}) 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 when 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}). Because 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 an $(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}}

In this section we show that for arbitrary prescribed sequence of nondecreasingly ordered nonnegative integers 
there exists an $(a,b)$-tournament  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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,q_n,n)$-tournament for any $\mathbf{q}.$

\begin{lemma} If $n \geq 2,$ then for any\label{lemma-exist} vector of nonnegative integers 
$\mathbf{q} = (q_1, \ldots, q_n)$ there exists a loopless directed multigraph $T$ with outdegree vector 
$\mathbf{q}$ so, that $E \leq q_n.$
\end{lemma}
\begin{biz} Let $m_{n1} = d_n$ and  $m_{i,i+1} = q_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 $\mathbf{q}.$ 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. Their results 
also can serve as basis of the existence of a tournament having arbitrary outdegree sequence.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Description of a naive reconstructing algorithm\label{subsec25-52}}
Sorting of the elements of $D$ is not necessary.

\textit{Input}. $n $: the number of players $(n \geq 2)$; \\
$\mathbf{q} = (q_1, \ldots, q_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.

\newpage
\noindent \textsc{Naive-Construct}$(n,\mathbf{q})$\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              \>              \> $m_{ij} = 0$ \\
\hspace{-7mm}04 $m_{n1} = q_n$ \\
\hspace{-7mm}05 \textbf{for} \= $i = 1$ \textbf{to} $n - 1$ \\
\hspace{-7mm}06              \> $m_{i,i+1} = q_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 now on we suppose that $\mathbf{q}$ is a nondecreasing sequence 
of nonnegative integers, that is $0 \leq q_1$ $\leq q_2 \leq \ldots \leq q_n.$  
Let $h = \lceil q_n/(n - 1) \rceil.$ 

Since $\Delta(\mathbf{q})$ is a finite set for any finite score vector $\mathbf{q},$  
$e(\mathbf{q}) = \min\{E(T) | T \in \Delta(\mathbf{q})\}$ exists.

\medskip
\begin{lemma} \emph{(Iványi \cite{Ivanyi2009})} If $n \geq 2$, then for\label{lemma-e} any sequence 
$\mathbf{q} = (q_1,\ldots,q_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 $q_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 
$\mathbf{q} = (q_1, \ldots, q_n)$ holds $e(D) = \lceil q_n/(n - 1) \rceil$.
\end{kov}
\begin{biz} According to Lemma \ref{lemma-e} $h = \lceil q_n/(n - 1) \rceil$ 
is the smallest upper bound for $e.$
\end{biz}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Description of a construction algorithm\label{subsec25-54}}
The following algorithm constructs a $(0,2h,n)$-tournament $T$ having $E \leq h$ \ for any $\mathbf{q}.$ 

\textit{Input}. $n $: the number of players $(n \geq 2)$; \\
$\mathbf{q} = (q_1, \ldots, q_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.

\bigskip
\noindent \textsc{Pigeonhole-Construct}$(n,\mathbf{q})$\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 = q_i - (n - 1)\lfloor q_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 q_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 q_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{subsec25-55}}
Let $S_i \ (i = 1, \ 2, \ \ldots, \ n)$ be the sum of the first $i$ elements of $\mathbf{q}.$ 
$B_i \ (i = 1, \ 2, \ \ldots, \ n)$ be the binomial coefficient $i(i - 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 $q_n,$  
the pigeonhole principle implies $f \geq \lceil q_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{q_n}{n - 1} \right \rceil.\label{equation-fupperbound}
\end{equation}  

These observations imply a useful characterization of $f$.

\begin{lemma} \emph{(Iványi \cite{Ivanyi2009})} If $n \geq 2,$ then for\label{lemma-fgbounds} arbitrary sequence 
$\textbf{q} = (q_1, \ldots, q_n)$ there exists 
a $(g,f,n)$-tournament having $\textbf{q}$ 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{q_n}{n - 1} \right  
\rceil \right) \leq f \leq 2 \left \lceil \frac{q_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 $q_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 $q_i = q_n = 2c(n - 1) \ (c > 0, \ i = 1, \ 2, \ \ldots, \ n - 1),$ then 
$q_n/(n - 1) = 2c$ and $S_n/B_n = c$, that is $S_n/B_n$ is twice larger than $q_n/(n - 1)$. In the 
other extremal case, when $q_i = 0 \ (i = 1, \ \ldots, n - 1)$ and $q_n = cn(n - 1) > 0,$ 
then $q_n/(n - 1) = cn,$ $S_n/B_n = 2c,$ so $q_n/(n - 1)$ is 
$n/2$ times larger, than $S_n/B_n$.

If $\textbf{q} = (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}[!t]
\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 $\textbf{q} = (0,0,0,40,40,40).$\label{figure-1}}
\end{center}
\vspace{-2mm}
\end{figure}

In 2009 we proved the following assertion.
\begin{tetel} \emph{(Iványi \cite{Ivanyi2009}} For $n \geq 2$ a\label{theorem-interval} nondecreasing sequence 
$\textbf{q} = (q_1, \ldots, q_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 q_i \leq bB_n - L_k - (n - k)q_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} 
q_i  \right ) \quad (1 \leq k \leq n).\label{equation-loss} 
\end{equation}
\end{tetel}

The theorem was 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{Description of a testing algorithm\label{subsec25-56}}
The following algorithm \textsc{Interval-Test}  decides whether a given $\textbf{q}$ 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 $\textbf{q}$ 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)$; \\
$\textbf{q} = (q_1, \ldots, q_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.

\bigskip
\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)q_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)q_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$ (in 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{Description of an algorithm computing $f$ and $g$\label{subsec25-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)$; \\
$\textbf{q} = (q_1, \ldots, q_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).

\bigskip
\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} + q_i$  \\ 
\hspace{-7mm}05 $l = \max (\lceil S_n/B_n \rceil,\lceil q_n/(n - 1) \rceil$) \\
\hspace{-7mm}06 $u = 2 \left \lceil q_n/(n - 1) \right \rceil$ \\
\hspace{-7mm}07 $W = \textsc{True}$                      \hspace{3.7cm} $\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{(Iványi \cite{Ivanyi2010})} Algorithm\label{lemma-fg} \textsc{MinG}-\textsc{MaxG} 
computes the values $f$ and $g$ for arbitrary sequence 
$\textbf{q} = (q_1,\ldots,q_n)$ in $O(n \log(q_n/(n))$ time.
\end{lemma}
\begin{biz} According to Lemma \ref{lemma-fgbounds} $F$ is an element of the interval 
$[\lceil q_n/(n - 1)\rceil, \lceil 2q_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 (q_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{subsec25-58}}
Analyzing 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 the following \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)$; \\
$\mathbf{q} = (q_1, \ldots, q_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. 

\bigskip
\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{4.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} + q_i$  \\ 
\hspace{-7mm}05 $a = 0$ \\
\hspace{-7mm}06 $b = \min 2 \left \lceil q_n/(n - 1) \right \rceil$ \\
\hspace{-7mm}07 \textbf{for} \= $i = 1$ \textbf{to} $n$         \hspace{5cm} $\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{4.5cm} $\rhd$ Computation of $f$ \\
\hspace{-7mm}12              \> $L_i = \max(L_{i - 1},bB_n - S_i - (n - i)q_i$ \\
\hspace{-7mm}13              \> $b_i = (S_i + (n - i)q_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 $\mathbf{q} = (q_1,\ldots,q_n)$ in $\Theta(n)$ time.
\end{lemma}
\begin{biz} Lines 01, 05, 06, and 16 require only constant time, lines 02--06, 07--10, and 11--15 
require $\Theta(n)$ time, so the total running time is $\Theta(n)$. 
\end{biz}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tournament with $f$ and $g$\label{sec25-59}}
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 characterizes this algorithm.

This algorithm is an extended version of the algorithm \textsc{Score-Slicing} proposed in \cite{Ivanyi2009}.

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)$; \\
$\mathbf{q} = (q_1, \ldots, q_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.  \\

\bigskip
\noindent \textsc{Mini-Max}$(n,\mathbf{q})$\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,\mathbf{q})$ \hspace{3.3 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 = q_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{4.9 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{ Description of the score slicing algorithm\label{subsec25-510}}
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 \cdots \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 investigated players $(k > 2)$; \\
$\textbf{p}_k = (p_0,p_1,\ldots,p_k) \ (k = 3, \ 4, \ \ldots, \ n)$: prefix of the provisional score sequence $p$; \\
$\mathcal{M}[1 \ . \ . \ n,1 \ . \ . \ n]$: matrix of provisional points; \\  
 
\textit{Output.} $M$: number of missing points \\
$\textbf{p}_k$: prefix of the provisional score sequence. 

\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 distributed after each match; \\
$b$: maximal number of points distributed after each match.

\bigskip
\noindent \textsc{Score-Slicing2}$(k,\mathbf{p}_k)$\inddef{\textsc{Score-Slicing2}}
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $P_0 = 0$ \\ 
\hspace{-7mm}02 \textbf{for} \= $i = 1$ \textbf{to} $k - 1$  \hspace{1.85 cm} $\rhd$ Initialization \\ 
\hspace{-7mm}03              \> $P_i = P_{i-1} + p_i$\\
\hspace{-7mm}04              \> $A_i = P_i - aB_i$ \\
\hspace{-7mm}05 $M = (k - 1)b - p_k$\\
\hspace{-7mm}06 \textbf{while} \= $M>0$ \textbf{and} $A_{k-1}>0$ \hspace{0.2 cm} $\rhd$ There are missing and additional points\\
\hspace{-7mm}07                \> $x = k-1$\\   
\hspace{-7mm}08                \> \textbf{while} \= $r_{x,k} == b$ \\
\hspace{-7mm}09                \>                \> $x = x-1$\\
\hspace{-7mm}10                \> $f = 1$ \\
\hspace{-7mm}11                \> \textbf{while} \= $p_{x-f +1} == p_{x-f}$\\
\hspace{-7mm}12                \>                \> $f = f + 1$\\ 
\hspace{-7mm}13                \> $d = p_{x- f + 1}-p_{x- f}$\\
\hspace{-7mm}14                \> $m = \min(b,d,\lceil A_x/b \rceil,\lceil M/b \rceil)$\\
\hspace{-7mm}15                \> \textbf{for} \= $i = f$ \textbf{downto} $1$\\
\hspace{-7mm}16                \>              \> $y = \min(b-r_{x+1-i,k},m,M,A_{x+1-i},p_{x+1-i})$\\
\hspace{-7mm}17                \>              \> $r_{x+1-i,k} = r_{x+1-i,k} + y$\\
\hspace{-7mm}18                \>              \> $p_{x+1-i} = p_{x+1-i}-y$\\
\hspace{-7mm}19                \>              \> $r_{k,x+1-i} = b - r_{x+1-i,k}$\\
\hspace{-7mm}20                \>              \>             \> $M = M - y$\\
\hspace{-7mm}21                \>              \> \textbf{for} \= $j = i$ \textbf{downto} $1$\\
\hspace{-7mm}22                \>              \>              \> $A_{x+1-i} = A_{x+1-i} - y$\\
\hspace{-7mm}23 \textbf{while} \= $M > 0$                                \hspace{2.8 cm} $\rhd$ No missing points \\
\hspace{-7mm}24                \> $i = k - 1$ \\
\hspace{-7mm}25                \> $y = \max(m_{ki} + m_{ik} - a, m_{ki},M)$ \\
\hspace{-7mm}26                \> $r_{ki} = r_{ki} -y$ \\
\hspace{-7mm}27                \> $M = M - y$ \\
\hspace{-7mm}28                \> $i = i - 1$ \\
\hspace{-7mm}29 \textbf{return} $p_k,M$
\end{tabbing}

Let us consider an example. Figure \ref{figure-2} shows the point table of a 
$(2,10,6)$-tournament $T.$ We remark that the termin \ki{point table}\inddef{point table} is used as a
synonym of the termin point matrix.\index{point matrix}

\begin{figure}[!t]
\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 $\mathbf{q}$ = (9,9,19,20,32,34).
In \cite{Ivanyi2009} the algorithm \textsc{Score-Slicing} resulted the 
point table reprezented in Figure \ref{figure-3}.

\begin{figure}[!t]
\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-Slicing}.\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}[!t]
\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   &  1  &  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}

In the second place \textsc{Mini-Max} calls \textsc{Score-Slicing2} with parameter $k = 5,$ and get $A_4 = 9$ 
and $M = 13.$ At first $P_4$ gets $1$ point, then $P_3$ and $P_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. 

In the third place \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_{41} = 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} = 7$, and $m_{41} = 7$, 
as the fifth row and fifth column of Figure \ref{figure-4} show. The returned score sequence is $p = (9,9,15)$.

In the fourth place \textsc{Mini-Max} calls \textsc{Score-Slicing2} with parameter $k = 3,$ and gets $A_2 = 10$ 
and $M = 9$. At first P$_1$ and  P$_2$ get $4$ points, resulting $m_{13} = 4$, and $m_{23} = 4,$ and 
$M = 2,$ and $A_2 = 0.$ Then \textsc{MINI-MAX} sets in lines 23--26 $m_{31} = 4$ and $m_{32} = 4.$ 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 $\mathbf{q}$ does 
not allow to build a perfectly balanced $(k,k,n)$-tournament).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{ Analysis of the minimax reconstruction algorithm\label{subsec25-511}}
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 interesting property of $f$ and $g$ is that they 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 of 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 problems of combinatorial optimization 
\cite{Frank1980,Frank2011}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Imbalances in $(0,b)$-tournaments\label{sec25-6}}
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)$-tournaments.\label{subsec-6.1}}
A $(0,1,n)$-tournament is a directed graph (shortly digraph) without loops and without multiple arcs, is 
also called \ki{simple digraph}\inddef{simple digraph} 
\cite{GrossY2004}. The \ki{imbalance}\inddef{imbalance} of a vertex
$v_i$ in a digraph is $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 nondecreasing 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)$-tournaments\label{subsec25-6.2}}
A $(0,b,n)$-tournament is a digraph in which multiarcs are permitted, and
which has no loops \cite{GrossY2004}. If $b \geq 2$ then a $(0,b,n)$-tournament 
is an orientation of a simple multigraph 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  
have been 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,$ then 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 analogue to Theorem 2.2 of Avery \cite{Avery1991}.\\

\begin{lemma} \emph{(Avery 1991 \cite{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} \emph{(Pirzada, Naikoo, Samee, Iványi 2010 \cite{PirzadaNSI2010})} 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})}
 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.

Let $V = V_1 \cup V_2$ with, $V_1 \cap V_2 = \emptyset$ 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<n.$ Let $\mathbf{b}_1=(q_1 - 1,q_2,\ldots,q_{n-1},q_{n}+1],$ so that $\mathbf{b}_1$ satisfies  
the conditions (\ref{eq-PNSI}). Thus by the minimality of
$b_1,$ the sequences $\mathbf{b}_1$ is the imbalances sequence of some $(0,b,n)$-tournament $T_1$ with vertex 
set, say $V_1).$ Let $b_{v_{1}} = b_{1}-1$ and $b_{v_n}=a_n +1.$ Since $b_{v_n} > 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}\label{kov-PNSI} \emph{(Pirzada, Naiko, Samee, Iványi \cite{PirzadaNSI2010})}
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<i,$ 
\begin{equation}
q_{k} \leq q_{i}< b(i-n).
\end{equation}
That is,
\begin{equation}
q_{1}< b(i-n),q_2 < b(i-n), \ldots, b_i < b(i-n).
\end{equation}
Adding these inequalities, we get
\begin{equation}
\sum _{k=1} ^i q_k < bi(i-n),
\end{equation}
which contradicts Theorem \ref{tetel-PNSI3}.

Therefore, $b(i-n)\leq q_{i}$.

The second inequality is dual to the first. In the converse
$(0,b,n)$-tournament with imbalance sequence
$\mathbf{q}=(q_1^{\prime},q_{2}^{\prime},\ldots,q_n^{\prime})$ we have, by the first inequality
\begin{equation}
\begin{split}
q_{n-i+1}^{\prime}&\geq b[(n-i+1)-n]\\& = b(-i+1).
\end{split}
\end{equation}
\indent Since $b_{i}=-b_{n-i+1}^{\prime},$ therefore
\begin{equation*}
q_{i}\leq - b(-i+1) = b(i-1).
\end{equation*}
\indent Hence, $q_{i}\leq b(i-1).$ 
\end{biz}

Now we obtain the following inequalities for imbalances in $(0,b,n)$-tournament.

\begin{tetel} \emph{(Pirzada, Naikoo, Samee, Iványi 2010 \cite{PirzadaNSI2010})} If\label{tetel-PNSI4} 
$\mathbf{q} = (q_{1},\ldots,q_{n})$ is an imbalance sequence of a 
$(0,b,n)$-tournament with $q_{1}\geq q_{2}\geq \ldots \geq q_{n},$ then
\begin{equation}
\sum _{i=1}^{k} q_i^2 \leq \sum _{i=1}^k (2bn-2bk -q_i)^2,
\end{equation}
for $1 \leq k \leq n,$ with equality when $k = n.$
\end{tetel}
\begin{biz}
By Theorem \ref{tetel-PNSI3}, we have for $1 \leq k \leq n,$ with equality when $k=n$
\begin{equation}
bk(n-k)\geq \sum _{i=1}^k q_i,
\end{equation}
implying
\begin{equation*}
\sum _{i=1}^k q_i^2 + 2(2bn-2bk)bk(n-k) \geq \sum _{i=1}^k b_i^2 +2(2bn-2bk)\sum _{i=1}^k q_i,
\end{equation*}
from where
\begin{equation}
\sum _{i=1}^k q_i^2 + k(2bn-2bk)^2 -2(2bn-2bk)\sum _{i=1}^k q_{i}\geq \sum _{i=1}^k q_i^2,
\end{equation}
and so we get the required
\begin{equation}
\begin{split}
q_1^2 + q_2^2 + \ldots + q_k^2 & + (2bn-2bk)^2 + (2bn-2bk)^2+ \ldots+(2bn-2bk)^2\\&-2(2bn-2bk)q_1 
- 2(2bn-2bk)b_2 - \ldots - 2(2bn-2bk)b_k\\&\geq \sum _{i=1}^k q_i^2,
\end{split}
\end{equation}
or
\begin{equation}
\sum _{i=1}^k (2bn-2bk-q_i)^2 \geq \sum _{i=1}^k q_i^2.
\end{equation}
\end{biz}
\vspace{-2mm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Supertournaments\label{sec25-7}}\index{supertournament|(}
In Section \ref{sec25-1} we defined the 
  $\mathbf{(a,b,k},m,n)$-supertournaments.\index{abkmnsupertournament@$(\mathbf{a,b,k},m,n)$-supertournament}
  \inddef{abkmnsupertournament@$(\mathbf{a,b,k},m,n)$-supertournament}

Now at first we present some results on the special case $m = 1,$ that is on the hypertournaments.

\subsection{Hypertournaments\label{sec25-71}}
\ki{Hypergraphs}\inddef{hypergraph} are generalizations of graphs \cite{Berge1976,Berge1989}. 
While edges of a graph are pairs of vertices of the graph, 
edges of a hypergraph are subsets of the vertex set, consisting of at least two vertices. 
An edge consisting of $k$ vertices is
called a $k$-edge. A $k$-hypergraph is a hypergraph all of whose edges are $k$-edges. 
A $k$-hypertournament is a complete 
$k$-hypergraph with each $k$-edge endowed with an orientation, that is, a linear arrangement of the vertices 
contained in the hyperedge. Instead of scores of vertices in a tournament, 
Zhou et al. \cite{ZhouP2008} considered scores 
and losing scores of vertices in a $k$-hypertournament, and derived a
result analogous to Landau's theorem \cite{Landau1953}. The score $s(v_{i})$ or $s_{i}$ of a vertex $v_{i}$ is the 
number of arcs containing $v_{i}$ and in which $v_{i}$ is not the last element, 
and the losing score $r(v_{i})$ or $r_{i}$ 
of a vertex $v_{i}$ is the number of arcs containing $v_{i}$ and in which $v_{i}$ is the last element. 
The score sequence (losing score sequence) is formed by listing the scores (losing scores) in non-decreasing order.

The following characterizations of score sequences and losing score sequences in $k$-hypertournaments can be 
found in G. Zhou et al. \cite{ZhouYZ2000}.

\begin{tetel} \emph{(Zhou, Yang, Zhao  \cite{ZhouYZ2000})}\label{theorem-ZhouYZ2000-1} Given two non-negative 
integers $n$ and $k$ with $n \geq 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, Yang, Zhao \cite{ZhouYZ2000})}\label{theorem-ZhouYZ-2000-2} 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-ZhouYZ2000-1} and Theorem \ref{theorem-ZhouYZ-2000-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 is 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<t$, we let $e(u_{1h}, u_{1t})$ denote to be the new arc obtained from $e$ by interchanging 
$u_{1h}$ and $u_{1t}$ in $e$. An arc containing $\alpha _{i}$ vertices from $U_{i}$ for each $i$, $(1\leq i\leq k)$ 
is called an ($\alpha _{1},\alpha _{2},\ldots, \alpha _{k}$)-arc.


For a given vertex $u_{ij_{i}}\in U_{i}$ for each $i$, $1\leq i\leq k$ and $ 1\leq j_{i}\leq \alpha _{i}$, 
the score $d_{M}^{+}(u_{ij_{i}})$ (or simply $d^{+}(u_{ij_{i}})$) is the number of $\sum _{1}^{k} \alpha _{i}$-arcs 
containing $u_{ij_{i}}$ and in which $u_{ij_{i}}$ is not the last element. The
losing score $d_{M}^{-}(u_{ij_{i}})$ (or simply $d^{-}(u_{ij_{i}})$)
is the number of $\sum _{1}^{k} \alpha _{i}$-arcs containing $u_{ij_{i}}$ and in which
$u_{ij_{i}}$ is the last element. By arranging the losing scores of each vertex set $U_{i}$ separately in 
non-decreasing order, we get $k$ lists called
losing score lists of $M$ and these are denoted by $R_{i}=[r_{ij_{i}}]_{j_{i}=1}^{n_{i}}$ 
for each $i$, $(1\leq i\leq k)$. 
Similarly, by arranging the score lists of each vertex set $U_{i}$ separately in non-decreasing order, we get $k$
lists called score lists of $M$ which are denoted as $S_{i}=[s_{ij_{i}}]_{j_{i}=1}^{n_{i}}$ for each 
$i$ $(1\leq i\leq k)$.
 
The following two theorems are the main results of this subsection.

\begin{tetel} \emph{(Pirzada, Zhou, Iványi \cite[Theorem 3]{PirzadaZI2010})} Given\label{theorem-PirzadaZI20103} $k$ 
nonnegative integers $n_{i}$ and $k$ nonnegative integers $\alpha _{i}$ 
with $1 \leq \alpha _i \leq n _i$ for each i $(1\leq i\leq
k)$, the $k$ nondecreasing lists $R_{i}=[r_{ij_{i}}]_{j_{i}=1}^{n_{i}}$ of
nonnegative integers are the losing score lists of a $k$-partite
hypertournament if and only if for each $p_{i}$ $(1\leq i\leq k)$ with $p_{i}\leq n_{i}$,
\begin{equation}
\sum _{i=1}^{k}\sum _{j_{i}=1}^{p_{i}}r_{ij_{i}}\geq\prod _{i=1}^{k}{\binom{p_{i}}{\alpha _{i}}},\label{eq-PZI20101}
\end{equation}
with equality when $p_{i}=n_{i}$ for each $i$ $(1\leq i\leq k)$.
\end{tetel}

\begin{tetel} \emph{(Pirzada, Zhou, Iványi [Theorem 4]\cite{PirzadaZI2010})} Given\label{theorem-PZI20104} $k$ 
nonnegative integers $n_{i}$ and $k$ nonnegative integers $\alpha _{i}$ with 
$1 \leq \alpha _i \leq n _i$ for each $i$ $(1 \leq i \leq k)$, the $k$ non-decreasing lists 
$S_{i}=[s_{ij_{i}}]_{j_{i}=1}^{n_{i}}$ of non-negative integers are the score lists of a $k$-partite hypertournament 
if and only if for each $p_{i}$, $(1\leq i\leq k)$ with $p_{i}\leq n_{i}$
\begin{equation}
\sum _{i=1}^{k}\sum _{j_{i}=1}^{p_{i}}s_{ij_{i}}\geq \left(  \sum _{i=1}^{k}\frac{\alpha _{i}p_{i}}{n_{i}}\right)
\left(  \prod _{i=1}^{k}{\binom{n_{i}}{\alpha _{i}}}\right)+\prod _{i=1}^{k}{\binom{n_{i}-p_{i}}{\alpha _{i}}}-\prod
_{i=1}^{k}{\binom{n_{i}}{\alpha _{i}}},\label{eq-PZI20102}
\end{equation}
with equality, when $p_{i} = n_{i}$ for each $i$ $(1 \leq i \leq k)$.
\end{tetel}

We note that in a $k$-partite hypertournament $M$, there are exactly
$\prod _{i=1}^{k}{\binom{n_{i}}{\alpha _{i}}}$ arcs and in each arc only
one vertex is at the last entry. Therefore,
\begin{equation*}
\sum _{i=1}^{k}\sum _{j_{i}=1}^{n_{i}}d_{M}^{-}(u_{ij_{i}})=\prod _{i=1}^{k}{\binom{n_{i}}{\alpha _{i}}}.
\end{equation*}

In order to prove the above two theorems, we need the following Lemmas.

\begin{lemma} \emph{(Pirzada, Zhou, Iványi [Lemma 5]\cite{PirzadaZI2010})}  If\label{lemma-PirzadaZI20101} $M$ is a 
$k$-partite hypertournament of order $\sum _{1}^{k}n_{i}$ 
with score lists $S_{i}=[s_{ij_{i}}]_{j_{i}=1}^{n_{i}}$ for each $i$ $(1\leq i\leq k)$, then
\begin{equation}
\sum _{i=1}^{k}\sum _{j_{i}=1}^{n_{i}}s_{ij_{i}}=\left[  \left(  \sum _{1=1}
^{k}\alpha _{i}\right)  -1\right]  \prod _{i=1}^{k}{\binom{n_{i}}{\alpha _{i}}}.
\end{equation}
\end{lemma}
\begin{biz} We have $n_{i}\geq \alpha _{i}$ for each $i$ $(1\leq i\leq k)$. If $r_{ij_{i}}$ is the losing score 
of $u_{ij_{i}}$ $\in U_{i}$, then
\begin{equation}
\sum _{i=1}^{k}\sum _{j_{i}=1}^{n_{i}}r_{ij_{i}}=\prod _{i=1}^{k}{\binom{n_{i}}{\alpha _{i}}}.
\end{equation}

The number of $[\alpha _{i}]_{1}^{k}$ arcs containing $u_{ij_{i}}$ $\in U_{i}$
for each $i$, $(1\leq i\leq k)$, and $1\leq j_{i}\leq n_{i}$ is 
\begin{equation}
\frac{\alpha _{i}}{n_{i}}\prod _{t=1}^{k}{\binom{n_{t}}{\alpha _{t}}}.
\end{equation}

Thus,
\begin{equation}
\begin{split}
\sum _{i=1}^{k}\sum _{j_{i}=1}^{n_{i}}s_{ij_{i}}&=\sum _{i=1}^{k}\sum _{j_{i}=1}^{n_{i}}\left(
  \frac{\alpha _{i}}{n_{i}}\right)  
  \prod _{1}^{k}{\binom{n_{t}}{\alpha _{t}}}-{\binom{n_{i}}{\alpha _{i}}}\\&=\left(\sum _{i=1}^{k}
\alpha _{i}\right)  
\prod _{1}^{k}{\binom{n_{t}}{\alpha _{t}}}-\prod _{1}^{k}{\binom{n_{i}}{\alpha _{i}}}\\&=\left[\left(\sum
_{1=1}^{k}\alpha _{i}\right)  -1\right]  \prod _{1}^{k}{\binom{n_{i}}{\alpha _{i}}}.
\end{split}
\end{equation}
\end{biz}

\begin{lemma} \emph{(Pirzada, Zhou, Iványi [Lemma 6]\cite{PirzadaZI2010})} \label{lemma-PirzadaZI20102} 
{If $R_{i}=[r_{ij_{i}}]_{j_{i}=1}^{n_{i}}$ 
$(1\leq i\leq k)$ are $k$ losing score lists of a $k$-partite hypertournament
$M$, then there exists some $h$ with
\begin{equation}
r_{1h}<{\frac{\alpha _{1}}{n_{1}}}{\prod _{1}^{k}{\binom{n_{p}}{\alpha _{p}}}}
\end{equation}
so that $R_{1}^{\prime}=[r_{11}, r_{12},\ldots, r_{1h}+1,\ldots,
r_{1n_{1}}]$, $R_{s}^{\prime}=[r_{s1}, r_{s2},\ldots, r_{st}-1,\ldots,
r_{sn_{s}}]$ ($2\leq s\leq k$) and $R_{i}=[r_{ij_{i}}]_{j_{i}=1}^{n_{i}}$, ($2\leq i\leq
k$), $i\neq s$ are losing score lists of some $k$-partite
hypertournament, $t$ is the largest integer such that
$r_{s(t-1)}<r_{st}=\ldots =r_{sn_{s}}$.}
\end{lemma}
\begin{biz} Let $R_i=[r_{ij_{i}}]_{j_{i}=1}^{n_{i}}$ $(1\leq i\leq k)$
be losing score lists of a $k$-partite hypertournament $M$ with vertex sets
$U_i=\{u_{i1},u_{i2},\ldots,u_{ij_{i}}\}$ so that
$d^{-}(u_{ij_i})=r_{ij_i}$ for each $i$ $(1 \leq i \leq k,$ $1\leq j_i\leq n_i).$ 

Let $h$ be the smallest integer such that
$$r_{11}= r_{12}=\ldots= r_{1h}<r_{1(h+1)}\leq \ldots \leq r_{1n_{1}}$$
and $t$ be the largest integer such that\\
$$r_{s1}\leq r_{s2}\leq \ldots \leq r_{s(t-1)}< r_{st}=\ldots=r_{sn_{s}}$$

Now, let
$$R_{1}^{\prime}=[r_{11}, r_{12},\ldots, r_{1h}+1,\ldots,r_{1n_{1}}],$$

$$R_{s}^{\prime}=[r_{s1}, r_{s2},\ldots, r_{st}-1,\ldots,r_{sn_{s}}$$ 
$(2\leq s\leq k)$, and $R_{i}=[r_{ij_{i}}]_{j_{i}=1}^{n_{i}}$, $(2\leq
i\leq k)$, $i\neq s$.\\
\indent Clearly, $R_{1}^{\prime}$ and $R_{s}^{\prime}$ are both in
non-decreasing order.

Since $r_{1h}<{\frac{\alpha _{1}}{n_{1}}}{\prod _{1}^{k}{\binom{n_{p}}{\alpha _{p}}}}$,
there is at least one $[\alpha _{i}]_{1}^{k}$-arc $e$ containing both
$u_{1h}$ and $u_{st}$ with $u_{st}$ as the last element in $e$, let
$e^{\prime} = (u_{1h},u_{st})$. Clearly, $R_{1}^{\prime}$,
$R_{s}^{\prime}$ and $R_{i}=[r_{ij_{i}}]_{j_{i}=1}^{n_{i}}$ for each
$i$ $(2\leq i\leq k)$, $i\neq s$ are the $k$ losing score lists of
$M^{\prime}=(M-e)\cup e^{\prime}$. 
\end{biz}

The next observation follows from Lemma \ref{lemma-PirzadaZI20101}, and the proof can be easily established.

\begin{lemma} \emph{(Pirzada, Zhou, Iványi [Lemma 7]\cite{PirzadaZI2010})} \label{lemma-PirzadaZI20107} 
Let $R_{i}=[r_{ij_{i}}]_{j_{i}=1}^{n_{i}}$, $(1\leq i\leq k)$ be $k$ 
nondecreasing sequences of nonnegative integers satisfying (\ref{eq-PZI20101}. If
$r_{1n_{1}}<\frac{\alpha _{1}}{n_{1}}\prod _{1}^{k}{\binom{n_{t}}{\alpha _{t}}}$,
then there exist $s$ and $t$ ($2\leq s\leq k$), $1\leq t\leq n_{s}$ such that
$R_{1}^{\prime}=[r_{11}, r_{12},\ldots, r_{1h}+1,\ldots,
r_{1n_{1}}]$, $R_{s}^{\prime}=[r_{s1}, r_{s2},\ldots, r_{st}-1,\ldots,
r_{sn_{s}}]$ and $R_{i}=[r_{ij_{i}}]_{j_{i}=1}^{n_{i}}$, ($2\leq i\leq
k$), $i\neq s$ satisfy (\ref{eq-PZI20101}).
\end{lemma}

\textcolor{magenta}{\textbf{Proof}} {\bf of Theorem \ref{theorem-PirzadaZI20103}.} {\bf Necessity.} Let $R_{i}$, 
$(1\leq i\leq k)$ be the $k$ losing score lists of a $k$-partite hypertournament $M(U_{i},1\leq i\leq k).$ 
For any $p_{i}$ with $\alpha _{i}$ $\leq p_{i}$ $\leq n_{i}$, 
let $U_{i}^{\prime}=\{u_{ij_{i}}\}_{j_{i}=1}^{p_{i}}(1\leq i\leq k)$ be
the sets of vertices such that $d^{-}(u_{ij_{i}})=r_{ij_{i}}$ for each
$1\leq j_{i}\leq p_{i}$, $1\leq i\leq k$. Let $M^{\prime}$ be the
$k$-partite hypertournament formed by $U_{i}^{\prime}$ for each $i$
$(1\leq i\leq k)$.

Then,
\begin{equation}
\begin{split}
\sum _{i=1}^{k}\sum _{j_{i}=1}^{p_{i}}r_{ij_{i}}
&\geq\sum _{i=1}^{k}\sum _{j_{i}=1}^{p_{i}}d_{M^{\prime}}^{-}(u_{ij_{i}})\\&
=\prod_{1}^{k}\left(\begin{array}[c]{c}p_{t}\\
\alpha _{t}\end{array}\right).
\end{split}
\end{equation}
{\bf Sufficiency.} We induct on $n_{1}$, keeping $n_{2},\ldots,n_{k}$ fixed.
For $n_{1}=\alpha _{1}$, the result is obviously true. So, let $n_{1}
>\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}

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)$.

Applying Lemma \ref{lemma-PirzadaZI20101} 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-PirzadaZI20101} 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-PirzadaZI20102}, 
$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{theorem-PZI20104}.} 
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)$.

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-PZI20101}) 
and (\ref{eq-PZI20102}) are equivalent provided
\begin{equation}
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),
\end{equation}  
for each $i$ $(1\leq i\leq k \hbox{ and } 1\leq j_{i} \leq n_{i})$.

First assume (\ref{eq-PZI20102}) 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)$. 

Thus (1) holds.

Now, when (\ref{eq-PZI20101}) holds, using a similar argument as above, we can show 
that (\ref{eq-PZI20102}) holds. This completes the proof. \hfill   $\blacksquare$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Supertournaments\label{subsec-25-72}}

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.\index{supertournament|)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Football tournaments\label{sec25-8}}\index{football tournament|(}
The football tournaments\index{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-8-1}}
In this section we describe eight properties of football sequences. These properties serve as necessary conditions 
for a given sequence to be a football sequence.

\begin{defi} A\label{def-football} \textbf{football tournament}\inddef{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}\inddef{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, \ldots, f_n)$. The number of football sequences for $n$ teams 
is denoted by $\phi(n).$ The values of $\phi(n)$ are known for $i = 1, \ldots, 8$ \cite{KovacsP2002}.

In this subsection at first we describe six algorithms which require $\Theta(n)$ time in worst case, 
then more complicate algorithms follow.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Linear time testing algorithms\label{subsubsec-25-8-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 = (q_1,\ldots,q_n)$ of integers will be called 
\textbf{$n$-bounded} (shortly: bounded), if and only if
\begin{equation}
0 \leq q_i \leq 3(n - 1) \quad \emph{for \ }  i = 1, \ 2, \ \ldots, \ n.
\end{equation}
\end{defi}

\begin{lemma} \emph{(Lucz, Iványi, Sótér \cite{LuczIS2012})} \label{lemma-footbal-is-bounded} Every football sequence 
is a bounded sequence.\nevindex{Lucz, Loránd}\nevindex{Sótér, Péter}\nevindex{Iványi, Antal Miklós}
\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{Boundness-Test}.

\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)$\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), if and only if
\begin{equation}
q_1 \leq q_2 \leq \cdots \leq q_n.
\end{equation} 
\end{defi}

\begin{lemma} \emph{(Lucz, Iványi, Sótér \cite{LuczIS2012})} 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)$\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 1$, 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 nonincreasing sequence $q = (q_1,q_2,\ldots,q_n)$ is called 
\ki{intervallum type}\inddef{intervallum sequence} (shortly: intervallum), if and only if 
\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)$\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} \emph{(Lucz, Iványi, Sótér \cite{LuczIS2012})} 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)$\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 us 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}
\vspace{-4mm}
\begin{defi} A loss satisfying sequence $q = (q_1,q_2,\ldots,q_n)$ is called 
\ki{draw loss satisfying,}\inddef{loss satisfying sequence} if and only if
\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} \emph{(Lucz, Iványi, Sótér \cite{LuczIS2012})} 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)$\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} \emph{(Lucz, Iványi, Sótér \cite{LuczIS2012})} 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 us 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} \emph{(Lucz, Iványi, Sótér \cite{LuczIS2012})} Every\label{lemma-strong} 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)$\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{figure-2}.

\begin{defi} A victory satisfying sequence $q = (q_1,\ldots,q_n)$ is called \ki{sport sequence}\inddef{sport sequence} 
if it can be transformed into a sport matrix.
\end{defi}

\begin{lemma} \emph{(Lucz, Iványi, Sótér \cite{LuczIS2012})} Every\label{lemma-sport} 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 
\ki{obligatory wins, draws}, resp. \ki{losses}.\inddef{obligatory win}\inddef{obligatory draw}\inddef{obligatory loss} 
\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)$\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 us 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 interval 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 for $(0,2)$ 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 interval 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 only $(0,3,6),$ $(0,4,4),$ $(1,1,6),$ $(1,2,4),$ $(1,3,4),$ 
$(2,2,2),$ $(3,3,3)$ are 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 paired sport sequences is $\pi(4) = 40.$ We now that 
$\varphi(4) = 40$, so our linear algorithms evaluate the input sequences correctly up to $n = 4.$   

If $n \geq 5$, then $\varphi(5) = 355,$ but our approximating algorithms end with $\pi(5) = 360,$ that is 
the quality of 5 sequences remains open.   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Polynomial testing algorithms of the draw sequences\label{subsec-25-72}}
Earlier we used a greedy approach to check whether the necessary number 
of draws is allocatable. 

\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} \emph{(Iványi, Lucz, Sótér \cite{IvanyiLS2011Acta})} 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 us suppose we get a potential draw sequence. In this subsection we describe 
the testing algorithms \textsc{Quick-Havel-Hakimi} and \textsc{Linear-Erdõs-Gallai}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Quick Havel-Hakimi algorithm\label{subsec-QuickHH}}
Algorithm \textsc{Quick-Havel-Hakimi-Test} is based on the following classical theorem 
\cite{Hakimi1962,Havel1955,Lovasz2007}.

\begin{tetel} \emph{(Havel \cite{Havel1955}, Hakimi \cite{Hakimi1962})}. If $n \geq 3,$ 
then a nonincreasing sequence $q = (q_1,\ldots,q_n)$ of positive integers is the outdegree sequence 
of a simple graph $G$ if and only if $q' = (q_2 - 1, q_3 - 1, \ldots,  q_{q_1} - 1, q_{q_1 + 1} - 1, q_{q_1 + 2}, 
\ldots, q_{d_n})$ is the outdegree sequence of some simple graph $G'.$ 
\end{tetel}

\begin{biz} See \cite{Hakimi1962,Havel1955}.
\end{biz}

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. 
Another interesting condition is 
\begin{lemma} \emph{(Iványi, Lucz, Sótér \cite{IvanyiLS2011Acta})} If a nonincreasing sequence $d = (d_1,\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. 

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{Linear Erdõs-Gallai algorithm\label{subsec-LinearEG}}
For given nondecreasing sequence $q = (q_1,\ldots,q_n)$ of nonnegative integers the first $i$ elements 
of the sequence is called the \ki{head} of the sequence\inddef{head of a sequence} and last $n - i$ elements are 
called \ki{the tail}\inddef{tail of a sequence} belonging to the $i$th element of the sequence. 
The sum of the elements of the head is denoted by $H_i,$ while the sum of the element of the tail 
is denoted by $T_i.$ The sum $\sum_{k=i+1}^n \min(i,b_k)$ is denoted by $C_i$ and is called the capacity of the tail 
belonging to $q_i.$ If $H_n$ is even, then $\textbf{q}$ is called \ki{even,}\inddef{even sequence} 
otherwise the sequence is called \ki{odd sequence.}\inddef{odd sequence} 

Another classical theorem on the testing of the potential draw sequences whether they are graphical is 
the theorem proved by Erdõs and Gallai in 1960 \cite{ErdosG1960}.

\begin{tetel} \emph{(Erdõs, Gallai, \cite{ErdosG1960})} If  $n \geq 1,$\label{tetel-EG} 
the $n$-regular sequence $(q_1\ldots,q_n)$ is graphical if and only if
\begin{equation}
H_n \quad \mbox{is even}\label{eq-EGparos}
\end{equation}
and
\begin{equation}
H_i - i(i - 1) \leq C_i \quad (i = 1, \ldots, n - 1).\label{eq-EGbinom}
\end{equation}
\end{tetel}

\begin{biz} 
See \cite{Choudum1986,ErdosG1960,SierksmaH1991,TripathiVW2010}.
\end{biz}

Recently we could improve this theorem \cite{IvanyiLS2011Acta}. 
The algorithm \textsc{Erdõs-Gallai-Linear} exploits, that $q$ is monoton. It determines the $C_i$ capacities 
in constant time. The base of the quick computation is thesequence $m(q)$ containing pointers.
 
For given sequence $q$ let $m(q) = (m_1,\ldots,m_{n-1}),$ where $m_i$ points to the element of $q_k$ 
having the maximal index among such elements of $q$ which are greater or equal with $i.$

\begin{tetel} \emph{(Iványi, Lucz, Sótér \cite{IvanyiLS2011Acta})} If  $n \geq 1,$\label{tetel-EGL} 
the $n$-regular sequence $(q_1\ldots,q_n)$ is graphical if and only if
\begin{equation}
H_n \quad \mbox{is even}\label{eq-EGLparos}
\end{equation}
and if $i > m_i,$ then
\begin{equation}
H_i \leq i(i - 1) + H_n - H_i,\label{eq-EGLlargei}
\end{equation}
further if $i \leq m_i,$ then
\begin{equation}
H_i \leq i(i - 1) + i(m_i -i) + H_n - H_{m_i},\label{eq-EGLlargei}
\end{equation}
\end{tetel}
\begin{biz}
(\ref{eq-EGLparos}) is the same as (\ref{eq-EGparos}). 

During the testing of the elements of $q$ by \textsc{Erdõs-Gallai-Linear} there are two cases: 
\begin{itemize}
\item if $i > m_i,$ then the contribution of the tail of $q$ equals to 
$H_n - H_i,$ since the contribution $C_k$ of the element $q_k$ is only $q_k.$ 
\item if $i \leq m_1,$ then the contribution of the tail of $q$ consists of two parts: $C_{i+1},\ldots,C_{m_i}$ 
equal to $i,$ while $C_j = b_j$ for $j = m_{i} + 1,\ldots,n.$ 
\end{itemize}

Therefore in the case $n - 1 \geq i > m_i$ we have
\begin{equation}
C_i = i(i - 1) + H_n - H_i,\label{eq-EGLClargei}
\end{equation}
and in the case $1 \leq i \leq m_i$ 
\begin{equation}
C_i = i(i - 1) + i(m_i -i) + H_n - H_{m_i}.\label{eq-EGLCsmalli}
\end{equation}
\end{biz}

The following program is based on Theorem \ref{theorem-EGL}. 
It decides on arbitrary $n$-regular sequence whether it is graphicakl or not. 

\textit{Input}. $n$: number of vertices $(n \geq 1)$; \\
$q = (q_1,\ldots,q_n)$: $n$-regular sequence.  

\textit{Output}. $L$: logical variable, whose value is \textsc{True}, if the input is graphical, 
and it is \textsc{False}, if the input is not graphical. 

\textit{Work variables.} $i$ and $j$: cycle variables; \\
$H = (H_1,\ldots,H_n)$: $H_i$ is the sum of the first $i$ elements of the tested $q$; \\
$m = (m_1,\ldots,m_{n-1})$: $m_i$ is the maximum of the indices of such elements of $q,$ which are 
not smaller than $i$;
$H_0 = 0$: help variable to compute of the other elenments of the sequence $H$; \\
$q_0 = n -1$: help variable to compute the elements of the sequence $m$. \\

\bigskip  
\noindent \textsc{Linear-Erdõs-Gallai}$(n,b)$\inddef{\textsc{Linear-Erdõs-Gallai}}
\vspace{-2mm}
\begin{tabbing}%
199 \= xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx \+ \kill
\hspace{-7mm}01 $H_0 = 0$ \\                                 \` $\rhd$ Line 01: initialization \\
\hspace{-7mm}02 \textbf{for} \= $i = 1$ \textbf{to} $n$   \` $\rhd$ Lines 02--03: computation of the elements of $H$ \\  
\hspace{-7mm}03              \> $H_i = H_{i-1} + q_i$ \\ 
\hspace{-7mm}04 \textbf{if} \= $H_n$ \textrm{ odd}    \` $\rhd$ Lines 04--06: test of the parity   \\ 
\hspace{-7mm}05             \> $L = \textsc{False}$ \\
\hspace{-7mm}06             \> \textbf{return} \\
\hspace{-7mm}07 $q_0 = n - 1$                             \` $\rhd$ Line 07: initialization of $b_0$ \\ 
\hspace{-7mm}08 \textbf{for} \= $j = n$ \textbf{downto} $q_1 + 1$ \` $\rhd$ Lines 08--09: setting of some pointers  \\
\hspace{-7mm}09              \> $m_j = 0$ \\
\hspace{-7mm}10 \textbf{for} \= $i = 1$ \textbf{to} $n$         \` $\rhd$ Lines 10--16:  calculation of the pointers \\ 
\hspace{-7mm}11              \> \textbf{if} \= $q_i < q_{i-1}$  \\ 
\hspace{-7mm}12              \>             \> \textbf{for} \= $j = q_{i-1}$ \textbf{downto} $q_i + 1$ \\
\hspace{-7mm}15              \>             \>              \> $m_j = i - 1$ \\
\hspace{-7mm}16              \> $m_{q_i} = i$ \\ 
\hspace{-7mm}17 \textbf{for} \= $j = q_n - 1$ \textbf{downto} $1$  \` $\rhd$ Lines 17--18: setting of some pointers \\
\hspace{-7mm}18              \> $m_j = n - 1$ \\                            
\hspace{-7mm}19 \textbf{for} \= $i = 1$ \textbf{to} $n - 1$            \` $\rhd$ Lines 19--25: test of $q$ \\  
\hspace{-7mm}20              \> \textbf{if} \= $i > m_i$ and $H_i >  i(i - 1) + H_n - H_i$ \\
\hspace{-7mm}21              \>             \> $L = \textsc{False}$ \\
\hspace{-7mm}22              \>             \> \textbf{return} $L$ \\           
\hspace{-7mm}23              \> \textbf{if} \= $i \leq m_i$ and $H_i >  i(i - 1) + H_n - H_i$ \\ 
\hspace{-7mm}24              \>             \> $L = \textsc{False}$ \\
\hspace{-7mm}25              \>             \> \textbf{return} $L$ \\
\hspace{-7mm}26 $L = \textsc{True}$ \` $\rhd$ Lines 26--27: the program ends with \textsc{True} value  \\
\hspace{-7mm}27 \> \textbf{return} $L$  \\ 
\end{tabbing}

\begin{tetel} \emph{(Iványi, Lucz \cite{IvanyiL2011Comb}, Iványi, Lucz, Sótér \cite{IvanyiLS2011Acta})} 
Algorithm \textsc{Linear-Erdõs-Gallai} decides in $O(n)$ time, whether an  $n$-regular sequence 
$q = (q_1,\ldots,q_n)$ is graphical or not.  
\end{tetel} 

\begin{biz} Line 1 requires $O(1)$ time, lines 2--3 $O(n)$ time, lines 4--6 $O(1)$ time, line 07 $O(1)$ time, 
line 08--09 $O(1)$ time, lines 10--18 $O(n)$ time, lines 19--25 $O(n)$ time and lines 26--27 $O(1)$ time, 
therefore the total time requirement of the algorithm is $O(n)$. 
\end{biz}

Until now the number of good sequences was known only for $n = 1, \ 2, \ \ldots, \ 23,$ see 
\textit{Online Encyclopedia of Integer Sequences} \cite{Sloane2011}.   
Using the new and quick algorithms we determined $\gamma(n)$ for $n = 24, \ 25, \ \ldots, \ 28$ 
too \cite{IvanyiL2011Comb,IvanyiLS2011Acta,IvanyiLS2011AML}.
Figure \ref{fig-sorozatszam} contains the number of good sequences $\gamma(n)$ for $n = 1, \ \ldots, \ 28,$ 
and also $\gamma(n + 1)/\gamma(n)$ for $n = 1, \ \ldots, \ 27.$ 

\begin{figure}[!t]
\begin{small}
\begin{center}
\begin{tabular}{||c|c|c|c|c||}  \hline \hline
$n$  & $\beta(n)$  &$\varphi(n)$     & $\gamma(n)$  & $\gamma(n+1)/\gamma(n)$    \\ \hline \hline
$1$  &$\mathbf{1}$ &$\mathbf{0}$     & $\mathbf{1}$ & $2.000000$\\ \hline
$2$  &$\mathbf{2}$ &$\mathbf{2}$     & $\mathbf{2}$ & $2.000000$\\ \hline
$3$  &$\mathbf{4}$ &$\mathbf{4}$    & $\mathbf{4}$ & $2.750000$      \\ \hline
$4$  &$\mathbf{4}$ &$\mathbf{11}$    & $\mathbf{11}$ & $2.818182$\\ \hline
$5$  &$\mathbf{31}$&$\mathbf{31}$    &$\mathbf{31}$  & $3.290323$     \\ \hline
$6$  &    $103$    &$\mathbf{102}$   &$\mathbf{102}$ & $3.352941$      \\ \hline 
$7$  &    $349$    &$344$            &$\mathbf{342}$ & $3.546784$    \\ \hline 
$8$  &    $1256$   &$1230$           &   $1213$      & $3.595218$\\ \hline 
$9$  &    $4577$   &$4468$           &  $4361$       & $3.672552$ \\ \hline 
$10$ &     $17040$ &$16582$          &$16016$        & $3.705544$\\ \hline 
$11$ &     $63944$ &$62070$          &$59348$        & $3.742620$ \\ \hline 
$12$ &   $242218$  &$234596$         &$222117$       & $3.765200$ \\ \hline 
$13$ & $922369$    &$891852$         & $836315$      & $3.786674$ \\ \hline 
$14$ &$3530534$    &$3409109$        & $3166852$     & $3.802710$ \\ \hline 
$15$ &$13563764$   &$13082900$       &   $12042620$  & $3.817067$ \\ \hline 
$16$ &$52283429$   &$50380684$       &   $45967479$  & $3.828918$ \\ \hline 
$17$ &$202075949$  &$194550002$      & $176005709$   & $3.839418$ \\ \hline 
$18$ &$782879161$  &$753107537$      &$675759564$   & $3.848517$ \\ \hline 
$19$ &$3039168331$ &$2921395019$     & $2600672458$  & $3.856630$ \\ \hline 
$20$ &$11819351967$&$11353359464$    & $10029832754$ & $3.863844$  \\ \hline 
$21$ &   $???$     &   $???$         & $38753710486$ & $3.870343$ \\ \hline 
$22$ &   $???$     &   $???$         &$149990133774$       & $3.876212$ \\ \hline 
$23$ &   $???$     &   $???$         &$581393603996$       & $3.881553$\\ \hline 
$24$ &   $???$     &   $???$         &$2 256 710 139 346$  & $3.886431$        \\ \hline 
$25$ &   $???$     &   $??$          &$8 770 547 818 956$  & $3.890907$      \\ \hline 
$26$ &   $???$     &   $???$         &$34 125 389 919 850$ & $3.895031$\\ \hline 
$27$ &   $???$     &   $???$         &$132 919 443 189 544$& $3.897978$        \\ \hline 
$28$ &$???$        &   $???$         &$518 232 001 761 434$& $???$      \\ \hline \hline
\end{tabular}
\caption{Number of Binomial, fejfelezõ és good sequences, further the ratio of the numbers of good sequences 
for neighbouring values of $n$.\label{fig-sorozatszam}}
\end{center}
\end{small}
\end{figure} 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Testing of the pairing sport property at cautious allocation of the draws}
\textsc{Sport-Test} investigated, whether the scores allow to include $S_n - 2$ $\textbinom{n}{2}$ 
draws into the sport matrix. 

Let us consider the sport sequence $(2,3,3,9).$ In a  unique way we get the sport matrix

\begin{table}[!t]
\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.

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 us 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 + \cdots + 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 + \cdots + 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. ??? 
\index{football tournament|)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Reconstruction of the tested sequences\label{sec25-9}}
The reconstruction begins with the study of the inner draws. Let us 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.$

Let us 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 monoton sequence is possible in a football tournament with 5 teams?
\ujgyak \label{ex-256} How many sportmatrix is possible in a football tournament with 5 teams? 
\end{gyak}

\begin{fld}
\ujfld{Football score sequences}
{Design a program generating all football sequences of length 6. Implement your program.}
\ujfld{Draw sequences}
{Design a program which generates all draw sequences of a tournament with $n$ teams.}
\end{fld}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{fejmegj}
A nondecreasing sequence of nonnegative integers $q = (q_1, \ldots, q_n)$ 
is a score sequence of a $(1,1,1)$-tournament, if and only if  
the sum of the elements of $q$ equals to $B_n$ and the sum of the first 
$i \ (i = 1, \ 2, \ \ldots, \ n - 1)$ elements of 
$q$ is at least $B_i$ \cite{Landau1953}.\nevindex{Landau, H. G.}

$q$ is a score sequence of a $(k,k,n)$-tournament, iff the sum of the elements of $q$ equals to $kB_n,$ 
and the sum of the first $i$ elements of $D$ is at least $kB_i$ \cite{KemnitzD1997,Moon1962}.
\nevindex{Kemnitz, Arnfried}\nevindex{Dulff, Susann} 

$q$ is a score sequence of an $(a,b,n)$-tournament, if and only 
if (\ref{equation-interval}) holds \cite{Ivanyi2009}.\nevindex{Iványi, Antal Miklós}

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$. 
 
There are further papers on imbalances\index{imbalance} in different graphs 
\cite{KayibiKP2011,MubayiWW2001,Pirzada2008,PirzadaAK2011,PirzadaI2012MaCS,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}

You can find many references in \cite{Ivanyi2009,Ivanyi2010,IvanyiLS2011Acta}.

\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, further 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) and Zoltán Kása (Sapientia 
Hungarian University of Transylvania) for the consultation.

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliography{AlgofInf3-10Sept}
\bibliographystyle{algofinf}

\begin{printindex}
\end{printindex}

\begin{printnevindex}
\end{printnevindex}

\end{document}
