Stability and Turán Numbers of a Class of Hypergraphs via Lagrangians

Source abstract

Given a family of r -uniform hypergraphs ${\cal F}$ (or r -graphs for brevity), the Turán number ex( n , ${\cal F})$ of ${\cal F}$ is the maximum number of edges in an r -graph on n vertices that does not contain any member of ${\cal 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 ⩾ n ( F ), where n ( F ) denotes the number of vertices in F , let H F p denote the r -graph obtained as follows. Label the vertices of F as v 1 ,. . ., v n ( F ). Add new vertices v n(F)+1 ,. . ., 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 } ∪ B i,j , where the B i,j are pairwise disjoint over all such pairs { i, j }. We call H F p 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 F p ) = | 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 ).