اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدUniversal Cycles of Restricted Classes of Words
171
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 combinat
orial 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 b
y 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 sever
al 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
