The shift graph and the Ramsey degree of \([\mathbb N]^\omega\) (Q2453809): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s10474-013-0349-1 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2069420335 / rank | |||
Normal rank |
Revision as of 20:43, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The shift graph and the Ramsey degree of \([\mathbb N]^\omega\) |
scientific article |
Statements
The shift graph and the Ramsey degree of \([\mathbb N]^\omega\) (English)
0 references
10 June 2014
0 references
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\).
0 references
partition relation
0 references
Ramsey degree
0 references
non-meager filter
0 references
shift graph
0 references