Big Ramsey Degrees of Countable Ordinals

Fuente: arXiv
Saved in:
Bibliographic Details
Main Authors: Boyland, Joanna, Gasarch, William, Hurtig, Nathan, Rust, Robert
Format: Preprint
Published: 2023
Subjects:
Online Access:
Tags: Add Tag
No Tags, Be the first to tag this record!
_version_ 1866912696451989504
author Boyland, Joanna
Gasarch, William
Hurtig, Nathan
Rust, Robert
author_facet Boyland, Joanna
Gasarch, William
Hurtig, Nathan
Rust, Robert
contents Ramsey's theorem states that for all finite colorings of an infinite set, there exists an infinite homogeneous subset. What if we seek a homogeneous subset that is also order-equivalent to the original set? Let $S$ be a linearly ordered set and $a \in N$. The big Ramsey degree of $a$ in $S$, denoted $T(a,S)$, is the least integer $t$ such that, for any finite coloring of the $a$-subsets of $S$, there exists $S'\subseteq S$ such that (i) $S'$ is order-equivalent to $S$, and (ii) if the coloring is restricted to the $a$-subsets of $S'$ then at most $t$ colors are used. Mašulović \& Šobot (2019) showed that $T(a,ω+ω)=2^a$. From this one can obtain $T(a,ζ)=2^a$. We give a direct proof that $T(a,ζ)=2^a$. Mašulović and Šobot (2019) also showed that for all countable ordinals $α< ω^ω$, and for all $a \in N$, $T(a,α)$ is finite. We find exact value of $T(a,α)$ for all ordinals less than $ω^ω$ and all $a\in N$.
format Preprint
id arxiv_https___arxiv_org_abs_2305_07192
institution arXiv
publishDate 2023
record_format arxiv
spellingShingle Big Ramsey Degrees of Countable Ordinals
Boyland, Joanna
Gasarch, William
Hurtig, Nathan
Rust, Robert
Combinatorics
05D10
Ramsey's theorem states that for all finite colorings of an infinite set, there exists an infinite homogeneous subset. What if we seek a homogeneous subset that is also order-equivalent to the original set? Let $S$ be a linearly ordered set and $a \in N$. The big Ramsey degree of $a$ in $S$, denoted $T(a,S)$, is the least integer $t$ such that, for any finite coloring of the $a$-subsets of $S$, there exists $S'\subseteq S$ such that (i) $S'$ is order-equivalent to $S$, and (ii) if the coloring is restricted to the $a$-subsets of $S'$ then at most $t$ colors are used. Mašulović \& Šobot (2019) showed that $T(a,ω+ω)=2^a$. From this one can obtain $T(a,ζ)=2^a$. We give a direct proof that $T(a,ζ)=2^a$. Mašulović and Šobot (2019) also showed that for all countable ordinals $α< ω^ω$, and for all $a \in N$, $T(a,α)$ is finite. We find exact value of $T(a,α)$ for all ordinals less than $ω^ω$ and all $a\in N$.
title Big Ramsey Degrees of Countable Ordinals
topic Combinatorics
05D10
url https://arxiv.org/abs/2305.07192