On 30.10.2006 at 12:20 in S1, there is the following noon lecture:
On an approximate version of the Loebl-Komlos-Sos conjecture
Diana Piguet, Maya Stein
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.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010