For positive integers n≥ s> r, the Tur\'an function $T(n,s,r)$ is the smallest size of an r-graph with n vertices such that every set of s vertices contains at least one edge. Also, define the Tur\'an density $t(s,r)$ as the limit of T(n,s,r)/ n r as n→∞. The question of estimating these parameters received a lot of attention after it was first raised by Tur\'an in 1941. A trivial lower bound is t(s,r)≥ 1/s s-r. In the early 1990s, de Caen conjectured that r· t(r+1,r)→∞ as r→∞. We disprove this conjecture by showing more strongly that for every integer R≥1 there is μR (in fact, μR can be taken to grow as (1+o(1))\, Rln R) such that t(r+R,r)≤ (μR+o(1))/ r+R R as r→∞, that is, the trivial lower bound is tight for every R up to a multiplicative constant μR.
No takes yet. Share an insight, caveat, or question.
Oleg Pikhurko (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: