On local Turán problems

Abstract: Since its formulation, Turán's hypergraph problems have been among the most challenging open problems in extremal combinatorics. One of them is the following: given a 3-uniform hypergraph F on n vertices in which any five vertices span at least one edge, prove that $|F|\ge(1/4 -o(1))\binom{n}{3}$. The construction showing that this bound would be best possible is simply ${X \choose 3} \cup {Y \choose 3}$ where X and Y evenly partition the vertex set. This construction satisfies the following more general (2p+1, p+1)-property: any set of 2p+1 vertices spans a complete sub-hypergraph on p+1 vertices.

In this talk, we will show that, quite surprisingly, for all p>2 the (2p+1,p+1)-property implies the conjectured lower bound. Furthermore, we will prove that for integers r, a >= 2, the minimum edge density of an r-uniform hypergraph satisfying the (ap+1, p+1)-property tends to $1/a^{r-1}$ when p tends to infinity.

Joint work with Peter Frankl and Vojtěch Rödl.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).