# Ramsey Numbers of Ordered Graphs

@article{Balko2020RamseyNO, title={Ramsey Numbers of Ordered Graphs}, author={Martin Balko and Josef Cibulka and Karel Kr'al and Jan Kyn{\vc}l}, journal={Electronic Journal of Combinatorics}, year={2020}, volume={27} }

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 $N$ such that every ordered complete graph with $N$ vertices and with edges colored by two colors contains a monochromatic copy of $\mathcal{G}$.
In contrast with the case of unordered graphs, we show that there are arbitrarily large ordered matchings $\mathcal{M}_n$ on $n$ vertices for which… Expand

#### Figures and Tables from this paper

#### 7 Citations

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

Ramsey numbers of ordered graphs under graph operations

- Mathematics
- 2019

An ordered graph $\mathcal{G}$ is a simple graph together with a total ordering on its vertices. The (2-color) Ramsey number of $\mathcal{G}$ is the smallest integer $N$ such that every 2-coloring of… Expand

Upper Bounds for 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

Off-Diagonal Ordered Ramsey Numbers of Matchings

- Mathematics, Computer Science
- Electron. J. Comb.
- 2019

It is shown that the off-diagonal ordered Ramsey numbers for matchings in which edges do not cross are nearly linear, and a truly sub-quadratic upper bound for random matchings with interval chromatic number 2 is proved. Expand

Biclique Partitions and Off-diagonal Ordered Ramsey Numbers SPUR Final Paper , Summer 2018

- 2018

We study two separate combinatorial problems. First, we look at the problem of partitioning the edges of the complete graph Kn into the minimum possible number of complete bipartite graphs… Expand

On Ordered Ramsey Numbers of Tripartite 3-Uniform Hypergraphs

- Mathematics
- Trends in Mathematics
- 2021

#### References

SHOWING 1-10 OF 35 REFERENCES

New Lower Bound for Multicolor Ramsey Numbers for Even Cycles

- Computer Science, Mathematics
- Electron. J. Comb.
- 2005

A lower bound is given for $k-$color Ramsey number $R(C_{m), C_{m}, \ldots , C{m})$, where $m \geq 4$ is even and $C{m}$ is the cycle on $m$ vertices. Expand

Ordered Ramsey numbers

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

It is proved that even for matchings there are labelings where the ordered Ramsey number is superpolynomial in the number of vertices and a general upper bound on ordered Ramsey numbers is proved. Expand

On the Geometric Ramsey Number of Outerplanar Graphs

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 2015

This work applies polynomial upper bounds of geometric Ramsey numbers of pathwidth-$$2$$2 outerplanar triangulations in both convex and general cases to prove an upper bound on the Ramsey number of a path with n ordered vertices. Expand

Generalized Ramsey theory for graphs

- Mathematics
- 1972

The classical Ramsey numbers [7] involve the occurrence of monochromatic complete subgraphs in line-colored complete graphs. By removing the completeness requirements and admitting arbitrary… Expand

Generalized Ramsey theory for graphs. II. Small diagonal numbers

- Mathematics
- 1972

Consider a finite nonnull graph G with no loops or multiple edges and no isolated points. Its Ramsey number r(G) is defined as the minimum number p such that every 2-coloring of the lines of the… Expand

Recent developments in graph Ramsey theory

- Mathematics, Computer Science
- Surveys in Combinatorics
- 2015

There has been a great deal of recent progress on the study of Ramsey numbers and their variants, spurred on by the many advances across extremal combinatorics. 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

Ramsey numbers of sparse hypergraphs

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

This work significantly improves on the Ackermann-type upper bound that arises from the regularity proofs, and presents a construction which shows that, at least in certain cases, this bound is not far from best possible. Expand

Ordered Ramsey numbers

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

The ordered Ramsey number ρ(D1,D2,...,Dk) is the least integer n such that every k-arc-colouring of the transitive tournament TTn on n vertices contains a Ci-coloured Di for some i, 1 ≤ i ≤ k. 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