On ordered Ramsey numbers of bounded-degree graphs

Abstract: An ordered graph is a pair

m a t h c a l G = (G, p r e c)

where

G

is a graph and

p r e c

is a total ordering of its vertices. The ordered Ramsey number

o v e r l i n e R (m a t h c a l G)

is the minimum number

N

such that every

2

-coloring of the edges of the ordered complete graph on

N

vertices contains a monochromatic copy of

m a t h c a l G

. We show that for every integer

d g e q 3

, almost every

d

-regular graph

G

satisfies

o v e r l i n e R (m a t h c a l G) g e q f r a c n^{3 / 2 - 1 / d} 4 l o g n l o g l o g n

for every ordering

m a t h c a l G

of

G

. In particular, there are 3-regular graphs

G

on

n

vertices for which the numbers

o v e r l i n e R (m a t h c a l G)

are superlinear in

n

, regardless of the ordering

m a t h c a l G

of

G

. This solves a problem of Conlon, Fox, Lee, and Sudakov. On the other hand, we prove that every graph

G

on

n

vertices with maximum degree 2 admits an ordering

m a t h c a l G

of

G

such that

o v e r l i n e R (m a t h c a l G)

is linear in

n

. We also show that almost every ordered matching

m a t h c a l M

with

n

vertices and with interval chromatic number two satisfies

o v e r l i n e R (m a t h c a l M) g e q c n^{2} / l o g^{2} n

for some absolute constant

c

.

Recommendations

Cites Work

Cited In (12)

This page was built for publication: On ordered Ramsey numbers of bounded-degree graphs