A polychromatic Ramsey theory for ordinals
| aut.relation.endpage | 570 | |
| aut.relation.startpage | 559 | |
| aut.relation.volume | 8087 LNCS | |
| aut.researcher | Liu, Jiamou | |
| dc.contributor.author | Huschenbett, M | |
| dc.contributor.author | Liu, J | |
| dc.contributor.editor | Chatterjee, K | |
| dc.contributor.editor | Jiri, S | |
| dc.date.accessioned | 2014-02-12T20:52:37Z | |
| dc.date.available | 2014-02-12T20:52:37Z | |
| dc.date.copyright | 2013 | |
| dc.date.issued | 2013 | |
| dc.description.abstract | The Ramsey degree of an ordinal α is the least number n such that any colouring of the edges of the complete graph on α using finitely many colours contains an n-chromatic clique of order type α. The Ramsey degree exists for any ordinal α < ω ω . We provide an explicit expression for computing the Ramsey degree given α. We further establish a version of this result for automatic structures. In this version the ordinal and the colouring are presentable by finite automata and the clique is additionally required to be regular. The corresponding automatic Ramsey degree turns out to be greater than the set theoretic Ramsey degree. Finally, we demonstrate that a version for computable structures fails. | |
| dc.identifier.citation | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol.8087 LNCS, pp.559 - 570 | |
| dc.identifier.doi | 10.1007/978-3-642-40313-2_50 | |
| dc.identifier.issn | 0302-9743 | |
| dc.identifier.issn | 1611-3349 | |
| dc.identifier.uri | https://hdl.handle.net/10292/6737 | |
| dc.language | English | |
| dc.publisher | Springer Berlin Heidelberg | |
| dc.relation.uri | http://dx.doi.org/10.1007/978-3-642-40313-2_50 | |
| dc.rights | An author may self-archive an author-created version of his/her article on his/her own website and or in his/her institutional repository. He/she may also deposit this version on his/her funder’s or funder’s designated repository at the funder’s request or as a result of a legal obligation, provided it is not made publicly available until 12 months after official publication. He/ she may not use the publisher's PDF version, which is posted on www.springerlink.com, for the purpose of self-archiving or deposit. Furthermore, the author may only post his/her version provided acknowledgement is given to the original source of publication and a link is inserted to the published article on Springer's website. The link must be accompanied by the following text: "The final publication is available at www.springerlink.com”. (Please also see Publisher’s Version and Citation). | |
| dc.rights.accessrights | OpenAccess | |
| dc.title | A polychromatic Ramsey theory for ordinals | |
| dc.type | Journal Article | |
| pubs.elements-id | 157155 | |
| pubs.organisational-data | /AUT | |
| pubs.organisational-data | /AUT/Design & Creative Technologies | |
| pubs.organisational-data | /AUT/Design & Creative Technologies/School of Computing & Mathematical Science |