Structure, Generating, and Counting Problems in Combinatorial Families

小行星9622772 组合结构的有效生成和计数不仅需要良好的算法设计技术，而且还需要对所涉及的组合家族的数学结构有一些了解。另一方面，组合数学的研究有时会受到阻碍，因为对象变得如此之大，以至于很难查看它们或收集有关它们的任何数据。这项调查继续有效的组合生成和计数的工作，在组合学的经典问题的新的重点。递归分解技术的新应用是这项工作早期阶段结果的关键。结果和技术将直接应用于解决一些突出的结构问题，在相关领域的组合学，图论和群论。具体来说，调查员将解决开放的问题，在组合格雷码，有效的上市算法的几个组合家庭，有效的算法来计算和制表组合家庭，汉密尔顿周期的顶点传递图和凯莱图，渐近和双射之间的关系，某些家庭的整数分区，匹配和对称链分解偏序集的分区和排列。 这项研究是在组合数学的一般领域。组合数学的目标之一是找到有效的方法来研究如何安排对象的离散集合。 离散系统的行为对现代通信极为重要。例如，大型网络的设计，如电话系统中的网络设计，以及计算机科学中的算法设计，都要处理离散的对象集，这就需要使用组合研究。

9622772 Savage Efficient generation and counting of combinatorial structures requires not only good algorithm design techniques, but also some insight into the mathematical structure of the combinatorial family involved. On the other hand, investigations in combinatorial mathematics are at times hampered because the objects get large so quickly that it is hard to view them or to gather any data about them. This investigation continues work on efficient combinatorial generation and counting, with a new emphasis on classical problems in combinatorics. Novel application of recursive decomposition techniques have been the key to results in earlier phases of this work. The results and techniques will be applied to address directly some outstanding structural problems in related areas of combinatorics, graph theory, and group theory. Specifically, the investigator will address open problems in combinatorial Gray codes, efficient listing algorithms for several combinatorial families, efficient algorithms to count and tabulate combinatorial families, Hamilton cycles in vertex transitive graphs and Cayley graphs, asymptotic and bijective relationships between certain families of integer partitions, and matchings and symmetric chain decompositions in posets of partitions and permutations. This research is in the general area of Combinatorics. One of the goals of Combinatorics is to find efficient methods of studying how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.