Graph Universal Cycles of Combinatorial Objects

Abstract

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,\dots ,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.

16 pages, 13 figures