An ordered graph is a simple graph with an ordering on its vertices. Define the ordered path Pn to be the monotone increasing path with n edges. The ordered size Ramsey number r̃(Pr,Ps) is the minimum number m for which there exists an ordered graph H with m edges such that every two-coloring of the edges of H contains a red copy of Pr or a blue copy of Ps. For 2≤r≤s, we show [Formula presented], where C>0 is an absolute constant. This problem is motivated by the recent results of Bucić et al. (2019) and Letzter and Sudakov (2019) for oriented graphs.
- Ordered graphs
- Ramsey numbers
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics