Contributions to the Theory of de Bruijn Cycle
Contributions to the Theory of de Bruijn Cycle
复制标题
对德布鲁因循环理论的贡献
作者：
Andre A Campbell;A. Godbole;Bill Kay
de bruijn循环是组合对象集合的长度a的循环列表，因此每个对象在周期中完全显示为一组连续元素。在本文中，我们展示了de bruijn的原始定理的力量，即以k，n的所有值在k-letter字母上以n字母为单词的单词存在，以证明我们可以创建de bruijn Cycles为了分配[n] = {1,2，....，n}的元素，以分配布尔晶格的任何标记子框中的集合； de Bruijn的定理对应于所讨论的子库由单个地面元素组成时。 Chung，Diaconis和Graham的具有里程碑意义的工作扩大了发现Bruijn循环的议程，可能是下一个最自然的组合物体，即[N]的K-Subsets。在这一领域，重要的贡献是霍尔伯特和鲁迪伊的贡献。在这里，我们遵循Blanca和Godbole的方向，他们证明，在适当的编码中，可以在[n $ of [n $ of Subere of [n $ of of [s of of [s''中创建de bruijn周期。 0 <= s <t <= n $。在本文中，我们将此结果推广到在S和T之间具有重量的单词的De Bruijn周期存在，其中这些参数受到适当限制。
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$ of size in the interval [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.