Tight paths in fully directed hypergraphs

Abstract

It is well-known that every tournament has a spanning path. We consider hypergraph analogues. In an \emph{$r$-uniform fully directed hypergraph}, or \emph{$r$-digraph}, every edge is a list or $r$ distinct vertices. An $(r,k)$-tournament is an $r$-digraph $G$ such that for every $r$-set $S$ of vertices in $G$, exactly $k$ of the orderings of $S$ are edges in $G$. A \emph{directed tight path} is an $r$-digraph $G$ whose vertices can be ordered so that the intervals of size $r$ are the edges in $G$. Let $f(n,r,k)$ be the maximum $s$ such that every $n$-vertex $(r,k)$-tournament contains a tight path on $s$ vertices. Since every tournament has a spanning path, we have $f(n,2,1)=n$. In this paper, we show that the minimum $k$ such that $f(n,r,k)$ tends to infinity with $n$ is in the interval $\left[\left(1-\frac{1}{r}-O(\frac{\log r}{r^2\log \log r})\right)r!,\left(1-\frac{1}{r}-\frac{\ddot{I}†(r)-1}{r!}\right)r!\right]$ where $\ddot{I}†(r)$ is the Euler Totient Function, and we find the exact value when $r\le 5$. We also show that $\hat{I}\text{c◯}(\sqrt{\log n/\log \log n})\le f(n,3,3)\le O(\log n)$ and $f(n,3,4)\ge \hat{I}\text{c◯}(n^{1/5})$.

18 pages, 5 figures; minor revisions