# Ordered Ramsey numbers

@article{Conlon2017OrderedRN, title={Ordered Ramsey numbers}, author={David Conlon and Jacob Fox and Choongbum Lee and Benny Sudakov}, journal={J. Comb. Theory, Ser. B}, year={2017}, volume={122}, pages={353-383} }

Abstract Given a labeled graph H with vertex set { 1 , 2 , … , n } , the ordered Ramsey number r ( H ) is the minimum N such that every two-coloring of the edges of the complete graph on { 1 , 2 , … , N } contains a copy of H with vertices appearing in the same order as in H . The ordered Ramsey number of a labeled graph H is at least the Ramsey number r ( H ) and the two coincide for complete graphs. However, we prove that even for matchings there are labelings where the ordered Ramsey number… Expand

#### Topics from this paper

#### 27 Citations

Some Ordered Ramsey Numbers of Graphs on Four Vertices.

- Mathematics
- 2018

An ordered graph $H$ on $n$ vertices is a graph whose vertices have been labeled bijectively with $\{1,...,n\}$. The ordered Ramsey number $r_<(H)$ is the minimum $n$ such that every two-coloring of… Expand

Minimal Ordered Ramsey Graphs

- Mathematics, Computer Science
- Discret. Math.
- 2020

It is proved that each Ramsey finite (not necessarily connected) ordered graph H has a pseudoforest as a Ramsey graph and therefore is a star forest with strong restrictions on the positions of the centers of the stars. Expand

Ramsey Numbers of Interval 2-Chromatic Ordered Graphs

- Computer Science, Mathematics
- Graphs Comb.
- 2019

The lower bounds linear in the number of vertices for the Ramsey numbers of certain classes of 2-ichromatic ordered graphs are obtained and a linear upper bound is proved for a class of 2.ichromatics ordered graphs. Expand

Chromatic Number of Ordered Graphs with Forbidden Ordered Subgraphs

- Mathematics, Computer Science
- Comb.
- 2018

It is proved that f≺(H) ≠∞ if and only if H is acyclic and does not contain a copy of any of the five special ordered forests on four or five vertices, which the authors call bonnets. Expand

On edge-ordered Ramsey numbers

- Computer Science, Mathematics
- Random Struct. Algorithms
- 2020

It is proved that for every edge-ordered graph $H$ on $n$ vertices, the authors have $r_{edge}(H;q) \leq 2^{c^qn^{2q-2}\log^q n}$, where $c$ is an absolute constant. Expand

Ramsey Numbers of Ordered Graphs

- Mathematics
- 2020

An ordered graph is a pair $\mathcal{G}=(G,\prec)$ where $G$ is a graph and $\prec$ is a total ordering of its vertices. The ordered Ramsey number $\overline{R}(\mathcal{G})$ is the minimum number… Expand

Edge-ordered Ramsey numbers

- Computer Science, Mathematics
- Eur. J. Comb.
- 2020

A natural class of edge-orderings, called lexicographic edge- orderings, is introduced, for which the authors can prove much better upper bounds on the corresponding edge-ordered Ramsey numbers. Expand

Tilings in vertex ordered graphs.

- Mathematics
- 2020

Over recent years there has been much interest in both Tur\'an and Ramsey properties of vertex ordered graphs. In this paper we initiate the study of embedding spanning structures into vertex ordered… Expand

Ramsey Numbers for Partially-Ordered Sets

- Mathematics, Computer Science
- Order
- 2018

A refinement of Ramsey numbers is presented by considering graphs with a partial ordering on their vertices, a natural extension of the ordered Ramsey numbers, and connections to well studied Turán-type problems in partially-ordered sets, particularly those in the Boolean lattice are explored. Expand

On-line size Ramsey number for monotone k-uniform ordered paths with uniform looseness

- Mathematics, Computer Science
- Eur. J. Comb.
- 2021

The upper bounds improve prior results when $t$ grows faster than $m/\log m$ and generalize the results to $\ell$-loose monotone paths, where each successive edge begins $ell$ vertices after the previous edge. Expand

#### References

SHOWING 1-10 OF 45 REFERENCES

On Ramsey Numbers of Sparse Graphs

- Computer Science, Mathematics
- Combinatorics, Probability and Computing
- 2003

It is shown that, for every , sufficiently large n, and any graph H of order , either H or its complement contains a (d,n)-common graph, that is, a graph in which every set of d vertices has at least n common neighbours. Expand

Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions

- Computer Science, Mathematics
- Combinatorics, Probability and Computing
- 2003

It is proved that, for any fixed bipartite graph H in which all degrees in one colour class are at most r, the Turán number is the maximum possible number of edges in a simple graph on n vertices that contains no copy of H. Expand

The Ramsey number of dense graphs

- Mathematics
- 2013

The Ramsey number r(H) of a graph H is the smallest number n such that, in any two-colouring of the edges of K_n, there is a monochromatic copy of H. We study the Ramsey number of graphs H with t… Expand

On graphs with linear Ramsey numbers

- Computer Science
- J. Graph Theory
- 2000

In this paper, the use of the regularity lemma is avoided altogether, and it is shown that one can in fact take, for some ®xed c, c
< 2 (log )2 in the general case, and even even 1. Expand

On two problems in graph Ramsey theory

- Mathematics, Computer Science
- Comb.
- 2012

This work improves the upper bound on the existence of a constant c such that, for any graph H on n vertices, rind(H) ≤ 2cnlogn, and moves a step closer to proving this conjecture. Expand

Two remarks on the Burr-Erdos conjecture

- Computer Science, Mathematics
- Eur. J. Comb.
- 2009

It is shown that for such graphs r(H)@?2^c^"^d^l^o^g^nn, improving on an earlier bound of Kostochka and Sudakov, the Ramsey number of random graphs G(n,d/n) has Ramsey number linear in n. Expand

The Ramsey number of a graph with bounded maximum degree

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 1983

Abstract The Ramsey number of a graph G is the least number t for which it is true that whenever the edges of the complete graph on t vertices are colored in an arbitrary fashion using two colors,… Expand

ON THE MAGNITUDE OF GENERALIZED RAMSEY NUMBERS FOR GRAPHS

- 1973

If G and H are graphs (which will mean finite, with no loops or parallel lines), define the Ramsey number r(G, H) to be the least number p such that if the lines of the complete graph Kp are colored… Expand

Ordered Ramsey theory and track representations of graphs

- Mathematics
- 2015

We introduce an ordered version of Ramsey numbers for hypergraphs using linearly ordered vertex sets. In this model, we obtain bounds on the ordered Ramsey numbers of the k-uniform hypergraph whose… Expand

Induced Ramsey Numbers

- Mathematics, Computer Science
- Comb.
- 1998

The induced Ramsey number of pairs of graphs (G, H) is investigated to be the smallest possible order of a graph Γ with the property that, whenever its edges are coloured red and blue, either a red induced copy of G arises or else a blue induced copies of H arises. Expand