Ramsey numbers of ordered graphs
Here we store the experimental results described in
Abstract:
- M. Balko, J. Cibulka, K. Král, and J. Kynčl. Ramsey numbers of ordered graphs, in preparation (2015) [arXiv].
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 Mn on n vertices for which OR(Mn) 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 v1,...,vn be the vertices of the path Pn in the order as they appear along the path. The alternating path (Pn, <) is an ordered path where v1 < v3 < v5 < ... < vn < vn-1 < vn-3 < ... < v2 for n odd and v1 < v3 < v5 < ... < vn-1 < vn < vn-2 < ... < v2 for n even. In the following table, we include colorings of KN that avoid monochromatic copy (Pn, <) 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 KN 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 KN. 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 KN 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(Pn, <) for n <= 8.
Results for ordered 4-cycles:Let v1,..., v4 be the vertices of the cycle C4 with edges {v1, v2}, {v2, v3}, {v3, v4}, and {v1, v4}. In the following table, we include colorings of KN that avoid monochromatic copy of an ordered 4-cycle (C4, <).
Orderding of the 4-cycle The size N of the coloring Coloring v1 < v2 < v3 < v4 13 v1 < v3 < v2 < v4 9 v1 < v2 < v4 < v3 10 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 KN 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