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 风格的归约思想，我们提出了第一个正式的方法来表述所有经典的 Young 表双射都在事实上线性关系等价。还讨论了其他组合对象和几个新方向。自数学早期以来，组合对象就发挥了重要作用。这些对象包括各种图形集、树、整数分区、较小形状区域的平铺等。查找或估计此类对象的数量是一个基本问题，该问题在某些情况下已得到解决，但在许多其他情况下仍然悬而未决。有时，人们能够通过直接组合论证（双射）将此类对象的数量与其他对象的数量联系起来。我们建议对这些双射的本质进行深入研究，看看它们是否（以及如何）不仅揭示了这些组合对象的数量，而且揭示了结构结果。