2018/08/31 by Gerbner, Dániel, Methuku, Abhishek, Palmer, Cory · 4 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1808.10842
For a graph F, a hypergraph H is a Berge copy of F (or a Berge-F in short), if there is a bijection f : E(F) → E(H) such that for each e ∈ E(F) we have e ⊂ f(e). A hypergraph is Berge-F-free if it does not contain a Berge copy of F. We denote the maximum number of hyperedges in an n-vertex r-uniform Berge-F-free hypergraph by exr(n,\textrmBerge-F). In this paper we prove two general lemmas concerning the maximum size of a Berge-F-free hypergraph and use them to establish new results and improve several old results. In particular, we give bounds on exr(n,\textrmBerge-F) when F is a path (reproving a result of Győri, Katona and Lemons), a cycle (extending a result of Füredi and Özkahya), a theta graph (improving a result of He and Tait), or a K2,t (extending a result of Gerbner, Methuku and Vizer). We also establish new bounds when F is a clique (which implies extensions of results by Maherani and Shahsiah and by Gyárfás) and when F is a general tree.