A new approach for the Brown-Erdős-Sós problem

EUROCOMB’23

Abstract
The celebrated Brown-Erdős-Sós conjecture states that for every fixed $e$, every $3$-uniform hypergraph with $\Omega(n^2)$ edges contains $e$ edges spanned by $e+3$ vertices. Up to this date all the approaches towards resolving this problem relied on highly involved applications of the hypergraph regularity method, and yet they supplied only approximate versions of the conjecture, producing $e$ edges spanned by $e+O(\log e/\log \log e)$ vertices. We describe a completely different approach, which reduces the problem to a variant of another well-known conjecture in extremal graph theory. A resolution of the latter would resolve the Brown-Erdős-Sós conjecture up to an absolute additive constant.

Pages:
812–818
References

N. Alon, M. Krivelevich, and B. Sudakov. Turán numbers of bipartite graphs and related Ramsey-type questions, Comb. Probab. Comput 12 (2003), 477#494.
https://doi.org/10.1017/S0963548303005741

W. G. Brown, P. Erdős and V.T. Sós, Some extremal problems on r -graphs, New Directions in the Theory of Graphs, Proc. 3rd Ann Arbor Conference on Graph Theorey, Academic Press, New York, 1973, 55-63.

W. Brown, P. Erdős and V. Sós. On the existence of triangulated spheres in 3-graphs, and related problems, Periodica Mathematica Hungarica, 3(3#4) (1973), 221-228.
https://doi.org/10.1007/BF02018585

B. Bukh, Extremal graphs without exponentially-small bicliques, manuscipt 2022.

D. Conlon, private commuication, 2022.

D. Conlon, O. Janzer and J. Lee, More on the extremal number of subdivisions,

Combinatorica 41 (2021), 465-494.
https://doi.org/10.1007/s00493-020-4202-1

D. Conlon and J. Lee, On the extremal number of subdivisions, Int. Math. Res. Not.

2021, 9122-9145.

D. Conlon, L. Gishboliner, Y. Levanzov and A. Shapira, A new bound for the Brown-Erd®s-Sós problem, J. Combin. Theory Ser. B. 158 (2023), 1-35.
https://doi.org/10.1016/j.jctb.2022.08.005

P. Erdős, Some recent results on extremal problems in graph theory. Results, Theory

of Graphs (Internat. Sympos., Rome, 1966), pages 117#123, 1967.

Z. Füredi, On a Turán type problem of Erd®s, Combinatorica 11 (1991), 75#79.
https://doi.org/10.1007/BF01375476

W. T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. of Math. 166 (2007), 897#946.
https://doi.org/10.4007/annals.2007.166.897

W. T. Gowers and J. Long, The length of an s -increasing sequence of r -tuples, Combin. Probab. Comput. 30 (2021), 686#721.
https://doi.org/10.1017/S0963548320000371

A. Grzesik, O. Janzer and Z. L. Nagy, The Turán number of blow-ups of trees, J. Combin. Theory Ser. B. 156 (2022), 299-309.
https://doi.org/10.1016/j.jctb.2022.05.004

O. Janzer, The extremal number of the subdivisions of the complete bipartite graph, SIAM J. Discrete Math. 34 (2020), 241-250.
https://doi.org/10.1137/19M1269798

O. Janzer, Disproof of a conjecture of Erd®s and Simonovits on the Turán number of graphs with minimum degree 3, Int. Math. Res. Not., to appear.

T. Kővári, V. T. Sós and P. Turán, On a problem of K. Zarankiewicz, Colloquium Math. 3 (1954), 50-57.
https://doi.org/10.4064/cm-3-1-50-57

B. Nagle, V. Rödl and M. Schacht, The counting lemma for regular k -uniform hypergraphs, Random Structures Algorithms 28 (2006), 113#179.
https://doi.org/10.1002/rsa.20117

K.F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104-109.
https://doi.org/10.1112/jlms/s1-28.1.104

V. Rödl and J. Skokan, Regularity lemma for k -uniform hypergraphs, Random Structures Algorithms 25 (2004), 1#42.
https://doi.org/10.1002/rsa.20017

V. Rödl and J. Skokan, Applications of the regularity lemma for uniform hypergraphs, Random Structures Algorithms 28 (2006), 180#194.
https://doi.org/10.1002/rsa.20108

I. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, in Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18, Volume II, 939-945.

G. N. Sárközy and S. Selkow, An extension of the Ruzsa-Szemerédi theorem, Combinatorica 25 (2004), 77-84.
https://doi.org/10.1007/s00493-005-0006-6

D. Solymosi and J. Solymosi, Small cores in 3 -uniform hypergraphs, J. Combin. Theory Ser. B. 122 (2017), 897-910.
https://doi.org/10.1016/j.jctb.2016.11.001

E. Szemerédi, Regular partitions of graphs, In: Proc. Colloque Inter. CNRS, 1978, 399-401.

B. Sudakov and I. Tomon, Turán number of bipartite graphs with no K t,t , Proc. Amer. Math. Soc. 148 (2020), 2811-2818.
https://doi.org/10.1090/proc/15042

T. Tao, A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A 113 (2006), 1257#1280.
https://doi.org/10.1016/j.jcta.2005.11.006

Metrics

0

Views

0

PDF views