Is Ramsey's theorem omega-automatic?
Is Ramsey's theorem omega-automatic?
复制标题
拉姆齐定理是欧米茄自动的吗？
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
D. Kuske
中科院分区：
文献类型：
--
作者：
D. Kuske
研究了-自动（超）图中无穷团的存在性。事实证明，这种情况比一般的不可数图要好得多，但不如自动图好。
We study the existence of infinite cliques in omega-automatic (hyper-)graphs. It turns out that the situation is much nicer than in general uncountable graphs, but not as nice as for automatic graphs.
More specifically, we show that every uncountable omega-automatic graph contains an uncountable co-context-free clique or anticlique, but not necessarily a context-free (let alone regular) clique or anticlique. We also show that uncountable omega-automatic ternary hypergraphs need not have uncountable cliques or anticliques at all.