2024/12/23 by Domagoj Bradač, Bradač, Domagoj, Patryk Morawski +5
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Topology and Set Theory #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2412.17599
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 KN 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) ≤ e^109 √(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.