On the size edge-ordered Ramsey numbers of graphs

Abstract

For edge-ordered graphs $G^{\prec }$ and $H^{\prec }$, the size edge-ordered Ramsey number ${\hat{r}}_{\text{edge}}(G^{\prec },H^{\prec })$ is defined as the smallest integer $m$ for which there exists an edge-ordered graph $F^{\prec }$ (with underlying graph $F$) having $m$ edges, such that every $2$-coloring of the edges of $F^{\prec }$ contains a monochromatic edge-ordered subgraph isomorphic to $G^{\prec }$ or a monochromatic edge-ordered subgraph isomorphic to $H^{\prec }$. Fox and Li posed a foundational question: which families of edge-ordered graphs have linear or near-linear size edge-ordered Ramsey numbers? In this paper, we apply Szemerédi's regularity lemma to prove that, even for sparse graph families, specifically the well-defined class of edge-ordered book graphs, the size edge-ordered Ramsey numbers of this family exhibit non-linear growth. Furthermore, we show that three families of edge-ordered graphs exhibit linear or near-linear size edge-ordered Ramsey numbers.