Document Open Access Logo

Is Ramsey's Theorem omega-automatic?

Author Dietrich Kuske



PDF
Thumbnail PDF

File

LIPIcs.STACS.2010.2483.pdf
  • Filesize: 333 kB
  • 12 pages

Document Identifiers

Author Details

Dietrich Kuske

Cite AsGet BibTex

Dietrich Kuske. Is Ramsey's Theorem omega-automatic?. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 537-548, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/LIPIcs.STACS.2010.2483

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.
Keywords
  • Logic in computer science
  • automata
  • Ramsey theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail