A new bound 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 not containing e edges spanned by at most v vertices. One of the most influential open problems in extremal combinatorics then asks, for a given number of edges e ≥ 3, what is the smallest integer d = d(e) such that f(n, e+d, e) = o(n²)? This question has its origins in work of Brown, Erdős and Sós from the early 70's and the standard conjecture is that d(e) = 3 for every e ≥ 3. The state of the art result regarding this problem was obtained in 2004 by Sárközy and Selkow, who showed that f(n, e+2+[log₂e], e) = o(n²). The only improvement over this result was a recent breakthrough of Solymosi and Solymosi, who improved the bound for d(10) from 5 to 4. We obtain the first asymptotic improvement over the Sárközy–Selkow bound, showing that f(n, e+O(log e / log log e), e) = o(n²).
Additional Information
[Conlon] supported in part by NSF Award DMS-2054452. [Gishboliner] supported in part by SNSF grant 200021_196965. [Shapira] supported in part by ISF Grant 1028/16, ERC Consolidator Grant 863438 and NSF-BSF Grant 20196.Attached Files
Published - 1-s2.0-S0095895622000818-main.pdf
Files
Name | Size | Download all |
---|---|---|
md5:545b0c6339c4c15d501a6fdce18cc7c9
|
720.6 kB | Preview Download |
Additional details
- Eprint ID
- 117650
- Resolver ID
- CaltechAUTHORS:20221031-575177800.7
- DMS-2054452
- NSF
- 200021_196965
- Swiss National Science Foundation (SNSF)
- 1028/16
- Israel Science Foundation
- 863438
- European Research Council (ERC)
- 20196
- Binational Science Foundation (USA-Israel)
- Created
-
2022-11-09Created from EPrint's datestamp field
- Updated
-
2022-11-11Created from EPrint's last_modified field