Universal cycles for combinatorial structures
type: Item
instance of: scholarly article
title: Universal cycles for combinatorial structures
zbMATH Open document ID: 0776.05001
DOI: 10.1016/0012-365X(92)90699-G
author: Persi Diaconis
author: Fan Chung
author: Ron Graham
published in: Discrete Mathematics
publication date: 1993-05-16T00:00:00Z
review text: 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 \…
reviewed by: Jack van Lint
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05A18
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 166352
zbMATH Keywords: De Bruijn cycles
zbMATH Keywords: universal cycle
zbMATH Keywords: permutations
zbMATH Keywords: partitions
Wikidata QID: Q29041464
MaRDI profile type: Publication
cites work: Q5834367
cites work: Universal tilings and universal (0,1)-matrices
cites work: Toroidal tilings from de Bruijn-Good cyclic sequences
cites work: Universal tilings of the plane by 0-1 -matrices
cites work: A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
cites work: Q3686626
cites work: Q4040797
cites work: Q3903002
cites work: Construction of infinite de Bruijn arrays
cites work: Oriented subtrees of an arc digraph
cites work: Q5585020
cites work: m-ary closed sequences
cites work: On Pseudo-Random Arrays
cites work: A problem in arrangements
cites work: A theory of two-dimensional linear recurring arrays
cites work: Binary Ring Sequences
full work available at URL: 0012-365x(92)90699-g
OpenAlex ID: W2085157194
description: scientific article; zbMATH DE number 166352