Paperlane

no. 12 · Tuesday 10 November 2026

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

Xiangliang Kong, Chong Shangguan and Xin Wang

math.CO · v2 · 21 pp

Abstract

For integers $e\ge3$, 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. The lower-bound part of a longstanding conjecture of Erdős, Frankl, and Rödl from 1986 asserts that $f_3(n,e+3,e)\ge n^{2-o(1)}$ for every fixed $e\ge3$. We prove that $f_3(n,9,6)\ge n^2\exp(-O((\log n)^{2/3}))$, resolving the first open case not covered by the classical construction of Ruzsa and Szemerédi in 1976, which established $f_3(n,6,3)\ge n^{2-o(1)}$. We also establish near-quadratic lower bounds for $f_3(n,e+3,e)$ with $e=9,10,11$. We further extend the result for $e=6$ to every fixed uniformity $r\ge4$.

comments
21 pages
fields
Combinatorics
pdf ↗ page arXiv:2611.05261 ↗