%compiled 64 times
\documentclass[oneside,12pt]{amsart}

\usepackage{amssymb}
%\usepackage{amsrefs}

%\usepackage{fancyhdr}
%\pagestyle{fancy}
%\fancyhf{} %delete the current header
%\fancyhead[L]{Ma121a\#2}
%\fancyhead[R]{Yang \thepage}
%\renewcommand{\headrulewidth}{0pt}
%\fancypagestyle{title}{
%\fancyhf{}
%\fancyhead[L]{Ma121a\#2}
%\fancyhead[R]{2005.10.12}
%}

\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}

%\renewcommand{\proof}{\subsubsection*{Proof}}

\newcommand{\abs}[1]{\left\lvert#1\right\rvert}
\renewcommand{\l}{\ell}

\renewcommand{\labelenumi}{(\roman{enumi})}

\newcommand{\bibvol}[1]{\textbf{#1}}
\newcommand{\bibbook}[1]{\textit{#1}}
\newcommand{\bibjournal}[1]{\textit{#1}}

\begin{document}
\title{Hamiltonian Cycles in Tournaments}
\author{Jed Yang}%\\5 Jul 2006}
\date{July 5, 2006}
\date{\today}
\date{}
%    \address{address}                                    
%    \curraddr{curaddr}
%    \email{email}
%    \urladdr{urladdr}
    \dedicatory{First Progress Report\\\textup{July 5, 2006}}
%    \date{date}
%    \thanks{thanks}
%    \translator{translator}                                 
%    \keywords{keyword}
%    \subjclass{subjclass}
%    \begin{abstract}...\end{abstract}   
\maketitle
%\thispagestyle{title}

\section{Definitions}
Let $V$ be a $n$-set (set of size $n$).
Let $E$ be the collection of all possible $k$-subsets (subsets of size $k$) of $V$, $2\leq k\leq n$,
each taken in one of its $k!$ possible permutations.
A pair $T=(V,E)$ is called a \emph{hypertournament}, or a \emph{$k$-tournament}.
Each element of $V$ is a \emph{vertex}, and each ordered $k$-tuple of $E$ is a \emph{hyperedge} or, simply, an \emph{edge}.
For vertices $u,v\in V$ and an edge $e=(x_1,\ldots,x_k)\in E$,
we say $u$ \emph{dominates} $v$ via edge $e$ if $u$ precedes $v$ in $e$,
that is if $u=x_i$, $v=x_j$, $1\leq i<j\leq k$.
We denote this by $uev$.
A \emph{path} consists of an alternating sequence $$x_0 e_1 x_1 e_2 x_2\ldots x_{\l-1} e_{\l} x_{\l}$$
of distinct vertices $x_i$ and distinct edges $e_i$ so that $x_{i-1}$ dominates $x_i$ via $e_i$, $i=1,\ldots,\l$.
Such a path has \emph{length} $\l$.
A \emph{cycle} is a path when all vertices are distinct except $x_0=x_{\l}$.
A path (cycle) of $T$ is \emph{Hamiltonian} if it contains all vertices of $T$.
A $k$-tournament $T$ is \emph{pancyclic} if it contains cycles of all possible lengths.
It is \emph{vertex-pancyclic} if each vertex of $T$ is contained in cycles of all possible lengths.
A $k$-tournament $T$ is \emph{strong} if there is a path from $u$ to $v$ for each pair $u,v\in V$.
The vertex set $V$ and the edge collection $E$ is also denoted $V(T)$ and $E(T)$, respectively.
A hypertournament $T$ is \emph{$d$-edge-connected} if, for any two vertices $u,\ v\in V$,
there are $d$ pairwise edge-disjoint paths from $x$ to $y$.
For an ordinary graph $(V,E)$, $\Gamma(v)$ is the neighbors of $v$.
For $A\subseteq V$, we denote by $\Gamma(A)$ the set $\bigcup_{a\in A}\Gamma(a)$.

\section{Background and Motivation}
Gutin and Yeo~\cite{gy} proved the following.
\begin{thm}
\begin{enumerate}
\item Every $k$-tournament on $n$ vertices, $3\leq k\leq n-1$, has a Hamiltonian path.
\item Every strong $k$-tournament on $n$ vertices, $3\leq k\leq n-2$, has a Hamiltonian cycle.
\end{enumerate}
\end{thm}

Recently, Petrovic and Thomassen~\cite{pt} proved the following generalization of (ii).
%\begin{lemma}
%\label{pt-lemma}
%If $k\geq 4$ and $n\geq k+1+24d$, or $k=3$ and $n\geq 30d+2$,
%then the bipartite graph $G$ contains a spanning subgraph $G'$ (called a \emph{star matching})
%such that every vertex in $A$ has degree $2nd$ for $k\geq 4$ and $10d$ for $k=3$, and furthermore,
%every vertex in $B$ has degree $1$ or $0$ in $G'$.
%\end{lemma}

\begin{thm}
\label{pt-thm}
Let $T$ be a $d$-edge-connected $k$-tournament on $n$ vertices.
If $n\geq k+1+24d$ for $k\geq 4$, and $n\geq 30d+2$ for $k=3$, then $T$ has $d$ edge-disjoint Hamiltonian cycles.
\end{thm}

Gutin and Yeo~\cite{gy} mentioned as unsolved the problem of deciding if a $k$-tournament is pancyclic.
Petrovic and Thomassen~\cite{pt} characterized the pancyclic $k$-tournaments:
If $k\geq4$ and $n\geq k+25$ or if $k=3$ and $n\geq32$, then $T$ is vertex-pancyclic if and only if
$T$ is strong.

This characterization is incomplete in that it is only for $n$ large compared to $k$.
Furthermore, this is claimed without explaination.
Therefore, I shall deduce this claim from the proof of Theorem~\ref{pt-thm}, in the case when $d=1$.
Then I shall attempt to solve the general problem for $n$ not necessarily sufficiently large.
The work of Petrovic and Thomassen~\cite{pt} is very recent (2006), and therefore fits into ongoing work in mathematics.

\section{Progress}
The primary problem we are working on is to characterize vertex-pancyclic $k$-tournaments on $n$ vertices.
I read the primary reference \cite{pt} of my problem and read \cite{gy}, where the original problem was posed.
I understood the proof of Moon's theorem (every strong tournament is vertex pancyclic) from \cite{bg},
and deduced Camion's theorem (every strong tournament has a Hamiltonian cycle).
I independently proved Redei's theorem (every tournament has a Hamiltonian path) and presented the proof to my mentor Professor Wilson.
I found additional sources \cite{moon,t-e,t-p}.
I used the insight gained from \cite{gy} to understand the proof of Theorem~\ref{pt-thm} from \cite{pt}.
With a few modifications, Theorem~\ref{pt-thm} implies the result of Petrovic and Thomassen~\cite{pt} regarding the primary problem.

For the case of $k=3$, Petrovic and Thomassen answered the primary problem for $n\geq32$, we answer it for $n\geq29$.
\begin{lem}\label{lem-4}
Let $T$ be a $3$-tournament and $P$ a path of $T$.
A pair of distinct vertices $x$ and $y$ can be in at most four of the hyperedges of $P$.
\end{lem}
\begin{proof}
Let $P=v_0e_1v_1\ldots e_{\l}v_{\l}$.
Suppose $x = v_m$ and $y=v_n$ (remember that vertices are distinct).
As the hyperedges of a $3$-tournament are triplets,
if a hyperedge $e_i$ of $P$ contains both $x$ and $y$, at least one of the vertices is an endpoint of the hyperedge in $P$.
Therefore the hyperedges of $P$ containing both $x$ and $y$ are all incident upon $v_m$ or $v_n$ in $P$.
Hence there are at most four hyperedges of a path that contains a specific pair of distinct vertices.

If one of $x$ and $y$ is not a vertex of $P$ (respectively neither of them are), then it is clear that
the maximum number of hyperedges containing both $x$ and $y$ is reduced to two (respectively zero).
\end{proof}

Now we slightly alter Lemma 1 from \cite{pt}.
Given a $3$-tournament $T$, we form a bipartite graph $G$ with partite classes $A$ and $B$.
Every pair of vertices in $T$ is a vertex in $A$.
Every $3$-subset of vertices in $T$ is a vertex in $B$.
A vertex in $A$ is joined to a vertex in $B$ if the corresponding pair of vertices is contained in the corresponding $k$-subset.
\begin{lem}\label{yang-lem-29}
If $n\geq29$, then the bipartite graph $G$ contains a spanning subgraph $G'$ such that every vertex in $A$ has degree $9$
and every vertex in $B$ has degree at most $1$ in $G'$.
\end{lem}
\begin{proof}
Every vertex in $A$ has degree $n-2\geq27$ in $G$, and every vertex in $B$ has degree $3$ in $G$.
It follows that, for any subset $S\subseteq A$, $\abs{\Gamma(S)}\geq\frac{n-2}{3}\abs{S}\geq9\abs{S}$.
Hence $G'$ exists by Hall's marriage theorem.
\end{proof}

Using $G'$ we form an ordinary tournament ($2$-tournament) $T'$ from $T$ with vertex set $V(T)$ in the following way.
For $u,v\in V(T)$, orient the edge $uv$ from $u$ to $v$ iff $u$ dominates $v$ in at least 5 out of 9 neighbors of $\{u,v\}$ in $G'$.

\begin{thm}
\label{yang-thm-29}
Let $T$ be a $3$-tournament on $n$ vertices.
If $n\geq29$, then $T$ is vertex-pancyclic if and only if $T$ is strong.
\end{thm}
\begin{proof}
It is obvious from the definition that a vertex-pancyclic $T$ is strong.
Now assume that $T$ is strong.
Fix a vertex $x$ of $T$ and a length $\l\in\{3,\ldots,n\}$, we shall find an $\l$-cycle of $T$ through $x$.
By construction of $T'$, if $u$ dominates $v$ in $T'$, then $u$ dominates $v$ via $5$ hyperedges of $T$.
Call these the ``corresponding hyperedges.''
Moreover, these $5\binom{n}{2}$ hyperedges are distinct by Lemma~\ref{yang-lem-29}.

If $T'$ is strong, then by Camion's theorem $T'$ has a Hamiltonian cycle $H'$.
Pick a corresponding hyperedge for each edge of $H'$, then we have a Hamiltonian cycle $H$ in $T$.
Thus we may assume that $T'$ is not strong.

The relation that two vertices $u$ and $v$ are strongly connected (that there exists a $u\to v$ path and a $v\to u$ path)
is an equivalence relation; call the equivalence classes the strong components.
If $S_1$ and $S_2$ are strong components, there cannot be both an $S_1\to S_2$ edge and an $S_2\to S_1$ edge.
Hence we get a tournament on the strong components, treating each component as a vertex,
and orienting the edges between vertices according to the direction of the edges between the strong components.
By Redei's theorem, there is a Hamiltonian path.
Therefore, we can order the strong components of $T'$ as $T'_1,\ldots,T'_t$ such that
there are no hyperedges from $T'_j$ to $T'_i$, $1\leq i<j\leq t$.

Because $T$ is strong, there exists a path $P=x_0e_1x_1e_2x_2\ldots e_px_p$ in $T$ connecting a vertex from the terminal component $T'_t$ to the initial component $T'_1$.
Adding the $p$ edges $\{x_0x_1,x_1x_2,\ldots,x_{p-1}x_p\}$ to $T'$, we obtain a strong semi-complete digraph $D$
(every pair of vertices has one or two edges between them).
As Moon's theorem (a strong tournament is vertex-pancyclic) extends to strong semi-complete digraphs (see \cite{bg}),
there exists an $\l$-cycle $C'$ of $D$ through $x$.
We will form a cycle $C$ of $T$ from $C'$ by using the same vertex set (in the same permutation).
The only condition we need to check is that no edges are repeated.
For an edge $x_{i-1}x_i$ of $C'$ that originated from $P$, we use $e_i$ for $C$; note that these are distinct.
%Edges of $C'$ that originated from $P$ are already edges of $T$, and they are distinct.
For the remaining edges of $C'$, recall that each one has $5$ corresponding hyperedges.
By Lemma~\ref{lem-4}, at most $4$ of these $5$ hyperedges are in $P$.
Therefore, for each of the remaining edges, there exists a corresponding hyperedge that is disjoint from those of $P$.
These edges are themselves distinct by construction of $G'$ (vertices in $B$ has degree at most $1$; Lemma~\ref{yang-lem-29}).
Therefore by using these hyperedges, we have an $\l$-cycle $C$ of $T$ through $x$.
As $\l$ and $x$ are arbitrary, $T$ is vertex-pancyclic.
\end{proof}

\section{Plans and Remarks}
In the coming month, we plan to continue improving the partial result to the primary problem.
There are several steps of the proof of Theorem \ref{pt-thm} that may be improved,
especially for the special case of $d=1$.

In reading \cite{pt}, the lack of clear definitions of terminology made the proofs difficult to follow.
We utilized \cite{gy} as a resource to understand the terminology.
In the future, if similar situations arise, we shall read references provided by the paper in question
to further understand both terminology used and techniques employed.
Thus the resources needed will be the vast journal archives that the Caltech library system provides.
Another challenge is to know the proper direction of approach to unsolved problems.

%\begin{bibdiv}
%\begin{biblist}
%\bib{gy}{article}{
%   title={Hamiltonian paths and cycles in hypertournaments},
%   author={G. Gutin and A. Yeo},
%   journal={J Graph Theory},
%   volume={25},
%   date={1997},
%   pages={277--286}
%}
%\end{biblist}
%\end{bibdiv}
\newpage
\begin{thebibliography}{9}
\bibitem{bg} J. Bang-Jensen and G. Gutin, \bibbook{Digraphs: Theory, Algorithms and Applications}, Springer-Verlag, London (2001).
\bibitem{gy} G. Gutin and A. Yeo, Hamiltonian paths and cycles in hypertournaments, \bibjournal{J Graph Theory} \bibvol{25} (1997), 277--286.
\bibitem{moon} J. W. Moon, \bibbook{Topics on Tournaments}, Holt, Rinehart and Winston, New York (1968).
\bibitem{pt} V. Petrovic and C. Thomassen, Edge-disjoint Hamiltonian cycles in hypertournaments, \bibjournal{J Graph Theory} \bibvol{51} (2006), 49--52.
\bibitem{t-p} C. Thomassen, Problem 1, \bibjournal{Discrete Math} \bibvol{36} (1981), 231.
\bibitem{t-e} C. Thomassen, Edge-disjoint Hamiltonian paths and cycles in tournaments, \bibjournal{Proc London Math Soc} \bibvol{45} (1982), 151--168.
\end{thebibliography}
\end{document}

\section{Unsolved Problems}

A related problem is whether vertex-connectivity $10^{10}$ implies two edge-disjoint Hamiltonian cycles; see \cite{pt,t1,t2}.
For $k\geq2$, a graph $G$ is said to have vertex-connectivity $k$ when it has at least $k+1$ vertices and the 
removal of $k-1$ vertices does not result in a disconnected graph.
I can also explore other related problems concerning hypertournaments and edge-disjoint Hamiltonian cycles.

%For $n$ sufficiently large compared to $k$, this is a special case of Petrovic and Thomassen \cite{pt}.
%Setting $d=1$ in Theorem \ref{pt-thm}, we have this following:
%If $T$ is a $1$-edge-connected (strong) $k$-tournament on $n$ vertices,
%and $n\geq k+25$ for $k\geq 4$, and $n\geq 32$ for $k=3$, then $T$ has a Hamiltonian cycle.
%Now if $T$ has an Hamiltonian cycle, then clearly $T$ is strong.
%Therefore for sufficiently large $n$, $T$ is strong if and only if $T$ has a Hamiltonian cycle