Combinatorial Enumeration and Random Generation

组合枚举和随机生成

• 批准号: 0402028
• 负责人: Igor Pak
• 金额: --
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-07-01 至 2008-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0402028&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-在形式约化思想的基础上，我们提出了第一种形式化的方法，证明了所有经典的Young表双射实际上都是线性关系等价的。 本文还讨论了几种组合对象和几个新的方向。从数学的早期开始，组合对象就扮演着重要的角色。 这些对象包括各种图形集、树、类的划分、具有较小形状的区域的平铺等。寻找或估计这些对象的数量是一个基本问题，在某些情况下已经解决，在许多其他情况下仍然是开放的。 有时人们可以通过一个直接的组合论元（双射）把这些对象的个数与其他对象的个数联系起来。 我们提出了一个深入的研究这些双射的性质，是否（以及如何），他们不仅揭示了数量，但这些组合对象的结构结果。