Partitioning Subwords of Long Words
Let W be a partition of \(\omega =\{1,2,3,...\}\) into r classes. Schur (1916) proved that there is an infinite subset of one class which contains all sums of any two integers in it! This was extended by Rado (1933) and others (Sanders and Folkman) to: For any W and any positive integer n there is an infinite subset of one class which contains all sums of n or fewer distinct integers in the subset!! Erdős conjectured (a long time ago) and \textit{N. Hindman} [J. Comb. Theory, Ser. A 17,1-11 (1974; Zbl 0285.05012)] proved that for any W there is an infinite subset of one class which contains all finite sums of distinct integers in it!!! In the paper under review the author proves a related result. First we need some definitions. Let A be a finite alphabet and W: \(\omega\to A\) a word over A of length \(\omega\). The word W' is a subword of W if and only if there exists \(i_ 0<i_ 1<i_ 2<..\). such that \(W'(k)=W(i_ k)\) for all \(k<length(W')\). Sub(W) denotes the set of all subwords of W. A word W over A with parameter \(\lambda\) is a word over the alphabet \(A\cup \{\lambda \}\) in which \(\lambda\) occurs, and then W(a), \(a\in A\), denotes the word obtained by replacing all occurrences of \(\lambda\) by a. Main Theorem. Let A be a finite alphabet and k, \(\delta<\omega\). Every word W: \(\omega\to A\) which contains each letter infinitely often has the following property: For every mapping \(\Delta\) : Sub(W)\(\to \delta\) there exist k words with parameters \(W_ 0(\lambda_ 0),...,W_{k- 1}(\lambda_{k-1})\) such that \(\Delta\) is constant on the set \(\{W_{i_ 0}(a_{i_ 0})\times...\times W_{i_{j-1}}(a_{i_{j- 1}})| 0\leq i_ 0<...<i_{j-1}<k,\quad 0<j\leq k,\quad a_{i_ 0},...,a_{i_{j-1}}\in A\}.\) For the entire collection see [Zbl 0513.00004].
- Density versions of two generalizations of Schur's theorem
- Defining long words succinctly in FO and MSO
- Partition theorems for left and right variable words
- Characterization of a word by its subwords
- ON PARTITIONS SEPARATING WORDS
- scientific article; zbMATH DE number 4168694 (Why is no real title available?)
- On additive properties of sets defined by the Thue-Morse word
- Partitions of factorisations of parameter words
This page was built for publication: Partitioning Subwords of Long Words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3315512)