Department of
Applied
Mathematics

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.