# Universal Cycles for Permutations (1993-2012)

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