A Local Approach to the Erdős-Sós Conjecture

0504792 - ÚI 2020 RIV US eng J - Journal Article
Rozhoň, Václav
A Local Approach to the Erdős-Sós Conjecture.
SIAM Journal on Discrete Mathematics. Roč. 33, č. 2 (2019), s. 643-664. ISSN 0895-4801. E-ISSN 1095-7146
R&D Projects: GA ČR GJ16-07822Y
Institutional support: RVO:67985807
Keywords : Erdős-Sós conjecture * embedding of trees * extremal combinatorics
OECD category: Pure mathematics
Impact factor: 0.750, year: 2019
Method of publishing: Limited access
http://dx.doi.org/10.1137/18M118195X

A famous conjecture of Erdős-Sós states that every graph with average degree more than k-1 contains all trees with k edges as subgraphs. We prove that the Erdős-Sós conjecture holds approximately, if the size of the embedded tree is linear in the size of the graph, and the maximum degree of the tree is sublinear.
Permanent Link: http://hdl.handle.net/11104/0296345