Combinatorial Generation, Gray Codes, and Structure Problems

点击翻译按钮获取中文摘要

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.