×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] de Bruijn, N.G., A combinatorial problem, Proc. nederl. akad. wetensch., 49, 758-764, (1946) · Zbl 0060.02701
[2] Clapham, C.R.J., Universal tilings and universal (0,1)-matrices, Discrete math., 58, 87-92, (1986) · Zbl 0597.05021
[3] Cook, J.C., Toroidal tilings from de bruijn—good cyclic sequences, Discrete math., 70, 209-210, (1988) · Zbl 0652.05013
[4] Dehnhardt, K.; Harborth, H., Universal tilings of the plane by 0−1 matrices, Discrete math., 73, 65-70, (1988/1989) · Zbl 0708.05016
[5] Fredericksen, H., A survey of full length nonlinear shift register cycle algorithms, SIAM rev., 24, 195-221, (1982) · Zbl 0482.68033
[6] 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
[7] Gordon, B., On the existence of perfect maps, IEEE trans. inform. theory, 12, 486-487, (1966)
[8] Graham, R.L.; Knuth, D.E.; Patashnik, O., Concrete mathematics, (1989), Addison-Wesley Reading, MA · Zbl 0668.00003
[9] Graham, R.L.; Rothschild, B.L.; Spencer, J.H., Ramsey theory, (1980), Wiley New York · Zbl 0455.05002
[10] Hurlbert, G., Ph.D. thesis, (1990), Rutgers Univ
[11] Iványi, A., Construction of infinite de Bruijn arrays, Discrete appl. math., 22, 289-293, (1988/1989) · Zbl 0662.94011
[12] Brad Jackson, personal communication.
[13] Knuth, D.E., Oriented subtrees of an arc diagraph, J. combin. theory, 3, 309-314, (1967) · Zbl 0161.21001
[14] Knuth, D.E.; Knuth, D.E., Fundamental algorithms, (), 576-581 · Zbl 0191.17903
[15] Lempel, A., m-ary closed sequences, J. combin. theory, 10, 253-258, (1971) · Zbl 0224.05008
[16] 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
[17] Martin, M.H., A problem in arrangements, Bull. amer. math. soc., 40, 859-864, (1934) · Zbl 0010.28901
[18] MacWilliams, F.J.; Sloane, N.J.A., Pseudo-random sequences and arrays, Proc. IEEE, 64, 1715-1729, (1976)
[19] 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
[20] Sinden, F.W., Sliding window codes, AT&T Bell labs tech. memorandum, (1985)
[21] Stein, S., The Mathematician as an explorer, Sci. amer., 149-158, (1961), May
[22] 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.