Turán Problems for Berge-(k, p)-Fan Hypergraph

Abstract

Let F be a graph. A hypergraph ${\cal H}$ is Berge-F if there is a bijection $f:E(F) \rightarrow E({\cal H})$ such that e ⊂ f(e) for every e ∈ E(F). A hypergraph is Berge-F-free if it does not contain a subhypergraph isomorphic to a Berge-F hypergraph. The authors denote the maximum number of hyperedges in an n-vertex r-uniform Berge-F-free hypergraph by ex _r (n, Berge-F).

A (k, p)-fan, denoted by F _k,p, is a graph on k(p − 1) + 1 vertices consisting of k cliques with p vertices that intersect in exactly one common vertex. In this paper they determine the bounds of ex _r(n, Berge-F) when F is a (k, p)-fan for k ≥ 2, p ≥ 3 and r ≥ 3.

Keywords

Berge-hypergraph / Turán number

References

[1] Alon N, Shikhelman C. Many T copies in H-free graphs. J. Combin. Theory Ser. B, 2016, 121: 146-172

[2] Bondy J A, Chvátal V. A method in graph theory. Discrete Math., 1976, 15(2): 111-135

[3] Chen G, Gould R J, Pfender F, Wei B. Extremal graphs for intersecting cliques. J. Combin. Theory Ser. B, 2003, 89: 159-171

[4] Duan X, Ning B, Peng X Maximizing the number of cliques in graphs with given matching number. Discrete Appl. Math., 2020, 287: 110-117

[5] Gerbner D, Methuku A, Palmer C. General lemmas for Berge-Turán hypergraph problems. European J. Combin., 2020, 86: 103082

[6] Gerbner D, Methuku A, Vizer M. Generalized Turán problems for disjoint copies of graphs. Discrete Math., 2019, 342: 3130-3141

[7] Gerbner D, Palmer C. Extremal results for Berge hypergraphs. SIAM J. Discrete Math., 2017, 31(4): 2314-2327

[8] Gerbner D, Patkós B. Extremal Finite Set Theory, 2018, Boca Raton: CRC Press

[9] Grősz D, Methuku A, Tompkins C. Uniformity thresholds for the asymptotic size of extremal Berge-F-free hypergraphs. European J. Combin., 2020, 88: 103109

[10] Győri E, Katona G Y, Lemons N. Hypergraph extensions of the Erdős-Gallai Theorem. Electron. J. Combin., 2016, 58: 238-246

[11] Győri E, Lemons N. 3-uniform hypergraphs avoiding a given odd cycle. Combinatorica, 2012, 32: 187

[12] Palmer C, Tait M, Timmons C, Wagner A Z. Turán number for Berge-hypergraphs and related extremal problem. Discrete Math., 2019, 342: 1553-1563