Ordered Ramsey numbers of graphs with m m edges

Domagoj Bradač, Patryk Morawski, Benny Sudakov, Yuval Wigderson · 2024

Read Ordered Ramsey numbers of graphs with m m edges by Domagoj Bradač, Patryk Morawski, Benny Sudakov, Yuval Wigderson (2024) 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-2412-17599.txt.

Introduction

Domagoj Bradač, Patryk Morawski, Benny Sudakov, and Yuval Wigderson bound a Ramsey-type number for ordered graphs in this 2024 mathematics paper. Ramsey numbers ask how large a complete graph must be before any red-blue coloring of its edges forces a single-colored copy of a given pattern. Here the pattern's vertices come in a fixed order, and copies must respect that order.

The team studies the worst case over all ordered graphs with a given number of edges and no isolated vertices. They prove an upper bound whose exponent grows like the square root of the edge count, times a small extra factor. The bound is tight up to that extra factor, which settles most of the question earlier work had left open. As a bonus, the same bound carries over to the oriented Ramsey number for directed graphs with the same number of edges.

Catalog record

CREATORDomagoj Bradač, Patryk Morawski, Benny Sudakov, Yuval Wigderson
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-17599

Browse the full library · About the Tower of Babel

Full text

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

Ordered Ramsey numbers of graphs with m m edges Domagoj Bradač, Patryk Morawski, Benny Sudakov, Yuval Wigderson Abstract Given a vertex-ordered graph G G , the ordered Ramsey number r < ​ ( G ) r_{<}(G) is the minimum integer N N such that every 2 2 -coloring of the edges of the complete ordered graph K N K_{N} contains a monochromatic ordered copy of G G . Motivated by a similar question posed by Erdős and Graham in the unordered setting, we study the problem of bounding the ordered Ramsey number of any ordered graph G G with m m edges and no isolated vertices. We prove that r < ​ ( G ) ≤ e 10 9 ​ m ​ ( log ⁡ log ⁡ m ) 3 / 2 r_{<}(G)\leq e^{10^{9}\sqrt{m}(\log\log m)^{3/2}} for any such G G , which is tight up to the ( log ⁡ log ⁡ m ) 3 / 2 (\log\log m)^{3/2} factor in the exponent. As a corollary, we obtain the corresponding bound for the oriented Ramsey number of a directed graph with m m edges. 1 Introduction For a graph G , the Ramsey number r(G) is the minimum integer N such that every 2 -coloring of the edges of the complete graph K_{N} on N vertices contains a monochromatic copy of G . The existence of these numbers was famously proved by Ramsey [ 26 ] , while the first good quantitative bounds were proved by Erdős and Szekeres [ 15 ] . Since then, the field of graph Ramsey theory has flourished, and determining how r(G) depends on the graph G has become one of the most-studied questions in combinatorics. Arguably, the most important question in the field is determining the Ramsey number r(K_{n}) of the complete graph K_{n} on n vertices. Here, after almost a century of only minor improvements on the standard bounds 2^{n/2}\leq r(K_{n})\leq 4^{n} , a significant breakthrough was recently achieved by Campos, Griffiths, Morris and Sahasrabudhe [ 5 ] who showed an exponentially better upper bound of (4-\varepsilon)^{n} for some constant \varepsilon>0 , see also [ 22 , 2 ] . Another prominent direction of study is to understand the Ramsey numbers of sparse graphs. In 1975, Burr and Erdős [ 4 ] conjectured that Ramsey numbers of graphs with bounded degeneracy are linear in their number of vertices. In 1983, Chvátal, Rödl, Szemerédi and Trotter [ 6 ] proved a special case of the conjecture, namely that bounded degree graphs have linear Ramsey numbers. However, proving the Burr–Erdős conjecture in full generality was very challenging, and it was only resolved by Lee in 2017 [ 24 ] . A related question was posed by Erdős and Graham in 1973: among all graphs G on m edges, what graph maximizes the Ramsey number? The intuition given by the above considerations is that one would like to make G as dense as possible. In fact, Erdős and Graham [ 12 ] conjectured that among all graphs with m=\binom{n}{2} edges and no isolated vertices it is the complete graph K_{n} that has the maximum Ramsey number. This conjecture remains open, and is likely very difficult. Motivated by the lack of progress, in the 1980’s Erdős [ 11 ] asked whether the Ramsey number of any such graph G is at least not much larger that the Ramsey number of the complete graph of the same size. In other words, he conjectured that there exists a constant c>0 such that for any graph G with m edges and no isolated vertices we have r(G)\leq 2^{c\sqrt{m}} . This conjecture was proved by Sudakov [ 30 ] in 2011. In this paper, we will study the analogue of the above conjecture for ordered graphs. An ordered graph G on n vertices is a graph whose vertices are labeled with \{1,\dots,n\} . We say that an ordered graph G on [N] contains a an ordered graph H on [n] if there exists a mapping \phi:V(H)\to V(G) such that \phi(i)<\phi(j) for each 1\leq i<j\leq n and (\phi(i),\phi(j))\in E(G) whenever (i,j)\in E(H) . For an ordered graph G we then define its ordered Ramsey number r_{<}(H) as the minimum N such that any 2 -coloring of the complete ordered graph on [N] contains a monochromatic copy of H . The systematic study of ordered Ramsey numbers was initiated by Conlon, Fox, Lee and Sudakov [ 7 ] and, independently, by Balko, Cibulka, Král and Kynčl [ 3 ] . Since then it has attracted a considerable amount of interest (e.g. [ 3 , 27 , 19 , 18 ] ). In general, ordered Ramsey numbers can behave very differently from their non-ordered counterparts. For example, the Burr–Erdős conjecture does not hold for ordered graphs as there exist ordered matchings whose Ramsey number is superpolynomial in their number of vertices [ 7 , 3 ] . In this paper, we initiate the study of the analogue of the conjecture by Erdős for ordered graphs. Question 1.1 . Does there exist a constant c>0 such that for any ordered graph H with m edges and no isolated vertices it holds that r_{<}(H)\leq 2^{c\sqrt{m}} ? We believe the answer to this question should indeed be positive. Our main result is a proof of a slightly weaker bound, which differs from the conjectured truth by an additional (\log\log m)^{3/2} factor in the exponent. Theorem 1.2 . Let H be an ordered graph with m edges and no isolated vertices. Then r_{<}(H)\leq e^{10^{9}\sqrt{m}(\log\log m)^{3/2}}. In fact, we prove a somewhat stronger statement, namely an off-diagonal version of Theorem 1.2 in which we may be searching for two different graphs in the two colors; see Theorem 2.1 for the precise statement. As a consequence of the off-diagonal result, we immediately get a corresponding theorem for directed graphs. For an acyclic directed graph D , its oriented Ramsey number, denoted \mathchoice{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\displaystyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\displaystyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\displaystyle r\hfil$\crcr}}}{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\textstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\textstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\textstyle r\hfil$\crcr}}}{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\scriptstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\scriptstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\scriptstyle r\hfil$\crcr}}}{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\scriptscriptstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\scriptscriptstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\scriptscriptstyle r\hfil$\crcr}}}(D) , is the minimum integer N such that every tournament on N vertices contains a copy of D . Let D^{+} and D^{-} be ordered graphs obtained by taking the underlying graph of D and the vertex ordering to be a topological sort of D and its reverse, respectively. Fox, He and Wigderson [ 17 ] observed that \mathchoice{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\displaystyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\displaystyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\displaystyle r\hfil$\crcr}}}{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\textstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\textstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\textstyle r\hfil$\crcr}}}{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\scriptstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\scriptstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\scriptstyle r\hfil$\crcr}}}{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\scriptscriptstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\scriptscriptstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\scriptscriptstyle r\hfil$\crcr}}}(D)\leq r_{<}(D^{+},D^{-}) . Theorem 2.1 thus implies the following: Corollary 1.3 . Let D be an acyclic directed graph with m edges and no isolated vertices. Then \mathchoice{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\displaystyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\displaystyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\displaystyle r\hfil$\crcr}}}{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\textstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\textstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\textstyle r\hfil$\crcr}}}{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\scriptstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\scriptstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\scriptstyle r\hfil$\crcr}}}{\vbox{\halign{#\cr\kern-0.7pt\cr$\mkern 2.0mu\scriptscriptstyle\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraitd}$}}{{}\hbox{$\textstyle{\montraitd}$}}{{}\hbox{$\scriptstyle{\montraitd}$}}{{}\hbox{$\scriptscriptstyle{\montraitd}$}}}\mkern-1.5mu\leaders{\hbox{$\scriptscriptstyle\mkern 0.0mu\mathrel{\mathchoice{{}\hbox{$\displaystyle{\montraita}$}}{{}\hbox{$\textstyle{\montraita}$}}{{}\hbox{$\scriptstyle{\montraita}$}}{{}\hbox{$\scriptscriptstyle{\montraita}$}}}\mkern 0.0mu$}}{\hfill}\mkern-1.5mu\fldr$\crcr\kern-0.3pt\cr$\hfil\scriptscriptstyle r\hfil$\crcr}}}(D)\leq e^{10^{9}\sqrt{m}(\log\log m)^{3/2}}. The study of oriented Ramsey numbers was initiated by Stearns in 1951 [ 29 ] and since then they have been extensively studied in the literature (e.g. [ 17 , 9 , 10 , 23 , 25 ] ). Recently, Fox, He and Wigderson [ 17 ] showed that, as for the ordered graphs, the Burr–Erdős conjecture is not true in the oriented setting. More precisely, they showed that for any \Delta and any n sufficiently large with respect to \Delta ,

Read the complete text