On Non-degenerate Berge–Turán Problems

Gerbner, Dániel (2024) On Non-degenerate Berge–Turán Problems. GRAPHS AND COMBINATORICS, 40 (2). ISSN 0911-0119

Preview

Text s00373-024-02757-w.pdf - Published Version Download (232kB) | Preview

Abstract

Given a hypergraph H and a graph G, we say that H is a Berge-G if there is a bijection between the hyperedges of H and the edges of G such that each hyperedge contains its image. We denote by exk(n,Berge-F) the largest number of hyperedges in a k-uniform Berge-F-free graph. Let ex(n,H,F) denote the largest number of copies of H in n-vertex F-free graphs. It is known that ex(n,Kk,F)≤exk(n,Berge-F)≤ex(n,Kk,F)+ex(n,F), thus if χ(F)>r, then exk(n,Berge-F)=(1+o(1))ex(n,Kk,F). We conjecture that exk(n,Berge-F)=ex(n,Kk,F) in this case. We prove this conjecture in several instances, including the cases k=3 and k=4. We prove the general bound exk(n,Berge-F)=ex(n,Kk,F)+O(1).

Actions (login required)

Edit Item