{"id":"arxiv/2609.05417","url":"https://arxiv.org/abs/2609.05417","tags":["math.CO"],"score":0,"title":"The Erd\\H os-Sós conjecture in dense graphs","domain":"math.CO","source":"arxiv","authors":["Bruce Reed","Maya Stein"],"reviews":0,"subject":"math.CO","summary":"The Erd\\H os--Sós conjecture states that every $n$-vertex graph with more than $(k-2)n/2$ edges contains every $k$-vertex tree. We prove that for every $γ$ there is an $n_0$ such that for all $n\\ge n_0$ and $k \\ge γn$ the conjecture holds. As a corollary of our result, we obtain a solution of a 51-year-old problem of Erd\\H os and Graham on the multicolor Ramsey numbers of trees.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-04","reactions":{}}