Derrick Stolee - Iowa State University - Research Browser

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
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
C. Cox, D. Stolee, Ramsey numbers for partially-ordered sets.
Web Version
Data
Ramsey numbers for partially-ordered sets

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

Derrick Stolee - Iowa State University - Research Browser