On the probability of existence of a universal cycle or a universal word for a set of words

arXiv1908.01116MaRDI QIDQ6323136FDOQ6323136

Herman Z. Q. Chen, Sergey Kitaev, Brian Y. Sun

Publication date: 2 August 2019

Abstract: A universal cycle, or u-cycle, for a given set of words is a circular word that contains each word from the set exactly once as a contiguous subword. The celebrated de Bruijn sequences are a particular case of such a u-cycle, where a set in question is the set $A^n$ of all words of length $n$ over a $k$-letter alphabet $A$. A universal word, or u-word, is a linear, i.e. non-circular, version of the notion of a u-cycle, and it is defined similarly. Removing some words in $A^n$ may, or may not, result in a set of words for which u-cycle, or u-word, exists. The goal of this paper is to study the probability of existence of the universal objects in such a situation. We give lower bounds for the probability in general cases, and also derive explicit answers for the case of removing up to two words in $A^n$, or the case when $k=2$ and $nleq4$.

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Eulerian and Hamiltonian graphs (05C45)

This page was built for publication: On the probability of existence of a universal cycle or a universal word for a set of words

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