Ordered Ramsey Numbers of Powers of Paths

Given two vertex-ordered graphs H₁ H 1 and H₂ H 2 , the ordered Ramsey number R_<(H₁,H₂) R < ( H 1 , H 2 ) is the smallest N such that whenever the edges of a vertex-ordered complete graph KN K N are red/blue-coloured, then there is a red (ordered) copy of H₁ H 1 or a blue (ordered) copy of H₂ H 2 . Let Pₙᵗ P n t denote the t -th power of a monotone path on n vertices. The ordered Ramsey numbers of powers of paths have been extensively studied. We prove that there exists an absolute constant C such that R_<(Kₛ,Pₙᵗ)≤ R(Kₛ,Kₜ)C · n R < ( K s , P n t ) ≤ R ( K s , K t ) C · n holds for all s , t , n , which is tight up to the value of C . As a corollary, we obtain that there is an absolute constant C such that R_<(Kₙ,Pₙᵗ)≤ nCt R < ( K n , P n t ) ≤ n Ct . These results resolve a problem and a conjecture of Gishboliner, Jin and Sudakov. Furthermore, we show that R_<(Pₙᵗ,Pₙᵗ)≤ n⁴⁺ᵒ⁽¹⁾ <mml:math xmlns:mml="http://www.