A near-quadratic lower bound for the Brown--Erdős--Sós $(9,6)$-problem

Abstract

Let $f_3(n,e+3,e)$ denote the maximum number of edges in an $n$-vertex $3$-uniform hypergraph containing no $e$ distinct edges spanning at most $e+3$ vertices. It has long been conjectured that $f_3(n,e+3,e)\ge n^{2-o(1)}$ for every fixed $e\ge 3$. We prove that $f_3(n,9,6)\ge n^2\exp (-O((\log n{)}^{2/3}))$, settling the first unsolved case of the conjecture.

arXiv comment7 pages