Noon lecture

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

On 03.03.2016 at 12:20 in S6, there is the following noon lecture:

Bounds on ordered Ramsey numbers of bounded-degree graphs (Jirka Matoušek Prize talk)

Martin Balko

Abstract

An ordered graph is a graph together with a total ordering of its vertices. The ordered Ramsey number of an ordered graph G is the minimum number N such that every ordered complete graph with N vertices and with edges colored by two colors contains a monochromatic copy of G.

We show that there are 3-regular graphs on n vertices for which the ordered Ramsey numbers are superlinear in n, regardless of the ordering. This gives a positive answer to a problem of Conlon, Fox, Lee, and Sudakov.

On the other hand, we prove that every graph on n vertices with maximum degree 2 admits an ordering such that the corresponding ordered Ramsey number is linear in n.

This is a joint work together with Pavel Valtr and Vít Jelínek.

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