\documentclass[b5paper,11pt]{book}
\usepackage{Szeged-2011marcius28}
\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}

\begin{center}
\huge
\textcolor{blue}{\textbf{\sf{$(a,b)$-VERSENYEK}}}

\large
\vspace{4mm}
\textcolor{green}{\textbf{Iványi Antal, Pong Bui Minh}}


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





\section*{Bevezetés}
Legyenek $a \geq 0,$ $b \geq a$, $n \geq 1$ és $k \geq 2$ 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)$.

A $\mathcal{H}_n(a,b,k)$ \textbf{hiperverseny} olyan hipergráf, amelynek $n$ csúcsa  van, és bármely $k$ különbözõ csúcsa között 
összesen legalább $a$ és legfeljebb $b$ hiperél van. Ez a verseny megadható olyan $\mathcal{M} = [m_{ij}]_{c \times (n + 1)}$ 
mátrixszal, amelynek $c = \textbinom{n}{k}$ sora és $n$ oszlopa van, sorai a csúcsokból képezett $k$-asokhoz tartoznak 
(lexikografikus sorrendben) és minden sor elemei azt mutatják, hogy a $k$-asban szereplõ csúcsokból hány hiperél meg az oszlopnak 
megfelelõ csúcshoz. 


Egy $\mathcal{T}_n(a,b)$ verseny kifokainak nemcsökkenõen rendezett $\mathbf{s} = \langle s_1, s_2,\ldots,$ \linebreak
\noindent $ s_n \rangle$ sorozatát \textbf{pontsorozatnak}, befokainak nemcsökkenõen rendezett 
$\mathbf{t} = \langle t_1, t_2, \ldots, t_n \rangle$ sorozatát \textbf{vesztõsorozatnak}, az $\mathbf{(s,t)}$ sorozatpárt 
\textbf{kettõs sorozatnak}, a különbözõ kifokainak $\mathbf{h} = \{ h_1, h_2, \ldots, h_m \}$ 
halmazát pedig \textbf{ponthalmaznak} 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 $S_{tenisz} = \{1:0\}$, a \textbf{sakk} eredményei $S_{sakk} = \{2:0, \ 1:1 \}$, 
a focié $S_{foci} =\{3:0, \ 1:1 \}$. A tenisz és a sakk \textbf{teljes sportok,} míg a foci \textbf{hiányos sport.}

\section*{1. 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.    
 
\section*{2. Focisorozatok ellenõrzése \cite{Ivanyi2003,Ivanyi2004,Ivanyi2006,Palvolgyi2009}}
Kérdéses annak bonyolultsága, hogy nemnegatív egészek növekvõ sorozata lehet-e egy focibajnokság pontsorozata.

2003-ban arról beszéltem, hogyan próbáltuk adott sorozatról gyorsan eldönteni, hogy lehet-e focisorozat.

\textcolor{blue}{\section*{3. $(a,b)$-sorozatok ellenõrzése \cite{Avery1991,BeasleyBR2009,Brualdi2001,BrualdiK2009,
Csirik2003,ErdosG1960,Frank1976,GriggsR1999,GuiduliGyTW1998,Hakimi1962,Havel1955,Ivanyi2009,IvanyiSP2011,KemnitzD1997,
Landau1953,Meierling2009,Moon1968,PecsySz2000,PirzadaNSI2010,Reid1996,Ryser1957,Thomassen1981}}}
A témakör klasszikus eredménye Landau 1953-as tétele \cite{Landau1953}.
\begin{tetel} \emph{(Landau, 1953)}
A nemnegatív egészeket tartalmazó $\mathbf{s} = (s_1,s_2,$\linebreak 
\noindent $\ldots,s_n)$ monoton nemcsökkenõ sorozat 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 \cite{Moon1963} kiterjesztette $(a,a,n)$-versenyekre, majd Kemnitz és Dolff 
1997-ben \cite{KemnitzD1997} adtak egy egyszerû bizonyítást a kiterjesztésre. Számos helyreállító algoritmus ismert, például 
Gervacio és Ryser \cite{Gervacio1988,Gervacio1993,Moon1968} javasoltak négyzetes futási idejû algoritmust.

$(a,b)$-sorozatok gyors ellenõrzését teszi lehetõvé a következõ tétel \cite{Ivanyi2009}.

\begin{tetel} \emph{(Iványi, 2009)} Nemnegatív\label{tetel-Ivanyiabell} egészek 
$D = \langle d_1, d_2, \ldots, d_n \rangle$ nemcsökkenõ 
sorozata (ahol $n \geq 2$) akkor és csak akkor pontsorozata egy $T_n(a,b)$ versenynek, ha  
\begin{equation}
aB_k \leq \sum_{i = 1}^k d_i \leq bB_n - L_k - (n - k)d_k \quad (1 \leq k \leq n),\label{equation-interval}
\end{equation}
ahol
\begin{equation}
L_0 = 0, \hbox{ és } L_k = \max \left( L_{k - 1}, \ bB_k - \sum_{i = 1}^{k} d_i  
\right ) \quad (1 \leq k \leq n).\label{equation-loss} 
\end{equation}
\end{tetel}

Ha létezik megfelelõ verseny, akkor a \cite{Ivanyi2009} cikkben és a \cite{Hamori2011} TDK-dolgozatban leírt 
algoritmus $O(n^2d_n)$ idõ alatt elõállít egyet. 

Csirik János kérdezte 2003-ban \cite{Csirik2003}, hogy mit mondhatunk egy sorozatról akkor, 
ha csak a mérkõzések egy része van lejátszva. Ha nem írjuk elõ, mely meccsek vannak lejátszva, akkor a feladat értelmezhetõ 
$(0,1)$-versenyként, és akkor az \ref{tetel-Ivanyiabell} tétellel megoldható.

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

Ha egy $\mathbf(s)$ sorozat nem pontsorozatra nem teljesednek annak szükséges feltételei, hogy $(a,b)$-verseny 
pontsorozata lehessen, találhatunk alkalmas $a'$ és $b'$ számokat úgy, hogy \textbf{s} pontsorozata legyen valamely 
$(a',b')$-versenynek. Ha például a $P_i$ versenyzõ az összes pontját a $P_{i+1}$ versenyzõ ellen szerzi (modulo $n$), 
akkor máris van megoldásunk. 

Egy tavaly megjelent cikkben \cite{Ivanyi2010} sikerült a lehetõ legnagyobb 
$a$ és a legkisebb $b$ értéket meghatározni, amelyekkel adott $\mathbf{s}$ helyreállítható, és gyors 
helyreállító algoritmus is sikerült találni, 
amely a \textsc{Pont-szeletelés} javított változata. 

\textcolor{blue}{\section*{5. (1,1)-halmazok és (2,2)-halmazok karakterizálása 
\cite{Hager1986,IvanyiP2004,IvanyiBP2011,PirzadaIK2011,Reid1978,Reid2004,Yao1989}}} 
Reid 1978-ban fogalmazta meg \cite{Reid1978} híres sejtését, amely szerint a teniszezõk mindenre képesek. Ez matematikai 
formában a következõ.
\begin{sejtes} \emph{(Reid, 1978)} Nemnegatív egész számok bármely $H$ halmazához létezik olyan $T_n$ $(1,1)$-verseny, amelynek 
$H$ a ponthalmaza.  
\end{sejtes}

Probléma felvetõ cikkében Reid bizonyította a sejtést 1-, 2- és 3-elemû halmazokra, majd 
Hager 1986-ban \cite{Hager1986} 4- és 5-elemû halmazokra. Yao 1989-ben -- Landau tételét felhasználva -- 
átfogalmazta a következõ aritmetikai állítássá, és számelméleti eszközökkel be is bizonyította \cite{Yao1989}, 
Konstruktív bizonyítás azonban mindmáig nem ismert.

\begin{tetel} \emph{(Yao, 1988)} Ha $0 \leq h_1 < h_2 < \cdots < h_m$, akkor léteznek olyan 
$x_1, \ x_2, \ \ldots, \ x_m$ pozitív egészek, amelyekre
$$
\sum_{i=1}^{j} x_i h_i \geq \frac{(\sum_{i=1}^{j} x_i)(\sum_{i=1}^{j} x_i - 1)}{2}, \ j \in[1:m-1]$$
és
$$\sum_{i=1}^{m} x_i h_i = \frac{(\sum_{i=1}^{m} x_i)(\sum_{i=1}^{m} x_i - 1)}{2}\koz .$$
\end{tetel}

A sakkozók is sok ponthalmazt elõ tudnak állítani, de nem mindet \cite{IvanyiP2004}.

\begin{lemma} \emph{(Iványi, Phong,2004)} Ha $k \geq 1,$ és az $\mathbf{s}$ pontsorozathoz a 
$\mathbf{h}$ ponthalmaz tartozik, akkor az $m = 1$ esetben  
\begin{equation}
n = 2h_1 + 1
\end{equation}
és az $m \geq 2$ esetben
\begin{equation}
\frac{2h_1}{k} + 1 < n < \frac{2h_m}{k} + 1 \label{eq-bounds}
\end{equation}
és
\begin{equation}
n \geq h_m + 1\koz.
\end{equation}
\end{lemma}

Ez a lemma az $m = 1$ esetben pontos választ ad \cite{IvanyiP2004}.

\begin{kov} Ha $\mathbf{h} = \langle h_1 \rangle$, akkor pontosan a 
$\mathbf{s} = \langle h_1^{2h_1 + 1} \rangle$ pontsorozathoz tartozik a  $\mathbf{h}$ ponthalmaz.
\end{kov}
 
Másik érdekes következmény az, hogy nincs olyan sakkverseny, amelyen az elsõ és az utolsó között egy pont különbség van. . Sakkban 
ugyanis $k = 2$, és ekkor (\ref{eq-bounds}) szerint $h_1 + 1 < n < h_m + 1$, ami nem lehetséges, ha $h_m$ és $h_1$ 
különbsége 1.  
 
A 2004-es debreceni MACS konferencián konstruktív eredményeket is elmondtunk. 

\textcolor{blue}{\section*{6. Kettõs $(a,b)$-sorozatok optimális helyreállítása \cite{Hakimi1965,IvanyiSP2011,PatrinosH1976}}} 
Hakimi a következõ, kettõs sorozatokra vonatkozó tételt bizonyította 1965-ben \cite{Hakimi1965}, amelynek $a = b = 1$ 
speciális esetét a közelmúltban újra bizonyították H. Kim, Z. Toroczkai, Miklós István, Erdõs L. Péter és 
Székely László \cite{Kim2009}.

\begin{tetel} \emph{(Hakimi1965)} Legyen\label{thm-Hakimi} $n \geq 2$ egy pozitív $D = (d_1, d_2, \ldots, d_n)$ and $L = (l_1, l_2, 
\ldots, l_n)$ két, nemnegatív egészeket tartalmazó vektor, amelyek úgy vannak rendezve, hogy $d_i + l_i \leq d_{i+1} + l_{i+1} 
\ (i = 1, 2, \ldots, n - 1$, és $d_1 + l_1 > 0$. Akkor és csak akkor van olyan $(0,\infty)$-verseny, amelynek $D$ a pontvektora és  
$L$ a vesztõvektora, ha
\begin{equation}
\sum _{i=1}^n d_i = \sum _{i=1}^n l_i\label{eq-sum}
\end{equation}
és  
\begin{equation}
\sum _{i=1}^n (d_i + l_i) \geq d_n + l_n.\label{eq-last} 
\end{equation}
\end{tetel}

Ezt a tételt felhasználva lineáris idõ alatt eldönthetõ, hogy adott $(D,L)$ vektorpár 
kettõs vektora-e egy $(0,\infty)$ versenynek. Célunk:

a) ha $L$ és $D$ kielégítik az \ref{thm-Hakimi} tétel feltételeit, hogyan konstruálhatunk a lehetõ legkiegyensúlyozottabb 
versenyt?

b) ha $L$ és $D$ nem elégítik ki az \ref{thm-Hakimi} tétel feltételeit, hogyan definiáljuk a legjobb közelítõ megoldást és 
azt hogyan állítsuk elõ.

\section*{7. $(a,b)$-sorozatok közelítõ helyreállítása \cite{Ivanyi2011,IvanyiSP2011}}
Ha nem léteznek az elõírt foksorozatokkal rendelkezõ versenyek, akkor természetes feladat közelítõ megoldás keresése. Tegyük fel, 
hogy a 2012-es magyar focibajnokságban minden csapat megmondhatja, hány gólt akar rúgni, és hányat kapni. 
Valószínû, hogy több gólt akarnak majd rúgni, mint kapni, ezért minden kívánság nem teljesíthetõ. 

Az $n$ csapathoz hozzávéve \textbf{még egyet,} és mindenki annak rúgja a góljait, és attól kapja, 
könnyen teljesíthetõk a többiek kívánságai. Ekkor optimalizációs cél lehet, hogy a többlet csapat szerepe minél kisebb legyen. 
Egy másik lehetõség, hogy több csapatnál is megengedjük a kívánságoktól való eltérést, 
de az eltérések összegét akarjuk minimalizálni.
   
\section*{8. Hiperversenyek \cite{Hamori2011,Hager1986,PirzadaZI2010,ZhouYZ2000}}
Korábban a tanszéken rendszeresen rendeztünk ultibajnokságot. Hármas csoporokban játszottunk. Mi idõre játszottunk, de lehetne úgy, 
hogy például 1000 pontot teszünk az asztal közepére, és azon osztozunk. 

Szoktunk hárman úgy teniszezni, hogy felváltva vagyunk egyedül, és 5 gémet játszunk. 
Így mindig van gyõztes. A gyõzelem két pontot ér (ha ketten gyõznek, feleznek). Így egy \idez{körben} hat pont osztódik ki, és 
a lehetséges kiosztások halmaze $S = (4,1,1),(3,3,0),(2,2,2)$. Ez így egy hiányos (6,6,3) hipersport. Ha valahogy definiálunk egy 
gyõztest, aki egy pontot kap, akkor egy teljes (1,1,3) hipersportot kapunk. Utóbbira átvihetõ a Landau-tétel lényege, 
elõbbi nehéz.

Négyen szoktunk úgy játszani, hogy minden párosításban játszunk egy szettet. Ha egy szet két pontot ér, amelyet 
a gyõztesek osztanak el egymás között, akkor $S = (3,1,1,1), (2,2,2,0)$ és egy hiányos $(6,6,4)$ hipersportot kapunk. 
Ha csak egy gyõztest definiálunk, akkor egy teljes $S = (1,1,4)$ hipersportot kapunk.  

Végére hagytam a kérdést: mire képesek az $(1,1,3)$ hipersportolók?  \\

\textcolor{red}{\textbf{@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@}} \\

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{Avery1991} P. Avery, Score sequences of oriented graphs. \textit{J. Graph Theory} 
\textbf{15} 3 (1991) 251--257. 

\bibitem{BeasleyBR2009} L. B.  Beasley, D. E. Brown, K. B. Reid, Extending partial tournaments. 
\textit{Math. Comput. Modelling} \textbf{50} 1 (2009) 287--291.

\bibitem{Brualdi2001} A. R. Brualdi, J. Shen, Landau's inequalities for tournament scores and a short proof of a 
theorem on transitive sub-tournaments, \textit{J. Graph Theory} \textbf{38} 4 (2001) 244--254. 

\bibitem{BrualdiK2009} A. R. Brualdi, K. Kiernan, Landau's and Rado's theorems and partial tournaments. 
\hrefun{http://www.combinatorics.org/Volume_16/PDF/v16i1n2.pdf}{\textit{Electron.}} 
\textit{J. Combin.} \textbf{16} \#N2 (6 pp) (2009). \textbf{letölthetõ}  

\bibitem{Csirik2003} Csirik János: Szóbeli kérdés. Szeged, 2003. április 22.

\bibitem{ErdosG1960} P. \hrefun{http://hu.wikipedia.org/wiki/Erd$\%$C5$\%$91s_P$\%$C3$\%$A1l}{Erd\H os}, 
T. Gallai, Graphs with prescribed degrees of vertices (Hungarian). \textit{Mat. Lapok} 
\textbf{11} (1960) 264--274. 

\bibitem{Frank1976} A. Frank, A. Gy\'arf\'as, \hrefun{http://www.cs.elte.hu/~frank/cikkek/FrankP2.PDF}{How to orient} 
the edges of a graph? In \textit{Combinatorics. Vol. 1} 
(ed. A. Hajnal and V. T. S\'os), North-Holland, Amsterdam-New York, 1978. pp. 353--364. \textbf{letölthetõ}

\bibitem{Gervacio1988} S. V. Gervacio, Score sequences: Lexicographic enumeration and tournament construction
\textit{Discrete Math.} \textbf{72} 1--3 (1988) 151--155. 

\bibitem{Gervacio1993} S. V. Gervacio, Construction of tournaments with a given score sequence. 
\textit{Southeast Asian Bull. Math.} \textbf{17} 2 (1993) 151--155. 

\bibitem{GriggsR1999} J. \hrefun{http://www.math.sc.edu/~griggs/}{Griggs}, K. B. Reid, Landau's theorem revisited, 
\hrefun{http://ajc.maths.uq.edu.au/?page=get_volumes&volume=20}{\textit{Australas.}} \textit{J. Comb.} 
\textbf{20} (1999) 19--24.  \textbf{letölthetõ}

\bibitem{GuiduliGyTW1998}  B. Guiduli, A. Gyárfás, S. Thomassé, P. Weidl,  
$2$-partition-transitive tournaments. \textit{J.} \hrefun{http://www.sciencedirect.com/science/journal/00958956}{\textit{Combin.}} 
\textit{Theory Ser. B} \textbf{72} 2 (1998) 181--196. \textbf{digitálisan}

\bibitem{Hager1986} M. Hager: On score sets for tournaments, 
\hrefun{}{\textit{Discrete Mathematics}} \textbf{58} (1) (1986) 25--34. \textbf{digitálisan}

\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. \hrefun{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. \hrefun{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. \hrefun{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. \hrefun{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}  
\hrefun{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. \hrefun{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}: 
Reconstruction of complete interval tournaments. 
\hrefun{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. \hrefun{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}: 
Reconstruction of complete interval tournaments. II. 
\hrefun{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. \hrefun{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. \hrefun{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}, 
B. M. \hrefun{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. \hrefun{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}, 
B. M. \hrefun{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. \hrefun{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}, 
S. \hrefun{http://www.dharwadker.org/pirzada/}{Pirzada}: 
Comparison based ranking. In: 
\hrefun{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{Kim2009} H. Kim, Z. Toroczkai, I. Miklós, P. L. Erdõs, L. A. Székely, Degree-based graph construction.  
\textit{J. Physics: Math. Theor. A} (2009) \textbf{42} (39) 392001 (10 pp). 

\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{Meierling2009} D. Meierling, L. Volkmann, A remark on degree sequences of multigraphs. 
\textit{Math. Methods Oper. Res.} \textbf{69} 2 (2009) 369--374. 

\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{Palvolgyi2009} D. Pálvölgyi, Deciding soccer scores and partial orientations of graphs. 
\hrefun{http://www.acta.sapientia.ro/acta-math/matematica-main.htm}{\textit{Acta Univ. Sapientiae, Mathematica}} 
\textbf{1} 1 (2009) 35--42.  

\bibitem{PatrinosH1976} A. N. Patrinos, S. L. Hakimi, Relations between graphs and integer-pair sequences. 
\textit{Discrete Math.} \textbf{15} 4 (1976) 347--358.

\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. \hrefun{http://www.dharwadker.org/pirzada/}{Pirzada}, \textit{Graph Theory}. 
Orient BlackSwan, Hyderabad, 2011 (nyomdában). \textbf{digitálisan}

\bibitem{PirzadaIK2011} S. \hrefun{http://www.dharwadker.org/pirzada/}{Pirzada}, 
A. \hrefun{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: \hrefun{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. \hrefun{http://www.dharwadker.org/pirzada/}{Pirzada}, T. A. Naikoo, U. Samee, A. 
\hrefun{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}: Imbalances in directed multigraphs. 
\hrefun{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. \hrefun{http://www.dharwadker.org/pirzada/}{Pirzada}, G. Zhou, A. 
\hrefun{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}: 
Score lists in multipartite hypertournaments. 
\hrefun{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{Ryser1957} H. J. Ryser, Combinatorial properties of matrices of zeros and ones. 
\hrefun{}{Canad.} J. Math. \textbf{9} (1957) 371--377. \textbf{letölthetõ}

\bibitem{Sierksma1991} G. Sierksma, H. Hoogeveen, Seven criteria for integer sequences being graphic, \textit{J. Graph Theory} 
\textbf{15} 2 (1991) 223--231. \textbf{digitálisan}

\bibitem{Thomassen1981} C. Thomassen, Landau's characterization of tournament score sequences. In \textit{The Theory and 
Applications of Graphs}. John Wiley \& Sons, 1981, pp. 589--591.

\bibitem{ZhouYZ2000} G. Zhou, T. Yao, K. Zhang, On score sequences of $k$-hypertournaments. 
\textit{Eur. J. Comb.} \textbf{21} 8 (2000) 993--1000. 

\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  \hrefun{tony@compalg.inf.elte.hu}{tony@compalg.inf.elte.hu}

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

\end{document} 


