m
• D

F Nous contacter

0

Multi angle

Multi angle $k$-abelian singletons and Gray codes for Necklaces

Auteurs : Whiteland, Markus (Auteur de la Conférence)
CIRM (Editeur )

Résumé : $k$-abelian singletons in connection with Gray codes for Necklaces. This work is based on [1]. We are interested in the equivalence classes induced by $k$-abelian equivalence, especially in the number of the classes containing only one element, $k$-abelian singletons. By characterizing $k$-abelian equivalence with $k$-switchings, a sort of rewriting operation, we are able to obtain a structural representation of $k$-abelian singletons. Analyzing this structural result leads, through rather technical considerations, to questions of certain properties of sets of vertex-disjoint cycles in the de Bruijn graph $dB_\Sigma(k-1)$ of order $k-1$. Some problems turn out to be equivalent to old open problems such as Gray codes for necklaces (or conjugacy classes). We shall formulate the problem in the following.
Let $\mathcal{C} = \lbrace V_1, . . . , V_n\rbrace$ be a cycle decomposition of $dB_\Sigma(n)$, that is, a partition of the vertex set $\Sigma^n$ into sets, each inducing a cycle or a loop in $dB_\Sigma(n)$. Let us then define the quotient graph $dB_\Sigma/\mathcal{C}$ as follows. The set of points are the sets in $\mathcal{C}$. For distinct sets $X, Y \in \mathcal{C}$, we have and edge from $X$ to $Y$ if and only if there exists $x{\in}X,y{\in}Y$ such that $(x,y){\in}dB_\Sigma(n)$. An old result shows that the size of a cycle decomposition of $dB_\Sigma(n)$ is at most the number of necklaces of length $n$ over $\Sigma$ (see [2]). We call a cycle decomposition maximal, if its size is maximal. In particular, the cycle decomposition given by necklaces is maximal.
Conjecture 1. For any $\Sigma$ and $n{\in}\mathbb{N}$, there exist a maximal cycle decomposition $\mathcal{C}$ of $dB_\Sigma(n)$ such that $dB_\Sigma(n)/\mathcal{C}$ contains a hamiltonian path.
A natural candidate to study here is the cycle decomposition given by necklaces. This has been studied in the literature in the connection of Gray codes for necklaces. Concerning this, there is an open problem since $1997$ $[3]$ : Let $\Sigma = \lbrace0, 1\rbrace$, $n$ odd, and $\mathcal{C}$ be the cycle decomposition given by necklaces of length $n$ over $\lbrace0,1\rbrace$. Does $dB(n)/\mathcal{C}$ contain a hamiltonian path ?
The answer to the above has been verified to be ”yes” for $n \le 15$ $([1]$). The case of $n \ge 4$ and $n$ even, the graph is bipartite with one partition larger than the other. On the other hand, we can find other maximal cycle decompositions of $dB_\Sigma(4)$, $dB_\Sigma(6)$, and $dB_\Sigma(8)$ for the binary alphabet which all admit hamiltonian quotient graphs.
We concluded in $[1]$ that Conjecture $1$ is equivalent to the following $\Theta$-estimation of the number of $k$-abelian singletons of length $n$.
Conjecture 2. The number of $k$-abelian singletons of length $n$ over alphabet $\Sigma$ is of order $\Theta(n^{N_{\Sigma}(k-1)-1})$, where $N_\Sigma(l)$ is the number of necklaces of length $l$ over $\Sigma$.

Codes MSC :
05Axx - Enumerative combinatorics
68R15 - Combinatorics on words
94B25 - Combinatorial codes

 Informations sur la Vidéo Réalisateur : Hennenfent, Guillaume Langue : Anglais Date de publication : 31/03/16 Date de captation : 16/03/16 Collection : Research talks Format : MP4 Durée : 00:25:24 Domaine : Combinatorics ; Computer Science Audience : Chercheurs ; Doctorants , Post - Doctorants Download : http://videos.cirm-math.fr/2016-03-16_Whiteland.mp4 Informations sur la rencontre Nom du congrès : Combinatorics on words / Combinatoire des motsOrganisteurs Congrès : Cassaigne, Julien ; Nowotka, DirkDates : 14/03/16 - 18/03/16 Année de la rencontre : 2016 URL Congrès : http://conferences.cirm-math.fr/1429.htmlCitation DataDOI : 10.24350/CIRM.V.18946003Cite this video as: Whiteland, Markus (2016). $k$-abelian singletons and Gray codes for Necklaces. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.18946003URI : http://dx.doi.org/10.24350/CIRM.V.18946003

### Voir aussi

Bibliographie

1. [1] Karhumäki, J., Puzynina, S., Rao, M., & Whiteland, M.A. On the cardinalities of k-abelian equivalence classes, (submitted, 2016) -

2. [2] Mykkeltveit, J. (1972). A Proof of Golomb’s Conjecture for the de Bruijn Graph, Journal of Combinatorial Theory (B), 13, 40-45 - http://dx.doi.org/10.1016/0095-8956(72)90006-8

3. [3] Savage, C. (1997). A Survey of Combinatorial Gray Codes, SIAM Review 39.4, 605-629 - http://dx.doi.org/10.1137/S0036144595295272

Z