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

\usepackage{amssymb}

%\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}
%}

\renewcommand{\proof}{\subsubsection*{Proof}}
\newcommand{\solution}{\subsubsection*{Solution}}

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

\begin{document}
\title{Hamiltonian Cycles in Tournaments}
\author{Jed Yang}
\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_{k-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$.

\section{Known Results}
Gutin and Yeo \cite{gy} proved the following.
\newtheorem{thm}{Theorem}
\newtheorem{lemma}{Lemma}
\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}

\section{Unsolved Problems}
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.
My first task in the beginning of the summer shall be to deduce this claim from the proof of Theorem \ref{pt-thm}.
Then I shall attempt to solve the general problem for $n$ not necessarily sufficiently large.

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

\section{Exposure and Experiences}
I am a sophomore majoring in mathematics.
I have taken Ma 121a, and will have finished Ma 121b and c by the summer.
I have also attended several seminars in combinatorics on Thursday mornings.
I find combinatorics, especially graph theory, very interesting and would like to have further exposure and experience working
on hypertournaments and graph theory in general this coming summer.

\begin{thebibliography}{9}
\bibitem{gy} G. Gutin and A. Yeo,
Hamiltonian paths and cycles in hypertournaments,
J Graph Theory 25 (1997), 277-286.
\bibitem{pt} V. Petrovic and C. Thomassen,
Edge-disjoint Hamiltonian cycles in hypertournaments,
J Graph Theory 51 (2006), 49-52.
\bibitem{t1} C. Thomassen, Problem 1, Discrete Math 36 (1981), 231.
\bibitem{t2} C. Thomassen, Edge-disjoint Hamiltonian paths and cycles in tournaments,
Proc London Math Soc 45 (1982), 151-168.
\end{thebibliography}
\end{document}