Turán numbers for Berge-hypergraphs and related extremal problems

Abstract

Let $F$ be a graph. We say that a hypergraph $H$ is a {\it Berge}-$F$ if there is a bijection $f:E(F)\to E(H)$ such that $e\subseteq f(e)$ for every $e\in 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,\textrm{Berge-}F)$. In this paper we establish new upper and lower bounds on $\ex_r(n,\textrm{Berge-}F)$ for general graphs $F$, and investigate connections between $\ex_r(n,\textrm{Berge-}F)$ and other recently studied extremal functions for graphs and hypergraphs. One case of specific interest will be when $F=K_{s,t}$. Additionally, we prove a counting result for $r$-graphs of girth five that complements the asymptotic formula ${\text{ex}}_3(n,\text{Berge-}\{C_2,C_3,C_4\})=\frac{1}{6}{n}^{3/2}+o(n^{3/2})$ of Lazebnik and Verstraëte [{\em Electron.\ J. of Combin}. {\bf 10}, (2003)].