2019/12/18 by David Conlon, Conlon, David, Lior Gishboliner +5
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.1912.08834
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(n2)? 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 + \lfloor log2 e \rfloor,e) = o(n2). 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/ loglog e), e) = o(n2).