A Ramsey Characterisation of Eventually Periodic Words
Authors:
- Maria-Romina IvanMIMaria-Romina Ivan
- Imre LeaderILImre Leader
- Luca Q. ZamboniLZLuca Q. Zamboni
Preprint
Abstract
A factorisation $x = u_1 u_2 \cdots$ of an infinite word $x$ on alphabet $X$ is called `monochromatic', for a given colouring of the finite words $X^*$ on alphabet $X$, if each $u_i$ is the same colour. Wojcik and Zamboni proved that the word $x$ is periodic if and only if for every finite colouring of $X^*$ there is a monochromatic factorisation of $x$. On the other hand, it follows from Ramsey's theorem that, for \textit{any} word $x$, for every finite colouring of $X^*$ there is a suffix of $x$ having a monochromatic factorisation. A factorisation $x = u_1 u_2 \cdots$ is called `super-monochromatic' if each word $u_{k_1} u_{k_2} \cdots u_{k_n}$, where $k_1 < \cdots < k_n$, is the same colour. Our aim in this paper is to show that a word $x$ is eventually periodic if and only if for every finite colouring of $X^*$ there is a suffix of $x$ having a super-monochromatic factorisation. Our main tool is a Ramsey result about alternating sums that may be of independent interest.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- On some variations of coloring problems of infinite wordsJournal of Combinatorial Theory, Series A, 2016
- Extensions of Infinite Partition Regular SystemsThe Electronic Journal of Combinatorics, 2015
- Transitive sets in Euclidean Ramsey theoryJournal of Combinatorial Theory, Series A, 2012
- Infinite partition regular matricesCombinatorica, 1995
- A canonical partition relation for finite subsets of ωJournal of Combinatorial Theory, Series A, 1976
- Ramsey's theorem with sums or unionsJournal of Combinatorial Theory, Series A, 1975
- Finite sums from sequences within cells of a partition of NJournal of Combinatorial Theory, Series A, 1974