Induced Turán problems and traces of hypergraphs

Abstract

Let $F$ be a graph. We say that a hypergraph $H$ contains an induced Berge $F$ if the vertices of $F$ can be embedded to $H$ (e.g., $V(F)\subseteq V(H)$) and there exists an injective mapping $f$ from the edges of $F$ to the hyperedges of $H$ such that $f(xy)\cap V(F)=\{x,y\}$ holds for each edge $xy$ of $F$. In other words, $H$ contains $F$ as a trace. Let $e{x}_r(n,B_{ind}F)$ denote the maximum number of edges in an $r$-uniform hypergraph with no induced Berge $F$. Let $ex(n,K_r,F)$ denote the maximum number of $K_r$'s in an $F$-free graph on $n$ vertices. We show that these two Turán type functions are strongly related.