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)
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.
Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019