Stability and Turán numbers of a class of hypergraphs via Lagrangians

Abstract

Given a family of $r$-uniform hypergraphs $\mathcal{F}$ (or $r$-graphs for brevity), the Turán number $ex(n,\mathcal{F})$ of $\mathcal{F}$ is the maximum number of edges in an $r$-graph on $n$ vertices that does not contain any member of $\mathcal{F}$. A pair $\{u,v\}$ is covered in a hypergraph $G$ if some edge of $G$ contains $\{u,v\}$. Given an $r$-graph $F$ and a positive integer $p\ge n(F)$, let $H_p^F$ denote the $r$-graph obtained as follows. Label the vertices of $F$ as $v_1,\dots ,v_{n(F)}$. Add new vertices $v_{n(F)+1},\dots ,v_p$. For each pair of vertices $v_i,v_j$ not covered in $F$, add a set $B_{i,j}$ of $r-2$ new vertices and the edge $\{v_i,v_j\}\cup B_{i,j}$, where the $B_{i,j}$'s are pairwise disjoint over all such pairs $\{i,j\}$. We call $H_p^F$ the expanded $p$-clique with an embedded $F$. For a relatively large family of $F$, we show that for all sufficiently large $n$, $ex(n,H_p^F)=|T_r(n,p-1)|$, where $T_r(n,p-1)$ is the balanced complete $(p-1)$-partite $r$-graph on $n$ vertices. We also establish structural stability of near extremal graphs. Our results generalize or strengthen several earlier results and provide a class of hypergraphs for which the Turán number is exactly determined (for large $n$).

26 pages