m
• E

F Nous contacter

0

Multi angle

H 1 $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 . 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 ). 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$ $$ : 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$ $($). 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 $$ 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 Langue : Anglais Date de publication : 31/03/16 Date de captation : 16/03/16 Collection : Research talks ; Combinatorics ; Computer Science Format : MP4 Durée : 00:25:24 Domaine : Combinatorics ; Computer Science Audience : Chercheurs ; Doctorants , Post - Doctorants Download : https://videos.cirm-math.fr/2016-03-16_Whiteland.mp4 Informations sur la rencontre Nom de la rencontre : Combinatorics on words / Combinatoire des motsOrganisateurs de la rencontre : 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 Data DOI : 10.24350/CIRM.V.18946003 Cite this video as: Whiteland, Markus (2016). $k$-abelian singletons and Gray codes for Necklaces. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.18946003 URI : http://dx.doi.org/10.24350/CIRM.V.18946003

Voir aussi

Bibliographie

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

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.  Savage, C. (1997). A Survey of Combinatorial Gray Codes, SIAM Review 39.4, 605-629 - http://dx.doi.org/10.1137/S0036144595295272

Ressources Electroniques (Depuis le CIRM)

Books & Print journals

Recherche avancée

0
Z