Partitions of factorisations of parameter words (Q5937586)

For a finite set \(A\), and a set \(\Lambda=\{\lambda_1, \dots, \lambda_k\}\) of parameters disjoint from \(A\), a \(k\)-parameter word \(w\) over \(A\) is formed from the alphabet \(A\cup\Lambda\), and is required to have each of the parameters \(\lambda_i\) appearing at least once \((1\leq i\leq k)\). The parameters are ordered so that the first occurrence of \(\lambda_i\) precedes the first occurrence of \(\lambda_j\) whenever \(i<j\); the set of such words is denoted by \(A{n\choose k}\); \(w\in A{n\choose k}\) is an ascending parameter word if each occurrence of \(\lambda_i\) precedes each occurrence of \(\lambda_j\) when \(i<j\), and the set of such words is denoted by \(A^<{n\choose k}\). For \(w\in A{m\choose k}\) and \(f\in A{n\choose m}\) \(f\circ w\in A{n\choose k}\) is defined to be the word obtained from \(f\) by replacing, for every \(i\leq m\), every occurrence of \(\lambda_i\) in \(f\) by the \(i\)th letter in \(w\). For any word \(w\) over \(A\cup\Lambda\)---not necessarily a \(k\)-parameter word---\(w^\prime\) is the word over \(\Lambda\) alone obtained by suppressing all letters from \(A\); such words over \(\Lambda\) may be written in the form \(\prod_{j=1}^t\lambda_{i_j}^{a_j}\), where \(a_j\geq 1\) and \(i_{j+1}\neq i_j\) \((j=1,\dots,t-1)\) and \(a_t\geq 1\)---no commutativity is assumed. The associated pattern \(\pi(w)\) of \(w\) is defined to be the word \(\prod_{j=1}^t\lambda_{i_j}\). A factorisation of \(w\in A{n\choose k}\) is a sequence \(\overline{w}=(w_1,\dots,w_s)\) of subwords of \(w\) such that \(w=w_1\dots w_s\); the type of \(\overline{w}\) is the sequence \(\tau(w)=(\pi(w_1),(w_{21},\pi(w_2)),\dots,(w_{s1},\pi(w_s)))\), where \(w_{i1}\) is the first letter of the subword \(w_i\), \(i\geq 2\). With any \(f\in A^<{N\choose m}\) and any factorisation \(\overline{w}=(w_1,\dots,w_s)\) of \(w\in A{n\choose k}\) is associated a factorisation \(\overline{f}=(f_1,\dots,f_s)\) of \(f\) where, for \(i\geq 2\), the first letter of \(f_i\) is \(\lambda_{\nu(i)}\), where \(\nu(i)=|w_1|+\dots+|w_{i-1}|+1\), and the parameter \(\lambda_{\nu(i)}\) occurs in no \(f_j\) \((j<i)\); \(f\star\overline{w}\) is defined to be \((f_1\circ w_1,\dots,f_s\circ w_s)\). A variant of a theorem of Graham and Rothschild [\textit{R. L. Graham} and \textit{B. L. Rothschild}, Ramsey's theorem for \(n\)-parameter sets. Trans. Am. Math. Soc. 159, 257-292 (1971; Zbl 0233.05003)] is proved: Theorem C. For \(m,k,r\in\mathbb{N}\) and for any finite alphabet \(A\), there exists a natural number \(N\) that depends primitive recursively on \(m,k,r\) and \(|A|\), such that, for every \(r\)-colouring \(\chi\) of the class of factorisations of words in \(A {n\choose k}\), there exists some \(f\in A^<{N\choose m}\) such that, for all \(u\in A{m\choose k}\) and all factorisations \(\overline{u}\) of \(u\), the colour \(\chi(f\star\overline{u})\) depends on \(\tau(\overline{u})\) only.