Ordered Ramsey and Turán numbers of alternating paths and their variants
Gaurav Kucheriya, Allan Lo, Jan Petr, Amedeo Sgueglia, Jun Yan · 2026
Read Ordered Ramsey and Turán numbers of alternating paths and their variants by Gaurav Kucheriya, Allan Lo, Jan Petr, Amedeo Sgueglia, Jun Yan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-12358.txt.
Introduction
Kucheriya, Lo, Petr, Sgueglia, and Yan bound ordered Ramsey and Turán numbers for alternating paths. An ordered graph carries a total order on its vertices, which copies must respect. Balko and co-authors asked if the alternating path minimizes the ordered Ramsey number among paths. Their path visits vertices in a bouncing order from the ends toward the middle. The team proves an upper bound close to a small multiple of the path length. Similar methods fix the exact ordered Turán number and cover several related path variants.
Catalog record
| CREATOR | Gaurav Kucheriya, Allan Lo, Jan Petr, Amedeo Sgueglia, Jun Yan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41211 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.12358
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Ordered Ramsey and Turán numbers of alternating paths and their variants Gaurav Kucheriya, Allan Lo, Jan Petr, Amedeo Sgueglia, Jun Yan Abstract An ordered graph is a graph whose vertex set is equipped with a total order. The ordered complete graph K N < K_{N}^{<} is the complete graph with vertex set [ N ] [N] equipped with the natural ordering of the integers. Given an ordered graph H H , the ordered Ramsey number R < ( H ) R_{<}(H) is the smallest integer N N such that every red/blue edge-colouring of K N < K_{N}^{<} contains a monochromatic copy of H H with vertices appearing in the same relative order as in H H . Balko, Cibulka, Král, and Kynčl asked whether, among all ordered paths on n n vertices, the ordered Ramsey number is minimised by the alternating path AP n \AP_{n} – the ordered path with vertex set [ n ] [n] such that the vertices encountered along the path are 1 , n , 2 , n − 1 , 3 , n − 2 , … 1,n,2,n-1,3,n-2,\dots . Motivated by this problem, we make progress on establishing the value of R < ( AP n ) R_{<}(\AP_{n}) by proving that R < ( AP n ) ≤ ( 2 + 2 2 + o ( 1 ) ) n . R_{<}(\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 AP n \AP_{n} , and study the ordered Ramsey and Turán numbers of several related ordered paths. 1 Introduction An ordered graph is a graph whose vertex set is equipped with a total order. We will equivalently view an n -vertex ordered graph as a graph whose vertices are labelled with \{1,2,\dots,n\} (so the total order is the usual ordering of integers). We say that an ordered graph G contains an ordered graph H if there is an injection f:V(H)\to V(G) that preserves both the vertex order and adjacency, that is, for all i<j in V(H) , we have f(i)<f(j) in V(G) , and f(i)f(j)\in E(G) whenever ij\in E(H) . We say that G avoids H if G does not contain H . In recent years, there has been increasing interest in translating classical results on graphs to the ordered setting. Here we consider ordered Ramsey and Turán problems for different ordered paths. 1.1 Ordered Ramsey number The graph-theoretic version of Ramsey’s theorem [ 16 ] states that for every fixed graph H , there exists N such that every red/blue edge-colouring of the complete graph on N vertices contains a monochromatic copy of H . The smallest integer N with the above property is called the Ramsey number of H and is denoted by R(H) . The problem of quantitatively determining R(H) has attracted a lot of attention over the past several decades, but has remained extremely challenging in general. Even when H is the complete graph, little progress had been made since the upper bound of Erdős and Szekeres [ 10 ] in 1935 until the recent major breakthrough of Campos, Griffiths, Morris, and Sahasrabudhe [ 5 ] . Recently, Balko, Cibulka, Král, and Kynčl [ 1 ] , as well as Conlon, Fox, Lee, and Sudakov [ 7 ] , independently initiated a systematic study of the analogue of Ramsey’s theorem for ordered graphs. For a comprehensive survey of results in this area we refer to Balko [ 3 ] . Given an ordered graph H , the ordered Ramsey number R_{<}(H) is defined to be the smallest natural number N such that every red/blue edge-colouring of K_{N}^{<} , the ordered complete graph on \{1,2,\ldots,N\} , contains a monochromatic ordered copy of H . It is straightforward to observe that R_{<}(H) is well-defined as R_{<}(H)\leq R(K_{|H|}) . Moreover, although it always holds that R(H)\leq R_{<}(H) , the quantities R(H) and R_{<}(H) may behave very differently and a change in the labels of the vertices of H may result in drastic changes in the ordered Ramsey number. For example, this was observed for paths in [ 1 ] . Let P_{n} be the n -vertex path on [n] . In the unordered setting, Gerencsér and Gyárfás [ 12 ] showed that R(P_{n})=\left\lfloor 3n/2\right\rfloor-1 , which is linear in n . In the ordered setting, consider first the labelled path on [n] where the vertices encountered along the path are 1,2,\dots,n-1,n . This is usually known as the monotone ordered path on n vertices and is denoted by \MP_{n} . The Erdős–Szekeres theorem [ 10 ] , dating back to the very origins of Ramsey theory, implies that R_{<}(\MP_{n})=(n-1)^{2}+1 , which is quadratic in n . On the other hand, Balko, Cibulka, Král, and Kynčl [ 1 , Proposition 3] showed that for a different vertex labelling, yielding the so-called alternating path, the ordered Ramsey number is again linear in n and more closely resembles the linear behaviour of R(P_{n}) . The interest in this particular ordered path is also due to a still open problem [ 1 , Problem 29] which asks whether among all the ordered paths on n vertices, the alternating path minimises the ordered Ramsey number. The alternating path \AP_{n} on n vertices is the labelled path with vertex set [n] such that the vertices encountered along the path are: 1,n,2,n-1,\ldots,n/2,n/2+1 , if n is even; and 1,n,2,n-1,\ldots,\lfloor n/2\rfloor,\lfloor n/2\rfloor+2,\lfloor n/2\rfloor+1 , if n is odd. See Figure 1 (b) for a drawing of AP_{8} . It was proved in [ 1 ] that (5/2+o(1))n=5\lfloor n/2\rfloor-4\leq R_{<}(\AP_{n})\leq 2n-3+\sqrt{2n^{2}-8n+11}=(2+\sqrt{2}+o(1))n. The proof of the upper bound above uses an extremal result on \{0,1\} -matrices established by Füredi and Hajnal [ 11 , Theorem 2.2] and Cibulka [ 6 , Corollary 1.9] . Later, Balko, Jelínek, and Valtr [ 2 , Lemma 5.1] , while studying the ordered Ramsey number of graphs with bounded maximum degree, used a different method and obtained the weaker upper bound R_{<}(\AP_{n})\leq(4+o(1))n . We refine their method and make progress towards determining the precise linear multiplicative factor. Theorem 1 . R_{<}(\AP_{n})\leq 2n-2+\left\lfloor\frac{\sqrt{2(n-2)^{2}+(-1)^{n}}-1}{2}\right\rfloor=\left(2+\frac{\sqrt{2}}{2}+o(1)\right)n . In his master’s thesis [ 15 ] , Poljak listed the exact values or lower bounds on R_{<}(\AP_{n}) up to n=13 , which were obtained from computer experiments using a SAT solver algorithm. It is surprising that, as shown in Table 1 below, the upper bound from Theorem 1 matches all the known results reported in [ 15 ] . However, we do not believe that our bound is sharp for large n . n 2 3 4 5 6 7 8 9 10 11 12 13 UB 2 4 7 9 12 15 17 20 23 25 28 31 [ 15 ] 2 4 7 9 12 15 17 20 23 \geq 25 \geq 28 \geq 31 Table 1 : Upper bounds (UB) from Theorem 1 and results from [ 15 ] on R_{<}(\AP_{n}) . 1.2 Ordered Turán numbers Turán-type problems constitute another major research direction in extremal graph theory and are closely related to Ramsey-type problems. Given a graph H , the goal is to determine the Turán number of H , denoted by \ex(n,H) , which is the maximum number of edges