An approximate version of the Loebl-Komlós-Sós conjecture

Resumo:

Our talk is about an interesting conjecture of Loebl, Komlós, and Sós, which affirms the following. Given some natural number k, and some graph G, assume that at least half of the vertices of G have degree at least k. Then each tree with k edges is a subgraph of G.

Using Szemerédi's regularity lemma, and a version of Edmonds' and Gallai's matching theorem, we prove an approximate version of this conjecture for large enough graphs G, under the additional requirement that k is linear in n.

This is joint work with Diana Piguet.