Power saving 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 on $n$ vertices which does not contain $v$ vertices spanning at least $e$ edges. A central problem in extremal combinatorics, famously posed by Brown, Erdős and Sós in 1973, asks whether $f(n,e+3,e)=o(n^2)$ for every $e\ge 3$. A classical result of Sárközy and Selkow states that $f(n,e+\lfloor {\log }_{2}e\rfloor +2,e)=o(n^2)$ for every $e\ge 3$. This bound was recently improved by Conlon, Gishboliner, Levanzov and Shapira. Motivated by applications to other problems, Gowers and Long made the striking conjecture that $f(n,e+4,e)=O(n^{2-\epsilon })$ for some $\epsilon =\epsilon (e)>0$. Conlon, Gishboliner, Levanzov and Shapira, and later, Shapira and Tyomkyn reiterated the following approximate version of this problem. What is the smallest $d(e)$ for which $f(n,e+d(e),e)=O(n^{2-\epsilon })$ for some $\epsilon =\epsilon (e)>0$? In this paper, we prove that for each $e\ge 3$ we have $f(n,e+\lfloor {\log }_{2}e\rfloor +38,e)=O(n^{2-\epsilon })$ for some $\epsilon >0$. This shows that one can already obtain power saving near the Sárközy-Selkow bound at the cost of a small additive constant.

16 pages