A generalization of the Kővári-Sós-Turán theorem
share
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). 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, ..., v_t and replacing every edge e in E(H) with t edges e ∪{v_1},..., e ∪{v_t} 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). Thus ex_d+1(n,K_H,t) = O(n^d+1-1/t) for any d-uniform hypergraph H with ex_d(n, H) = Θ(n^d-1), which implies the Kővári-Sós-Turán theorem in the d = 1 case. As a corollary, this implies that ex_d+1(n, K_H,t) = O(n^d+1-1/t) when H is a d-uniform hypergraph 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.
READ FULL TEXT