Turan numbers for Berge-hypergraphs and related extremal problems

摘要

Let F be a graph. We say that a hypergraph H is a Berge-F if there is a bijection f : E(F) -> E(H) such that e subset of f (e) for every e is an element of E(F). Note that Berge-F actually denotes a class of hypergraphs. The maximum number of edges in an n-vertex r-graph with no subhypergraph isomorphic to any Berge-F is denoted ex(r)(n, Berge-F). In this paper, we investigate the case when F = K-s,K-t and establish an upper-bound when r >= 3, and a lower-bound when r = 4 and t is large enough compared to s. Additionally, we prove a counting result for r-graphs of girth five that complements the asymptotic formula ex(3)(n, Berge-{C-2, C-3, C-4}) = 1/6n(3/2) + 0(n(3/2)) of Lazebnik and Verstraete (2003). (C) 2019 Elsevier B.V. All rights reserved.