论文标题
KőVári-Sós-Turán定理的概括
A generalization of the Kővári-Sós-Turán theorem
论文作者
论文摘要
我们提供了一个新的证明kőVári-sós-turán定理，即$ ex（n，k_ {s，t}）= o（n^{2-1/t}）$ for $ s，t \ geq 2 $。新的证明是基本的，避免使用凸度。对于任何$ d $ - 均匀的超图$ h $，让$ ex_d（n，h）$是$ h $ - free $ d $ d $ - 均匀的超图中的最大边数。令$ k_ {h，t} $为$（d+1）$ - 通过添加$ t $ t $ t $ t $ h $获得的均匀超图，添加$ t $ n新顶点$ v_1，\ dots，v_t $，并用$ e e（h）中的每个边缘$ e $ e $ e（h）$ t $ t $ t $ e edges $ \ left \ {v_t \ right \} $ in $ e（k_ {h，t}）$。如果$ h $是$ 1 $ - 均匀的超图，上面有$ s $ edges的$ s $顶点，则$ k_ {h，t} = k_ {s，t} $。 我们证明$ ex_ {d+1}（n，k_ {h，t}）= o（ex_d（n，h）^{1/t} n^{d+1-d/t}+t}+t n^d）$对于任何$ d $ d $ -d-robiontry hypraph $ h $，至少有两个ex_d（ex_d（ex_d n，n，h）= o（n，n，h）= o（d）。因此，对于任何$ d $ d $ - 均匀的hypergraph $ h $，$ ex_ {d+1}（n，n，k_ {h，t}）= o（n^{d+1-1/t}）$，至少有两个边缘带有两个边缘，例如$ ex_d（n，h）= o（n^{d-1}）$，这意味着kővári-sorem in $ n $ n = r = d $ d = r = d = r = d = d = d = d = d = d = d = d = d = d = d = 1这也意味着$ ex_ {d+1}（n，k_ {h，t}）= o（n^{d+1-1/t}）$时，$ h $是一个$ h $ a $ d $ - 均匀的超盖，至少两个边缘，其中所有边缘都是成对的，其中所有边缘均与Mububayi和Verstra和Verstra和Verstra的上限证明了上限。我们还获得了0-1矩阵Turán问题的类似边界。
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.
