Skip to Main content Skip to Navigation
Conference papers

Is Ramsey's theorem omega-automatic?

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.
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, February 16, 2010 - 2:51:06 PM
Last modification on : Saturday, June 25, 2022 - 10:31:59 AM
Long-term archiving on: : Friday, June 18, 2010 - 6:46:46 PM


Files produced by the author(s)


  • HAL Id : inria-00457041, version 1



Dietrich Kuske. Is Ramsey's theorem omega-automatic?. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.537-548. ⟨inria-00457041⟩



Record views


Files downloads