On cardinalities of k-abelian equivalence classes

DOI10.1016/J.TCS.2016.06.010zbMATH Open1356.68166arXiv1605.03319OpenAlexW2963619970MaRDI QIDQ728280FDOQ728280

Authors: Juhani Karhumäki, Svetlana Puzynina, Michaël Rao, Markus A. Whiteland 

Publication date: 19 December 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: 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 $mathcalO(n^{N_m(k-1)-1})$, where $N_m(l)=frac1lsu{m}_{dmidl}varphi(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.

Full work available at URL: https://arxiv.org/abs/1605.03319

Recommendations

• Regularity of k-Abelian Equivalence Classes of Fixed Cardinality
• On the enumeration of Abelian \(K\)-complete mappings
• \(k\)-abelian equivalence and rationality
• \(k\)-abelian equivalence and rationality
• scientific article; zbMATH DE number 1816762
• scientific article; zbMATH DE number 4204331
• On cardinal numbers related with a compact abelian group
• On a cardinal group invariant related to decompositions of Abelian groups
• scientific article; zbMATH DE number 3784978
• scientific article; zbMATH DE number 5734050

zbMATH Keywords

necklacesde Bruijn graphGray codesHamiltonian paths\(k\)-abelian equivalence

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• Graph theory
• An Efficient Algorithm for Generating Necklaces with Fixed Density
• Title not available (Why is that?)
• A Survey of Combinatorial Gray Codes
• A proof of Golomb's conjecture for the de Bruijn graph
• \(k\)-abelian pattern matching
• Variations of the Morse-Hedlund theorem for \(k\)-abelian equivalence
• On a generalization of abelian equivalence and complexity of infinite words
• Gray codes for necklaces and Lyndon words of arbitrary base
• Gray-ordered binary necklaces
• Title not available (Why is that?)
• Computing Binary Combinatorial Gray Codes Via Exhaustive Search With SAT Solvers
• Strongly \(k\)-abelian repetitions
• Fine and Wilf's theorem for \(k\)-abelian periods
• Uniform words

Cited In (7)

• Regularity of k-Abelian Equivalence Classes of Fixed Cardinality
• Reverse-safe text indexing
• \(k\)-abelian equivalence and rationality
• \(k\)-abelian equivalence and rationality
• The binomial equivalence classes of finite words
• On cardinal numbers related with a compact abelian group
• Abelian combinatorics on words: a survey

This page was built for publication: On cardinalities of \(k\)-abelian equivalence classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q728280)