Stability and Turán Numbers of a Class of Hypergraphs via Lagrangians. (29th March 2017)

• Record Type: Journal Article
• Authors: BRANDT, AXEL; IRWIN, DAVID; JIANG, TAO
• Is Part Of: Combinatorics, probability and computing. Volume 26:Number 3(2017:May)
• Page Start: 367
• Page End: 405
• Publication Date: 2017-03-29
• Subjects: Primary 05C65, -- Secondary 05C35; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548316000444
• Languages: English
• ISSNs: 0963-5483

Abstract

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, . . ., 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 ).