Contributions to the theory of de Bruijn cycle

zbMATH Open1318.05002arXiv1304.2820MaRDI QIDQ5262055FDOQ5262055

Authors: André Alexander Campbell, Anant P. Godbole, Bill Kay 

Publication date: 9 July 2015

Abstract: A de Bruijn cycle is a cyclic listing of length A, of a collection of A combinatorial objects, so that each object appears exactly once as a set of consecutive elements in the cycle. In this paper, we show the power of de Bruijn's original theorem, namely that the cycles bearing his name exist for n-letter words on a k-letter alphabet for all values of k,n, to prove that we can create de Bruijn cycles for the assignment of elements of [n]={1,2,....,n} to the sets in any labeled subposet of the Boolean lattice; de Bruijn's theorem corresponds to the case when the subposet in question consists of a single ground element. The landmark work of Chung, Diaconis, and Graham extended the agenda of finding de Bruijn cycles to possibly the next most natural set of combinatorial objects, namely k-subsets of [n]. In this area, important contributions have been those of Hurlbert and Rudoy. Here we follow the direction of Blanca and Godbole, who proved that, in a suitable encoding, de Bruijn cycles can be created for the subsets of [n$ofsizeintheinterval[s,t];0<=s<t<=n$. In this paper we generalize this result to exhibit existence of de Bruijn cycles for words with weight between s and t, where these parameters are suitably restricted.

Full work available at URL: https://arxiv.org/abs/1304.2820

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Generalized de Bruijn cycles
• Universal cycles for combinatorial structures
• Universal cycles of \(k\)-subsets and \(k\)-permutations
• scientific article; zbMATH DE number 1890156
• On the de Bruijn torus problem

zbMATH Keywords

de Bruijn's theorem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cited In (6)

• A proof of Simmons' conjecture
• Generalized de Bruijn cycles
• Universal and overlap cycles for posets, words, and juggling patterns
• Graph universal cycles of combinatorial objects
• Title not available (Why is that?)
• The combinatorics of N. G. de Bruijn

This page was built for publication: Contributions to the theory of de Bruijn cycle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5262055)