when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2010.2483
URN: urn:nbn:de:0030-drops-24838
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2483/

Kuske, Dietrich

### Is Ramsey's Theorem omega-automatic?

 pdf-format:

### 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.

### BibTeX - Entry

@InProceedings{kuske:LIPIcs:2010:2483,
author =	{Dietrich Kuske},
title =	{{Is Ramsey's Theorem omega-automaticl}},
booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
pages =	{537--548},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-16-3},
ISSN =	{1868-8969},
year =	{2010},
volume =	{5},
editor =	{Jean-Yves Marion and Thomas Schwentick},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},