Totally Unclustered BWT Images of Any Length over Non-Binary Alphabets

Let $w=BWT(u)$. Consider the permutation $\sigma ={\pi }_w^{-1}$. It can be understood as follows: writing the multiset of letters of $w$ in lexicographic order, where equal letters are sorted by occurrence order in $w$, the position in $w$ of the $i$-th letter is $\sigma (i)$. In particular, since the Parikh vector of $w$ is $(m,\mathrm{\dots },m)$, the positions of 0 in $w$ are $\sigma (0),\mathrm{\dots },\sigma (m-1)$, the positions of 1 are $\sigma (m),\mathrm{\dots },\sigma (2m-1)$, and so on, until the last letter, which occurs at positions $\sigma ((k-1)m),\mathrm{\dots },\sigma (km-1)$. In particular, there is a tie in $w$ at block $i$ if and only if, for some $j\in \{0,\mathrm{\dots },k-1\}$ the $j$th letter of ${\mathrm{\Sigma }}_k$ occurs at positions $ki+k-1$ and $k(i+1)$, and in that case they are respectively the $(i+1)$-th and the $i+2$-th occurrences of this letter. In other words, we have $\sigma (jm+i)=ki+k-1$ and $\sigma (jm+i+1)=k(i+1)$, as claimed. $◀$

The following lemma provides conditions under which Hamiltonian cycles can be rerouted to avoid a specified edge. We will use it to break ties in BWT images of generalized de Bruijn words by rerouting the corresponding Hamiltonian cycles so that they avoid one of the edges responsible for the tie.

Let $G$ be a directed Hamiltonian graph, $A$ and $B$ two subsets of $V(G)$ satisfying the conditions of the statement, and $\gamma$ a Hamiltonian cycle visiting $e=(x,y)\in A\times B$. Since $\gamma$ is a cycle, we can write it as a sequence of vertices starting with $y$ and ending with $x$. Sets $A$ and $B$ have cardinality at least $3$, and every vertex from $A$ must be followed by a vertex from $B$. Hence, one can write $\gamma ={\gamma }_1\cdot {\gamma }_2\cdot {\gamma }_3$ where each ${\gamma }_i$ starts with a vertex from $B$ and ends with a vertex from $A$, for every $i\in \{1,2,3\}$. Since each $(x,y)\in A\times B$ is an edge, the sequence ${\gamma }^{\prime }={\gamma }_1\cdot {\gamma }_3\cdot {\gamma }_2$ is still a Hamiltonian cycle for $G$, which does not visit $(x,y)$. Furthermore, $\gamma$ and ${\gamma }^{\prime }$ differ only on edges in $A\times B$, and the statement follows. $◀$

The following lemma shows that the rightmost tie in the BWT of a generalized de Bruijn word can always be removed.

Suppose $i_0$ is the rightmost tie of $w$. From the hypothesis, it follows that $w_{k{i}_0+k-1}=w_{k(i_0+1)}$, and from Lemma 15, there is a fixed $j_0\in \{0,\mathrm{\dots },k-1\}$ such that $\sigma (j_{0}m+i_0)=k{i}_0+k-1$ and $\sigma (j_{0}m+i_0+1)=k(i_0+1)$, where $j_0$ depends on the letter $w_{k{i}_0+k-1}=w_{k(i_0+1)}$.

By Lemma 8, the permutation $\sigma ={\pi }_w^{-1}$ is a cycle, and by Theorem 13, this cycle corresponds to the consecutive vertex labels of a Hamiltonian cycle of $G=\mathrm{GDB}(k,km)$. Consider the sets $A_{i_0}=\{i_0,m+i_0,\mathrm{\dots },(k-1)m+i_0\}\subseteq V(G)$, $B_{i_0}=\{k{i}_0,k{i}_0+1,\mathrm{\dots },k{i}_0+k-1\}\subseteq V(G)$. Note that the edge $(j_{0}m+i_0,k{i}_0+k-1)$ is visited by the cycle corresponding to $\sigma$ and that it is an edge from $A_{i_0}$ to $B_{i_0}$. Those sets both have cardinality $k\ge 3$, and by construction of $G$, they satisfy the conditions of Lemma 16. We can then obtain a Hamiltonian cycle of $G$, corresponding to a permutation ${\sigma }^{\prime }$, with ${\sigma }^{\prime }(j_{0}m+i_0)\ne k{i}_0+k-1$, hence $w^{\prime }$ has no tie at $i_0$, and ${\sigma }^{\prime }(\mathrm{\ell })=\sigma (\mathrm{\ell })$ for every $\mathrm{\ell }\notin A_{i_0}$ (importantly, we still have $\sigma (j_{0}m+i_0+1)=k(i_0+1)$, so the conditions of Lemma 15 cannot hold for some $j\ne j_0$), and the words $w$ and $w^{\prime }$ differ only at block $i_0$ (namely, at positions $k{i}_0,\mathrm{\dots },k{i}_0+k-1$). Since $i_0$ was the rightmost tie in $w$, we deduce that $w^{\prime }$ has no tie at block $i\ge i_0$. $◀$

We can now prove our main result:

By Theorem 13, generalized de Bruijn words are in bijection with Hamiltonian cycles in $\mathrm{GDB}(k,km)$, or equivalently, with Eulerian cycles in $\mathrm{GDB}(k,m)$. Since $\mathrm{GDB}(k,m)$ is Eulerian for every $k,m$, there is at least one generalized de Bruijn word $u$ of length $km$ over ${\mathrm{\Sigma }}_k$. If $BWT(u)$ has no tie, then $u$ is a generalized de Bruijn with totally unclustered BWT. Otherwise, let $i_0$ be the rightmost tie for $w$. By Lemma 19, there exists $w^{\prime }=BWT([u^{\prime }])$, for some generalized de Bruijn word $[u]$, such that either $w^{\prime }$ has no tie, and therefore $[u^{\prime }]$ is totally unclustered, or its rightmost tie is at block , and recursively apply at most $i_0+1$ times the same approach until we eventually obtain a word with no ties, which is then the BWT of some generalized de Bruijn word that has a totally unclustered BWT. $◀$

As a direct consequence of Theorem 3, we obtain the following result for ordinary de Bruijn words.

Corollary 21 shows a clear separation from the binary case, where de Bruijn words with totally unclustered BWT do not exist [24, Theorem 5.2].

Moreover, in the case of de Bruijn words with totally unclustered BWT, the clustering ratio depends only on $k$, as shown in the following proposition.

Recall that $[u]$ is a de Bruijn word of length $k^d$. Clearly, $|\mathrm{RLE}(v)|=1+|\{0\le i\le k^d-2,v[i]\ne v[i+1]\}|$. Since $[u]$ is a de Bruijn word, each string from ${\mathrm{\Sigma }}_k^2$ occurs exactly $k^{d-2}$ times as a circular factor of $[u]$, and ${\mathrm{\Sigma }}_k^2$ contains $k^2-k$ strings having two distinct letters. Finally, since $v$ is minimal among rotations of $[u]$, its first and last letters must be distinct, hence exactly one of the circular occurrences of a pair of distinct letters is not an occurrence in $v$. Wrapping up, we obtain $|\mathrm{RLE}(v)|=k^{d-2}(k^2-k)=k^{d-1}(k-1)$. Now, since $v$ has totally unclustered BWT, which means that $r(v)=|v|=k^d$, we conclude that $r(v)/|\mathrm{RLE}(v)|=k/(k-1)$. $◀$

Let $u$ be a ternary generalized de Bruijn word of length $n=3m$, and $w=BWT(u)$. Let $\sigma ={\pi }_w^{-1}$ be its inverse standard permutation, corresponding to a Hamiltonian cycle $\gamma$ of $\mathrm{GDB}(3,3m)$. Let $A_m=\{m-1,2m-1,3m-1\}$ and $B_m=\{3m-3,3m-2,3m-1\}$, and write $e_1$ for the edge $(3m-1,3m-2)$ and $e_2=(3m-1,3m-3)$. Notice also that the edge $(3m-1,3m-1)$ is visited by no Hamiltonian cycle, since it is a self-loop. Now, $\gamma$ must visit one edge among $e_1$ and $e_2$: in particular, it visits $e_1$ if and only if $w\in P_m$, and $e_2$ if and only if $w\in Q_m$. In both cases, since $A_m$ and $B_m$ satisfy the conditions of Lemma 16, we can obtain a Hamiltonian cycle ${\gamma }^{\prime }$ visiting $e_2$ (resp. $e_1$) if and only if $\gamma$ visits $e_1$ (resp. $e_2$), hence a word $w^{\prime }$ which is the $BWT$ image of a de Bruijn word and such that $w^{\prime }\in Q_m$ (resp. $w^{\prime }\in P_m$) if and only if $w\in P_m$ (resp. $w\in Q_m$). Since no other block is affected, we obtain an involution on the set of BWT images of generalized de Bruijn words, mapping $P_m$ to $Q_m$. $◀$

From Lemma 24, we know that $P_m$ and $Q_m$ are both nonempty. Without loss of generality, let $w\in P_m$. We apply Lemma 19 iteratively to $w$, following the same procedure as in the proof of Theorem 3. At each step, we eliminate the rightmost tie (at some block $j\le m-1$) until the word becomes totally unclustered. Crucially, this process does not affect the final block of the word, so the position $w_{3m-2}=\text{2}$ remains unchanged. Hence, we obtain a totally unclustered word $w^{\prime }\in P_m$. $◀$

Let us assume $w\in P_m$, and therefore $w_{3m-3}=\text{2}$. Observe that the word $w^{\prime }$ of length $3m-1$ is obtained by deleting from $w$ the 2 at position $3m-3$. As the last block of $w$ is a permutation of ${\mathrm{\Sigma }}_3$, we have $w_{3m-3}\ne w_{3m-1}$, so $w^{\prime }$ remains totally unclustered.

We now track the effect on the standard permutation. For all , the relative order remains the same, so ${\pi }_{w^{\prime }}(i)={\pi }_w(i)$. Since the removed 2 was the last of its kind, we had ${\pi }_w(3m-2)=3m-1$. The symbol at position $3m-1$ in $w$ is now at $3m-2$ in $w^{\prime }$, so ${\pi }_{w^{\prime }}(3m-2)={\pi }_w(3m-1)$. All other values are preserved. Thus, ${\pi }_{w^{\prime }}$ is obtained by deleting $3m-1$ from the cycle of ${\pi }_w$, which yields a $(3m-1)$-cycle. Therefore, $w^{\prime }=BWT(u^{\prime })$ for some necklace $u^{\prime }$ of length $3m-1$, and it is totally unclustered.

Now, assume that $w\in Q_m$, and therefore $w_{3m-1}=\text{2}$. We define $w^{\prime \prime }$ as the word of length $3m+1$ obtained by inserting a 2 between positions $3m-2$ and $3m-1$ in $w$. This insertion is not adjacent to the existing 2 at position $3m-3$, so it increases the number of runs by $1$, and $w^{\prime }$ remains totally unclustered.

Let us verify that ${\pi }_{w^{\prime }}$, the standard permutation of $w^{\prime }$, is a cycle. Since the insertion occurs after the last 2 of $w$, all positions before $3m-1$ preserve their relative order: for all , we have ${\pi }_{w^{\prime }}(i)={\pi }_w(i)$. The inserted 2 at position $3m-1$ is now the new last 2, so ${\pi }_{w^{\prime }}(3m-1)=3m$. The former position $3m-1$ (now shifted to $3m$) keeps its image: ${\pi }_{w^{\prime }}(3m)={\pi }_w(3m-1)$. All subsequent values are unchanged. Thus, ${\pi }_{w^{\prime }}$ is obtained by inserting $3m$ just after $3m-1$ in the cycle of ${\pi }_w$. Since ${\pi }_w$ is a $(3m)$-cycle, this operation yields a $(3m+1)$-cycle, so $w^{\prime }=BWT(u^{\prime })$ for some necklace $u^{\prime }$ of length $3m+1$, and is totally unclustered. $◀$