Ordered Ramsey numbers of graphs with $m$ edges

Abstract

Given a vertex-ordered graph $G$, the ordered Ramsey number $r_{<}(G)$ is the minimum integer $N$ such that every $2$-coloring of the edges of the complete ordered graph $K_N$ contains a monochromatic ordered copy of $G$. Motivated by a similar question posed by Erdős and Graham in the unordered setting, we study the problem of bounding the ordered Ramsey number of any ordered graph $G$ with $m$ edges and no isolated vertices. We prove that $r_{<}(G)\le e^{10^9\sqrt{m}(\log \log m{)}^{3/2}}$ for any such $G$, which is tight up to the $(\log \log m{)}^{3/2}$ factor in the exponent. As a corollary, we obtain the corresponding bound for the oriented Ramsey number of a directed graph with $m$ edges.

13 pages