\documentclass[b5paper,11pt]{book}
\usepackage{Szeged-2011marcius23}
\addtocounter{chapter}{1}
\def\binom#1#2{\left(\strut\displaystyle{#1 \atop #2}\right)}
\def\textbinom#1#2{\left(\strut\textstyle{#1 \atop #2}\right)}


\begin{document}

\section*{$(a,b)$-versenyek pontsorozatai és ponthalmazai} 

\begin{center}
Iv\'anyi Antal, Pong Bui Minh


(\textit{Szeged, 2011. március 29.})
\end{center}





\subsection*{Bevezetés}
Legyenek $a \geq 0,$ $b \geq a$ and $n \geq 1$ be nemnegatív egész számok. A $\mathcal{T}_n(a,b)$ \textbf{verseny} olyan 
irányított gráf, amelynek $n$ csúcsa  van, és bármely két különbözõ csúcsa között összesen legalább $a$ és legfeljebb $b$ él van. 
Ez a verseny megadható olyan $\mathcal{M} = [m_{ij}]_{n\times n}$ mátrixszal, amelyben $m_{ii} = 0 \ (1\leq i \leq n)$ 
és $a \leq m_{ij} + m_{ji}  \leq b \ (1 \leq i < j \leq n)$. 

Egy $\mathcal{T}_n(a,b)$ verseny kifokainak nemcsökkenõen rendezett $\mathbf{s} = \langle s_1, s_2,$ \linebreak 
\noindent $\ldots, s_n \rangle$ sorozatát \textbf{pontsorozatnak}, különbözõ kifokainak $\mathbf{t} = \{ t_1, t_2,$ \linebreak 
\noindent $ \ldots, t_m \}$ 
halmazát \textbf{ponthalmaznak} nevezzük. Az $\mathbf{(s,t)}$ sorozatpárt a verseny \textbf{kettõs pontsorozatának} nevezzük. 

A \textbf{sport} azon szabályok összessége, amelyek rögzítik a lehetséges eredményeket. Például a \textbf{tenisz} egyetlen 
lehetséges eredménye $\{1:0\}$, a \textbf{sakk} eredményei $\{2:0, \ 1:1 \}$, a focié $\{3:0, \ 1:1 \}$. A tenisz és a sakk 
\textbf{teljes sportok,} míg a foci \textbf{hiányos sport.}

\subsection*{1. feladat. Focimátrix elõállítása, amelyben a sorösszegek különbözõek 
és minimális számú hármas van a mátrixban \cite{Ivanyi2002}}
Ezt a feladatot Bege Antal kolozsvári kolléga adta Blázsik Zolinak és nekem az 1999-es visegrádi MACS konferencián, 
és a 2001-es félixfürdõi MACS-on mondtam el a megoldást.

Egy körmérkõzéses focibajnokságban biztosítanunk kell, hogy a csapatok pontszámai különbözzenek úgy, hogy ehhez a 
lehetõ legkevesebb gyõzelemre legyen szükség. Elõször nézzük a feladatot sakkverseny esetén. Legyen $n = 2k + 1 résztvevõ$. 
Elõször írjunk az eredménymátrixba mindenhová egyest. Az elsõ $k$ versenyzõt nevezzük erõsnek, a $(k + 1)$-ediket közepesnek, 
az utolsó $k$-t pedig gyengének. Az elsõ erõs versenyzõ gyõzzön minden gyenge ellen, így neki $k + 2k = 3k$ pontja lesz. A második 
erõs versenyzõ csak a $(k - 1)$ leggyengébb ellen gyõzzön, \ldots, a $k$-adik erõs versenyzõ pedig csak a $(k + 2).$ 
versenyzõ ellen. Így a pontszámok $3k, \ 3k - 1, \ \ldots k$ lesznek. Ez az optimális megoldás $n^2/8$ + $O(n)$ gyõzelmet igényel. 

A foci optimális megoldását négy csapaton mutatom meg. Elõször itt is döntetlenekkel töltjük ki az eredménymátrixot, 
majd az elsõ csapat nyer a második ellen és a második nyer a negyedik ellen. Így a pontszámok 5, 4, 3 és 2 lesznek, összesen két 
gyõzelem árán. Az ilyen módon kapott optimális megoldás $(3/2 - \sqrt{2})n^2 + O(n) \sim 0.0858 n^2 + O(n)$ 
gyõzelmet igényel.    
 
\subsection*{2. feladat. Focisorozatok ellenõrzése \cite{Ivanyi2003,Ivanyi2004,Ivanyi2006}}
Kérdéses annak bonyolultsága, hogy nemnegatív egészek növekvõ sorozata lehet-e egy focibajnokság pontsorozata.


\subsection*{3. $(a,b)$-sorozatok ellenõrzése 
\cite{Csirik2003,Hakimi1962,Havel1955,Ivanyi2009,IvanyiSP2011,KemnitzD1997,Landau1953,Moon1968,PecsySz2000,
PirzadaNSI2010,Reid1996}}
A témakör klasszikus eredménye Landau 1953-as tétele.
\begin{tetel}
A nemnegatív egészeket tartalmazó $\mathbf{s} = (s_1,s_2,\ldots,s_n)$ monoton nemcsökkenõ sorouat akkor és csak akkor 
pontsorozata egy $(1,1,n)$-versenynek, ha
\begin{equation}
\sum _{i=1}^k s_i \geq \binom{m}{2} \quad (k = 1, 2, \ldots n - 1)
\end{equation}
és
\begin{equation}
\sum _{i=1}^n s_i \geq \binom{n}{2}.
\end{equation}
\end{tetel}

Ezt a tételt Moon 1963-ban kiterjesztette $(a,a,n)$-versenyekre, majd Kemnitz és Dulff 1997-ben adtak egy egyszerû 
bizonyítást a kiterjesztésre.

Csirik János kérdezte 2003-ban, hogy mit mondhatunk egy sorozatról akkor, ha csak a mérkõzések egy része van lejátszva.

\subsection*{4. $(a,b)$-sorozatok optimális helyreállítása \cite{Ivanyi2010,IvanyiSP2011,KovacsP2002}}

\subsection*{5. (1,1)-halmazok és (2,2,n)-halmazok karakterizálása 
\cite{IvanyiP2004,IvanyiBP2011,PirzadaIK2011,Reid1978,Reid2004,Yao1989}} 

\subsection*{6. Kettõs $(a,b)$-sorozatok optimális helyreállítása \cite{Hakimi1965,IvanyiSP2011}} 

\subsection*{7. $(a,b)$-sorozatok közelítõ helyreállítása \cite{Ivanyi2011,IvanyiSP2011}} 

\subsection*{8. Hiperversenyek \cite{Hamori2011,PirzadaZI2010}}

Az irodalomjegyzékben \textbf{letölthetõ} megjegyzéssel szereplõ mûvek letölthetõk a megadott honlapról, 
a \textbf{digitálisan} megjegyzéssel szereplõ mûvek letölthetõek a 
\href{http://compalg.inf.elte.hu/~tony/Kutatas/Szeged/}{http://compalg.inf.elte.hu/$\sim$tony/Kutatas/Szeged/} 
honlapról, míg a \textbf{nyomtatva} megjegyzéssel szereplõ mûveket nyomtatott formában magammal viszem. 

\vspace{2mm}
\begin{thebibliography}{x}
\large
\vspace{-2mm}
\bibitem{Csirik2003} Csirik János: Szóbeli kérdés. Szeged, 2003. április 22.

\bibitem{Hakimi1962} S. L. 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. \textbf{digitálisan} 

\bibitem{Hakimi1965} S. L. Hakimi, On the degrees of the vertices of a directed graph. \textit{J. Franklin Inst.} 
\textbf{279} (1965) 290--308. \textbf{digitálisan}

\bibitem{Hamori2011} Hámori Ádám: Rangsorolás csoportos összehasonlítással. TDK dolgozat kézirata. 
ELTE IK, Budapest, 2011. \textbf{digitálisan}

\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. \textbf{digitálisan}

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

\bibitem{Ivanyi2003} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}: 
Rangsorolási algoritmusok. Szegedi informatikai szeminárium, 2003. április 22. \textbf{digitálisan}

\bibitem{Ivanyi2004} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}: 
Pontsorozatok ellenõrzése. XXV. Operációkutatási konferencia elõadáskivonatai (Debrecen, 2004. október 17--20). 
\textbf{digitálisan}

\bibitem{Ivanyi2006} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}: 
Deciding the validity of the score sequence of a soccer tournament. In: \emph{Open problems of the}  
\href{http://lemon.cs.elte.hu/egres/open/Deciding_the_validity_of_the_score_sequence_of_a_soccer_tournament}
{\emph{Egerváry Research Group}}. \textbf{letölthetõ}

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

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

\bibitem{Ivanyi2011} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}: 
Directed graphs with prescribed score sequences. In: Proc. of the 7th  Hungarian-Japanese Symposium 
(Kyoto, May 31 - June 3, 2011), elfogadva. \textbf{digitálisan}

\bibitem{IvanyiP2004} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}, 
B. M. \href{mailto:bui@compalg.inf.elte.hu}{Phong}: On the unicity of multitournaments. In: 
\textit{Fifth Conference on Mathematics and Computer Science} (Debrecen, June 9--12, 2004), 2004. \textbf{digitálisan}

\bibitem{IvanyiBP2011} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}, 
B. M. \href{mailto:bui@compalg.inf.elte.hu}{Phong}, S. Pirzada: 
Score sets of $(a,b)$-tournaments. In: \emph{Automata and  
Formal Languages} (Debrecen, August 17--22, 2011), benyújtva. \textbf{digitálisan}

\bibitem{IvanyiSP2011} A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}, 
S. \href{http://www.dharwadker.org/pirzada/}{Pirzada}: 
Comparison based ranking. In: 
\href{http://compalg.inf.elte.hu/~tony/Oktatas/FirstExpert/Volume3/}{\emph{Algorithms of Informatics}}, Vol. 3, 
ed. by A. Iványi. AnTonCom, Budapest 2011, 1262--1291. Manuscript. \textbf{digitálisan}

\bibitem{KemnitzD1997} A. Kemnitz, S. Dolff, Score sequences of multitournaments. 
\textit{Congr. Numer.} \textbf{127} (1997), 85--95. \textbf{nyomtatva} 

\bibitem{KovacsP2002} Kovács Gábor Zsolt, Pataki Norbert: Rangsorolási sorozatok elemzése. TDK doldozat. 
ELTE TTK Informatikai Tanszékcsoport, Budapest, 2002. \textbf{digitálisan}  

\bibitem{Landau1953} H. G. Landau, On dominance relations and the structure of animal societies. III. 
The condition for a score sequence, \textit{Bull. Math. Biophys.} \textbf{15} (1953), 143--148. \textbf{digitálisan}

\bibitem{Moon1963} J. W. Moon, An extension of Landau's theorem on tournaments. 
\hrefun{http://projecteuclid.org/DPubS?verb=Display\&version=1.0\&service=UI\&handle=euclid.pjm/1103034568\&page=record}
{\textit{Pacific}} \textit{J. Math.} \textbf{13} (1963) 1343--1345. \textbf{letölthetõ}  

\bibitem{Moon1968} J. W. Moon, \textit{Topics on Tournaments}. Holt, Rinehart and Winston. 
New York, 1968. \textbf{Rényi Intézet Könyvtára}

\bibitem{PecsySz2000} G. P\'ecsy, L. Sz\H ucs, Parallel verification and enumeration of tournaments.  
\textit{Stud. Univ. Babe\c s-Bolyai, Inform.} \textbf{45,} 2 (2000) 11--26. \textbf{letölthetõ}

\bibitem{Pirzada2011} S. \href{http://www.dharwadker.org/pirzada/}{Pirzada}, \textit{Graph Theory}. 
University of Kashmir, Srinagar, Kashmir, India. Orient BlackSwan, Hyderabad, 2011 (nyomdában). \textbf{digitálisan}

\bibitem{PirzadaIK2011} S. \href{http://www.dharwadker.org/pirzada/}{Pirzada}, 
A. \href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}, 
M. A. \hrefun{http://faculty.kfupm.edu.sa/PYP/malikhan/}{Khan}: Score sets and kings in oriented graphs. 
In: \href{http://compalg.inf.elte.hu/~tony/Oktatas/FirstExpert/Volume3/}{\emph{Algorithms of Informatics}}, 
Vol. 3, ed. by A. Iványi. AnTonCom, Budapest 2011. Kézirat. \textbf{digitálisan}

\bibitem{PirzadaNSI2010} S. \href{http://www.dharwadker.org/pirzada/}{Pirzada}, T. A. Naikoo, U. Samee, A. 
\href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}: Imbalances in directed multigraphs. 
\href{http://www.acta.sapientia.ro/acta-math/matematica-main.htm}{\emph{Acta Univ. Sapientiae, Mathematica}}, 
\textbf{2} (2) 2010, 137--145. \textbf{letölthetõ}

\bibitem{PirzadaZI2010} S. \href{http://www.dharwadker.org/pirzada/}{Pirzada}, G. Zhou, A. 
\href{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}: 
Score lists in multipartite hypertournaments. 
\href{http://www.acta.sapientia.ro/acta-info/informatica-main.htm}{\textit{Acta Univ. Sapientiae, Informatica}}, 
\textbf{2} (2) (2010), 184--193. \textbf{letölthetõ}

\bibitem{Reid1978} K. B. Reid, Score sets for tournaments. \textit{Congr. Numer.} \textbf{21} 
(1978) 607--618. 

\bibitem{Reid1996} K. B. Reid, Tournaments: Scores, kings, 
generalizations and special topics, \textit{Congr. Numer.} \textbf{115} (1996) 171--211. \textbf{nyomtatva}

\bibitem{Reid1998} K. B. Reid, C. Q. Zhang, Score sequences of semicomplete digraphs, 
\textit{Bull. Inst. Combin. Appl.} \textbf{24} (1998) 27--32. 

\bibitem{Reid2004} K. B. Reid, Tournaments. In \textit{Handbook of Graph Theory} (ed. J. L. Gross, J. Yellen),  
CRC Press, Boca Raton, 2004. \textbf{ELTE TTK Könyvtára}


\bibitem{Yao1989} X. Yao: On Reid conjecture of score sets for tournaments,
\textit{Chinese Science Bulletin,} \textbf{10} (1989), 804--808. \textbf{nyomtatva}

\end{thebibliography}

A szerzõk címe: Iványi Antal: \quad  \href{tony@compalg.inf.elte.hu}{tony@compalg.inf.elte.hu}

Phong Bui Minh: \quad  \href{bui@compalg.inf.elte.hu}{bui@compalg.inf.elte.hu}

\end{document} 


