On a generalization of Thue sequences (Q2346472)

Summary: A sequence is \textit{Thue} or \textit{nonrepetitive} if it does not contain a repetition of any length. We consider a generalization of this notion. A \(j\)-subsequence of a sequence \(S\) is a subsequence in which two consecutive terms are at indices of difference \(j\) in \(S\). A \(k\)-\textit{Thue sequence} is a sequence in which every \(j\)-subsequence, for \(1\leq j \leq k\), is also Thue. It was conjectured that \(k+2\) symbols are enough to construct an arbitrarily long \(k\)-Thue sequence and shown that the conjecture holds for \(k \in \{2,3,5\}\). In this paper we present a construction of \(k\)-Thue sequences on \(2k\) symbols, which improves the previous bound of \(2k + 10\sqrt{k}\). Additionaly, we define cyclic \(k\)-Thue sequences and present a construction of such sequences of arbitrary lengths when \(k=2\) using four symbols, with three exceptions. As a corollary, we obtain tight bounds for total Thue colorings of cycles. We conclude the paper with some open problems.