Turán numbers of hypergraph trees

Abstract

An $r$-graph is an $r$-uniform hypergraph tree (or $r$-tree) if its edges can be ordered as $E_1,\dots ,E_m$ such that $\forall i>1\exists \alpha (i)<i$ such that $E_i\cap ({\bigcup }_{j=1}^{i-1}{E}_j)\subseteq E_{\alpha (i)}$. The Turán number $ex(n,\mathcal{H})$ of an $r$-graph $\mathcal{H}$ is the largest size of an $n$-vertex $r$-graph that does not contain $\mathcal{H}$. A cross-cut of $\mathcal{H}$ is a set of vertices in $\mathcal{H}$ that contains exactly one vertex of each edge of $\mathcal{H}$. The cross-cut number $\sigma (\mathcal{H})$ of $\mathcal{H}$ is the minimum size of a cross-cut of $\mathcal{H}$. We show that for a large family of $r$-graphs (largest within a certain scope) that are embeddable in $r$-trees, $ex(n,\mathcal{H})=(\sigma -1)\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)+o(n^{r-1})$ holds, and we establish structural stability of near extremal graphs. From stability, we establish exact results for some subfamilies.