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 metadatas

Cited literature [4 references]  Display  Hide  Download
Contributor : Publications Loria <>
Submitted on : Tuesday, February 16, 2010 - 2:51:06 PM
Last modification on : Thursday, January 11, 2018 - 6:20:16 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