Partitioning Subwords of Long Words (Q3315512)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3845584
Language Label Description Also known as
default for all languages
No label defined
    English
    Partitioning Subwords of Long Words
    scientific article; zbMATH DE number 3845584

      Statements

      Partitioning Subwords of Long Words (English)
      0 references
      1983
      0 references
      infinite subset
      0 references
      finite alphabet
      0 references
      set of all subwords
      0 references
      0 references
      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].
      0 references

      Identifiers