Ordered Ramsey Theory

Problem and Results Summary

Consider $k$-uniform hypergraphs $H_1,\dots,H_t$ subject to a total ordering of their vertices.
The **ordered Ramsey number** $\operatorname{OR}(H_1,\dots,H_t)$ is the minimum integer $N$ such that every $t$-coloring of the edges of $K_N^k$ contains an $i$-colored copy of $H_i$ as an ordered subgraph for some $i \in [t]$.
When $H = H_1 = \cdots = H_t$, then we denote $\operatorname{OR}_t(H) = \operatorname{OR}(H_1,\dots,H_t)$.

Milans, Stolee, and West compute bounds on ordered Ramsey numbers of $k$-uniform ordered paths, finding that they are bounded by towers of height $k-1$.
We use these bounds to prove asymptotic bounds on the growth of the **track number** of the graph $L(K_n)$.

Cox and Stolee (*Discrete Math.*, 2016) determine the ordered Ramsey number of loose paths in terms of ordered Ramsey numbers of tight paths.
A $(k,\ell)$-path on $e$ edges, denoted $P_e^{k,\ell}$, is given by $e$ $k$-sets $A_1, \dots, A_e$ where consecutive edges intersect in $\ell$ vertices in the natural way.
Then the ordered Ramsey number $\operatorname{OR}_t(P_e^{k,\ell})$ is equal to $(k-\ell)\operatorname{OR}_t(P_e^{i,i-1}) + c_{k,\ell}$ where $c_{k,\ell}$ is a constant depending only on $k$ and $\ell$ (not $t$ or $e$) and $i$ is the maximum degree of $P_k^{k,\ell}$.
Further, they extend results of Conlon, Fox, Lee, and Sudakov on arbitrarily-ordered matchings to $k$-uniform matchings and $t$ colors.

Cox and Stolee (submitted) investigate Ramsey numbers of partially-ordered graphs. This notion considers coloring the $k$-chains of a poset trying to avoid monochromatic ordered copies of a partially-ordered $k$-uniform hypergraph. The focus is on 1-uniform and 2-uniform Boolean Ramsey numbers, where either the elements or the edges of the Boolean lattice are colored while avoiding certain small posets. In particular, they prove that the 2-color 2-uniform Boolean Ramsey number of a diamond is 5 using computational methods. In general, the 2-color 2-uniform Boolean Ramsey number of an $r$-diamond is logarithmic in $r$.

Research Papers

K. G. Milans, D. Stolee, D. B. West, Ordered Ramsey Theory and Track Representations of Graphs, *Journal of Combinatorics* 6(4) (2015) 445-456.

Web Version Official Version

Web Version Official Version

C. Cox, D. Stolee, Ordered Ramsey numbers of loose paths and matchings, *Discrete Mathematics* 339(2) (2016) 499-505.

Web Version arXiv Version Official Version

Web Version arXiv Version Official Version

Data

The following includes a Sage worksheet that generates SMT2 files that can be run using Z3.

- bramsey-smt2.sws is a Sage worksheet that generates SMT2 files for the satisfiability problem concerning 2-color Boolean Ramsey numbers.
- br1-sat-files.zip contains SMT2 files for 1-uniform Boolean Ramsey numbers.
- br2-sat-files.zip contains SMT2 files for 2-uniform Boolean Ramsey numbers.
**Warning: Large!**This 125MB .zip file unpacks to multiple GB.

Related Work

M. Balko, J. Cibulka, K. Král, J. Kynčl. Ramsey numbers of ordered graphs, preprint available as arXiv:1310.7208v3.

D. Conlon, J. Fox, C. Lee, and B. Sudakov. Ordered Ramsey numbers, preprint available as arXiv:1410.5292.

J. Fox, J. Pach, B. Sudakov, and A. Suk, Erdős-Szekeres-type theorems for monotone paths and convex bodies, *Proc. London Math. Society* **105** (2012) 953-982.

D. Grósz, A. Methuku, and C. Tompkins. An improvement of the general bound on the largest family of subsets avoiding a subposet, arXiv:1408.5783 [math.CO].

G. Moshkovitz and A. Shapira, Ramsey Theory, Integer Partitions and a New Proof of the Erdős-Szekeres Theorem, arXiv:1206.4001 [math.CO].

Presentations

Ordered Ramsey Theory and Track Representations of Graphs, presented at *AMS Northeast Section Meeting*, Rochester, NY September 22, 2012.

Slides

Slides