2025/12/25 by Yanyan Song, Song, Yanyan, Yaping Mao +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.2512.21647
openalex publication_date 2025/12/25 · openalex created_date 2025/12/30 · openalex updated_date 2026/07/28
For edge-ordered graphs G\prec and H\prec, the size edge-ordered Ramsey number redge(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.