Loebl–Komlós–Sós conjecture for trees

Let GG be an nn-vertex graph, let dd be a nonnegative integer, and let TT be a tree with dd edges.

Loebl–Komlós–Sós conjecture. If at least n/2n/2 vertices of GG have degree at least dd, then GG contains a copy of TT.

The conjecture replaces the average-degree condition in the Erdős–Sós conjecture by a median-degree condition. The source notes that it has been proved in several important cases, including large dense host graphs, while the general sparse bounded-degree form remains an active problem.

Sources & referencesView supporting material

Primary source

Alexey Pokrovskiy, “Hyperstability in the Erdős-Sós Conjecture”, arXiv:2409.15191 (2024).

Additional references

4 papers in this index state this conjecture (2008–2024). The statement above is taken from the most recent of them; the others are arXiv:1912.04004, arXiv:1406.3935, arXiv:0805.4834.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.