Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the probability of existence of a universal cycle or a universal word for a set of words
94
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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 $nleq 4$.
rate research
Read More
A universal word for a finite alphabet $A$ and some integer $ngeq 1$ is a word over $A$ such that every word in $A^n$ appears exactly once as a subword (cyclically or linearly). It is well-known and easy to prove that universal words exist for any $A$ and $n$. In this work we initiate the systematic study of universal partial words. These are words that in addition to the letters from $A$ may contain an arbitrary number of occurrences of a special `joker symbol $Diamond otin A$, which can be substituted by any symbol from $A$. For example, $u=0Diamond 011100$ is a linear partial word for the binary alphabet $A={0,1}$ and for $n=3$ (e.g., the first three letters of $u$ yield the subwords $000$ and $010$). We present results on the existence and non-existence of linear and cyclic universal partial words in different situations (depending on the number of $Diamond$s and their positions), including various explicit constructions. We also provide numerous examples of universal partial words that we found with the help of a computer.
A connected digraph in which the in-degree of any vertex equals its out-degree is Eulerian, this baseline result is used as the basis of existence proofs for universal cycles (also known as generalized deBruijn cycles or U-cycles) of several combinatorial objects. We extend the body of known results by presenting new results on the existence of universal cycles of monotone, augmented onto, and Lipschitz functions in addition to universal cycles of certain types of lattice paths and random walks.
It is well known that Universal Cycles of $k$-letter words on an $n$-letter alphabet exist for all $k$ and $n$. In this paper, we prove that Universal Cycles exist for restricted classes of words, including: non-bijections, equitable words (under suitable restrictions), ranked permutations, and passwords.
We prove a uniform bound on the topological Turan number of an arbitrary two-dimensional simplicial complex $S$: any $n$-vertex two-dimensional complex with at least $C_S n^{3-1/5}$ facets contains a homeomorphic copy of $S$, where $C_S > 0$ is an absolute constant depending on $S$ alone. This result, a two-dimensional analogue of a classical result of Mader for one-dimensional complexes, sheds some light on an old problem of Linial from 2006.
Chen, Kitaev, M{u}tze, and Sun recently introduced the notion of universal partial words, a generalization of universal words and de Bruijn sequences. Universal partial words allow for a wild-card character $diamond$, which is a placeholder for any letter in the alphabet. We settle and strengthen conjectures posed in the same paper where this notion was introduced. For non-binary alphabets, we show that universal partial words have periodic $diamond$ structure and are cyclic, and we give number-theoretic conditions on the existence of universal partial words. In addition, we provide an explicit construction for a family of universal partial words over alphabets of even size.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
