Abstrakt
An ordered graph is a pair G=(H,= 3, almost every d-regular graph satisfies R(G) >= n^(3/2-1/d)/(4log(n)log(log(n))) for every ordering of G. In particular, there are 3-regular graphs on n vertices for which the numbers R(G) are superlinear in n, regardless of the ordering G.
This solves 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 G such that R(G) is linear in n.
We also show that almost every ordered matching M with n vertices and with interval chromatic number two satisfies R(M) >= cn^2/log(n)^2 for some absolute constant c.