Power saving for the Brown-Erdős-Sós problem

2023/11/21 by Janzer, Oliver, Methuku, Abhishek, Milojević, Aleksa +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2311.12765

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²) for every e ≥ 3. A classical result of Sárközy and Selkow states that f(n, e+\lfloor log₂ e\rfloor+2, e)=o(n²) for every e ≥ 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-ε) for some ε=ε(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-ε) for some ε=ε(e)>0? In this paper, we prove that for each e≥ 3 we have f(n, e+\lfloor log₂ e\rfloor +38, e)=O(n^2-ε) for some ε>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.

Related

• A New Bound for the Brown--Erdős--Sós Problem
• A new approach for the Brown-Erdos-Sos problem
• The limit in the (k+2, k)-Problem of Brown, Erdős and Sós exists for all k≥ 2
• On the (6,4)-problem of Brown, Erdős and Sós
• On the quadratic 8-edge case of the Brown-Erdős-Sós problem