A Linear Hypergraph Extension of Turán's Theorem

  • Guorong Gao
  • An Chang


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.

Article Number