Combinatorial Enumeration and Random Generation

组合枚举和随机生成

• 批准号: 0837923
• 负责人: Igor Pak
• 金额: $ 4.09万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-05-01 至 2009-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0837923&HistoricalAwards=false
• 关键词: Combinatorial; Enumeration; Random; Generation

The study of bijections between combinatorial objectshas always remained an attractive part of Enumerativeand Algebraic Combinatorics. Despite their wideapplicability, their remains a complete lack of formalunderstanding as to which bijections are equivalent,and which one are "good" in a sense that they preservethe natural structure of the combinatorial objects.We initiate the study of asymptotic properties ofpartition bijections and claim that a large class ofwell known bijections are in fact "asymptotically stable".Using CS-style reduction ideas we propose the firstformal way to formulate that all classical Young tableaubijections are in fact linear tie equivalent. Othercombinatorial objects and several new directionsare also discussed. Since the early days of mathematics, combinatorial objectshave played an important role. These objects, whichinclude various sets of graphs, trees, partitions ofintegers, tilings of regions with smaller shapes, etc.Finding or estimating the number of such objects is afundamental problem which has been resolved in someinstances and remains open in many other case. Sometimesone is able to relate the number of such objects to thenumber of other objects by means of a direct combinatorialargument (a bijection). We propose an in-depth study ofthe nature of these bijection, as to whether (and how)they reveal not just the number, but structural resultson these combinatorial objects.

组合对象间对射的研究一直是枚举组合学和代数组合学中一个有吸引力的部分。尽管它们具有广泛的适用性，但对于哪些对偶是等价的，哪些对偶在保留组合对象的自然结构的意义上是“好的”，它们仍然完全缺乏正式的理解。我们开始研究分岔双射的渐近性质，并证明了一大类已知的双射实际上是“渐近稳定的”。利用cs风格的约简思想，我们提出了第一个形式化的方法来表述所有经典的杨氏表反实际上是线性相等的。还讨论了其他组合对象和几个新的方向。从数学的早期开始，组合对象就扮演着重要的角色。这些对象包括各种各样的图，树，手指的分区，具有较小形状的区域的平铺等。找到或估计这些对象的数量是一个基本问题，在某些情况下已经解决了，在许多其他情况下仍然开放。有时，人们可以通过直接组合参数（双射）将这类对象的数量与其他对象的数量联系起来。我们建议对这些双射的性质进行深入研究，以确定它们是否（以及如何）不仅揭示了这些组合对象的数量，而且揭示了它们的结构结果。