Abstrakt
An ordered graph is a graph together with a total ordering of its vertices. We study ordered Ramsey numbers, the analogue of Ramsey numbers for ordered graphs.
In contrast with the case of unordered graphs, we show that there are ordered matchings whose ordered Ramsey numbers are super-polynomial in the number of vertices. We also prove that ordered Ramsey numbers are polynomial in the number of vertices of the given ordered graph G if G has constant degeneracy and constant interval chromatic number or if G has constant bandwidth.
The latter result answers positively a question of Conlon, Fox, Lee, and Sudakov. For a few special classes of ordered graphs, we give asymptotically tight bounds for their ordered Ramsey numbers.
For so-called monotone cycles we compute their ordered Ramsey numbers exactly.