pith. sign in

arxiv: 0912.2625 · v2 · submitted 2009-12-14 · 💻 cs.LO · cs.DM· cs.FL

Is Ramsey's theorem omega-automatic?

classification 💻 cs.LO cs.DMcs.FL
keywords uncountableomega-automaticgraphsanticliquecliquecliquesaloneanticliques
0
0 comments X
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.