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

0504792 - ÚI 2020 RIV US eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GJ16-07822Y
Institucionální podpora: RVO:67985807
Klíčová slova: Erdős-Sós conjecture * embedding of trees * extremal combinatorics
Obor OECD: Pure mathematics
Impakt faktor: 0.750, rok: 2019
Způsob publikování: Omezený přístup
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.
Trvalý link: http://hdl.handle.net/11104/0296345