
























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 \geq 2$. The new proof is elementary, avoiding the use of convexity. For any $d$-uniform hypergraph $H$, let $ex_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 $ex_{d+1}(n,K_{H,t}) = O(ex_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 $ex_d(n, H) = o(n^d)$. Thus $ex_{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 $ex_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 $ex_{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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。