A linear hypergraph extension of Turán's theorem

Guorong Gao ; An Chang

The electronic journal of combinatorics, Tome 29 (2022) no. 4

Résumé

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.

Détail

DOI : 10.37236/10525

Classification : 05C65, 05C30, 05C35
Mots-clés : linear hypergraph, Turan's theorem, complete \(l\)-partite graph