Universal cycles of \(k\)-subsets and \(k\)-permutations (Q686158)

Universal cycles for combinatorial structures (a generalization of De Bruijn sequences) were introduced by \textit{F. Chung}, \textit{P. Diaconis} and \textit{R. Graham} [Universal cycles for combinatorial structures, Discrete Math. 110, No. 1-3, 43-59 (1992; Zbl 0776.05001)]. Some of the results of the paper under review were presented there without proof. The author considers \(k\)-subsets of \(N:=\{0,1,\ldots,n-1\}\) and \(k\)- permutations of \(N\). The main results for \(k\)-subsets are that a universal cycle exists for \(k=3\) if \((n,3)=1\) and \(n \geq 8\) and a universal cycle exists for \(k=4\) if \((n,4)=1\) and \(n \geq 9\). The analogous problem for \(k\)-combinations with repetition \((k=3,4)\) is also treated. The proofs depend on representing the problem by a suitable digraph and showing that the graph is eulerian and strongly connected. Finally, it is shown that for \(k \geq 3\) and \(n \geq k+1\), there is a universal cycle for the set of \(k\)-permutations of \(N\).