Stability and Turán Numbers of a Class of Hypergraphs via Lagrangians. (29th March 2017) - BRANDT, AXEL; IRWIN, DAVID; JIANG, TAO
Abstract : Given a family of r -uniform hypergraphs F (or r -graphs for brevity), the Turán number ex( n, F) of F is the maximum number of edges in an r -graph on n vertices that does not contain any member of 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, . . ., vn ( F ). Add new vertices vn(F)+1, . . ., vp . For each pair of vertices vi, vj not covered in F, add a set Bi, j of r − 2 new vertices and the edge vi, vj ∪ Bi, j, where the Bi, 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 ) = | Tr ( n, p − 1)|, where Tr ( 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 ).