Ordered Ramsey and Turán numbers of alternating paths and their variants

Abstract

An ordered graph is a graph whose vertex set is equipped with a total order. The ordered complete graph $K_N^{<}$ is the complete graph with vertex set $[N]$ equipped with the natural ordering of the integers. Given an ordered graph $H$, the ordered Ramsey number $R_{<}(H)$ is the smallest integer $N$ such that every red/blue edge-colouring of $K_N^{<}$ contains a monochromatic copy of $H$ with vertices appearing in the same relative order as in $H$. Balko, Cibulka, Král, and Kynčl asked whether, among all ordered paths on $n$ vertices, the ordered Ramsey number is minimised by the alternating path ${\mathrm{AP}}_n$ -- the ordered path with vertex set $[n]$ such that the vertices encountered along the path are $1,n,2,n-1,3,n-2,\dots$. Motivated by this problem, we make progress on establishing the value of $R_{<}({\mathrm{AP}}_n)$ by proving that \[ R_{<}(\mathrm{AP}_n)\leq \left(2+\frac{\sqrt{2}}{2}+o(1)\right)n. \] We then use similar methods to determine the exact ordered Turán number of ${\mathrm{AP}}_n$, and study the ordered Ramsey and Turán numbers of several related ordered paths.

17 pages, 6 figures. Fixed a typo in arXiv abstract