**Originators:** Chung, Diaconis, and Graham (1993)
(presented by Nathaniel Shar - REGS 2012)

**Definitions:**
A *$k$-permutation* of $[n]$ is a string of $k$ distinct elements of
$[n]$. A *universal cycle* for $k$-permutations of $[n]$ is a cyclic
arrangement $S$ using the alphabet $[n]$ such that the cyclic substrings of $S$
consist of each $k$-permutation of $[n]$ exactly once. A universal cycle for
$(n-1)$-permutations of $[n]$ is also called a universal cycle for permutations
of $[n]$ in *shorthand notation*. A universal cycle for permutations of
$[n]$ in *relative notation* on the alphabet $A$, where
$A \subseteq \mathbb{N}$, is a string $S$ of length $n!$ on $A$ such that for
every permutation $\pi \in S_n$, exactly one cyclic substring
$(x_1, \dots, x_n)$ of $S$ satisfies
$x_{\pi(1)} < x_{\pi(2)} < \cdots < x_{\pi(n)}$.

**Background:**
Chung, Diaconis, and Graham [CDG] observed that universal cycles for
permutations of $[n]$ in relative notation on $[n]$ did not exist and asked
whether there exist universal cycles of permutations of $[n]$ in relative
notation on $[n+1]$. This was answered affirmatively by Johnson [Jo].
The existence of universal cycles for permutations of $[n]$ in shorthand
notation was shown by Jackson [Ja], but his proof was nonconstructive. In 2005,
Knuth [Kn] asked for an explicit construction, which was provided by
Ruskey and Williams [RW] in 2010. [Related material can be found in
REGS 2011 Problem 33. The problem was also
presented at REGS 2010, but without a posted web page.]

**Question 1:** What is the value of $U(n)$, the number of universal
cycles for permutations of $[n]$ in relative notation on $[n+1]$?
Johnson [Jo] provides the bounds $420^{(n-1)!/24} \le U(n) \le (n+1)2^{n!-n}$.

**Question 2:** Ruskey and Williams [RW] explicitly constructed a
universal cycle for permutations of $[n]$ in shorthand notation. Does their
construction extend naturally to universal cycles for $k$-permutations of
$[n]$? If not, can we provide another construction for those universal cycles?

**Question 3:** What is the length of the shortest string on $[n]$ such
that every permutation of $[n]$ occurs at least once as a (noncyclic)
substring? Ashlock and Tillotson [AT] constructed such a string of length
$\sum_{j=1}^n j!$ and conjectured that it is shortest. They verified the
conjecture for $n \le 11$.

**References:**

[AT] Ashlock, D.; Tillotson, J.: Construction of Small
Superpermutations and Minimal Injective
Superstrings. Cong. Numerantium 93, 91-98 (1993).

[CDG] Chung, F.; Diaconis, P.; Graham, R.: Universal cycles for
combinatorial structures. Discr. Math. 110, 43-59 (1993). MR1197444

[Ja] Jackson, B: Universal cycles of $k$-subsets and
$k$-permutations. Discr. Math. 149, 123-129 (1996). MR1375103

[Jo] Johnson, R. J.: Universal cycles for
permutations. Discr. Math. 309, 17, 5264-5270 (2009). MR2548540

[Kn] Knuth, D. E.: The Art of Computer Programming, Vol. 4,
Fasc. 2. Addison-Wesley (2005). MR2251595

[RW] Ruskey, F.; Williams, A.: An explicit universal cycle for the
$(n-1)$-permutations of an $n$-set. ACM Trans. Alg. 6, no. 3, Art. 45
(2010). MR2682614