Constructions of Turán systems that are tight up to a multiplicative constant
Oleg Pikhurko · Advances in Mathematics · 2025
For positive integers n ⩾ s > r , the Turán 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án 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án in 1941. A trivial lower bound is t ( s , r ) ⩾ 1 / ( s s − r ) . In the 1990s, de Caen conjectured that r ⋅ t ( r + 1 , r ) → ∞ as r → ∞ and offered 500 Canadian dollars for resolving this question. 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 ) ) R ln 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 .