# zbMATH — the first resource for mathematics

Universal cycles for combinatorial structures. (English) Zbl 0776.05001
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 G. Hurlbert (Rutgers Univ. 1990).

##### MSC:
 05A05 Permutations, words, matrices 05A18 Partitions of sets 05C38 Paths and cycles 05C45 Eulerian and Hamiltonian graphs 05C20 Directed graphs (digraphs), tournaments
##### Keywords:
De Bruijn cycles; universal cycle; permutations; partitions
Full Text:
##### References:
  de Bruijn, N.G., A combinatorial problem, Proc. nederl. akad. wetensch., 49, 758-764, (1946) · Zbl 0060.02701  Clapham, C.R.J., Universal tilings and universal (0,1)-matrices, Discrete math., 58, 87-92, (1986) · Zbl 0597.05021  Cook, J.C., Toroidal tilings from de bruijn—good cyclic sequences, Discrete math., 70, 209-210, (1988) · Zbl 0652.05013  Dehnhardt, K.; Harborth, H., Universal tilings of the plane by 0−1 matrices, Discrete math., 73, 65-70, (1988/1989) · Zbl 0708.05016  Fredericksen, H., A survey of full length nonlinear shift register cycle algorithms, SIAM rev., 24, 195-221, (1982) · Zbl 0482.68033  Fan, C.T.; Fan, S.M.; Ma, S.L.; Sin, M.K., On de Bruijn arrays, Ars combin., 19A, 205-213, (1985) · Zbl 0568.94021  Gordon, B., On the existence of perfect maps, IEEE trans. inform. theory, 12, 486-487, (1966)  Graham, R.L.; Knuth, D.E.; Patashnik, O., Concrete mathematics, (1989), Addison-Wesley Reading, MA · Zbl 0668.00003  Graham, R.L.; Rothschild, B.L.; Spencer, J.H., Ramsey theory, (1980), Wiley New York · Zbl 0455.05002  Hurlbert, G., Ph.D. thesis, (1990), Rutgers Univ  Iványi, A., Construction of infinite de Bruijn arrays, Discrete appl. math., 22, 289-293, (1988/1989) · Zbl 0662.94011  Brad Jackson, personal communication.  Knuth, D.E., Oriented subtrees of an arc diagraph, J. combin. theory, 3, 309-314, (1967) · Zbl 0161.21001  Knuth, D.E.; Knuth, D.E., Fundamental algorithms, (), 576-581 · Zbl 0191.17903  Lempel, A., m-ary closed sequences, J. combin. theory, 10, 253-258, (1971) · Zbl 0224.05008  van Lint, J.H.; MacWilliams, F.J.; Sloane, N.J.A., On pseudo-random arrays, SIAM J. appl. math., 36, 62-72, (1979) · Zbl 0409.94024  Martin, M.H., A problem in arrangements, Bull. amer. math. soc., 40, 859-864, (1934) · Zbl 0010.28901  MacWilliams, F.J.; Sloane, N.J.A., Pseudo-random sequences and arrays, Proc. IEEE, 64, 1715-1729, (1976)  Normura, T.; Miyakawa, H.; Imai, H.; Fukuda, A., A theory of two-dimensional linear arrays, IEEE trans. inform. theory, 18, 775-785, (1972) · Zbl 0249.94001  Sinden, F.W., Sliding window codes, AT&T Bell labs tech. memorandum, (1985)  Stein, S., The Mathematician as an explorer, Sci. amer., 149-158, (1961), May  Yoeli, M., Binary ring sequences, Amer. math. monthly, 69, 852-855, (1962) · Zbl 0107.24903
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.