Symmetric Functions: Combinatorial Identities and Bijections

代数组合学是数学的一个分支，它利用代数和组合学之间的相互作用，使一个领域的证明方法可以用来证明另一个领域的定理和猜想。这个特殊的项目集中于通过利用组合对象（如tableaux和树）来证明对称函数的组合恒等式和双射。这项工作的动力来自于投票理论中的问题，它建立在我以前的工作基础上。这一建议的重点是发展一个新的领域对称函数理论，激发了问题的投票理论。这项研究的核心是关于排名模式的问题。在对称函数理论中，排序模式问题激发了哪些具有挑战性和引人注目的问题？这是一种独特的方法。这个提议不是专注于一种技术或一种对称函数，而是针对一个共同的原点，并问，如果我们从这个点出发，会出现什么有趣的对称函数问题？从这个中心枢纽辐射出各种感兴趣的辐条：布尔乘积多项式，避免模式的排列模式，交替树。什么是排名模式？这些是离散对象的有序排列。计算这种排列的数量并不困难：显然，所有可能排序的集合就是所有可能排列的集合；然而，现实比这更微妙，在许多应用程序中，并不是所有的排名都会发生。例如，如何为用户在选举中对候选人的排名建模？一个流行的模型优先考虑某些排名，但这导致了一个新问题：模型中可能有多少个排名？一般来说，高维模型很难回答，数学家们通过对组合对象进行双射来推导出答案。通过最近的工作，这个模型和超平面排列之间的联系已经建立起来，这导致了涉及Robinson-Schensted算法、交替符号矩阵、交替树和避免模式排列的猜想。我要针对的就是这些猜想。在此过程中，我将证明涉及组合对象的正式计数和禁止配置的表征的结果。在我的职业生涯中，大部分研究都集中在对称函数恒等式的组合证明上，在此基础上，我添加了一些关于截断对排序投票选举的影响的最新结果。这个社会选择方向与我的对称函数研究产生了交叉影响，并产生了新的思路和新的轨迹。虽然这个提议的目标是理论性的，但也有一个通往应用领域的桥梁，包括，在某些投票系统模型中显示优势和局限性的潜力，我希望社会选择社区成为我的结果的重要额外受众。

Algebraic combinatorics is the branch of mathematics that exploits the interplay between algebra and combinatorics so that the methods of proof in one area can be employed to prove theorems and conjectures in the other area. This particular project concentrates on proving combinatorial identities and bijections for symmetric functions through the exploitation of combinatorial objects such as tableaux and trees. The impetus for this work comes from problems in voting theory and it builds on my previous work. This proposal focuses on the development of a new sphere of symmetric function theory, motivated by problems in voting theory. At the very heart of this research are questions about ranking patterns. What challenging and compelling questions in symmetric function theory are inspired by ranking pattern questions? This is a distinctive approach. Instead of focusing on a technique or a type of symmetric function, this proposal targets a common origin point and asks, if we journey out from this point, what interesting symmetric function questions arise? From this central hub radiate out the various spokes of interest: Boolean product polynomials, pattern-avoiding permutation patterns, alternating trees. What are ranking patterns? These are ordered arrangements of discrete objects. Counting the number of such arrangements is not difficult: obviously, the set of all possible rankings is the set of all possible permutations; however, reality is more subtle than that and, in many applications, not all rankings occur. For example, how do you model users' rankings of candidates in an election? One popular model prioritizes certain rankings, but this leads to a new problem: how many rankings are possible in the model? Answering in general can be difficult for higher dimensional models, and mathematicians have derived answers by forging bijections to combinatorial objects. Through recent work, connections between this model and hyperplane arrangements have been made, and this has led to conjectures involving the Robinson-Schensted algorithm, alternating sign matrices, alternating trees, and pattern-avoiding permutations.  It is these conjectures I will target. Along the way I will prove results involving formal counting of combinatorial objects and the characterization of forbidden configurations. The majority of the research throughout my career has concentrated on combinatorial proofs of symmetric function identities, and to this I have added some recent results on the ramifications of truncation on ranked ballot elections. This social choice direction has cross pollinated my symmetric function research, and led to new ideas and new trajectories. While the goals of this proposal are theoretical, there is this bridge to the applied realm as well, including, the potential to show advantages and limitations in certain voting system models, and I expect the social choice community to be an important additional audience for my results.