A generalization of the K\H{o}v\'{a}ri-S\'{o}s-Tur\'{a}n theorem

We present a new proof of the K\H{o}v'{a}ri-S'{o}s-Tur'{a}n theorem that $ex(n,K_{s,t})=O(n^{2-1\mathrm{/}t})$ for $s,t\ge 2$. The new proof is elementary, avoiding the use of convexity. For any $d$-uniform hypergraph $H$, let $e{x}_d(n,H)$ be the maximum possible number of edges in an $H$-free $d$-uniform hypergraph on $n$ vertices. Let $K_{H,t}$ be the $(d+1)$-uniform hypergraph obtained from $H$ by adding $t$ new vertices $v_1,\dots ,v_t$ and replacing every edge $e$ in $E(H)$ with $t$ edges $e \cup \left{v_1\right},\dots, e \cup \left{v_t\right}$in$E(K_{H, t})$\mathrm{.}If$H$isthe$1$-uniform hypergraph on $s$ vertices with $s$ edges, then $K_{H,t}=K_{s,t}$. We prove that $e{x}_{d+1}(n,K_{H,t})=O(e{x}_d(n,H{)}^{1\mathrm{/}t}{n}^{d+1-d\mathrm{/}t}+t{n}^d)$ for any $d$-uniform hypergraph $H$ with at least two edges such that $ex_d(n, H) = o(n^d)$\mathrm{.}Thus$ex_{d+1}(n,K_{H,t}) = O(n^{d+1-1/t})$forany$d$-uniform hypergraph $H$ with at least two edges such that $e{x}_d(n,H)=O(n^{d-1})$, which implies the K\H{o}v'{a}ri-S'{o}s-Tur'{a}n theorem in the $d=1$ case. This also implies that $e{x}_{d+1}(n,K_{H,t})=O(n^{d+1-1\mathrm{/}t})$ when $H$ is a $d$-uniform hypergraph with at least two edges in which all edges are pairwise disjoint, which generalizes an upper bound proved by Mubayi and Verstra"{e}te (JCTA, 2004). We also obtain analogous bounds for 0-1 matrix Tur'{a}n problems.