Universal Cycles for K-subsets of an N-set
Author: Melinda Lanius
Publisher:
Published: 2012
Total Pages:
ISBN-13:
DOWNLOAD EBOOKGeneralized from the classic de Bruijn sequence, a universal cycle is a compact cyclic list of information. Existence of universal cycles has been established for a variety of families of combinatorial structures. These results, by encoding each object within a combinatorial family as a length-j word, employ a modified version of the de Bruijn graph to establish a correspondence between an Eulerian circuit and a universal cycle. We explore the existence of universal cycles for k-subsets of the integers {1, 2 ..., n}. The fact that sets are unordered seems to prevent the use of the established encoding techniques used in proving existence. We explore this difficulty and introduce an intermediate step that may allow us to use the familiar encoding and correspondence to prove existence. Moreover, mathematicians Persi Diaconis and Ron Graham hold that "the construction of universal cycles has proceeded by clever, hard, ad-hoc arguments" and that no general theory exists. Accordingly, our work pushes for a more general approach that can inform other universal cycle problems.
