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

CREATORColin Campbell, Luke Janik-Jones, Joe Sawada
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49882
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.11954

Browse the full library · About the Tower of Babel