Universal Cycles for Weak Orders
Universal Cycles for Weak Orders
复制标题
弱订单的通用循环
DOI：
--
复制
发表时间：
2012
影响因子：
0.8
通讯作者：
G. Hurlbert
中科院分区：
文献类型：
--
作者：
Victoria Horan;G. Hurlbert
通用周期是最初由Chung，Diaconis和Graham引入的De Bruijn周期和灰色代码的概括。它们是由许多作者开发的，因为对于各种组合物体，例如字符串，子集，置换，分区，矢量空间，和设计。 S-Overlap循环的一种几乎完全重叠的通用周期的概括是放宽这样的约束。在本文中，我们研究了弱点，这些关系是传递和完整的关系。我们证明了弱阶以及固定高度和/或体重弱阶的通用和S-重叠周期的存在，并将结果应用于有序分区的周期。
Universal cycles are generalizations of de Bruijn cycles and Gray codes that were introduced originally by Chung, Diaconis, and Graham in 1990. They have been developed by many authors since, for various combinatorial objects such as strings, subsets, permutations, partitions, vector spaces, and designs. One generalization of universal cycles, which require almost complete overlap of consecutive words, is s-overlap cycles, which relax such a constraint. In this paper we study weak orders, which are relations that are transitive and complete. We prove the existence of universal and s-overlap cycles for weak orders, as well as for fixed height and/or weight weak orders, and apply the results to cycles for ordered partitions as well.