Edge-ordered Ramsey numbers

DOI10.1016/J.EJC.2020.103100zbMATH Open1439.05129arXiv1906.08698OpenAlexW2981347346MaRDI QIDQ2178669FDOQ2178669

Publication date: 11 May 2020

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1906.08698

Recommendations

zbMATH Keywords

edge-ordered graphs lexicographic edge-orderings

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Cites Work

Cited In (6)

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)