Is Ramsey's theorem omega-automatic?
classification
💻 cs.LO
cs.DMcs.FL
keywords
uncountableomega-automaticgraphsanticliquecliquecliquesaloneanticliques
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.