Given a family F of r-graphs, let ex(n, F) be the maximum number of edges in an n-vertex r-graph containing no member of F. Let C(r) 4 denote the family of r-graphs with distinct edges A, B, C, D, such that A ∩ B = C ∩ D = O and A ∪ B = C ∪ D. For s1 l … l sr, let K(r) (s1,…,sr) be the complete r-partite r-graph with parts of sizes s1,…,sr.Furedi conjectured over 15 years ago that ex(n,C(3)4) l (n2) for sufficiently large n. We prove the weaker resultex(n, {C(3)4, K(3)(1,2,4)}) l (n2).Generalizing a well-known conjecture for the Turan number of bipartite graphs, we conjecture thatex(n, K(r)(s1,…,sr)) = Θ(nr−1/s),where s = Πr−1i=1 si. We prove this conjecture when s1 = … = sr−2 = 1 and(i) sr−1 = 2, (ii) sr−1 = sr = 3, (iii)sr > (sr−1−1)!.In cases (i) and (ii), we determine the asymptotic value of ex(n,K(r)(s1,…,sr)).We also provide an explicit construction givingex(n,K(3)(2,2,3)) > (1/6−o(1))n8/3.This improves upon the previous best lower bound of O(n29/11) obtained by probabilistic methods. Several related open problems are also presented.
['Dhruv Mubayi']
Some Exact Results and New Asymptotics for Hypergraph Turán Numbers