A Ramsey characterisation of eventually periodic words
A Ramsey characterisation of eventually periodic words
复制标题
最终周期词的拉姆齐表征
DOI：
10.1112/blms.12704
复制
发表时间：
2022
影响因子：
0.9
通讯作者：
Ivan M
中科院分区：
文献类型：
--
作者：
Ivan M
对于字母表X$X$上的有限字X$X^*$的给定着色，如果每个ui$u_i$是相同的颜色，则字母表X $X$上的无限字x$x$的因式分解x= u1 u2 <$$x = u_1 u_2 \cdots$被称为“单色”。Wojcik和Zamboni证明了词x$x$是周期性的当且仅当对于X的每一个有限着色都有x$x$的单色因式分解。另一方面，从拉姆齐定理可以得出，对于任意词x x，对于X的每一个有限着色，都有x x的后缀具有单色因子分解。如果每个单词uk 1uk 2 ukn$u_{k_1} u_{k_2} \cdots u_{k_n}$，其中k1<kn <kn$k_1 < \cdots <k_n$，是相同的颜色，则因子分解x= u1 u2 x = u_1 u_2 \cdots$被称为“超单色”。本文的目的是证明一个词x$x$最终是周期的，当且仅当对于X <$$X^*$的每一个有限着色，x$x$的后缀都有一个超单色因子分解。我们的主要工具是一个拉姆齐结果交替和可能是独立的利益。
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, foranyword 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.
登录
查看更多内容
无限单词的着色问题
DOI：
--
发表时间：
2013
期刊：
Journal of Combinatorial Theory
影响因子：
--
作者：
A. Luca;Elena V. Pribavkina;L. Zamboni
通讯作者：
L. Zamboni
关于无限字着色问题的一些变体
DOI：
--
发表时间：
2015
期刊：
Journal of Combinatorial Theory
影响因子：
--
作者：
A. Luca;L. Zamboni
通讯作者：
L. Zamboni
无限划分正则矩阵
DOI：
--
发表时间：
1995
期刊：
Comb.
影响因子：
--
作者：
W. Deuber;N. Hindman;I. Leader;H. Lefmann
通讯作者：
H. Lefmann
欧几里德拉姆齐理论中的传递集
DOI：
--
发表时间：
2010
期刊：
Journal of Combinatorial Theory
影响因子：
--
作者：
I. Leader;Paul A. Russell;M. Walters
通讯作者：
M. Walters
关于超单色因式分解和极限周期性的新猜想
DOI：
--
发表时间：
2018
期刊：
影响因子：
--
作者：
Caius Wojcik
通讯作者：
Caius Wojcik