Constructions of Turán systems that are tight up to a multiplicative constant

Abstract

For positive integers $n\ge 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)/\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ as $n\to \infty$. 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)\ge 1/\left(\genfrac{}{}{0ex}{}{s}{s-r}\right)$. In the early 1990s, de Caen conjectured that $r\cdot t(r+1,r)\to \infty$ as $r\to \infty$ and offered 500 Canadian dollars for resolving this question. We disprove this conjecture by showing more strongly that for every integer $R\ge 1$ there is ${\mu }_R$ (in fact, ${\mu }_R$ can be taken to grow as $(1+o(1))R\ln R$) such that $t(r+R,r)\le ({\mu }_R+o(1))/\left(\genfrac{}{}{0ex}{}{r+R}{R}\right)$ as $r\to \infty$, that is, the trivial lower bound is tight for every $R$ up to a multiplicative constant ${\mu }_R$.

arXiv comment10 pages, incorporating referees' comments and adding 2 new references, accepted by Advances in Mathematics