Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUniversal Cycles of Restricted Classes of Words
219
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
Rabinovitch showed in 1978 that the interval orders having a representation consisting of only closed unit intervals have order dimension at most 3. This article shows that the same dimension bound applies to two other classes of posets: those having a representation consisting of unit intervals (but with a mixture of open and closed intervals allowed) and those having a representation consisting of closed intervals with lengths in ${0,1}$.
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.
The independence polynomial of a graph is the generating polynomial for the number of independent sets of each size. Two graphs are said to be textit{independence equivalent} if they have equivalent independence polynomials. We extend previous work by showing that independence equivalence class of every odd path has size 1, while the class can contain arbitrarily many graphs for even paths. We also prove that the independence equivalence class of every even cycle consists of two graphs when $nge 2$ except the independence equivalence class of $C_6$ which consists of three graphs. The odd case remains open, although, using irreducibility results from algebra, we were able show that for a prime $p geq 5$ and $nge 1$ the independence equivalence class of $C_{p^n}$ consists of only two graphs.
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 ucycles or generalized deBruijn cycles or U-cycles) of several combinatorial objects. The existence of ucycles is often dependent on the specific representation that we use for the combinatorial objects. For example, should we represent the subset ${2,5}$ of ${1,2,3,4,5}$ as 25 in a linear string? Is the representation 52 acceptable? Or it it tactically advantageous (and acceptable) to go with ${0,1,0,0,1}$? In this paper, we represent combinatorial objects as graphs, as in cite{bks}, and exhibit the flexibility and power of this representation to produce {it graph universal cycles}, or {it Gucycles}, for $k$-subsets of an $n$-set; permutations (and classes of permutations) of $[n]={1,2,ldots,n}$, and partitions of an $n$-set, thus revisiting the classes first studied in cite{cdg}. Under this graphical scheme, we will represent ${2,5}$ as the subgraph $A$ of $C_5$ with edge set consisting of ${2,3}$ and ${5,1}$, namely the second and fifth edges in $C_5$. Permutations are represented via their permutation graphs, and set partitions through disjoint unions of complete graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
