Department of
Applied
Mathematics

On an approximate version of the Loebl-Komlos-Sos conjecture

Diana Piguet, Maya Stein

Abstract

The Loebl-Komlós-Sós conjecture states that every graph G on n vertices with the property that at least n/2 vertices have degree at least k, contains, as a subgraph, any tree with at most k edges. It is known only for a few special cases, for example paths. We outline the proof of an approximate version of the conjecture: for \epsilon>0, for large enough n=n(\epsilon), and for k linear in n, if at least (1+\epsilon)n/2 vertices have degree at least (1+\epsilon)k, then G contains any tree of size k. For k=n/2, this was already shown by Ajtai, Komlós and Szemerédi, and our proof partly follows their approach.