Universal and Near-Universal Cycles of Set Partitions
Document Type
Article
Publication Date
12-23-2015
Description
We study universal cycles of the set P(n,k) of k-partitions of the set [n]:={1,2,…,n} and prove that the transition digraph associated with 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 P(n,k) exist for all n≥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 (Formula presented) is odd (3≤k
Citation Information
Higgins, Zach; Kelley, Elizabeth; Sieben, Bertilla; and Godbole, Anant. 2015. Universal and Near-Universal Cycles of Set Partitions. Electronic Journal of Combinatorics. Vol.22(4). https://doi.org/10.37236/5051