Skip to main content
2 of 2
Added another reference
Timothy Chow
  • 82.7k
  • 26
  • 363
  • 587

A long time ago, M. Ajtai, J. Komlós, M. Simonovits, and E. Szemerédi announced a proof (for large $k$) of the Erdős–Sós conjecture that every graph with average degree more than $k-1$ contains all trees with $k$ edges as subgraphs, but the proof has not yet appeared as of this writing (2022).

What do I mean by "a long time ago"? Reinhard Diestel, in the notes to Chapter 7 of Graph Theory (5th edition), gives a date of 2009. But Václav Rozhoň, in A local approach to the Erdős-Sós conjecture, says that the result was announced in the early 1990's.


EDIT: I found another reference, Local and mean Ramsey numbers for trees, by B. Bollobás, A. Kostochka, and R. H. Schelp (J. Combin. Theory Ser. B 79 (2000), 100–103), which says, "It was announced recently that M. Ajtai, J. Komlós, and E. Szemerédi confirmed the Erdős–Sós conjecture for sufficiently large trees."
Timothy Chow
  • 82.7k
  • 26
  • 363
  • 587