Proof of the Brown-Erdős-Sós conjecture in groups

Abstract

The conjecture of Brown, Erdős and Sós from 1973 states that, for any $k\ge 3$, if a $3$-uniform hypergraph $H$ with $n$ vertices does not contain a set of $k+3$ vertices spanning at least $k$ edges then it has $o(n^2)$ edges. The case $k=3$ of this conjecture is the celebrated $(6,3)$-theorem of Ruzsa and Szemerédi which implies Roth's theorem on $3$-term arithmetic progressions in dense sets of integers. Solymosi observed that, in order to prove the conjecture, one can assume that $H$ consists of triples $(a,b,ab)$ of some finite quasigroup $\Gamma$. Since this problem remains open for all $k\ge 4$, he further proposed to study triple systems coming from finite groups. In this case he proved that the conjecture holds also for $k=4$. Here we completely resolve the Brown-Erdős-Sós conjecture for all finite groups and values of $k$. Moreover, we prove that the hypergraphs coming from groups contain sets of size $\Theta (\sqrt{k})$ which span $k$ edges. This is best possible and goes far beyond the conjecture.