Some Exact Results and New Asymptotics for Hypergraph Turán Numbers

Abstract

Given a family [Fscr ] of r-graphs, let ex(n, [Fscr ]) be the maximum number of edges in an n-vertex r-graph containing no member of [Fscr ]. Let C^(r)₄ denote the family of r-graphs with distinct edges A, B, C, D, such that A ∩ B = C ∩ D = Ø and A ∪ B = C ∪ D. For s₁ [les ] … [les ] s_r, let K^(r) (s₁,…,s_r) be the complete r-partite r-graph with parts of sizes s₁,…,s_r.

Füredi conjectured over 15 years ago that ex(n,C⁽³⁾₄) [les ] (ⁿ₂) for sufficiently large n. We prove the weaker result

ex(n, {C⁽³⁾₄, K⁽³⁾(1,2,4)}) [les ] (ⁿ₂).

Generalizing a well-known conjecture for the Turán number of bipartite graphs, we conjecture that

ex(n, K^(r)(s₁,…,s_r)) = Θ(n^r−1/s),

where s = Π^r−1_i=1s_i. We prove this conjecture when s₁ = … = s_r−2 = 1 and

(i) s_r−1 = 2, (ii) s_r−1 = s_r = 3, (iii)s_r > (s_r−1−1)!.

In cases (i) and (ii), we determine the asymptotic value of ex(n,K^(r)(s₁,…,s_r)).

We also provide an explicit construction giving

ex(n,K⁽³⁾(2,2,3)) > (1/6−o(1))n^8/3.

This improves upon the previous best lower bound of Ω(n^29/11) obtained by probabilistic methods. Several related open problems are also presented.