Derrick Stolee - Iowa State University - Research Browser

Ordered Ramsey Theory
A 3-uniform hypergraph
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.

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