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

https://hal.inria.fr/inria-00457041
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

File

kuske.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00457041, version 1

Citation

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⟩

Share

Metrics

Record views

170

Files downloads

191