Is Ramsey's theorem omega-automatic? - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2010

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.
Fichier principal
Vignette du fichier
kuske.pdf (225.33 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00457041 , version 1 (16-02-2010)

Identifiers

  • HAL Id : inria-00457041 , version 1

Cite

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⟩
77 View
172 Download

Share

Gmail Facebook X LinkedIn More