For positive integers , the Turán function 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 as the limit of as . 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 . In the early 1990s, de Caen conjectured that as and offered 500 Canadian dollars for resolving this question. We disprove this conjecture by showing more strongly that for every integer there is (in fact, can be taken to grow as ) such that as , that is, the trivial lower bound is tight for every up to a multiplicative constant .

生成讲解博客的中文版本

生成AI智能校验的中文版本