A Caltech Library Service

A New Bound for the Brown-Erdős-Sós Problem

Conlon, David and Gishboliner, Lior and Levanzov, Yevgeny and Shapira, Asaf (2019) A New Bound for the Brown-Erdős-Sós Problem. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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) so 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(loge/logloge),e)=o(n²).

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper ItemJournal Article
Conlon, David0000-0001-5899-1829
Gishboliner, Lior0000-0003-0688-8111
Additional Information:Supported in part by ISF Grant 1028/16 and ERC Starting Grant 633509.
Funding AgencyGrant Number
Israel Science Foundation1028/16
European Research Council (ERC)633509
Record Number:CaltechAUTHORS:20200915-144809437
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105389
Deposited By: Tony Diaz
Deposited On:15 Sep 2020 23:57
Last Modified:11 Nov 2022 18:02

Repository Staff Only: item control page