Ross Kanghttps://arxiv.org/abs/2603.12358
Here is the *third* manuscript coming out of the "Topics in Ramsey theory" online-only problem-solving session (https://sparse-graphs.mimuw.edu.pl/doku.php?id=sessions:2025sessions:2025session1) of the Sparse (Graphs) Coalition, which took place less than a year ago.
It is still surprising to realise what one can make of such events, if they are set up well.
#combinatorics #remoteconferences #graphtheory #extremalcombinatorics #openscience
Ordered Ramsey and Turán numbers of alternating paths and their variants
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\v cl 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.
Harald Pehl
WildFlyAS