A New Bound for the Brown--Erdős--Sós Problem

Abstract

Let $f(n,v,e)$ denote the maximum number of edges in a $3$-uniform hypergraph not containing $e$ edges spanned by at most $v$ vertices. One of the most influential open problems in extremal combinatorics then asks, for a given number of edges $e\ge 3$, what is the smallest integer $d=d(e)$ so that $f(n,e+d,e)=o(n^2)$? This question has its origins in work of Brown, Erdős and Sós from the early 70's and the standard conjecture is that $d(e)=3$ for every $e\ge 3$. The state of the art result regarding this problem was obtained in 2004 by Sárközy and Selkow, who showed that $f(n,e+2+\lfloor {\log }_{2}e\rfloor ,e)=o(n^2)$. The only improvement over this result was a recent breakthrough of Solymosi and Solymosi, who improved the bound for $d(10)$ from 5 to 4. We obtain the first asymptotic improvement over the Sárközy--Selkow bound, showing that $$f(n,e+O(\log e/\log \log e),e)=o(n^2).$$