Structure, Generating, and Counting Problems in Combinatorial Families

组合族中的结构、生成和计数问题

• 批准号: 9622772
• 负责人: Carla Savage
• 金额: $ 7万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-07-15 至 1999-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9622772&HistoricalAwards=false
• 关键词: Structure; Generating; Counting; Problems; Combinatorial

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.

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