Ordered and partially-ordered variants of Ramsey's theorem

Cox, Christopher
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Organizational Unit
Journal Issue

For a k-uniform hypergraph G with vertex set {1,...,n}, the ordered Ramsey number OR^k_t(G) is the least integer N such that every t-coloring of the edges of the complete k-uniform graph on vertex set {1,...,N} contains a monochromatic copy of G whose vertices follow the prescribed order.

Due to this added order restriction, the ordered Ramsey numbers can be much larger than the usual graph Ramsey numbers.

We determine that the ordered Ramsey numbers of loose paths under a monotone order grows as a tower of height two less than the maximum degree in terms of the number of edges and as a tower of height one less than the maximum degree in terms of the number of colors.

We also extend theorems of Conlon, Fox, Lee, and Sudakov on the ordered Ramsey numbers of 2-uniform matchings to provide upper bounds on the ordered Ramsey number of k-uniform matchings under certain orderings.

Beyond this, we introduce an extension of the ordered Ramsey number to consider graphs with only a partial ordering on their vertices. This extension also allows us to consider analogues of the Ramsey number where the host graph is constructed from an arbitrary poset. In particular, we focus on what we refer to as the Boolean Ramsey number, which illustrates the difficulty in this new direction in addition to demonstrating the connections to Turán-type problems in posets.

Mathematics, combinatorics, graph theory, ordered graphs, posets, Ramsey theory