On cardinalities of k-abelian equivalence classes

DOI10.1016/J.TCS.2016.06.010MaRDI QIDQ728280zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Combinatorics on words (68R15)

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.

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

Cites work

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

Cited in

(7)

• Abelian combinatorics on words: a survey
• 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

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)