A new bound for the Brown–Erdős–Sós problem
A new bound for the Brown–Erdős–Sós problem
复制标题
Brown–ErdÅs–S 问题的新界限
DOI：
10.1016/j.jctb.2022.08.005
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Shapira, Asaf
中科院分区：
文献类型：
--
作者：
Conlon, David;Gishboliner, Lior;Levanzov, Yevgeny;Shapira, Asaf
设f （n, v, e）表示不包含e条边的3-均匀超图中最多由v个顶点张成的最大边数。极值组合学中最具影响力的开放问题之一是，对于给定的边数e≥3，使f (n, e+ d, e)= 0 （n2）的最小整数d= d (e)是多少？这个问题起源于Brown， Erdős和Sós在70年代早期的研究，标准的猜想是对于每一个e≥3，d (e)= 3。关于这个问题的最新结果是由Sárközy和Selkow在2004年得出的，他们表明f (n, e+ 2+⌊log 2²e⌋，e)= o （n2）。唯一的改进是最近Solymosi和Solymosi的突破，他们将d（10）的界从5提高到4。我们在Sárközy-Selkow边界上得到了第一个渐近改进，表明f (n, e+ O (log (e) /log (e)), e)= O （n2）。
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 2)? 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 2 e⌋, e)= o (n 2). 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 2).