The shift graph and the Ramsey degree of [ N]^

Let \(\mathcal{K}_{\mathbb{N}}\) denote the class of all structures that are isomorphic to the set of non-negative integers with the usual ordering. The authors study the strength of stating that \(\mathcal{K}_{\mathbb{N}}\) has finite Ramsey degree in the absence of the axiom of choice. Kleinberg has shown that \(\omega \rightarrow [\omega]^{\omega}_{\omega}\) implies \(\omega \rightarrow [\omega]^{\omega}_l\) for some \(l\in \omega\), \(l \geq 2\). That means that \(\omega \rightarrow [\omega]^{\omega}_{\omega}\) implies that \(\mathcal{K}_{\mathbb{N}}\) admits a finite Ramsey degree. It is not known that \(\omega \rightarrow[\omega]^{\omega}_{\omega}\) implies that the least such \(l\) is 2. If this least \(l\) is 2, then \(\omega \rightarrow[\omega]^{\omega}_{\omega}\) implies that \(\mathcal{K}_{\mathbb{N}}\) is a Ramsey class. The shift graph is the graph on \([\mathbb{N}]^{\omega}\) where \(X\) and \(Y\) form an edge if \(X=S(Y)\) or \(Y=S(X)\), where \(S(A) = A \setminus\{\min A\}\). The authors show that if the shift graph has finite chromatic number then \(\mathcal{K}_{\mathbb{N}}\) has infinite Ramsey degree. In their proofs, they use the Rudin-Blass relation between filters on \(\omega\).

Recommendations

Cites work

Cited in

(4)

This page was built for publication: The shift graph and the Ramsey degree of \([\mathbb N]^\omega\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2453809)