Search

An ordered graph is a simple graph with an ordering on its vertices. Define the ordered path P n to be the monotone increasing path with n edges. The ordered size Ramsey number r ( P r , P s ) 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 P r or a blue copy of P s . For 2 ≤ r ≤ s , we show 1 8 r 2 s ≤ r ( P r , P s ) ≤ C r 2 s ( log s ) 3 , where C > 0 is an absolute constant. This problem is motivated by the recent results of Bucic et al. (2019) and Letzter and Sudakov (2019) for oriented graphs.