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 (2023) A new bound for the Brown-Erdős-Sós problem. Journal of Combinatorial Theory. Series B, 158 (2). pp. 1-35. ISSN 0095-8956. doi:10.1016/j.jctb.2022.08.005.

[img] PDF - Published 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) 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²).

Item Type:Article
Related URLs:
URLURL TypeDescription ItemDiscussion Paper
Conlon, David0000-0001-5899-1829
Gishboliner, Lior0000-0003-0688-8111
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.
Funding AgencyGrant Number
Swiss National Science Foundation (SNSF)200021_196965
Israel Science Foundation1028/16
European Research Council (ERC)863438
Binational Science Foundation (USA-Israel)20196
Subject Keywords:Brown-Erdős-Sós conjecture ; Hypergraph removal lemma
Issue or Number:2
Record Number:CaltechAUTHORS:20221031-575177800.7
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:117650
Deposited By: Research Services Depository
Deposited On:09 Nov 2022 19:42
Last Modified:11 Nov 2022 18:03

Repository Staff Only: item control page