Ordered Ramsey numbers of loose paths and matchings

详细信息    查看全文

• 作者：Christopher Cox ^{cocox@iastate.edu" class="auth_mail" title="E-mail the corresponding author} ; Derrick Stolee ; ^{dstolee@iastate.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：05C55 ; Ordered Ramsey numbers ; Hypergraph Ramsey theory ; Loose paths ; Matchings
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：499-505
• 全文大小：399 K

文摘

For a k$k$-uniform hypergraph G$G$ with vertex set {1,…,n}$\{1,\dots ,n\}$, the ordered Ramsey number OR_t(G)${OR}_t\left(G\right)$ is the least integer N$N$ such that every t$t$-coloring of the edges of the complete k$k$-uniform graph on vertex set {1,…,N}$\{1,\dots ,N\}$ contains a monochromatic copy of G$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. We also extend theorems of Conlon et al. (2015) on the ordered Ramsey numbers of 2-uniform matchings to provide upper bounds on the ordered Ramsey number of k$k$-uniform matchings under certain orderings.