IS RAMSEY'S THEOREM ω- AUTOMATIC?
Dietrich Kuske · 2010
Abstract. We study the existence of infinite cliques in ω-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 ω-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 ω-automatic ternary hypergraphs need not have uncountable cliques or anticliques at all.