Edge-ordered Ramsey numbers

Abstract: We introduce and study a variant of Ramsey numbers for edge-ordered graphs, that is, graphs with linearly ordered sets of edges. The edge-ordered Ramsey number

o v e r l i n e R_{e} (m a t h f r a k G)

of an edge-ordered graph

m a t h f r a k G

is the minimum positive integer

N

such that there exists an edge-ordered complete graph

m a t h f r a k K_{N}

on

N

vertices such that every 2-coloring of the edges of

m a t h f r a k K_{N}

contains a monochromatic copy of

m a t h f r a k G

as an edge-ordered subgraph of

m a t h f r a k K_{N}

. We prove that the edge-ordered Ramsey number

o v e r l i n e R_{e} (m a t h f r a k G)

is finite for every edge-ordered graph

m a t h f r a k G

and we obtain better estimates for special classes of edge-ordered graphs. In particular, we prove

o v e r l i n e R_{e} (m a t h f r a k G) l e q 2^{O (n^{3} l o g n)}

for every bipartite edge-ordered graph

m a t h f r a k G

on

n

vertices. We also introduce a natural class of edge-orderings, called lexicographic edge-orderings, for which we can prove much better upper bounds on the corresponding edge-ordered Ramsey numbers.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Edge-ordered Ramsey numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2178669)