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

Abstract

Let $F=(U,E)$ be a graph and $\mathcal{H}=(V,\mathcal{E})$ be a hypergraph. We say that $\mathcal{H}$ contains a Berge-$F$ if there exist injections $\psi :U\to V$ and $\phi :E\to \mathcal{E}$ such that for every $e=\{u,v\}\in E$, $\{\psi (u),\psi (v)\}\subset \phi (e)$. Let $e{x}_r(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$, $e{x}_r(n,F)=\Omega (n^2)$; we show that for sufficiently large $r$, $e{x}_r(n,F)=o(n^2)$. Let $thres(F)=\min \{r_0:e{x}_r(n,F)=o(n^2)\text{ for all }r\ge r_0\}$. We show lower and upper bounds for $thres(F)$, the uniformity threshold of $F$. In particular, we obtain that $thres(△)=5$, improving a result of Győri. We also study the analogous problem for linear hypergraphs. Let $e{x}_r^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 unformity threshold $thre{s}^L(F)=\min \{r_0:e{x}_r^L(n,F)=o(n^2)\text{ for all }r\ge r_0\}$. We show that $thre{s}^L(F)$ is equal to the chromatic number of $F$.