Paper
The asymptotic version of the Erdős-Sós conjecture and beyond
Klimošová, Piguet, and Rozhoň conjectured that any graph with minimum degree $k/2$ and sufficiently many vertices of degree $k$ should contain all trees with $k$ edges. We prove an asymptotic version of this conjecture for dense host graphs. We obtain interesting corollaries: the first is an asymptotic version of the Erdős--Sós conjecture for dense host graphs, which works without any bounded-degree restriction on th · Authors: Akbar Davoodi, Diana Piguet, Hanka Řada, Nicolás Sanhueza-Matamala · Published 2026-03-18 · arXiv:2603.17755
- Published
- 2026-03-18
- Authors
- 4
- arXiv
- 2603.17755
- Category
- math.CO
Abstract
arXiv:2603.17755
Akbar Davoodi, Diana Piguet, Hanka Řada, Nicolás Sanhueza-Matamala
Klimošová, Piguet, and Rozhoň conjectured that any graph with minimum degree $k/2$ and sufficiently many vertices of degree $k$ should contain all trees with $k$ edges. We prove an asymptotic version of this conjecture for dense host graphs. We obtain interesting corollaries: the first is an asymptotic version of the Erdős--Sós conjecture for dense host graphs, which works without any bounded-degree restriction on the guest trees. Secondly, by leveraging recent results by Pokrovsky, we can translate our results to sparse host graphs in the case of bounded-degree guest trees.