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
Authors
Research Projects
Organizational Units
Organizational Unit
Mathematics
Welcome to the exciting world of mathematics at Iowa State University. From cracking codes to modeling the spread of diseases, our program offers something for everyone. With a wide range of courses and research opportunities, you will have the chance to delve deep into the world of mathematics and discover your own unique talents and interests. Whether you dream of working for a top tech company, teaching at a prestigious university, or pursuing cutting-edge research, join us and discover the limitless potential of mathematics at Iowa State University!
Journal Issue
Is Version Of
Versions
Series
Department
Mathematics
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.

Comments
Description
Keywords
Citation
Source
Subject Categories
Copyright
Thu Jan 01 00:00:00 UTC 2015