2024/06/11 by Pikhurko, Oleg
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2406.07443
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\choose 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\choose s-r. In the early 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)) Rln R) such that t(r+R,r)≤ (μR+o(1))/ r+R\choose R as r→∞, that is, the trivial lower bound is tight for every R up to a multiplicative constant μR.