A Linear Hypergraph Extension of Turán's Theorem

Abstract

An $r$-uniform hypergraph is linear if every two edges intersect in at most one vertex. Given a family of $r$-uniform hypergraphs $\mathcal{F}$, the linear Turán number ex$_r^{lin}(n,\mathcal{F})$ is the maximum number of edges of a linear $r$-uniform hypergraph on $n$ vertices that does not contain any member of $\mathcal{F}$ as a subgraph.

Let $K_l$ be a complete graph with $l$ vertices and $r\geq 2$. The $r$-expansion of $K_l$ is the $r$-graph $K_l^+$ obtained from $K_l$ by enlarging each edge of $K_l$ with $r-2$ new vertices disjoint from $V(K_l)$ such that distinct edges of $K_l$ are enlarged by distinct vertices. When $l\geq r \geq 3$ and $n$ is sufficiently large, we prove the following extension of Turán's Theorem $$ex_{r}^{lin}\left(n, K_{l+1}^{+}\right)\leq |TD_r(n,l)|,$$ with equality achieved only by the Turán design $TD_r(n,l)$, where the Turán design $TD_r(n,l)$ is an almost balanced $l$-partite $r$-graph such that each pair of vertices from distinct parts are contained in one edge exactly. Moreover, some results on linear Turán number of general configurations are also presented.