Structure, Generating, and Counting Problems in Combinatorial Families

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

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.