On cardinalities of k-abelian equivalence classes
Michaël Rao; Juhani Kahumäki; Markus Whiteland; Svetlana Puzynina
On cardinalities of k-abelian equivalence classes
Michaël Rao
Juhani Kahumäki
Markus Whiteland
Svetlana Puzynina
Elsevier
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2021042716238
https://urn.fi/URN:NBN:fi-fe2021042716238
Tiivistelmä
Two words $u$ and $v$ are $k$-abelian equivalent if for each word $x$ of length at most $k$, $x$ occurs equally
many times as a factor in both $u$ and $v$. The notion of $k$-abelian equivalence is an intermediate notion between the abelian equivalence and the equality of words. In this paper, we study the equivalence classes induced by the $k$-abelian equivalence, mainly focusing on the cardinalities of the classes. In particular, we are interested in the number of singleton $k$-abelian classes, i.e., classes containing only one element. We find a connection between the
singleton classes and cycle decompositions of the de Bruijn graph. We show that the number of classes of words of length $n$ containing one single element is of order $mathcal O (n^{N_m(k-1)-1})$, where $N_m(l)= frac{1}{l}sum_{dmid l}arphi(d)m^{l/d}$ is the number of necklaces of length $l$ over an $m$-ary alphabet. We conjecture that the upper bound is sharp. We also remark that, for $k$ even and $m=2$, the lower bound $Omega (n^{N_m(k-1)-1})$
follows from an old conjecture on the existence of Gray codes for necklaces of odd length. We verify this conjecture for necklaces of length up to 15.
many times as a factor in both $u$ and $v$. The notion of $k$-abelian equivalence is an intermediate notion between the abelian equivalence and the equality of words. In this paper, we study the equivalence classes induced by the $k$-abelian equivalence, mainly focusing on the cardinalities of the classes. In particular, we are interested in the number of singleton $k$-abelian classes, i.e., classes containing only one element. We find a connection between the
singleton classes and cycle decompositions of the de Bruijn graph. We show that the number of classes of words of length $n$ containing one single element is of order $mathcal O (n^{N_m(k-1)-1})$, where $N_m(l)= frac{1}{l}sum_{dmid l}arphi(d)m^{l/d}$ is the number of necklaces of length $l$ over an $m$-ary alphabet. We conjecture that the upper bound is sharp. We also remark that, for $k$ even and $m=2$, the lower bound $Omega (n^{N_m(k-1)-1})$
follows from an old conjecture on the existence of Gray codes for necklaces of odd length. We verify this conjecture for necklaces of length up to 15.
Kokoelmat
- Rinnakkaistallenteet [19207]