Universal cycle constructions for k k -subsets and k k -multisets
Colin Campbell, Luke Janik-Jones, Joe Sawada · 2026
Read Universal cycle constructions for k k -subsets and k k -multisets by Colin Campbell, Luke Janik-Jones, Joe Sawada (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-11954.txt.
Description
Campbell and co-authors give efficient constructions of universal cycles for k-subsets and k-multisets. With plain string encodings, such cycles cannot always exist for these sets. Mapping the sets to labeled graphs restores existence but not an efficient build. Their new representation fixes that: successor rules build the cycles in linear time per symbol and linear space. Necklace concatenation then generates the same strings in constant amortized time per symbol. These are the first efficient constructions known for k-multisets.
Catalog record
| CREATOR | Colin Campbell, Luke Janik-Jones, Joe Sawada |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49882 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.11954