Ordered and partially-ordered variants of Ramsey's theorem

Thumbnail Image
Date
2015-01-01
Authors
Cox, Christopher
Major Professor
Advisor
Derrick P. Stolee
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Abstract

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.

Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
thesis
Comments
Rights Statement
Copyright
Thu Jan 01 00:00:00 UTC 2015
Funding
Subject Categories
Supplemental Resources
Source