Ramsey Numbers for Partially-Ordered Sets |
| |
Authors: | Christopher Cox Derrick Stolee |
| |
Affiliation: | 1.Carnegie Mellon University,Pittsburgh,USA;2.Microsoft,Raleigh,USA |
| |
Abstract: | We present a refinement of Ramsey numbers by considering graphs with a partial ordering on their vertices. This is a natural extension of the ordered Ramsey numbers. We formalize situations in which we can use arbitrary families of partially-ordered sets to form host graphs for Ramsey problems. We explore connections to well studied Turán-type problems in partially-ordered sets, particularly those in the Boolean lattice. We find a strong difference between Ramsey numbers on the Boolean lattice and ordered Ramsey numbers when the partial ordering on the graphs have large antichains. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|