\documentclass[oneside,12pt,reqno]{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}

\theoremstyle{remark}
\newtheorem*{rem}{Remark}

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

\newcommand{\abs}[1]{\left\lvert#1\right\rvert}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\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{Vertex-Pancyclicity of Hypertournaments}
\author{Jed Yang}
\date{}
%    \address{address}                                    
%    \curraddr{curaddr}
%    \email{email}
%    \urladdr{urladdr}
    \dedicatory{Final Report\\\textup{\today}}
%    \date{date}
%    \thanks{thanks}
%    \translator{translator}                                 
%    \keywords{keyword}
%    \subjclass{subjclass}
%    \begin{abstract}...\end{abstract}   
\begin{abstract}
A hypertournament, or a $k$-tournament, on $n$ vertices, $2\leq k\leq n$, is a pair $T = (V, E)$,
where the vertex set $V$ is a set of size $n$ and the edge set $E$ is the collection of all possible subsets of size $k$ of $V$,
called the edges, each taken in one of its $k!$ possible permutations.
A $k$-tournament is vertex-pancyclic if each vertex is contained in (directed) cycles of all possible lengths.
A $k$-tournament is strong if there is a path from $u$ to $v$ for each pair of distinct vertices $u$ and $v$.
We examine the question posed by Gutin and Yeo about the characterization of vertex-pancyclic hypertournaments.
We utilize the majority digraph to reduce a $k$-tournament to an ordinary tournament (2-tournament).
We employ this method to extend Moon's theorem (a tournament is vertex-pancyclic if and only if it is strong) to hypertournaments.
We prove that for a $k$-tournament on $n$ vertices, if $k\geq 8$ and $n\geq k + 3$, then it is vertex-pancyclic if and only if it is strong.
The same conclusion holds if $k\geq 5$ and $n\geq k + 4$, or if $k = 4$ and $n\geq 11$, or if $k = 3$ and $n\geq 15$.
We also prove that when $n\geq7$, $k\geq4$, and $n\geq k+2$, a strong $k$-tournament on $n$ vertices is pancyclic if and only if it is strong.
The bound $n\geq k+2$ is tight.
We also find bounds for the generalized problem when we extend vertex-pancyclicity to require $d$ edge-disjoint cycles of each possible length and extend strong connectivity to require $d$ edge-disjoint paths between each pair of vertices.
Our results include and extend that of Petrovic and Thomassen.
\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$; the cycle has the same length $\l$.
A path (cycle) of $T$ is \emph{Hamiltonian} if it contains all vertices of $T$.

$V(X)$ and $E(X)$ denote the set of vertices and edges of $X$, respectively, where $X$ could be a (hyper)tournament, path, or cycle.
For a path $P$ and $u,\ v\in V(P)$, $uPv$ is the segment of $P$ from $u$ to $v$.
For paths $P,\ Q$ such that the terminal vertex of $P$ and the initial vertex of $Q$ are the same or are separated by a single edge (as in the case of a $2$-tournament),
$PQ$ is the path by adjoining $Q$ after $P$.

A $k$-tournament $T$ is $\emph{Hamiltonian}$ if it admits a Hamiltonian cycle.
It 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.
It is \emph{$d$-disjoint-vertex-pancyclic} if each vertex of $T$ is contained in $d$ edge-disjoint $\l$-cycles for each possible length $\l$.
%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.
%For a set $X$ of vertices and edges, 

A hypertournament $T$ is \emph{$d$-edge-connected} if, for any two distinct vertices $u,\ v\in V$, there are $d$ pairwise edge-disjoint paths from $u$ to $v$.
A $k$-tournament is \emph{strongly connected}, or simply, \emph{strong}, if it is $1$-edge-connected.

For distinct vertices $u,\ v\in V(T)$, $E_T(u,v)$ denotes the set of edges of $E(T)$ in which $u$ dominates $v$;
the subscript $T$ is omitted when the tournament is clear from context.
%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 Known Results}
Redei's theorem and Camion's theorem are two of the most well-known and important theorems regarding tournaments and Hamiltonicity:
\begin{thm}[Redei]
Every tournament has a Hamiltonian path.
\end{thm}
\begin{thm}[Camion]
Every strong tournament has a Hamiltonian cycle.
\end{thm}
Moon's theorem generalizes Camion's theorem:
\begin{thm}[Moon]
Every strong tournament is vertex-pancyclic.
\end{thm}
The proof of Redei's theorem is very simple; and a proof of Moon's theorem can be found in \cite{bg}.
% FIXME: really? check!
We shall refer to these theorems directly by name.

It is natural for one to ask whether these theorems hold for hypertournaments as well.
Gutin and Yeo~\cite{gy} proved the following.
\begin{thm}\label{thm-gy}
Let $k\geq3$.
\begin{enumerate}
\item Every $k$-tournament on $n\geq k+1$ vertices has a Hamiltonian path.
\item Every strong $k$-tournament on $n\geq k+2$ vertices has a Hamiltonian cycle.
\end{enumerate}
\end{thm}

Recently, Petrovic and Thomassen~\cite{pt} proved the following generalization of (ii).
\begin{thm}\label{thm-pt}
\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 or vertex-pancyclic.
Petrovic and Thomassen~\cite{pt} characterized the vertex-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.

However, Petrovic and Thomassen's characterization of vertex-pan\-cyclic $k$-tournaments is incomplete in that it is only proved for sufficiently large $n$.
In this paper, we will improve the bound that was given.
Furthermore, regarding the pancyclicity question posed by Gutin and Yeo,
we will give a necessary and sufficient condition for a $k$-tournament to be pancyclic.
However, our characterization is only for $n\geq7$ and $k\geq4$.
Finally, we will improve upon the generalization made by Petrovic and Thomassen in Theorem~\ref{pt-thm}.

\section{On Vertex-Pancyclicity}
Petrovic and Thomassen answered the primary problem of deciding if a $k$-tournament is vertex-pancyclic 
for $n\geq k+25$, $k\geq4$ and $n\geq32$, $k=3$, we relax these restrictions of $n$.
Their proof applied Hall's theorem first to provide disjointness of hyperedges, then remove hyperedges used by the path $P$, which will be described below.
We reverse the order, applying Hall's theorem after removing the hyperedges of $P$.

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

\begin{lem}\label{yang-lem-swap}
If $n\geq k+3$ for $k\geq8$, $n\geq k+4$ for $k\geq 5$, $n\geq11$ for $k=4$, and $n\geq15$ for $k=3$,
then $\binom{k}{2}\leq\ceil{\frac12\binom{n-2}{k-2}}-(n-1)$ for $k\geq4$ and
$\binom{k}{2}\leq\ceil{\frac12\binom{n-2}{k-2}}-4$ for $k=3$.
\end{lem}
\begin{proof}
It is trivial to check the case of $k=3$.
Assume $k\geq4$.
Suppose $n=k+3$, the inequality can be rearranged to give $k^2+k+3=2(\binom{k}{2}+k+2)-1\leq\binom{n-2}{k-2}=\binom{k+1}{k-2}=\frac16(k^3-k)$.
It is easy to verify that $k^3-6k^2-7k-18\geq0$ for $k\geq8$.
Similarly, for $n=k+4$, $k\geq5$ suffices.
For $k=4$, the inequality holds with $n=11$.
Now we apply induction on $n$,
we wish $\binom{n-2}{k-2}-2\binom{k}{2}-2n+3\geq0$.
We have established the respective base cases above.
If this inequality holds, increasing $n$ by 1 increases $\binom{n-2}{k-2}-2\binom{k}{2}-2n+3$
by $\binom{n-1}{k-2}-\binom{n-2}{k-2}-2=\binom{n-2}{k-3}-2$.
This is nonnegative for $k\geq4$, $n\geq k+1$.
\end{proof}

\begin{rem}
The ceiling is actually required for the case of $k=5$, $n=9$; the inequality does not hold when the ceiling is removed.
\end{rem}

Given a $k$-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 $k$-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.

We form an ordinary tournament ($2$-tournament) $M$ 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$ if $u$ dominates $v$ in at least half of the hyperedges of $T$ containing $u$ and $v$.
$M$ is called the \emph{majority digraph} of $T$.
In the case where $u$ dominates $v$ in exactly half of the hyperedges, $M$ will have an edge from $u$ to $v$ and another edge from $v$ to $u$.
Therefore, it is possible that the majority digraph is not strictly a tournament.
However, this distinction is immaterial to the following proofs.
Alternatively, one can randomly choose one of the two edges to exclude from $M$ to gurantee the majority digraph to be a tournament.

\begin{thm}
\label{yang-thm-swap}
Let $T$ be a $k$-tournament on $n$ vertices.
If $n\geq k+3$ for $k\geq8$, $n\geq k+4$ for $k\geq 5$, $n\geq11$ for $k=4$, and $n\geq15$ for $k=3$,
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,4,\ldots,n\}$, we shall find an $\l$-cycle of $T$ through $x$.
By construction of $M$, if $u$ dominates $v$ in $M$, then $u$ dominates $v$ via $\ceil{\frac12\binom{n-2}{k-2}}$ hyperedges of $T$.
Call these the \emph{corresponding hyperedges}.

Assume first that $k>3$.
If $M$ is strong, then by Moon's theorem $M$ has an $\l$-cycle $C'$ of $M$ through $x$.
Pick a corresponding hyperedge for each edge of $C'$, then we have an $\l$-cycle $C$ in $T$.
Thus we may assume that $M$ 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 $M$ as $S_1,\ldots,S_t$ such that
there are no hyperedges from $S_j$ to $S_i$, $1\leq i<j\leq t$.
We say these strong components are \emph{canonically ordered}.
% new-4
$S_1$ and $S_t$ are called the \emph{initial} and \emph{terminal strong components} of $M$, respectively.

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 $S_t$ to the initial component $S_1$.
Adding the $p$ edges $\{x_0x_1,x_1x_2,\ldots,x_{p-1}x_p\}$ to $M$, 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 $\ceil{\frac12\binom{n-2}{k-2}}$ corresponding hyperedges.
Since $P$ has at most $n-1$ hyperedges,
%each edge of $C'$ has at least $\ceil{\frac12\binom{n-2}{k-2}}-(n-1)$ corresponding hyperedges available.
after removing the hyperedges in $P$ from $B$ in the bipartite graph $G$ constructed earlier,
the vertices in $A$ has degree at least $\ceil{\frac12\binom{n-2}{k-2}}-(n-1)$.
The vertices in $B$ has degree $\binom{k}{2}$,
thus by Hall's marriage theorem,
if $\binom{k}{2}\leq\ceil{\frac12\binom{n-2}{k-2}}-(n-1)$,
then there is a complete matching from $A$ into $B$.
By Lemma~\ref{yang-lem-swap}, the inequality is satisfied.
Thus we can choose a hyperedge for each remaining edge of $C'$ such that all the hyperedges chosen (including those from $P$) are distinct.
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.

Assume now $k=3$.
We repeat the first part of the proof.
Again, $P$ may have as many as $n-1$ hyperedges.
However, for each pair of vertices, by Lemma~\ref{lem-4}, at most $4$ of its corresponding hyperedges are in $P$.
Therefore we require $\binom{k}{2}\leq\ceil{\frac12\binom{n-2}{k-2}}-4$ instead, which is satisfied by Lemma~\ref{yang-lem-swap}.
\end{proof}

\begin{rem}
Gutin and Yeo~\cite{gy} proved that for $k\geq3$, a hypertournament with $n\geq k+1$ has a Hamiltonian path and one with $n\geq k+2$ has a Hamiltonian cycle (Theorem~\ref{thm-gy}).
These bounds are tight:
It is obvious that there are no Hamiltonian paths for $n=k$;
Gutin and Yeo constructed a strong $k$-tournament with $n=k+1$ vertices yet admits no Hamiltonian cycle (see \cite{gy}).
\end{rem}

For $k\geq8$, this theorem says a strong $k$-tournament with $n\geq k+3$ vertices is vertex-pancyclic.
We also know that this statement is false for $n=k+1$.
For the $n=k+2$ case, it is currently unknown whether the statement holds.
We will, however, fill this gap with pancyclicity in the following section.
Also, for $k<8$, there are a few more cases that have not been decided.

\section{On Pancyclicity}
For sufficiently large $n$ and $k$,
a strong $k$-tournament $T$ with $n=k+2$ vertices is pancyclic.
To show this, we will modify Lemmas~3.2 and 3.4 of \cite{gy}, which were used to prove the second part of Theorem~\ref{thm-gy}.

Given a strong $k$-tournament $T$ and its majority digraph $M$,
we say that $(P,Q)$ is an \emph{$\l$-cyclic pair of paths},
if $P$ is a $x\to y$ path in $T$ and $Q$ is a $y\to x$ path in $M$ such that
$V(P)\cap V(Q)=\{x,y\}$ and $\abs{V(P)\cup V(Q)}=\l$.
We also require that $x$ and $y$ be in different strong components of $M$ if $M$ is not strong.

\begin{lem}\label{yang-lem-pair}
For every strong $k$-tournament with $n$ vertices, there exists an $\l$-cyclic pair of paths.
\end{lem}
\begin{proof}
Let $T$ be a strong $k$-tournament with $n$ vertices.
Suppose the majority digraph $M$ of $T$ is strong.
Then by Moon's theorem, $M$ is vertex-pancyclic, hence there exists an $\l$-cycle $R=x_1 x_2\ldots x_\l x_1$ in $M$.
Then $P=x_1 e x_2$, where $e$ is a $x_1\to x_2$ edge, and $Q=x_2 R x_1$ form an $\l$-cyclic pair of paths.

Now we assume that $M$ is not strong, and let $S_1,\ldots,S_t$ be the canonically ordered strong components of $M$ (as in Theorem~\ref{yang-thm-swap}).
Let $R=x_1 e_1 x_2 e_2 \ldots e_{m-1} x_m$ be the shortest $S_t\to S_1$ path in $T$.
Then $x_1\in S_t$, $x_m\in S_1$, and $\{x_2,\ldots,x_{m-1}\}\cap(S_1\cup S_t)=\emptyset$.
%Let $S_{\l'}$ be the strong component containing $x_\l$.
Recall that $x_\l$ is not in $S_t$, and that there are no edges from $S_t\ni x_1$ to the strong component containing $x_\l$.
Therefore, since $M$ is semicomplete, $x_\l x_1$ is an edge in $M$.
Therefore, if $m\geq\l$, then $P=x_1 R x_\l$ and $Q=x_\l x_1$ form an $\l$-cyclic pair of paths, where the endpoints are in different strong components.

Now we assume $m<\l$, let $M'=M-\{x_2,x_3,\ldots,x_{m-1}\}$ and let $S'_1,\ldots,S'_{t'}$ be the canonically ordered strong components of $M'$.
Notice that $M'$ is also semi-complete, and that $x_1\in S'_{t'}$ and $x_m\in S'_1$ are still in the (new) terminal and initial components, respectively.
We want a path $Q$ of length $\l-m+1\geq2$ from $x_m$ to $x_1$ in $M'$, then $(R,Q)$ is an $\l$-cyclic pair of paths.

It remains to construct the desired path $Q$.
Let $j$ be minimum such that $s=\abs{S'_1}+\abs{S'_2}+\cdots+\abs{S'_j}+\abs{S'_{j+1}}\geq\l-m+1$.
For each strong component $S'_i$, $1\leq i\leq j$, we choose a Hamiltonian path $Q'_i$, which is guranteed by Camion's theorem.
For $Q'_1$, we stipulate that the path starts at $x_m\in S'_1$.
Now we construct path $Q'_{j+1}$ such that $Q=x_m Q'_1 Q'_2\ldots Q'_j Q'_{j+1} x_1$ is of length $\l-m+1$.
Notice that there is precisely an edge from the terminal vertex of $Q'_i$ to the initial vertex of $Q'_{i+1}$, so the path $Q$ is well-defined.
If $j+1=t'$, then $x_1\in S'_{j+1}$ and $S'_{j+1}$ is strong hence vertex-pancyclic (Moon's theorem).
Thus we can construct a cycle $C$ in $S'_{j+1}$ of length $\l-m+2-s+\abs{S'_{j+1}}$ passing through $x_1$.
Then let $Q'_{j+1}$ be obtained from $C$ by removing the edge of $C$ starting at $x_1$.
Otherwise, if $j+1<t'$, let $Q'_{j+1}$ be a path in $S'_{j+1}$ of length $\l-m+1-s+\abs{S'_{j+1}}$, which can be constructed similarly.
Then indeed $\abs{Q'_1}+\abs{Q'_2}+\cdots+\abs{Q'_j}+\abs{Q'_{j+1}\cup\{x_1\}}=\l-m+2$,
so $Q$ has length $\l-m+1$, as desired.
\end{proof}

%Now we modify Lemma 3.4 of \cite{gy}.
\begin{thm}\label{yang-thm-pancyclic}
Every strong $k$-tournament with $n$ vertices, where $n\geq k+2\geq6$ and $n\geq7$, is pancyclic.
\end{thm}
\begin{proof}
For $n\geq k+2\geq6$, $\tbinom{n-2}{k-2}\geq 2n-4$ if and only if $n\geq7$.
Let $T$ be a $k$-tournament with $n$ vertices, such that $n\geq k+2\geq6$ and $\tbinom{n-2}{k-2}\geq 2n-4$,
and let $M$ be the majority digraph of $T$.

Gutin and Yeo proved that $T$ is Hamiltonian (Theorem~\ref{thm-gy}).
%Gutin and Yeo proved in Lemma 3.4 of \cite{gy} that $T$ is Hamiltonian.
Thus we fix a length $\l\in\{3,4,\ldots,n-1\}$, and show that there exists an $\l$-cycle in $T$.

We first suppose that $M$ is strong.
Then by Moon's thereom, there exists an $\l$-cycle $C'=x_1x_2\ldots x_\l x_1$ in $M$.
Then for $i=1,2,\ldots,\l$, $\abs{E(x_{i-1},x_i)}\geq\tfrac12\tbinom{n-2}{k-2}\geq n-2$, where we define $x_0=x_\l$ (when $i=1$).
Hence if $\l\leq n-2$, by Hall's marriage theorem, we can choose corresponding hyperedges $e_j$'s from $T$
so that $C=x_1 e_1 x_2 e_2\ldots e_{\l-1}x_\l e_\l x_1$ is an $\l$-cycle in $T$.
So we may assume that $\l=n-1$.
%Since $k\geq4$, 
There exists distinct edges $e_1$ and $e_2$, such that $\{e_1,e_2\}\subseteq E(x_1,x_2)$.
Also, since $k\leq n-2=\l-1$, and that $e_1$ and $e_2$ does not contain the same set of vertices,
one of them does not contain a vertex in the set $\{x_3,x_4,\ldots,x_{\l-1}\}$.
Without loss of generality, assume $x_i\not\in e_1$, where $i\in\{3,4,\ldots,\l-1\}$.
Since $\abs{E(x_{i-1},x_i)}\geq \l-1$, by Hall's theorem, we can choose corresponding hyperedges $f_j$ from $T$
so that $$P=x_i f_1 x_{i+1} f_2 \ldots x_\l f_{\l-i+1} x_1 e_1 x_2 f_{\l-i+2} x_3 \ldots f_{\l-2}x_{i-1}$$
is a path of length $\l-1$.
Now as $e_1\not\in E(x_{i-1},x_i)$, since $x_i\not\in e_1$, and $\abs{E(x_{i-1},x_i)}\geq \l-1$,
there is an edge $f_{\l-1}\in E(x_{i-1},x_i)-E(P)$.
Hence $C=Px_{i-1}f_{\l-1}x_i$ is a cycle of length $\l$, as desired.

Now suppose that $M$ is not strong.
By Lemma~\ref{yang-lem-pair}, there exists an $\l$-cyclic pair of paths $(P,Q)$, where $P=x_1e_1x_2e_2\ldots e_{p-1}x_p$ is a path in $T$,
and $Q=y_1y_2\ldots y_q$ is a path in $M$, $y_1=x_p$ and $y_q=x_1$.
Recall that $y_1$ and $y_q$ are in different strong components of $M$.
Fix $i$ such that $y_i$ and $y_{i+1}$ are in different strong components of $M$.
By definition of $M$, $\abs{E(y_{j-1},y_j)}\geq\tfrac12\tbinom{n-2}{k-2}\geq n-2\geq \l-1$ for $j>1$.
Also, if $\abs{E(y_i,y_{i+1})}=n-2$, then $\abs{E(y_{i+1},y_i)}\geq n-2$; but $y_i$ and $y_{i+1}$ are in different strong components,
thus $\abs{E(y_i,y_{i+1})}\geq n-1\geq\l$.
%Also, for $1\leq a\leq i<b\leq q$, if $\abs{E(y_a,y_b)}=n-2$, then $\abs{E(y_b,y_a)}\geq n-2$; but $y_a$ and $y_b$ are in different strong components, thus
%$\abs{E(y_a,y_b)}\geq n-1$ for $1\leq a\leq i<b\leq q$.
%
%If $q=2$, then $P$ is a path satisfying (\ref{star}).
%So we may assume that $q>2$.
%By Hall's marriage theorem, 
As $\abs{E(y_{j-1},y_j)}\geq \l-1$ for $j>1$,
we can extend the path $P$ to a path $R=r_1 f_1 r_2 f_2\ldots f_{\l-1} r_\l$ in $T$
with $r_1 = y_{i+1},\ r_2=y_{i+2},\ldots,r_{q-i}=y_q=x_1,r_{q-i+1}=x_2,\ldots,r_{\l+1-i}=x_p=y_1,r_{\l+2-i}=y_2,\ldots,r_\l=y_i$,
using edges of $P$ and choosing the remaining edges as guranteed by Hall's theorem.
%
Now as $\abs{E(y_i,y_{i+1})}\geq\l$, there is an edge $f_\l \in E(y_i,y_{i+1})-E(R)$.
Hence $R y_i f_\l y_{i+1}$ is a cycle of length $\l$ in $T$.
%
%Since $\abs{E(R)}=\l-2$ and $\abs{E(y_{i-1},y_i)}\geq n-2$, and $\l<n$,
%there is an edge in $T$ in which $y_{i-1}$ dominates $y_i$ and which is not already used in $R$.
%Then we have a $y_{i+1}\to y_i$ path of length $\l-1$ by using $R$ and this extra edge,
%and that $\abs{E(y_i,y_{i+1})}\geq n-1$.
%
%Thus (\ref{star}) is completely proved.
%We first prove that $T$ has a pair of distinct vertices $u,\ v$ and a $u\to v$ path of length $\l-1$ in $T$ such that
%\[ \text{$\abs{E(v,u)}\geq n-1$.} \tag{*} \label{star}\]
%\[ \text{there exists a $u\to v$ path of length $\l-1$ in $T$ and $\abs{E(v,u)}\geq n-1$.} \tag{*} \label{star}\]
%
%Let $C=c_1d_1c_2d_2\ldots d_{\l-1}c_\l$ be a path of length $\l-1$ in $T$ such that $\abs{E(s_\l,s_1)}\geq n-1$.
%Since $\abs{E(C)}=\l-1$ and $\abs{E(s_\l,s_1)}\geq n-1$, and $\l<n$,
%there is an edge $e$ in $T$ in which $c_\l$ dominates $c_1$ and which is not already used in $C$.
%So $Cc_\l ec_1$ is a cycle of length $\l$ in $T$.
\end{proof}

%\begin{rem}
%When $M$ is strong, we even have vertex-pancyclicity.
%We need to re-examine the second half of the proof to see if it can't be simplified.
%\end{rem}

\section{On $d$-Disjoint-Vertex-Pancyclicity}
Now we consider the generalized problem by extending vertex-pan\-cyclicity to require $d$ edge-disjoint cycles of each possible length and
extending strong connectivity to require $d$ edge-disjoint paths between each pair of vertices.

To prove the following lemma, we introduce the calculus of finite differences:
The \emph{finite forward difference} $\Delta_x f(x)$ of a function $f(x)$ with respect to $x$ is defined as $\Delta_x f(x)=f(x+1)-f(x)$.
The $n$-th finite difference is defined inductively as $\Delta_x^n f(x)=\Delta_x(\Delta_x^{n-1} f(x))$.
If the function has more variables, they are held constant.
This is the discrete analog of the derivative.
\begin{lem}\label{yang-lem-swap-d}
If $n\geq k+2d+1$ for $k\geq8$, then 
$$d\left[\tbinom{k}{2}+(n-1)\right]\leq\ceil{\tfrac12\tbinom{n-2}{k-2}}.$$
\end{lem}
\begin{proof}
Suppose $k\geq8$ and $n\geq k+2d+1$, we want to show that
$$f=f(n,k,d)=\tbinom{n-2}{k-2}+1-2d\left[\tbinom{k}{2}+n-1\right]$$ is nonnegative.
Now
\begin{eqnarray*}
\Delta_n f(n,k,d)&=&\tbinom{n-1}{k-2}+1-2d\left[\tbinom{k}{2}+n\right]\\
&&-\left(\tbinom{n-2}{k-2}+1-2d\left[\tbinom{k}{2}+n-1\right]\right)\\
&=&\tbinom{n-2}{k-2}+\tbinom{n-2}{k-3}-2dn-\left(\tbinom{n-2}{k-2}-2dn+2d\right)\\
&=&\tbinom{n-2}{k-3}-2d,
\end{eqnarray*}
which is nonnegative when $n\geq k+2d+1$ and $k\geq8$.
Therefore it remains to show that $f$ is nonnegative when $n=k+2d+1$.
%We first show that $f$ is nonnegative when $n=k+2d+1$, and then show that $\Delta_n f(n,k,d)\geq0$ for all $k\geq8$, $d\geq1$, then we are done.

To show that $$g(k,d)=f(k+2d+1,k,d)=\tbinom{k+2d-1}{k-2}+1-2d\left[\tbinom{k}{2}+k+2d\right]$$ is nonnegative,
we shall show that $g(k,1)$, $\Delta_d\,g(k,1)$, $\Delta_d^2\,g(k,1)$ and $\Delta_d^3\,g(k,d)$ are all nonnegative for $k\geq8$.

Now $g(k,1)=\binom{k+1}{k-2}+1-2\left[\binom{k}{2}+k+3\right]$ reduces to the case of $n=k+3$ considered in Lemma~\ref{yang-lem-swap}, and is nonnegative.

Now note that $$\tbinom{k+2d+1}{k-2}=\tbinom{k+2d+1}{2d+3}=\tfrac{k+2d+1}{2d+3}\tfrac{k+2d}{2d+2}\tbinom{k+2d-1}{2d+1},$$
hence
\begin{eqnarray*}
\Delta_d\,g(k,d)&=&g(k,d+1)-g(k,d)\\
&=&\tbinom{k+2d+1}{k-2}-2\left[\tbinom{k}{2}+k\right]-4(d+1)^2-\tbinom{k+2d-1}{2d+1}+4d^2\\
&=&\left(\tfrac{k+2d+1}{2d+3}\tfrac{k+2d}{2d+2}-1\right)\tbinom{k+2d-1}{2d+1}-k^2-k-8d-4.
\end{eqnarray*}
In particular,
\begin{eqnarray*}
\Delta_d\,g(k,1)&=&\left(\tfrac{k+3}{5}\tfrac{k+2}{4}-1\right)\tbinom{k+1}{3}-k^2-k-8-4\\
&=&\tfrac{1}{120}(k^5+5k^4-15k^3-125k^2-106k-1440),
\end{eqnarray*}
which has only one real root between $5$ and $6$, and is $37$ when $k=6$.
Similarly,
\begin{eqnarray*}
\Delta_d^2\,g(k,d)&=&\Delta_d\,g(k,d+1)-\Delta_d\,g(k,d)\\
&=&\left[\left(\tfrac{k+2d+3}{2d+5}\tfrac{k+2d+2}{2d+4}-2\right)\left(\tfrac{k+2d+1}{2d+3}\tfrac{k+2d}{2d+2}\right)+1\right]\tbinom{k+2d-1}{2d+1}-8.
\end{eqnarray*}
Then
\begin{eqnarray*}
\Delta_d^2\,g(k,1)&=&\left[\left(\tfrac{k+5}{7}\tfrac{k+4}{6}-2\right)\left(\tfrac{k+3}{5}\tfrac{k+2}{4}\right)+1\right]\tbinom{k+1}{3}-8\\
&=&\tfrac{1}{5040}(k^2+19k+76)(k+1)k(k-1)(k-2)(k-3)-8,
\end{eqnarray*}
which is clearly increasing when $k\geq4$, and is 20 when $k=5$.
Finally,
\begin{eqnarray*}
\Delta_d^3\,g(k,d)&=&\Delta_d^2\,g(k,d+1)-\Delta_d^2\,g(k,d)\\
&=&\tfrac{(k^2+8dk+17k+16d^2+56d+30)(k+4d+7)(k-2)(k-3)(k-4)}{(2d+7)(2d+6)(2d+5)(2d+4)(2d+3)(2d+2)}\tbinom{k+2d-1}{2d+1},
\end{eqnarray*}
which is clearly nonnegative for $k\geq4$, $d\geq1$.
Therefore $g(k,d)\geq0$ for $k\geq8$, and $f(n,k,d)$ is increasing in $n$ for $n\geq k+2d+1$, we have that $f$ is indeed nonnegative for $n\geq k+2d+1$, $k\geq8$, as desired.
\end{proof}

\begin{thm}
\label{yang-thm-swap-d}
Let $T$ be a $k$-tournament on $n$ vertices.
If $n\geq k+2d+1$ for $k\geq8$ and $n\geq14d+1$ for $k=3$,
then $T$ is d-disjoint-vertex-pancyclic if and only if $T$ is $d$-edge-connected.
\end{thm}
\begin{proof}
We review the proof of Theorem~\ref{yang-thm-swap}.
It is again obvious that a $d$-disjoint-vertex-pancyclic $T$ is $d$-edge-connected.
Now assume that $T$ is $d$-edge-connected.
We again consider $k>3$ first.
Fix a vertex $x$ of $T$ and a length $\l\in\{3,\ldots,n\}$, we shall find $d$ disjoint $\l$-cycles of $T$ through $x$.
We again construct the majority digraph $M$.
Previously, since $T$ is strong, there exists a path $P$ in $T$ connecting a vertex $x_1$ from the terminal component $S_t$ to a vertex $x_2$ in the initial component $S_1$.
Now, because $T$ is $d$-edge-connected, $T$ has $d$ edge-disjoint paths $P_1,P_2,\ldots,P_d$ connecting $x_1$ to $x_2$.
We add the edges of $P_i$ to $M$ to obtain a strong semi-complete digraph $D_i$.
Moon's theorem gives us an $\l$-cycle $C_i'$ through $x$.
Now we choose corresponding hyperedges to get $d$ disjoint $\l$-cycles of $T$ through $x$.
The edges arising only from the $P_i$'s can be directly used, as before.
Since $P_i$ has at most $n-1$ hyperedges, $P_1,\ldots,P_d$ can use at most $d(n-1)$ hyperedges.
Since each remaining edge of $M$ corresponds to $\ceil{\frac12\tbinom{n-2}{k-2}}$ hyperedges,
after removing the hyperedges in the $P_i$'s from $B$ in the bipartite graph $G$,
the vertices in $A$ has degree at least $\ceil{\frac12\tbinom{n-2}{k-2}}-d(n-1)$.
Now we want to choose $d$ corresponding hyperedges for each of the remaining edges of $M$, such that all edges are disjoint.
This can be accomplished by replicating $A$ $d$ times.
Let $A'=\{(a,i):a\in A,\ 1\leq i\leq d\}$,
and join $(a,i)\in A'$ with $b\in B$ if and only if $a$ and $b$ are joined in $G$.
Consider this new bipartite graph with partite classes $A'$ and $B$.
Now each vertex in $B$ has degree $d\binom{k}{2}$.
By Hall's marriage theorem, if $$d\tbinom{k}{2}\leq\ceil{\tfrac12\tbinom{n-2}{k-2}}-d(n-1),$$
which is satisfied by Lemma~\ref{yang-lem-swap-d},
then there is a complete matching from $A'$ into $B$.
Thus for each edge $e$ of $M$, we get $d$ hyperedges of $T$ by taking those matched to $(e,i)$, $1\leq i\leq d$.
Now as these hyperedges are all distinct, and disjoint from those of $P_1,\ldots,P_d$,
we can use these to from edge-disjoint $\l$-cycles $C_1,\ldots,C_d$ through $x$ in $T$.

For $k=3$, Lemma~\ref{lem-4} allows us to replace $n-1$ with $4$ in the above proof.
Now $d\binom{k}{2}\leq\ceil{\frac12\binom{n-2}{k-2}}-4d$ becomes $3d\leq\ceil{\frac12(n-2)}-4d$,
which is satisfied when $n\geq14d+1$.
%The proof is the same as Theorem~\ref{yang-thm-swap} except we require
%$$\ceil{\tfrac12\tbinom{n-2}{k-2}}\geq d\left[\tbinom{k}{2}+n-1\right]$$
%(Lemma~\ref{lem-4} replaces $n-1$ with $4$ for $k=3$).
%We then replicate the partite class $A$ of graph $G$ $d$ times and apply Hall's marriage theorem.
%The details are (temporarily) omitted.
\end{proof}

\section{Conclusion}
We prove that a $k$-tournament $T$ on $n$ vertices is vertex-pancyclic if and only if $T$ is strong when $n\geq k+3$ for $k\geq8$,
$n\geq k+4$ for $k\geq5$, $n\geq11$ for $k=4$, and $n\geq15$ for $k=3$.
If we only require pancyclicity, then for $n\geq7$ and $k\geq4$, pancyclicity and strongly connectedness are equivalent for $n\geq k+2$.
This bound is tight.
Finally, we proved that $d$-disjoint-vertex-pancyclicity and $d$-edge-connectivity are also equivalent for sufficiently large $n$ and $k\geq8$ or $k=3$.

\section{Acknowledgements}
The author would like to thank Dr. Richard Wilson of the California Institute of Technology for his support in supervising this research.
We also gratefully acknowledge the support by the Summer Undergrad Research Fellowships program of the same institute.
This research is funded by the Richter Memorial Funds.

\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{lw} J. H. van Lint and R. M. Wilson, \bibbook{A Course in Combinatorics}, Cambridge University Press (1993).
%\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}

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