Noon lecture

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

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

Schelp's conjecture

Diana Piguet

Abstract

It is conjectured that for any edge-coloring of the complete graph K_{2n-2} by two colors, one of the colors is T_n-universal, i.e. it contains any tree on n vertices. This is known for large values of n. Inspired by this conjecture, R. Schelp asked whether we may delete many edges of K_{2n-2} without loosing the property that one of the color classes is T_n-universal and conjectured the following.

Conjecture (Schelp): For any edge-coloring of K_{t,t,t} by two colors, one of the color classes is universal with respect to the trees of order 3t/2-o(t) with bounded degree.

We prove this conjecture using the Regularity Lemma. This is a joint work with Julia Boettcher and Jan Hladky.

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