skip to content

Department of Pure Mathematics and Mathematical Statistics

The Turán density t(s,r) is the asymptotically smallest edge density
of an r-graph for which every set of s vertices contains at least one
edge. The question of estimating this function received a lot of
attention over decades of attempts. A trivial lower bound is t(s,r)\ge
1/{s\choose s−r). In the early 1990s, de Caen conjectured that
t(r+1,r) grows faster than O(1/r) and offered 500 Canadian dollars for
resolving this question.

I will give an overview of this area and present a construction
disproving this conjecture by showing more strongly that for every
integer R there is C such that t(r+R,r)\le C/{r+R\choose R}, that is,
the trivial lower bound is tight for every fixed R up to a
multiplicative constant C=C(R).

Further information

Time:

19Mar
Mar 19th 2026
14:30 to 15:30

Venue:

MR12

Speaker:

Oleg Pikhurko (Warwick)

Series:

Combinatorics Seminar