Name
Abstract | ||
|---|---|---|
The Ramsey degree of an ordinal a is the least number n such that any colouring of the edges of the complete graph on a using finitely many colours contains an n-chromatic clique of order type a. The Ramsey degree exists for any ordinal alpha < omega(omega) We provide an explicit expression for computing the Ramsey degree given a. 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-40313-2_50 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Ramsey theory,Complete graph,Discrete mathematics,Combinatorics,Clique,Ordinal number,Computer science,Finite-state machine,Order type,Regular language | Conference | 8087 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
8 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Huschenbett | 1 | 10 | 3.11 |
| Jiamou Liu | 2 | 49 | 23.19 |