2018/03/05 by Dániel Grósz, Grósz, Dániel, Abhishek Methuku +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Mathematical Approximation and Integration
paper · pdf · doi:10.48550/arxiv.1803.01953
openalex publication_date 2018/03/05 · openalex created_date 2022/10/06 · openalex updated_date 2026/08/01
Let F = (U,E) be a graph and \H = (V,\E) be a\nhypergraph. We say that \H contains a Berge-F if there exist\ninjections \ψ:U\→ V and \φ:E\→ \E such that for every\ne= u,v \∈ E, \ψ(u),\ψ(v) \⊂\φ(e). Let exr(n,F)\ndenote the maximum number of hyperedges in an r-uniform hypergraph on n\nvertices which does not contain a Berge-F.\n For small enough r and non-bipartite F, exr(n,F)=\Ω(n2); we show\nthat for sufficiently large r, exr(n,F)=o(n2). Let thres(F) = \min r0\n:exr(n,F) = o(n2) for all r \≥ r0 . We show lower and upper\nbounds for thres(F), the uniformity threshold of F. In particular, we\nobtain that thres( triangle) = 5, improving a result of Gy Hori.\n We also study the analogous problem for linear hypergraphs. Let exLr(n,F)\ndenote the maximum number of hyperedges in an r-uniform linear hypergraph on\nn vertices which does not contain a Berge-F, and let the linear unformity\nthreshold thresL(F) = \min r0 :exLr(n,F) = o(n2) for all r \≥\nr0 . We show that thresL(F) is equal to the chromatic number of F.\n