Universal cycles for combinatorial structures (Q1208348)

The following generalization of De Bruijn cycles is introduced. Let \(F_ n\) be a family of combinatorial objects ``of rank \(n\)''. Let \(m:=| F_ n|\). Assume that each \(F\in F_ n\) can be represented (or specified) by some sequence \(\langle x_ 1,\dots,x_ n\rangle\), where \(x_ i\in A\) for some fixed alphabet \(A\). We say that \(U=(a_ 0,a_ 1,\dots,a_{m-1})\) is a universal cycle for \(F_ n\) (or \(U\)-cycle) if \(\langle a_{i+1},\dots,a_{i+n}\rangle\), \(0\leq i<m\), runs through all the elements of \(F_ n\) (where index addition is performed modulo \(m)\). If \(F_ n\) is the set of all possible \(0-1\) sequences of length \(n\), then \(m=2^ n\) and with \(A=\{0,1\}\) a \(U\)-cycle is a De Bruijn cycle of length \(m\). The generalizations that are introduced (after a short survey of De Bruijn cycles) concern permutations of an \(n\)-set, partitions of an \(n\)-set and \(k\)-subsets of an \(n\)-set. The method of representation is an important aspect of the definition of the problem. Let \(a_ 1,a_ 2,\dots,a_ n\) be different elements of the \(N\)-set \(A\) \((N\geq n)\). We say that \(\langle a_ 1,\dots,a_ n\rangle\) represents the permutation \(\langle b_ 1,\dots,b_ n\rangle\) of \(\langle 1,2,\dots,n\rangle\) if \(a_ i<a_ j\Leftrightarrow b_ i<b_ j\) for \(i,j\) \((i\neq j)\). With this convention, the cycle \(\langle 1,4,5,2,4,3\rangle\) is a \(U\)-cycle for the six permutations of \(S_ 3\). This problem is treated using graphs in the same way as the standard treatment of De Bruijn cycles. The authors conjecture that for \(S_ n\) the minimal size of \(A\) is \(n+1\) \((n\geq 3)\). Several questions are posed. For partitions the following natural representation is used. The partition \(13\mid 25\mid 467\mid 8\) of \(\{1,2,\dots,8\}\) is represented by the sequence abacbccd (self-explanatory). An example of a \(U\)-set for the 2-subsets of a 5-set is \(\langle 1234524135\rangle\). For the problem of \(k\)-subsets of an \(n\)-set the authors conjecture (with a \$ 100 reward offered) that \(U\)-cycles exist if \(k\) divides \({n-1\choose k-1}\) and \(n\) is sufficiently large. In closing, the authors state that they have barely scratched the surface of this subject. A start in some of the possible directions of research can be found in the Ph. D. thesis of \textit{G. Hurlbert} (Rutgers Univ. 1990).