A Polychromatic Ramsey Theory for Ordinals

Martin Huschenbett

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 α. Ramsey's theorem states that the Ramsey degree of ω is 1 and it is well known that no other countably infinite ordinal has Ramsey degree 1. We show that the Ramsey degree of every ordinal α < ω^ω exists and provide a formula to compute it from α. 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.

Back