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.
Document type :
Conference papers
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.537-548, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées


https://hal.inria.fr/inria-00457041
Contributor : Publications Loria <>
Submitted on : Tuesday, February 16, 2010 - 2:51:06 PM
Last modification on : Tuesday, February 16, 2010 - 3:29:18 PM
Document(s) archivé(s) le : Friday, June 18, 2010 - 6:46:46 PM

File

kuske.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00457041, version 1

Collections

Citation

Dietrich Kuske. Is Ramsey's theorem omega-automatic?. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.537-548, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. <inria-00457041>

Share

Metrics

Record views

131

Document downloads

107