Combinatorial Patterns and Structures

组合模式和结构

• 批准号: 0653846
• 负责人: Huafei Yan
• 金额: $ 11.73万
• 依托单位: Texas A&M Research Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0653846&HistoricalAwards=false
• 关键词: Combinatorial; Patterns; Structures

This proposal focuses on the evolution of patterns and structures in discrete objects. Through a series of interrelated problems, the PI investigates properties and statistics of various combinatorial structures, including permutations, involutions, matchings and set partitions. By a variant of the RSK algorithm from algebraic combinatorics, matchings and set partitions are in one-to-one correspondence with oscillating and vacillating tableaux, which are certain random walks in the Hasse diagram of the lattice of integer partitions. Recently there have been major breakthroughs in understanding the statistics of such tableaux. Many unexpected and deep connections have been obtained with such areas as representation theory and random matrix theory. The proposed research concentrates on the combinatorial properties behind these connections, in particular, on the properties of crossings and nestings in matchings and set partitions, which are natural extensions of increasing and decreasing subsequences in permutations. The PI will study the problems from the following aspects: pattern avoidance, filling of Ferrer shapes and growth diagram, generating functions, and asymptotic distribution.She will also extend the theory to general graphs, chord configurations, and filling of certain polyminos. In this research, some algorithm plays an important role in understanding the evolution of combinatorial patterns and structures. This algorithmic approach is a particular emphasis of the project.This research is in the general area of combinatorics. One of the goals of combinatorics is to find efficient methods for arranging, enumerating, and manipulating discrete collections of objects. The proposed research is right aimed at these goals. The PI uses a combined algebraic and algorithmic approach to understand the formation and growth of discrete structures, which will help develop new methods and techniques in combinatorial theory. The proposed research are closed connected to other areas of mathematics, including analysis, representation theory, random matrix theory, and free probability theory. Results from this project would have direct applications in computer sciences, electronic engineering, operation research, and statistics.

这一建议侧重于离散对象中的模式和结构的演变。通过一系列相互关联的问题，PI研究了各种组合结构的性质和统计，包括排列、对合、匹配和集合划分。通过代数组合数学中RSK算法的一个变形，匹配和集合划分与振荡和摆动的表是一一对应的，它们是整数划分格的哈斯图中的某些随机游动。最近，在理解此类场面的统计数据方面取得了重大突破。它与表象理论、随机矩阵理论等领域有着许多意想不到的深层次联系。所提出的研究集中在这些连接背后的组合性质，特别是匹配和集合划分中的交叉和嵌套的性质，它们是排列中递增和递减子序列的自然扩展。PI将从模式避免、费雷尔形状和生长图的填充、母函数和渐近分布等方面研究这些问题，并将该理论扩展到一般图、弦构形和某些多项式的填充。在本研究中，一些算法在理解组合模式和结构的演化方面发挥了重要作用。这一算法方法是该项目的一个特别重点。这项研究是在组合学的一般领域。组合学的目标之一是找到有效的方法来安排、列举和操作离散的对象集合。拟议中的研究针对这些目标是正确的。PI使用代数和算法相结合的方法来理解离散结构的形成和增长，这将有助于开发组合理论的新方法和新技术。拟议的研究与其他数学领域密切相关，包括分析、表示理论、随机矩阵理论和自由概率理论。该项目的成果将直接应用于计算机科学、电子工程、运筹学和统计学。