Universal and near-universal cycles of set partitions (Q907241)

Summary: We study universal cycles of the set \(\mathcal P(n, k)\) of \(k\)-partitions of the set \([n]:= \{1, 2, \ldots , n\}\) and prove that the transition digraph associated with \(\mathcal P(n, k)\) is Eulerian. But this does not imply that universal cycles (or ucycles) exist, since vertices represent equivalence classes of partitions. We use this result to prove, however, that ucycles of \(\mathcal P(n, k)\) exist for all \(n\geqslant 3\) when \(k = 2\). We reprove that they exist for odd \(n\) when \(k = n - 1\) and that they do not exist for even \(n\) when \(k = n - 1\). An infinite family of \((n, k)\) for which ucycles do not exist is shown to be those pairs for which \(\{{n-2\atop k-2}\}\) is odd \((3\leqslant k < n - 1)\). We also show that there exist universal cycles \(k-2\) of partitions of \([n]\) into \(k\) subsets of distinct sizes when \(k\) is sufficiently smaller than \(n\), and therefore that there exist universal packings of the partitions in \(\mathcal P(n, k)\). An analogous result for coverings completes the investigation.