Turán Numbers of Ordered Tight Hyperpaths

Abstract

An ordered hypergraph is a hypergraph $G$ whose vertex set $V(G)$ is linearly ordered. We find the Turán numbers for the $r$-uniform $s$-vertex tight path $P_s^{(r)}$ (with vertices in the natural order) exactly when $r\le s<2r$ and $n$ is even; our results imply ${\mathrm{ex}}_{>}(n,P_s^{(r)})=(1-\frac{1}{2^{s-r}}+o(1))\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ when $r\le s<2r$. When $r\ge 2s$, the asymptotics of ${\mathrm{ex}}_{>}(n,P_s^{(r)})$ remain open. For $r=3$, we give a construction of an $r$-uniform $n$-vertex hypergraph not containing $P_s^{(r)}$ which we conjecture to be asymptotically extremal.

10 pages, 0 figures