A Survey on Ordered Ramsey Numbers

Martin Balko 1 · 2025

Read A Survey on Ordered Ramsey Numbers by Martin Balko 1 (2025) 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-2502-02155.txt.

Introduction

Martin Balko surveys a young branch of Ramsey theory in which the order of a graph's vertices matters. The ordered Ramsey number of a graph is the smallest arena size that forces a monochromatic copy of the graph in its exact given vertex order. The copy must appear inside any red-blue coloring of a complete graph's edges. How these numbers grow is a fresh and difficult set of questions.

The survey gathers recent progress on these quantities and ties the topic to other parts of combinatorics and to well-known conjectures. A recurring theme is how sharply ordered results can differ from their classical unordered counterparts, sometimes in surprising ways. Balko closes with a list of new open problems meant to challenge the field.

Catalog record

CREATORMartin Balko 1
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-02155

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Survey on Ordered Ramsey Numbers Thanks: M. Balko was supported by grant no. 23-04949X of the Czech Science Foundation (GAČR) and by the Center for Foundations of Modern Computer Science (Charles Univ. project UNCE 24/SCI/008). Martin Balko 1 Abstract The ordered Ramsey number of a graph G < G^{<} with a linearly ordered vertex set is the smallest positive integer N N such that any two-coloring of the edges of the ordered complete graph on N N vertices contains a monochromatic copy of G < G^{<} in the given ordering. The study of the quantitative behavior of ordered Ramsey numbers is a relatively new theme in Ramsey theory full of interesting and difficult problems. In this survey paper, we summarize recent developments in the theory of ordered Ramsey numbers. We point out connections to other areas of combinatorics and some well-known conjectures. We also list several new and challenging open problems and highlight the often strikingly different behavior from the unordered case. 1 Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Czech Republic [email protected] 1 Introduction In a broad sense, Ramsey theory refers to any result whose underlying philosophy can be captured by the statement “Every structure of a given kind contains a large well-organized substructure”. This part of discrete mathematics has developed enormously in the last few decades, emerging into a field with important statements in many areas, including combinatorics, geometry, logic, and number theory. Our focus will be on graph theory where one of the cornerstones of Ramsey theory, from which Ramsey theory derives its name, is Ramsey’s theorem [ 71 ] . This classical result states that for any two graphs G and H , there is a positive integer N such that every red-blue coloring of the complete graph K_{N} on N vertices contains a red copy of G or a blue copy of H as a subgraph of K_{N} . The smallest such N is called the Ramsey number of G and H and is denoted by R(G,H) . When G and H are isomorphic, we write R(G) instead of R(G,G) . Estimating the growth rate of Ramsey numbers is a notoriously difficult problem in general with a remarkable influence in combinatorics. Despite several attempts over the last 70 years, see for example [ 20 , 73 , 75 ] , Ramsey numbers are not fully understood even for complete graphs. For a long time, the best-known bounds on R(K_{n}) essentially were 2^{n/2}\leq R(K_{n})\leq 2^{2n}. (1) The lower bound is due to Erdős [ 33 ] while the upper bound was proved by Erdős and Szekeres [ 36 ] in their seminal paper from 1935 where they independently rediscovered Ramsey’s theorem. Very recently, Campos, Griffiths, Morris, and Sahasrabudhe [ 15 ] made a breakthrough and improved the exponential upper bound to R(K_{n})\leq(4-\varepsilon)^{n} for some small constant \varepsilon>0 . For sparser graphs, Ramsey numbers grow at a significantly slower rate. For example, a classical result by Chvátal, Rödl, Szemerédi, and Trotter [ 18 ] says that Ramsey numbers of bounded-degree graphs are only linear in the number of vertices. More precisely, for every positive integer \Delta , there is a positive integer C=C(\Delta) such that every n -vertex graph G with maximum degree \Delta satisfies R(G)\leq C\cdot n . In this survey, we focus on a more recent variant of Ramsey numbers defined for ordered graphs , that is, graphs with linearly ordered vertex sets. Studying these so-called ordered Ramsey numbers became quite an active area in graph Ramsey theory [ 26 ] which offers numerous applications in several parts of combinatorics such as discrete geometry and extremal theory of matrices. We try to summarize the recent developments in the theory of ordered Ramsey numbers, pointing out connections to other areas of combinatorics and some well-known conjectures. We also list several new and challenging open problems and highlight the often strikingly different behavior from the unordered case. In Section 2 , we survey the recent developments about ordered Ramsey numbers of ordered graphs. We start by mentioning general bounds on ordered Ramsey numbers. Then, we will focus on specific classes of ordered graphs, where we can prove much more precise estimates and, in some cases, even the exact formulas for the ordered Ramsey numbers. We also discuss extensions of ordered Ramsey numbers for more than two colors. In Section 3 , we consider hypergraph ordered Ramsey numbers . Besides general bounds, we focus on so-called monotone paths, a case with close connections to the classical Erdős–Szekeres theorem. Finally, in Section 4 we discuss edge-ordered Ramsey numbers where we work with the ordering of the edges, not vertices. We note that this paper is not intended to serve as an exhaustive survey of the subject. For example, we treat problems of an asymptotic nature rather than being concerned with the computation of exact ordered Ramsey numbers. We apologize in advance for any particularly glaring omissions. For the sake of clarity of presentation, we will maintain some conventions throughout the paper. For a positive integer n , we use [n] to denote the set \{1,\dots,n\} . We omit floor and ceiling signs whenever they are not crucial and we use \log to denote base 2 logarithm. 2 Graph Ordered Ramsey Numbers An ordered graph G^{<} is a pair (G,<) consisting of a graph G and a linear ordering < of the vertex set of G . We call G^{<} an ordering of G . Two ordered graphs G^{<} and H^{<} are isomorphic if their underlying graphs G and H are isomorphic via a one-to-one correspondence V(G)\to V(H) that preserves the vertex orderings. Note that, for every positive integer n , there is only one ordered complete graph on n vertices up to isomorphism. We use K^{<}_{n} to denote such an ordered complete graph. An ordered graph G^{<} is an ordered subgraph of an ordered graph H^{<} if G is a subgraph of H and the vertex ordering of G is a suborder of the vertex ordering of H . If an ordered graph H^{<} contains an ordered subgraph isomorphic to an ordered graph G^{<} , then we say that H^{<} contains a copy of G^{<} . We can now define an analog of Ramsey numbers for ordered graphs. The ordered Ramsey number R_{<}(G^{<},H^{<}) of two ordered graphs G^{<} and H^{<} is the minimum positive integer N such that every red-blue coloring of the edges of K^{<}_{N} contains a red copy of G^{<} or a blue copy of H^{<} . If G^{<} and H^{<} are isomorphic, then we simply write R_{<}(G^{<}) instead of R_{<}(G^{<},H^{<}) and we call it the diagonal case. We refer to R_{<}(G^{<},H^{<}) with non-isomorphic G^{<} and H^{<} as the off-diagonal case. Note that we have R(G)\leq R_{<}(G^{<}) for every graph G and each ordering G^{<} of G . Moreover, R(K_{n})=R_{<}(K^{<}_{n}) for every positive integer n . Since every ordered graph G_{<} on n vertices is an ordered subgraph of K^{<}_{n} , we thus obtain the bounds R(G)\leq R_{<}(G^{<})\leq R(K_{n}). It follows that the number R_{<}(G^{<}) is finite for every ordered graph G^{<} . Similarly, R_{<}(G^{<},H^{<}) is also finite for any ordered graphs G^{<} and H^{<} and thus ordered Ramsey numbers are well-defined.

Read the complete text