One of the most challenging open problems in extremal combinatorics, proposed by Erdos and Sos in 1971, asks to determine for every triple of positive integers l≤k≤n the largest subfamily A of the k-th layer n choose k of the cube, whose interesections forbid l, that is, it satisfies |A∩B|≠l for every A,B in 𝓐.

Significant progress on the Erdos--Sos problem was made by several authors including Frankl/Wilson (1981), Frankl/Furedi (1985) and Frankl/Rodl (1987), and much more recently, by Ellis/Keller/Lifshitz

(2016), Keller/Lifshitz (2021) and Kupavskii/Zaharov (2022). We shall discuss these results, and we shall outline the proof of the following new estimate:

Let n be a positive integer, let 0<p≤q≤1/2, and let l≤pn be a nonnegative integer. If F,G⊆\{0,1\}^n are two families whose cross intersections forbid l---that is, they satisfy |A∩B|≠l| for every A∈F and B∈G---then, setting t to be the minimum of l,pn-l, we have the subgaussian bound

μ_p (F) μ_q (G )≤2 exp⁡(-t^2/(58^2 pn)) where μ_p and μ_q denote the p-biased and q-biased measures on {0,1}^n, respectively.

This estimate extends the celebrated Frankl--Rodl theorem to the sparse setting, and it is actually optimal (modulo universal constants) for various choices of p,q,l.

This is joint work with Miltiadis Karamanlis.