Here we store the experimental results described in

- M. Balko, J. Cibulka, K. Král, and J. Kynčl.
*Ramsey numbers of ordered graphs*, in preparation (2015) [arXiv].

**Abstract:**
An *ordered graph* is a pair (*G*, <) where *G* is a graph and < is a total ordering of its vertices.
The *ordered Ramsey number* OR(*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 (*G*, <).

In contrast with the case of unordered graphs, we show that there are arbitrarily large ordered matchings *M*_{n} on *n* vertices for which OR(*M*_{n}) is superpolynomial in *n*. This implies that ordered Ramsey numbers of the same graph can grow superpolynomially in the size of the graph in one ordering and remain linear in another ordering.

We also prove that the ordered Ramsey number OR(*G*, <) is polynomial in the number of vertices of *G* if the bandwidth of (*G*, <) is constant or if (*G*, <) is an ordered graph of constant degeneracy and constant interval chromatic number.
The first result gives a positive answer to a question of Conlon, Fox, Lee, and Sudakov.

For a few special classes of ordered paths, stars or matchings, we give asymptotically tight bounds on their ordered Ramsey numbers. For so-called monotone cycles we compute their ordered Ramsey numbers exactly. This result implies exact formulas for geometric Ramsey numbers of cycles introduced by Károlyi, Pach, Tóth, and Valtr.

Further details can be found in the paper.

**Results for alternating paths:**
Let *v*_{1},...,*v*_{n} be the vertices of the path *P*_{n} in the order as they appear along the path.
The *alternating path* (*P*_{n}, <) is an ordered path where *v*_{1} < *v*_{3} < *v*_{5} < ... < *v*_{n} < *v*_{n-1} < *v*_{n-3} < ... < *v*_{2} for *n* odd and *v*_{1} < *v*_{3} < *v*_{5} < ... < *v*_{n-1} < *v*_{n} < *v*_{n-2} < ... < *v*_{2} for *n* even.
In the following table, we include colorings of *K*_{N} that avoid monochromatic copy (*P*_{n}, <) for small values of *n*.

The size *n* of the alternating path |
The size *N* of the coloring |
Coloring |

3 |
3 |
TXT |

4 |
6 |
TXT |

5 |
8 |
TXT |

6 |
11 |
TXT |

7 |
14 |
TXT |

8 |
16 |
TXT |

9 |
19 |
TXT |

10 |
21 |
TXT |

11 |
24 |
TXT |

12 |
27 |
TXT |

13 |
29 |
TXT |

Every coloring of *K*_{N} is stored as the upper triangular {0,1}-matrix with the number of rows and columns equal to *N* - 1.
For 1 <= *i* <= *j* <= *N* - 1, the entry (*i*, *j*) of this matrix represents the color of the edge {*i*, *j+1*} of *K*_{N}.
The red color is represented by 1, the blue color by 0.

The colorings were obtained using the Glucose SAT solver.
For given positive integers *n* and *N*, a simple C++ program 'generatorPath.cpp' produces a SAT formula that is satisfiable if and only if there is a coloring of *K*_{N} with no monochromatic alternating path on *n* vertices.
The output formula is saved in the DIMACS format and it can be used as an input for Glucose.

For *n* <= 8, the program reports unsatisfiability of the generated formula if *N* is larger that the value from the table.
This gives an exact value of OR(*P*_{n}, <) for *n* <= 8.

**Results for ordered 4-cycles:**
Let *v*_{1},..., *v*_{4} be the vertices of the cycle *C*_{4} with edges {*v*_{1}, *v*_{2}}, {*v*_{2}, *v*_{3}}, {*v*_{3}, *v*_{4}}, and {*v*_{1}, *v*_{4}}.
In the following table, we include colorings of *K*_{N} that avoid monochromatic copy of an ordered 4-cycle (*C*_{4}, <).

Orderding of the 4-cycle |
The size *N* of the coloring |
Coloring |

*v*_{1} < *v*_{2} < *v*_{3} < *v*_{4} |
13 |
PDF |

*v*_{1} < *v*_{3} < *v*_{2} < *v*_{4} |
9 |
PDF |

*v*_{1} < *v*_{2} < *v*_{4} < *v*_{3} |
10 |
PDF |

The colorings were obtained using the Glucose SAT solver.
For given positive integers *N* and *T* = 1, 2, 3, a simple C++ program 'generatorCycle.cpp' produces a SAT formula that is satisfiable if and only if there is a coloring of *K*_{N} with no monochromatic 4-cycle of type *T*.
The output formula is saved in the DIMACS format and it can be used as an input for Glucose.

For every type of ordering, the program reports unsatisfiability of the generated formula if *N* is larger that the value from the table.
This gives an exact value of the ordered Ramsey numbers for all of orderings of the 4-cycle.

A compressed directory with all colorings: [ZIP, 7 kB]

Last update: 22.7.2015