Uniformity thresholds for the asymptotic size of extremal Berge-F-free hypergraphs

Abstract

© 2020 Elsevier Ltd. Let F=(U,E) be a graph and H=(V,E) be a hypergraph. We say that H contains a Berge-F if there exist injections ψ:U→V and φ:E→E such that for every e={u,v}∈E, {ψ(u),ψ(v)}⊂φ(e). Let exr(n,F) denote the maximum number of hyperedges in an r-uniform hypergraph on n vertices which does not contain a Berge-F. For small enough r and non-bipartite F, exr(n,F)=Ω(n2); we show that for sufficiently large r, exr(n,F)=o(n2). Let th(F)=min{r0:exr(n,F)=o(n2)for allr≥r0}. We show lower and upper bounds for th(F), the uniformity threshold of F. In particular, we obtain that th(△)=5, improving a result of Győri (2006). We also study the analogous problem for linear hypergraphs. Let exr L(n,F) denote the maximum number of hyperedges in an r-uniform linear hypergraph on n vertices which does not contain a Berge-F, and let the linear uniformity threshold thL(F)=min{r0:exr L(n,F)=o(n2)for allr≥r0}. We show that thL(F) is equal to the chromatic number of F