Ordered and partially-ordered variants of Ramsey's theorem

Simple item page
dc.contributor.advisor Derrick P. Stolee
dc.contributor.author Cox, Christopher
dc.contributor.department Mathematics
dc.date 2018-08-11T14:30:22.000
dc.date.accessioned 2020-06-30T02:58:26Z
dc.date.available 2020-06-30T02:58:26Z
dc.date.copyright Thu Jan 01 00:00:00 UTC 2015
dc.date.embargo 2001-01-01
dc.date.issued 2015-01-01
dc.description.abstract <p>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.</p> <p>Due to this added order restriction, the ordered Ramsey numbers can be much larger than the usual graph Ramsey numbers.</p> <p>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.</p> <p>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.</p> <p>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 <em>Boolean Ramsey number</em>, which illustrates the difficulty in this new direction in addition to demonstrating the connections to Turán-type problems in posets.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/etd/14682/
dc.identifier.articleid 5689
dc.identifier.contextkey 8052050
dc.identifier.doi https://doi.org/10.31274/etd-180810-4243
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath etd/14682
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/28867
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/etd/14682/Cox_iastate_0097M_15011.pdf|||Fri Jan 14 20:24:29 UTC 2022
dc.subject.disciplines Mathematics
dc.subject.keywords Mathematics
dc.subject.keywords combinatorics
dc.subject.keywords graph theory
dc.subject.keywords ordered graphs
dc.subject.keywords posets
dc.subject.keywords Ramsey theory
dc.title Ordered and partially-ordered variants of Ramsey's theorem
dc.type article
dc.type.genre thesis
dspace.entity.type Publication
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48
thesis.degree.level thesis
thesis.degree.name Master of Science
File
Original bundle
Now showing 1 - 1 of 1
Name:
Cox_iastate_0097M_15011.pdf
Size:
543.17 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Theses and Dissertations