Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

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

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.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010