Back to Search
Start Over
A Ramsey characterisation of eventually periodic words.
- Source :
-
Bulletin of the London Mathematical Society . Dec2022, Vol. 54 Issue 6, p2437-2455. 19p. - Publication Year :
- 2022
-
Abstract
- A factorisation x=u1u2⋯$x = u_1 u_2 \cdots$ of an infinite word x$x$ on alphabet X$X$ is called 'monochromatic', for a given colouring of the finite words X∗$X^*$ on alphabet X$X$, if each ui$u_i$ is the same colour. Wojcik and Zamboni proved that the word x$x$ is periodic if and only if for every finite colouring of X∗$X^*$ there is a monochromatic factorisation of x$x$. On the other hand, it follows from Ramsey's theorem that, for any word x$x$, for every finite colouring of X∗$X^*$ there is a suffix of x$x$ having a monochromatic factorisation. A factorisation x=u1u2⋯$x = u_1 u_2 \cdots$ is called 'super‐monochromatic' if each word uk1uk2⋯ukn$u_{k_1} u_{k_2} \cdots u_{k_n}$, where k1<⋯<kn$k_1 < \cdots < k_n$, is the same colour. Our aim in this paper is to show that a word x$x$ is eventually periodic if and only if for every finite colouring of X∗$X^*$ there is a suffix of x$x$ having a super‐monochromatic factorisation. Our main tool is a Ramsey result about alternating sums that may be of independent interest. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00246093
- Volume :
- 54
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- Bulletin of the London Mathematical Society
- Publication Type :
- Academic Journal
- Accession number :
- 160783960
- Full Text :
- https://doi.org/10.1112/blms.12704