Beyond the Erdős–Sós conjecture

EUROCOMB’23

Abstract
We prove an asymptotic version of a tree-containment conjecture of Klimošová, Piguet and Rozhoň [European J. Combin. 88 (2020), 103106] for graphs with quadratically many edges. The result implies that the asymptotic version of the Erdős-Sós conjecture in the setting of dense graphs is correct.

Pages:
328–335
References

M. Ajtai, J. Komlós, M. Simonovits, and E. Szemerédi. On the approximative solution of the Erdős-Sós conjecture on trees. In preparation.

M. Ajtai, J. Komlós, M. Simonovits, and E. Szemerédi. The solution of the Erdős-Sós conjecture for large trees. In preparation.

M. Ajtai, J. Komlós, M. Simonovits, and E. Szemerédi. Some elementary lemmas on the Erdős-Sós conjecture on trees. In preparation.

Guido Besomi, Matías Pavez-Signé, and Maya Stein. On the Erdős-Sós conjecture for trees with bounded degree. Combin. Probab. Comput., 30(5):741-761, 2021.
https://doi.org/10.1017/S0963548320000528

Akbar Davoodi, Diana Piguet, Hanka Řada, and Nicolás Sanhueza-Matamala. The asymptotic version of the Erdős-Sós conjecture and beyond. In preparation.

Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, fifth edition edition, 2017.
https://doi.org/10.1007/978-3-662-53622-3_7

P. Erdős. Extremal problems in graph theory. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pages 29-36. Publ. House Czech. Acad. Sci., Prague, 1964.

P. Erdős and M. Simonovits. A limit theorem in graph theory. Studia Sci. Math. Hungar., 1:51-57, 1966.

P. Erdös and A. H. Stone. On the structure of linear graphs. Bull. Amer. Math. Soc., 52:1087-1091, 1946.
https://doi.org/10.1090/S0002-9904-1946-08715-7

Frédéric Havet, Bruce Reed, Maya Stein, and David R. Wood. A variant of the Erdös-Sós conjecture. J. Graph Theory, 94(1):131-158, 2020.
https://doi.org/10.1002/jgt.22511

Jan Hladký, János Komlós, Diana Piguet, Miklós Simonovits, Maya Stein, and Endre Szemerédi. The approximate Loebl-Komlós-Sós conjecture IV: Embedding techniques and the proof of the main result. SIAM J. Discrete Math., 31(2):1072-1148, 2017.
https://doi.org/10.1137/140982878

J. Komlós and M. Simonovits. Szemerédi's regularity lemma and its applications in graph theory. In Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), vol- ume 2 of Bolyai Soc. Math. Stud., pages 295-352. János Bolyai Math. Soc., Budapest, 1996.

Václav Rozhoň. A local approach to the Erdős-Sós conjecture. SIAM J. Discrete Math., 33(2):643-664, 2019.
https://doi.org/10.1137/18M118195X

Maya Stein. Tree containment and degree conditions. In Discrete Mathematics and Applications, volume 165 of Springer Optim. Appl., pages 459-486. Springer, Cham, 2020.
https://doi.org/10.1007/978-3-030-55857-4_19

Endre Szemerédi. Regular partitions of graphs. In Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), volume 260 of Col- loq. Internat. CNRS, pages 399-401. CNRS, Paris, 1978.

Metrics

0

Views

0

PDF views