Erdős–Sós conjecture

Status partial high confidence

The Erdős–Sós conjecture (1963) remains open in full generality. Major partial results have appeared: Pokrovskiy (2024) proved the conjecture for all sufficiently large bounded-degree trees; Davoodi, Piguet, Řada, and Sanhueza-Matamala (2026) established an asymptotic version for dense host graphs without any degree restriction on the guest tree; Reed and Stein (2026) proved the conjecture exactly (without approximation) for dense host graphs when k ≥ γn for any fixed γ > 0, also resolving a 51-year-old problem of Erdős and Graham on multicolor Ramsey numbers for trees. The long-announced proof by Ajtai, Komlós, Simonovits, and Szemerédi for sufficiently large k remains unpublished.

Cited literature (3)

• partial Hyperstability in the Erdős-Sós Conjecture (2024)
  Alexey Pokrovskiy · arXiv preprint · arXiv:2409.15191

  Proves the Erdős–Sós conjecture for all sufficiently large bounded-degree trees, by establishing a structure theorem that converts sparse T-free graphs into dense T-free ones amenable to regularity methods.

• partial The asymptotic version of the Erdős-Sós conjecture and beyond (2026)
  Akbar Davoodi, Diana Piguet, Hanka Řada, Nicolás Sanhueza-Matamala · arXiv preprint · arXiv:2603.17755

  Proves an asymptotic version of the Erdős–Sós conjecture for dense host graphs without any bounded-degree restriction on the guest tree, as a consequence of a more general tree-containment result.

• partial The Erdős-Sós conjecture in dense graphs (2026)
  Bruce Reed, Maya Stein · arXiv preprint · arXiv:2609.05417

  Proves the Erdős–Sós conjecture exactly (without approximation) for all graphs on n vertices when k ≥ γn for any fixed γ > 0, and as a byproduct resolves a 51-year-old problem of Erdős and Graham on multicolor Ramsey numbers for trees.

Reviewer notes. The full conjecture — every graph on n vertices with more than n(k-1)/2 edges contains every tree with k edges — remains open. Three significant partial results have appeared since the book's 2008 publication: (1) the bounded-degree case for large trees (Pokrovskiy 2024); (2) an asymptotic dense-graph result for all trees (Davoodi et al. 2026); (3) the exact dense-graph result for k ≥ γn (Reed–Stein 2026). The AKSS proof announced in the 1990s for 'large enough k' (without any bounded-degree restriction) was never formally published and has not appeared as of 2026. The companion paper arXiv:2409.15189 (Pokrovskiy, notes on covers) supports the 2409.15191 result. The arXiv paper 2608.25746 (Zhao–Peng) addresses a Gerbner–Palmer variant about clique counts in T-free graphs, not the original conjecture.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).