Noon lecture

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

On 05.02.2009 at 12:20 in S8, there is the following noon lecture:

Embedding thin large graphs

Jan Hladký

Abstract

We investigate under which minimum-degree condition does a graph $G$ contain a square-path and a square-cycle of a certain length. We give precise tresholds, assuming that the order of $G$ is large. This extends results of Fan and Kierstead [J. Combin. Theory Ser. B, 67(2), 167-182, 1996] and of Koml\'os, Sark\"ozy, and Szemer\'edi [Random Structures Algorithms, 9(1-2), 193-211, 1996] concerning containment of a spanning square-path and a spanning square-cycle, respectively.

The method also yields optimal minimum-degree threshold for the problem of embedding a three-colorable graph $H$ of bounded maximum degree and sublinear bandwidth in the case that the order $H$ is of the same order as the order of the hosting graph $G$. This can be thought of as a version of the Bollob\'as-Koml\'os Conjecture, solved recently by B\"ottcher, Schacht and Taraz [J. Combin. Theory Ser. B, 98(4), 752-777, 2008], [Math. Ann, 343(1),

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