A generalization of the Kővári-Sós-Turán theorem

Abstract

We present a new proof of the Kővári-Sós-Turán theorem that $ex(n,K_{s,t})=O(n^{2-1/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})$. If $H$ is the $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/t}{n}^{d+1-d/t}+t{n}^d)$ for any $d$-uniform hypergraph $H$ with at least two edges such that $e{x}_d(n,H)=o(n^d)$. Thus $e{x}_{d+1}(n,K_{H,t})=O(n^{d+1-1/t})$ for any $d$-uniform hypergraph $H$ with at least two edges such that $e{x}_d(n,H)=O(n^{d-1})$, which implies the Kővári-Sós-Turán theorem in the $d=1$ case. This also implies that $e{x}_{d+1}(n,K_{H,t})=O(n^{d+1-1/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ëte (JCTA, 2004). We also obtain analogous bounds for 0-1 matrix Turán problems.