Combinatorial Generation, Gray Codes, and Structure Problems

许多实际问题的解决需要从组合类中随机抽取一个对象，或者更糟的是，对类中的所有对象进行穷举搜索。为了使这样的搜索成为可能，即使对于中等规模的问题，组合生成方法也必须非常有效。举个例子，格雷码的组合生成方法是将对象生成为一个列表，其中的连续元素只有很小的差异，就像在二进制反映的格雷码中一样。每个组合格雷码问题都有一个替代的表述，作为一个相关图中的汉密尔顿路径或循环问题，它可能是顶点传递的，甚至是一个凯利图。组合生成效率的渐近改进不仅需要良好的数据结构和算法设计技术，而且更经常需要对所涉及的组合类的结构有一些新的见解。这些结构问题把我们带入了著名的关于Hamilton环、图同构、Cayley图和格中的对称链分解的开放问题的领域。结合结构问题的研究，在枚举问题上取得了进展。本文提出的研究是继续在组合生成和格雷码方面的工作，并直接解决相关领域的一些突出问题。这些问题包括顶点传递图和Cayley图上的Hamilton环问题，类de Bruijn序列上的新问题，以及涉及置换和整数划分的部分有序集合上对称链分解和完全匹配的存在性。

Many practical problems require for their solution the sampling of a random object from a combinatorial class or, worse, an exhaustive search through all objects in the class. In order for such a search to be possible, even for problems of moderate size, combinatorial generation methods must be extremely efficient. As an example, the Gray code approach to combinatorial generation is to generate the objects as a list in which successive elements differ only in a small way, as in the binary reflected Gray code. Each combinatorial Gray code problem has an alternate formulation as a Hamilton path or cycle problem in an associated graph, which may be vertex transitive or even a Cayley graph. Asymptotic improvement in the efficiency of combinatorial generation requires not only good data structures and algorithm design techniques, but, more often, some new insight into the structure of the combinatorial class involved. These structure questions put us into the realm of well-known open problems on Hamilton cycles, graph isomorphism, Cayley graphs, and symmetric chain decompositions in lattices. Progress on the enumeration problems is made by studying the structure problems hand in hand. The research proposed herein is to continue work on combinatorial generation and Gray codes and also to address directly some of the outstanding problems in related areas. These include the Hamilton cycle problem on vertex transitive graphs and Cayley graphs, new problems on de Bruijn - like sequences, and the existence of symmetric chain decompositions and complete matchings in certain partially ordered sets involving permutations and integer partitions.