\documentclass[11pt,twoside]{article} 
\usepackage{euler,acta-info}
\usepackage[latin2]{inputenc}
\frenchspacing

\usepackage{epic}
\usepackage{eepic}

\title{%
Imbalance sequences of football tournaments (February 6, 2012)
}

\newcommand{\vol}{\textbf{4,} 1 (2012) xx--yy}   %% to be completed by the editor, do not modify it
\setcounter{page}{1}  %% to be completed by the editor 

\newcommand{\amss}{\amssubj{%
%% Write here the AMS subject classification codes as: 68R15
05C85, 68R10
}}   %% Source:   http://www.ams.org/msc/    
\newcommand{\CRs}{\CRsubj{%
%% Write here the CR  Categories and Description codes codes as: 
G.2.2. [Graph Theory]: Subtopic - Network problems.
}}   %% Source: http://oldwww.acm.org/class/1998/
\newcommand{\keyw}{\keywords{%
%% Write here the keywords and phrases, as: 
tournament, imbalance sequence, polynomial algorithm, complexity
}} 

\newcommand{\idez}[1]{{\ideze}#1''}
\newcommand{\ideze}{\setbox0=\hbox{\lower1.38ex\hbox{''}}\dp0=0pt\box0}


\def\textbinom#1#2{\left(\strut\textstyle{#1 \atop #2}\right)}
\begin{document}
\maketitle
\twoauthors{%
\href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony&angolul=1}{Antal IV\'ANYI}}
{%
\href{http://compalg.inf.elte.hu/tanszek/index.php?angolul=1}{Department of Computer Algebra}, 
\href{http://www.elte.hu/en}{E\"otv\"os Lor\'and University}, Hungary}
{%
 \href{mailto:tony@compalg.inf.elte.hu}{tony@inf.elte.hu}
}{%
\href{http://people.inf.elte.hu/lulsaai}{Lor\'and LUCZ}
}{%
 \href{http://compalg.inf.elte.hu/tanszek/index.php?angolul=1}{Department of Computer Algebra}, 
 \href{http://www.elte.hu/en}{E\"otv\"os Lor\'and University}, Hungary}
{%
 \href{mailto:lorand-lutz@caesar.elte.hu}{lorand-lucz@caesar.elte.hu}}



 %% Short name of the authors and short title, to be included in heading.

\short{%
Antal Iv\'anyi and Lor\'and Lucz
}{%
Imbalance of football tournaments}

\begin{abstract}
An open problem is the complexity to decide whether a sequence of nonnegative integer numbers 
is the final score sequence of a football tournament \cite{Frank2011,Ivanyi2012,IvanyiP2012,LuczI2012}. 
In this paper we propose 
a polynomial algorithm to decide whether a sequence of 
nonnegative integers is the imbalance sequence of a football tournament.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\normalsize
\section{Introduction\label{sec-Intro}}
Let $a, \ b$ and $n$ be nonnegative integers $(b \geq a \geq 0, \ n \geq 1),$  
$\mathcal{T}(a,b.n)$ be the set of directed multigraphs $T = (V,E)$, where $|V| = n,$ 
and elements of each pair of different vertices $u, \ v \in V$ are connected 
with at least $a$ and at most $b$ arcs \cite{Ivanyi2009}. 
$T \in \mathcal{T}(a,b,n)$ is called $(a,b,n)$\textit{-tournament.} 
$(1,1,n)$-tournaments are the usual tournaments, and $(0,1,n)$-tournaments are also called 
oriented graphs or simple directed graphs \cite{Gross2004}. The set $\mathcal{T}$ is defined by
$$
\mathcal{T} = \bigcup _{b\geq 1, \ n \geq 1} \mathcal{T}(0,b,n).
$$

An $(a,b,n)$-tournament is called \textit{complete,} if the set of permitted results is $\{0:c, 1:c - 1, \ldots,c:0\}$ for all 
possible $c \ (a \leq c \leq b).$ Is some of these results are prohibited, then the tournament is called \textit{incomplete.} 

The first result on the out-degree sequences of complete $(1,1,n)$-tournaments belongs to Landau, 
who in 1953 published the following necessary and sufficient condition.

\begin{theorem} If\label{theorem1} $n \geq 1$ then a sequence $(s_1, \ldots, s_n)$ 
of integers \textit{satisfying} $0 \leq s_1 \leq \ldots \leq s_n$ is the 
score sequence of some $(1,1,n)$-tournament $T$ if and only if 
\begin{equation}
\sum_{i = 1}^k s_i \geq B_k, \quad 1 \leq k \leq n,\label{eq-Landau}
\end{equation}
with equality when k = n.
\end{theorem}

Further results connected with complete tournaments can be found e.g. in \cite{Ivanyi2009,Ivanyi2010,
IvanyiLMS2011,IvanyiP2012}.

For example football is an incomplete $(2,3,n)$-tournament since the permitted results are $0:3$ and $1:1$ while $0:2$ and $1:2$ are not permitted.

According to this definition $\mathcal{T}$ is the set of the finite directed loopless multigraphs.

For any vertex $v \in V$ let $d(v)^+$ and
$d(v)^-$ denote the out-degree and in-degree of $x,$ respectively. 
Define $f(v) = d(v)^+ - d(v)^-$ as the imbalance of the vertex $v.$ 
The imbalance sequence of $T \in \mathcal{T}$ is formed by listing the vertex 
imbalances of the vertices in nonincreasing or nondecreasing order. 

The following result due to Avery \cite{Avery1991} and Mubayi, Will and West \cite{Mubayi2001} 
provides a necessary and sufficient condition for a nonincreasing sequence $F$ of integers to be 
the imbalance sequence of a tournament $T \in \mathcal{T}(0,1,n)$.

\begin{theorem}\label{theorem1} \emph{(Avery \cite{Avery1991}, Mubayi, Will, West \cite{MubayiWW2001})} A nonincreasing 
sequence of integers $F = (f_{1},\ldots,f_{n})$  is an imbalance sequence of a $(0,1,n)$ tournament if and only if 
\begin{equation*}
\sum^{k}_{i=1}f_i\geq k(n-k), 
\end{equation*}
for $1 \leq k < n$ with equality when $k = n.$
\end{theorem}

\begin{proof} See \cite{Avery1991,MubayiWW2001}.  
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Imbalance sequences of complete tournaments \label{sec-imbalances}}

In 1991 Avery \cite{Avery1991}

In 2001 Mubay, Will and West \cite{MubayiWW2001}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Incomplete tournaments \label{sec-incomplete}}
The first results on incomplete tournaments were published by Reid and Zhang in 1998. 
\begin{theorem}  \emph{(Reid, Zhang \cite{ReidZ1998})} If\label{theorem2} $n \geq 1$ then the 
nondecreasing sequence of nonnegatíve integer numbers $s = (s_1,\ldots,s_n)$ is the outdegree sequence 
of a semicompleted tournamant $T$ if and only if 
\begin{equation}
\sum _{i=1} ^k s_i \geq \binom{k}{2} \quad \mbox{and} \quad s_k \leq n - 1
\end{equation}
for all $1 \leq k \leq n.$
\end{theorem}

\begin{theorem}  \emph{(Reid, Zhang \cite{ReidZ1998})} If\label{theorem3} $n \geq 1$ and $s = (s_1,\ldots,s_n)$ is a nondecreasing sequence of nonnegatíve integers, then there exists a tournament $T$ with out-degree sequence $t = t_1,\ldots,t_n$ such, that 
$t_i \leq s_i$ for $1 \leq i \leq n.$the outdegree sequence of a semicompleted tournamant $T$ if and only if 
\begin{equation}
\sum _{i=1} ^k s_i \geq \binom{k}{2} \quad \mbox{and} \quad s_k \leq n - 1
\end{equation}
for all $1 \leq k \leq n.$
\end{theorem}

\begin{theorem} \emph{(Reid, Zhang \cite{ReidZ1998})} Theorem \ref{theorem1}, 
Theorem \ref{theorem2} and Theorem \ref{theorem3} are equivalent.
\end{theorem}

In 2002 Iv\'anyi \cite{Ivanyi2002} solved the following problem posed by Antal Bege \cite{Bege1998}: 
How many wins are necessary and sufficient in a $(1,1,n)$ 
tournament to guarantee that the teams have different number of points. 

Let $x \geq 0$ be a real number and define \textit{the real football tournament} with the permitted results 
$0:0$ and $0:0$ and $-1:1 + x.$ Let $f(x,n)$ denote the 
above described number of wins in a real football tournament of $n$ teams. 

\begin{theorem} If $n \geq 1$ then
\begin{equation} 
f(n,1) = (3/2 - \sqrt{2})n^2 + O(n), 
\end{equation}
if $x$ is zero or an integer greater or equal 2, then
\begin{equation}
f(n,x) = \frac{\lfloor n/2 \rfloor(\lfloor n/2 \rfloor + 1)}{2} = \frac{n^2}{8} + \rho(n),
\end{equation} 
where $\rho(n) = 0,$ if $n$ is even and $\rho(n) = 1/8,$ if $n \geq 3$ is odd, and
if $x$ is irrational, then 
\begin{equation}
f(n,x) = O(n^{3/2}).
\end{equation}
\end{theorem}
\begin{proof} See \cite{Ivanyi2002}.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Imbalance sequences of football tournaments \label{sec-football}}
Let the permitted results of the \textit{simplified football tournament} $T_n$ $0:0$ and $0:1.$

The following assertion gives a necessary and sufficient condition for a nonincreasing sequence $s = (s_1,\ldots,s_n)$ to be the imbalance sequence of a football tournament.

\begin{theorem}\label{theoremimb} A nonincreasing sequence of integers $S = (s_1,\ldots,s_n)$ is an imbalance sequence 
of a football tournament if and only if $s_i$ $(i = 1,\ldots,n)$ is a multiple of 3 and $s' = (s_1/3,\ldots,s_n/3)$ is the imbalance sequence of a complete $(0,1,n)$-tournament.
\end{theorem}
\begin{proof} The result $1:1$ between players $P_i$ and $P_j$ do not change the imbalance of $P_i$ and $P_j.$ The other possible 
result $3:0$ adds 3 to the imbalance of $P_i$ and subtracts 3 from the imbalance of $P_j.$ Therefore if $s$ is 
an imbalance sequence of a football tournament, then all elements of $s$ are the multiple of 3.  

$s$ is the imbalance sequence of a football tournament if and only if $s'$ is the imbalance sequence of a 
simplified football tournament. $s'$ is the imbalance sequence of a simplified football tournament if and only if it is the 
imbalance sequence of a complete $(0,1,n)$-tournament. 
\end{proof} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Optimization \label{sec-optimization}}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Summary \label{sec-summary}}

The referenced papers can be found at the homepage of the author at \newline  
\href{http://compalg.inf.elte.hu/~tony/Kutatas/EGHH/}{http://compalg.inf.elte.hu/$\sim$tony/Kutatas/EGHH/}.

\paragraph{Acknowledgements.} The European Union and the European Social Fund have provided financial support to the project 
under the grant agreement no. T\'AMOP 4.2.1/B-09/1/KMR-2010-0003.


\begin{thebibliography}{99}
\bibitem{AnholzerBBK2011} M. \href{http://kbo.ue.poznan.pl/anholcer/}{Anholcer}, V. Babiy, 
S. \href{http://www.oplab.sztaki.hu/cv_bs_hu.htm}{Boz\'oki}, 
W. W. \href{http://www.cs.laurentian.ca/wkoczkodaj/info.html}{Koczkodaj}, 
A simplified implementation of the least squares solution for pairwise comparisons matrices. 
\href{http://www.springerlink.com/content/1435-246x/}{\textit{CEJOR}} \textit{Cent. Eur. J. Oper. Res.}
\textbf{19,} (4) (2011) 439--444. 

\bibitem{Avery1991} P. Avery, Score sequences of oriented graphs, 
\textit{J. Graph Theory} \textbf{15,} (3) (1991) 251--257.

\bibitem{Bege1998} A. Bege, Personal communication, Visegrád, 19998.

\bibitem{BozokiFP2011} S. \href{http://www.oplab.sztaki.hu/cv_bs_hu.htm}{Boz\'oki} S.,    
J. \href{http://www.oplab.sztaki.hu/cv_fj_hu.htm}{F\"ul\"op},  
A. \href{http://portal.uni-corvinus.hu/index.php?id=801}{Poesz}: 
On pairwise \href{http://www.springerlink.com/content/u5564j3413400n67/fulltext.pdf}{comparison matrices} 
that can be made consistent by the modification of a few elements. 
\href{http://www.springerlink.com/content/1435-246x/}{\textit{CEJOR}} \textit{Cent. Eur. J. Oper. Res.} \textbf{19} (2011) 157--175.

\bibitem{BozokiFR2010} S. \href{http://www.oplab.sztaki.hu/cv_bs_hu.htm}{Boz\'oki}: 
J. \href{http://www.oplab.sztaki.hu/cv_fj_hu.htm}{F\"ul\"op}, L. \href{http://www.sztaki.hu/~ronyai/}{R\'onyai}:  
On optimal completion of incomplete pairwise comparison matrices,    
\textit{Math. Comput. Modelling} \textbf{52} (2010) 318--333.

\bibitem{BrualdiK2009} A. R. \href{http://www.math.wisc.edu/~brualdi/}{Brualdi},   
K. Kiernan: Landau's and {R}ado's theorems and partial tournaments,   
\href{http://www.combinatorics.org/Volume_16/PDF/v16i1n2.pdf}{\textit{Electron.}}   
\textit{J. Combin.} \textbf{16,} (\#N2) (2009) 6 pages.

\bibitem{CormenLRS2009} T. H. \href{http://www.cs.dartmouth.edu/~thc/}{Cormen},   
Ch. E. \href{http://people.csail.mit.edu/cel/}{Leiserson},  
R. L. \href{http://people.csail.mit.edu/rivest/}{Rivest},  
C. \href{http://www.columbia.edu/~cs2035/}{Stein},     
\textit{Introduction to Algorithms} Third edition, The
\href{http://mitpress.mit.edu/main/home/default.asp}{MIT} 
Press/\href{http://www.mhprofessional.com/category/?cat=1012}{McGraw} Hill, 
Cambridge/New York, 2009.

\bibitem{ErdosG1960} P. \href{http://www-history.mcs.st-and.ac.uk/Mathematicians/Erdos.html}{Erd\H os},     
T. \href{http://hu.wikipedia.org/wiki/Gallai_Tibor}{Gallai},   
Graphs with vertices having 
\href{http://www.renyi.hu/~p_erdos/1961-05.pdf}{prescribed degrees} (Hungarian), \textit{Mat. Lapok} \textbf{11} (1960) 264--274.

\bibitem{Frank2011} A. \href{http://www.cs.elte.hu/~frank/}{Frank}, \textit{Connections in Combinatorial Optimization,}   
\href{http://oup.com/}{Oxford} University Press, Oxford, 2011.

\bibitem{Gross2004} J. L. Gross, J. Yellen, 
\textit{Handbook of Graph Theory,} CRC Press, Boca Raton, 2004. 

\bibitem{Hakimi1962} S. L. \href{http://en.wikipedia.org/wiki/S.\_L.\_Hakimi}{Hakimi},    
On the realizability of a set of integers as degrees of the vertices 
of a simple graph. \textit{J. SIAM Appl. Math.} \textbf{10} (1962) 496--506. 

\bibitem{Hakimi1965} S. L. \href{http://en.wikipedia.org/wiki/S.\_L.\_Hakimi}{Hakimi},  
On the degrees of the vertices of a graph, \textit{F. Franklin Institute,} \textbf{279,} (4) (1965) 290--308.

\bibitem{Havel1955} V. Havel, A remark on the existence of finite graphs (Czech), \textit{\u{C}asopis P\u{e}st. Mat.}  
\textbf{80} (1955), 477--480. 

\bibitem{Ivanyi2002} A.  \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iv\'anyi}, 
Maximal tournaments. \textit{Pure Math. Appl.} \textbf{13,} (1--2) (2002) 171--183.

\bibitem{Ivanyi2009} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iv\'anyi},   
Reconstruction of complete interval tournaments, \textit{Acta Univ. Sapientiae,} 
\href{http://www.acta.sapientia.ro/acta-info/informatica-main.htm}{\textit{Inform.}}, 
\textbf{1(1),} (2009) 71--88.

\bibitem{Ivanyi2010} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iv\'anyi},     
Reconstruction of complete interval tournaments. II, \textit{Acta Univ. Sapientiae,}  
\href{http://www.acta.sapientia.ro/acta-math/matematica-main.htm}{\textit{Math.}}, 
\textbf{2,} (1) (2010) 47--71.

\bibitem{Ivanyi2011Egres} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iv\'anyi},    
Deciding the validity of the score sequence of a soccer tournament, in: \textit{Open problems of the}   
\href{http://lemon.cs.elte.hu/egres/open/Deciding_the_validity_of_the_score_sequence_of_a_soccer_tournament} 
(ed. by A. \href{http://www.cs.elte.hu/~frank/}{Frank}), 
{\textit{Egerváry}} \textit{Research Group,} Budapest, 2011. 

\bibitem{Ivanyi2012} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iv\'anyi}, 
Degree sequences of multigraphs. \textit{Annales Univ. Sci. Budapest., Sect. Computatorica} (submitted).

\bibitem{IvanyiLMS2011} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iv\'anyi}, 
L. Lucz, F. T. Móri, P. Sótér, On the Erdős-Gallai and Havel-Hakimi algorithms. \textit{Acta Univ. Sapientiae, Inform.} 
\textbf{3,} (2) (2011) 230--268. 

\bibitem{IvanyiP2011} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iv\'anyi},     
S. \href{http://www.dharwadker.org/pirzada/}{Pirzada}, Comparison based ranking, in: 
ed. A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iv\'anyi}, 
\href{http://www.tankonyvtar.hu/}{\textit{Algorithms}} \textit{of Informatics, Vol. 3,}    
\href{http://www.antoncom.hu/books.htm}{AnTonCom}, Budapest 2011, 1209--1258. 

\bibitem{Keri2011} G. \href{http://www.oplab.sztaki.hu/cv_kg_hu.htm}{K\'eri}, 
On qualitatively consistent, transitive and contradictory judgment matrices emerging from 
multiattribute decision procedures, \href{http://www.springerlink.com/content/1435-246x/19/2/}{\textit{CEJOR}} 
\textit{Cent. Eur. J. Oper. Res.} \textbf{19,} (2) (2011) 215--224. 

\bibitem{KernP2001}  K. Kern, D. Paulusma, The new FIFA rules are hard: complexity aspects of 
sport competitions, \href{}{\textit{Discrete}} \textit{Appl. Math.} \textbf{108,} (3) (2001) 317--323.

\bibitem{KernP2004} K. Kern, D. Paulusma, The computational complexity of the elimination problem in
generalized sports competitions, \textit{Discrete} \href{}{\textit{Optimization}} \textbf{1} (2004) 205--214.

\bibitem{Landau1953} H. G. Landau, On dominance relations and the structure of 
\href{http://www.springerlink.com/content/765042v152l07721/}{animal societies}. III. 
The condition for a score sequence, \textit{Bull. Math.} 
\href{http://www.springerlink.com/content/765042v152l07721/}{\textit{Biophys.}} \textbf{15,} (1953) 143--148. 

\bibitem{MubayiWW2001} Mubayi, D., T. G. Will and D. B. West,    
Realizing degree imbalances in directed graphs, \textit{Discrete Math.}  
\textbf{239,} (1--3) (2001) 147--153. 

\bibitem{NarayanaB1964} T. V. Narayana, D. H. Bent, Computation of the number of score sequences in 
round-robin \href{http://cms.math.ca/10.4153/CMB-1964-015-1}{tournaments}, 
\href{http://cms.math.ca/cmb/}{\textit{Canad.}} \textit{Math. Bull.} \textbf{7,} (1) (1964) 133--136.

\bibitem{PecsySz2000} G. P\'ecsy, L. Sz\H ucs,   
\href{http://www.cs.ubbcluj.ro/~studia-i/2000-2/2-Pecsy.pdf}{Parallel} verification and enumeration of tournaments,  
\textit{Stud. Univ.} \href{http://www.cs.ubbcluj.ro/~studia-i/contents.php}{Babe\c s-Bolyai}, 
\textit{Inform.} \textbf{45,} (2) (2000) 11--26. 

\bibitem{ReidZ1998} K. B. Reid, C. Q. Zhang, Score sequences of semicomplete digraphs, 
\textit{Bull. Inst. Combin. Appl.} \textbf{24} (1998) 27--32.
   
\bibitem{Soroker1990} D. Soroker, \textit{Optimal parallel construction of prescribed tournaments,} 
\href{http://www.sciencedirect.com/science/journal/0012365X}{\textit{Discrete}} \textit{Appl. Math.} 
\textbf{29,} (1) (1990) 113--125.  

\bibitem{Temesi2011} J. Temesi, Pairwise comparison matrices and the error-free property of the decision maker, 
\href{http://www.springerlink.com/content/1435-246x/19/2/}{\textit{CEJOR}} \textit{Cent. Eur. J. Oper. Res.} 
\textbf{19,} (2) (2011) 239--249. 

\end{thebibliography}

\end{document}

